数据结构课程设计设计题目：单链表专业班级：11软会四班指导教师：吉宝玉日期：2012目录一、实验目的 (2)1、 (2)2、 (2)二、实验内容 (3)三、实验基本要求（软、硬件） (3)四、算法设计思想 (3)1、 (3)2、 (3)3、 (3)4、 (3)5、 (3)6、 (3)7、 (3)8、 (3)五、算法流程图 (4)六、算法源代码 (4)七、运行结果 (9)1、 (9)2、 (10)3、 (11)4、 (11)5、 (11)6、 (12)7、 (12)8、 (13)9、 (13)八、收获及体会 (14)一、实验目的1、理解并掌握单链表的结构特点和相关概念；2、学会单链表的基本操作：建立、插入、删除、查找、输入、撤销、逆置、求前驱和后继等并实现其算法。

二、实验内容利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。

三、实验基本要求（软、硬件）用VC++6.0软件平台，操作系统：Windows XP 硬件：内存要求：内存大小在256MB，其他配置一般就行。

四、算法设计思想1、定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。

2、定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。

3、定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。

4、定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表的前驱和后继的查找工作。

5、定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以在连链表的任意位置进行插入一个新节点。

6、定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。

7、定义一个逆置单链表的操作，通过定义这个算法，可以逆置输出单链表。

8、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为空。

五、算法流程图六、算法源代码#include <stdio.h>#include<stdlib.h>typedef struct node{ int data;struct node *next;}linklist;void setnull(linklist *H)//清空单链表{H->next=NULL;}void Leng(linklist *H)//求单链表长度{ linklist *p;int k;p=H;k=0;while(p->next!=NULL){p=p->next;k++;}printf("The linklist is:%d\n",k);}int GetElem(linklist *H,int i)//取单链表中的某个元素{linklist *p;int k;p=H;k=0;while(p->next!=NULL&&k<i){p=p->next;k++;}if(k==i&&p!=NULL)printf("i position data is %d\n",p->data);elseprintf("No find!\n");}void Insert(linklist *H,int i,int x)//向单链表中插入某个元素{linklist *p;int k;linklist *s;p=H;k=0;while(p->next!=NULL&&k<i-1){p=p->next;k++;}if(k==i-1&&p->next!=NULL){s=(linklist *)malloc(sizeof(linklist));s->data=x;s->next=p->next;p->next=s;}elseprintf("error\n");}void Delete(linklist *H,int x)//删除元素{linklist *p,*q;int k;p=H;k=0;while(p->next!=NULL&&p->next->data!=x) {p=p->next;k++;}if(p->next->data==x){q=p->next;p->next=q->next;free(q);}else printf("no find!\n");}void print(linklist *H)//输出单链表{linklist *p;int k;p=H;k=0;if(p->next==NULL)printf("链表为empty!");while(p->next!=NULL){k++;p=p->next;printf("%3d",p->data);}}int Locate(linklist *H,int x)//查找元素{linklist *p;int k;p=H;k=0;while(p->next!=NULL&&p->data!=x){p=p->next;k++;}if(p->data==x)printf("The position is %d\n",k);elseprintf("No find!\n");}void creatlist(linklist *H)//创建单链表{linklist *p,*s;int x;p=H;printf("please input x:");scanf("%d",&x);while(x!=-1){s=(linklist *)malloc(sizeof(linklist));s->data=x;s->next =p->next;p->next =s;p=p->next ;printf("please input x:");scanf("%d",&x);}p->next=NULL ;}void destroylist(linklist *H)//销毁单链表{H->next=NULL;H->data=NULL;}void next (linklist *H)//单链表中某个元素的后继{linklist *p;int k,x;p=H;k=0;printf("请输入x:");scanf("%d",&x);while(p->next!=NULL&&p->data!=x){p=p->next ;k++;}if(p->data==x)printf("该元素后继是%d",p->next->data );}void prior(linklist *H)//单链表中某个元素的前驱{ linklist *p;int k,x;p=H;k=0;printf("请输入x:");scanf("%d",&x);while(p->next!=NULL&&p->next->data!=x){p=p->next;k++;}if(p->next->data==x)printf("该元素前驱是%d",p->data );}void reverse(linklist *H)//单链表的逆置{linklist *p,*q,*r;q=NULL;p=H->next;while (p!=NULL){r=p->next ;p->next=q;q=p;p=r;}H->next=q;print(H);}void main(){ linklist *H;int k,x,i;int f;H=(linklist *)malloc(sizeof(linklist));setnull(H);printf("\nplease input f to choose flowing op,-1 to end"); printf("\n1:leng(H)");printf("\n2:GetElem(H,i)");printf("\n3:Insert(H,i,x)");printf("\n4:Delete(H,x)");printf("\n5:print(H)");printf("\n6:Locate(H,x)");printf("\n7:creatlinklist(H)");printf("\n8:destroylist(H)");printf("\n9:prior(H)");printf("\n10:next(H)");printf("\n11: reverse(H)\n");scanf("%d",&f);while(f!=-1){switch (f){case 1:Leng(H);break;case 2:printf("\nplease input getelem position i:");scanf("%d",&i);GetElem(H,i);break;case 3:printf("\nplease input i,x:");scanf("%d,%d",&i,&x);Insert(H,i,x);break;case 4:printf("\nplease input delete x:");scanf("%d",&x);Delete(H,x);break;case 5: print(H);break;case 6:printf("please input x:");scanf("%d",&x);Locate(H,x);break;case 7:creatlist(H);break;case 8:destroylist(H);break;case 9:prior(H);break;case 10:next(H);break;case 11:reverse(H);break;}printf("\nplease input f to choose flowing op,-1 to end"); printf("\n1:leng(H)");printf("\n2:GetElem(H,i)");printf("\n3:Insert(H,i,x)");printf("\n4:Delete(H,x)");printf("\n5:print(H)");printf("\n6:Locate(H,x)");printf("\n7:creatlinklist(H)");printf("\n8:destroylist(H)");printf("\n9:prior(H)");printf("\n10:next(H)");printf("\n11: reverse(H)\n");scanf("%d",&f);}}七、运行结果1、建立单链表2、输出3、插入4、查找5、删除6、求前驱7、求后继8、逆置9、撤销八、收获及体会通过这次的课程设计，我们对数据结构中单链表的应用有了更深的理解，并且使我们深刻的认识到实践的重要性，只有理论与实践相结合才能达到很好的学习效果，学到很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。