数据结构课程设计-单链表.doc

数据结构课程设计设 计 题 目： 单链表 小组成员姓名： 专 业 班 级： 计算机应用班 指 导 教 师： 安徽新华学院信息工程学院日期：2010年12月23日课题名称单链表院 系信息工程学院年级专业计应班成员姓名成员学号承担的任务成 绩单链表的建立、插入，整理单链表单链表的输出、查找，整理单链表单链表的前驱、后继，整理单链表单链表的删除、撤销，整理单链表单链表的逆置，整理单链表课题设计目的与设计意义1、课题设计目的：1、掌握单链表的结构特点及有关概念； 2、掌握单链表的建立、插入、删除、查找、输出、撤销、逆置、求前驱和后继等基本操作的算法实现。2、课题设计意义： 指导教师：李春梅2010年12月23日安徽新华学院课程设计成绩评定表目录一、实验目的21、22、2二、实验内容3三、实验基本要求（软、硬件）3四、算法设计思想31、32、33、44、45、46、47、48、4五、算法流程图4六、算法源代码5七、运行结果161、162、163、174、185、186、197、198、199、20八、收获及体会20一、实验目的1、理解并掌握单链表的结构特点和相关概念；2、学会单链表的基本操作：建立、插入、删除、查找、输入、撤销、逆置、求前驱和后继等并实现其算法。 二、实验内容 利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。三、实验基本要求（软、硬件）用vc+6.0软件平台，操作系统：windows xp 硬件：内存要求：内存大小在256mb，其他配置一般就行。 四、算法设计思想 1、定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。 2、定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。 3、定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。 4、定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表的前驱和后继的查找工作。 5、定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以在连链表的任意位置进行插入一个新节点。 6、定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。 7、定义一个逆置单链表的操作，通过定义这个算法，可以逆置输出单链表。 8、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为空。 五、算法流程图 六、算法源代码 #include #includetypedef 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:%dn,k);int getelem(linklist *h,int i)/取单链表中的某个元素linklist *p;int k;p=h;k=0;while(p-next!=null&knext;k+; if(k=i&p!=null)printf(i position data is %dn,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&knext;k+; if(k=i-1&p-next!=null) s=(linklist *)malloc(sizeof(linklist);s-data=x;s-next=p-next;p-next=s; elseprintf(errorn);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 %dn,k); else printf(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、撤销 八、收获及体会 通过这次的课程设计，我们对数据结构中单链表的应用有了更深的理解，并且使我们深刻的认识到实践的重要性，只有理论与实践相结合才能达到很好的学习效果，学到很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。由于刚开始对单链表的应用总体结构不熟悉，对书本知识的学习不够扎实，刚拿到题目的时候，还不好下手，就请教了一些学习成绩好一点的同学，并认真查找了一些资料，才对这次课程设计有了初步的了解。 根据对数据结构的了解，我们觉得我们对单链表的认识要深一点。因此我们选择了单链表的实验，作为线性表的一种存储结构，它的特点是可以从分利用存储单元来存储数据，并且可