单链表的操作实现实验报告

1、单链表的操作实现实验报告单链表的操作实现实验报告单链表的操作实现实验报告信息学院数据结构上机实验报告学号：104100058姓名：赵德刚班级：10A实验时间：年月日实验地址：同析3号楼开发环境：C+课程名称：数据结构-C语言描述实验性质：综合性实验设计性实验考据明验实验内容：单链表的实现题目本源：教材页题教师补充自选题目主要功能描述：链表的初始化、链表的创办（头部插入法、尾部插入法）、求表长、查找（按值查找、挨次号查找）、插入、删除、输出、两个有序单链表的合并等。设计解析：初始化：为单链表申请头结点空间，将单链表设置为空；创办：（1）头部插入法：（a）初始化空表；（b）申请新结点并赋值；（c）

2、插入新结点；（d）插入第i个元素。（2）尾部插入法：(a)建空表（b）申请结点并赋值；（c）插入第一个结点；（d）r-next=s,r=s;表长：从表头开始，将指针依次指向各个结点，向到达p-next=NULL为止，用j来计数。查找：（1）按值查找：在表中查找第i个结点，找到就返回该结点的储藏地址，用j来储藏扫描过的结点数（j的初值为0），但j=i时，结束。（2）挨次号查找：从表中第一个结点开始，当key等于查找到的元素的数据时停止查找。插入：在单链表中第i-1个结点并由指针指示，申请结点空间q，将数据域置为x，更新指针。删除：重新结点开始，删除第i个结点并释放空间；输出：当表不为空时，依次输

3、出表中元素；合并：与次序表相同，只需为新的结点申请一个空间。典型测试数据输入：输入数据个数：4输出：1，2，3，4预期结果：基本实现了单链表的基本数据：1，2，3，4各种操作。程序及运行结果正误判断：特别好正确，还可改进基本正确，还需改进还有错误不足之处或设计经验小结：（1）L是单链表的头指针的指针，用来接收头指针变量的地址，*L待初始化的单链表为头指针变量；2）节约了空间，接见结点时，只需知道头指针，就可以找到其他的元素；3）头插法建表获取的链表中的结点的次序和输入的次序相反，尾插法规一致；4）求表长时，算法的时间复杂度为O（n）。任课教师考语：教师签字：年月日注：每学期最少有一次设计性实验

4、。每学期结束请任课教师准时按量一致交到授课秘书处。源程前言件名及组成文件：#include,#include,#include,#include算法设计思想算法描述#include#include#include#include#defineTRUE1#defineFALSE0typedefintElemType;typedefstructNodeElemTypedata;structNode*next;Node,*LinkList;/*初始化*/voidInit(LinkList*head)*head=(LinkList)malloc(sizeof(Node);(*head)-next=NU

5、LL;LinkListcreate(intn)LinkListh,r,p;intx,i;h=(Node*)malloc(sizeof(Node);r=h;printf(请输入数据:n);for(i=1;idata=x;r-next=p;r=p;r-next=NULL;returnh;/*头部插入*/intCreatfromH(LinkListhead)LinkListp;ElemTypex;puts(输入数据，输入-1000结束输入!);while(1)scanf(%d,&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-next=h

6、ead-next;head-next=p;elsebreak;return1;return0;/*尾部插入*/LinkListCreatfromT(LinkListhead)LinkListp,q,t;ElemTypex;q=head;t=head;puts(输入数据，输入-1000结束输入!);while(1)scanf(%d,&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-next=NULL;t-next=p;t=p;returnq;intInslist(LinkList*head,inti,ElemTypex)LinkLis

7、tp,q;p=(*head);intj=0;while(p&jnext;j+;if(!p|ji-1)printf(插入地址不合法！);return0;q=(Node*)malloc(sizeof(Node);q-data=x;q-next=p-next;p-next=q;return1;输出voidOutput(LinkListhead)/*定义节点指针种类，并指向首元结点*/LinkListp;p=head-next;while(p!=NULL)printf(n%d,p-data);p=p-next;printf(n);/*求表长*/intLengthList(LinkListhead)in

8、ti;LinkListp;i=0;p=head-next;while(p!=NULL)i+;p=p-next;returni;/*查找*/intLocate1(LinkListhead,ElemTypex)LinkListp;inti=1;p=head-next;while(p!=NULL&p-data!=x)p=p-next;i+;if(p=NULL)return0;returni;intLocate2(LinkListhead,inti)intj;LinkListp;p=head;j=0;if(ii)returnNULL;while(p-next!=0&jnext;returnp-data

9、;/*删除*/intDel(LinkList*head,inti)LinkListp,q;intj=0;p=(*head);while(p-next!=NULL&jnext;j=j+;if(p=NULL&ji-1)printf(删除地址不合理!);return0;q=p-next;p-next=p-next-next;free(q);return1;/*合并两个单链表*/LinkListmerge(LinkListLa,LinkListLb)LinkListLc;LinkListq,p,r;p=La-next;q=Lb-next;Lc=La;Lc-next=NULL;r=Lc;while(p!

10、=NULL&q!=NULL)if(p-datadata)r-next=p;r=p;p=p-next;elser-next=q;r=q;q=q-next;if(p)r-next=p;elser-next=q;free(Lb);return(Lc);voidmain()LinkListhead,La,Lb;inti;charzdg,y;ElemTypex;while(zdg!=0)getch();system(CLS);puts(n);puts(*);puts(*puts(*puts(*puts(*0-退出3-输出6-删除功能选择1-创办2-插入4-表长5-查找7-合并*);*);*);*);pu

11、ts(*);printf(n);printf(请选择功能:n);scanf(%c,&zdg);switch(zdg)case0:puts(nn);puts(puts(puts(puts(puts(break;*);*感谢使用，再见！*);*);*);*);case1:puts(n);puts(*);puts(*0-般创办1-头部插入法2-尾部插入法*);puts(*);printf(请选择:n);scanf(%c,&y);y=getch();if(y=0)printf(输入数字的个数:n);scanf(%d,&i);head=create(i);if(y=1)CreatfromH(head);

12、printf(新的单链表为:);Output(head);if(y=2)printf(新的单链表为:);Output(CreatfromT(head);break;case2:puts(n);printf(请输入要插入的地址:n);scanf(%d,&i);printf(请输入要插入的数据:n);scanf(%d,&x);if(Inslist(&head,i,x)!=0)printf(插入成功!);Output(head);break;case3:puts(n);printf(输入的数据为:n);Output(head);break;case4:puts(n);printf(长度为:%d,Le

13、ngthList(head);break;case5:puts(n);puts(*);puts(*1-按值查找2-挨次号查找*);puts(*);printf(请选择:n);scanf(%c,&y);y=getch();if(y=1)printf(请输入要查找的元素:n);scanf(%d,&x);if(Locate1(head,x)!=0)printf(查找成功!该元素的地址是%d,Locate1(head,x);elseprintf(无此元素,查找失败!);if(y=2)printf(请输入要查找的元素的地址:n);scanf(%d,&i);if(Locate2(head,i)!=0)printf(查找成功,该%d号地址上的是%d!,i,Locate2(head,i);elseprintf(无此元素,查找失败!);break;case6:puts(n);printf(请输入你要删除的元素序号:);scanf(%d,&i);Del(&head,i);Output(head);break;case7:puts(n);printf(请输入La的数据:);printf(输入数字的个数:n);scanf(%d,&i);La=create(i);printf(请输入Lb的数据:);printf(输入数字的个数:n);scanf(%d,&i);L