课程设计——单链表2

《课程设计——单链表2》由会员分享，可在线阅读，更多相关《课程设计——单链表2（15页珍藏版）》请在装配图网上搜索。

1、靈瓯本澀坦M首 (置玉)M 炖M曹门gras ,寸I u u u el el 二 二 01 01理專姿，6 笳 V 9 x 寸 / J 二坡fclw,K、实验目的1、理解并掌握单链表的结构特点和相关概念；2、学会单链表的基本操作：建立、插入、删除、查找、输入、撤销、逆置、求前驱和后继等并实现其算法。二、实验内容利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除、查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的 结果，当所有操作完成后能撤销该单链表。三、实验基本要求（软、硬件）用VC+6.0软件平台，操作系统：Windows XP硬件：内存要求：内存大小在2

2、56MB, 其他配置一般就行。四、算法设计思想1、定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数 应用做好准备。2、定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这 一步通过调用输出链表的函数算法来实现对链表的输出操作。3、定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存 在。4、定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对 链表的前驱和后继的查找工作。5、定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便 可以在连链表的任意位置进行插入一个新节点。6、定义删除节点的操作，这个算法用于对链表中

3、某个多余节点的删除工作。7、定义一个逆置单链表的操作，通过定义这个算法，可以逆置输出单链表。8、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为 空。五、算法流程图1、整体流程2、插入流程3、删除流程六、算法源代码#include #includetypedef struct node int data;struct node *next;linklist;void set null(linklist *H) 清空单链表H-next=NULL;void Leng(linklist *H) 求单链表长度 linklist *p;int k; p=H;k=0;while(p-n

4、ext!=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 Inser t(linklist *H,int i,in t x)/ 向单链表中插入某个元素 linklist *p;int k;linklis

5、t *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 Dele te(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=

6、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 Loca te(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

7、) 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 ;vo

8、id des troylis t(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-nex t-da ta );void prior(linklist *H)单链表中某个元素的前驱 linklist *p;int k,x;p=H;

9、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-da ta );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

10、 *)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);prin

11、tf(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

12、(%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(

13、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、插入c：-. C:Rrogram FilesMicro

14、soft Visual StudioMyProjectsgfhetnjqiqFh.exe回田9：prior匚10：nextJI11: reuerse 隊摻please input i,x：2,15please input F to choose flowing op,-1 to end l：leng2:GetElen3 : Insert 4：Delete5:printB: Locate7：creatlinklistB:destroylist9：prior10：next11: ieuerse510 15 20 30 40please input f to choose flowing op,-1

15、 to end l：leng2:GetElen3:Insert4：Delete5:printH)B : Locate 7：creatlinklistB : destioylist 9：priorH)10：nextH)11: reuerse 4、查找5、删除6、求前驱7、求后继8、逆置9、撤销八、收获及体会通过这次的课程设计，我们对数据结构中单链表的应用有了更深的理解，并且使我们深刻的认识到实践的重要性，只有理论与实践相结合才能达到很好的学习效果，学 到很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能 力才能得到提高。由于刚开始对单链表的应用总体结构不熟悉，对书本知识

16、的学习不够扎 实，刚拿到题目的时候，还不好下手，就请教了一些学习成绩好一点的同学，并认真查找 了一些资料，才对这次课程设计有了初步的了解。根据对数据结构的了解，我们觉得我们对单链表的认识要深一点。因此我们选择 了单链表的实验，作为线性表的一种存储结构，它的特点是可以从分利用存储单元来存储 数据，并且可以方便的实现对数据进行插入、删除、输出等操作。在我们进行课程设计时，虽然在大体上算法是正确的，但时常会出现一些小 问题，使我们不得不花一些时间来查找、修改错误。通过这次课程设计，让我们充分认识到数据结构在编写程序方面的重要地位。 由于我们在课程设计中编写的是对单链表的基本操作，因此我们在这次课程设计中收获了 很多关于单链表的应用方面的知识。由于课程设计的题目还有很多，因此没有对其他的题 目进行深入的了解而感到遗憾，因此我们希望在以后的学习过程中，能够多多的学习这方面没知识来弥补自身不足的地方。