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

《单链表的操作实现实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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;typedefstruc

5、tNode{ElemTypedata;structNode*next;}Node,*LinkList;/*初始化*/voidInit(LinkList*head){*head=(LinkList)malloc(sizeof(Node));(*head)->next=NULL;}LinkListcreate(intn){LinkListh,r,p;intx,i;h=(Node*)malloc(sizeof(Node));r=h;printf("请输入数据:");for(i=1;i<=n;i++){scanf("%d",&x);p=(Node*)malloc(sizeof(N

6、ode));p->data=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=head->next;head->next=p;}elsebreak;}return1;return0;}/*尾部插入*/LinkListCr

7、eatfromT(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){LinkListp,q