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

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

2、请结点并赋值；（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） 求表长时，算法的时间复杂度为0 （n）。任课教师评语：教师签字：年月日注：每学期至少有一次设计性实验。每学期结束请任课教师

4、按时按量统一交到教学秘书处。源程序文件名及组成文件：#i nclude<stdio.h>,#i nclude<stdlib.h>,#i nclude<con io.h>,#i nclude<wi ndows.h>算法设计思想算法描述#in clude<stdio.h>#in clude<stdlib.h>#in clude<c oni o.h>#i nclude<wi ndows.h>#defi ne TRUE 1#defi ne FALSE 0typedef int ElemType; typed

5、ef struct NodeElemType data; struct Node * n ext;Node,*Li nkList;/*初始化*/void In it(Li nkList *head)*head=(L in kList)malloc(sizeof(Node); (*head)-> next=NULL;Lin kList create(i nt n)Lin kList h,r,p;int x,i;h=(Node*)malloc(sizeof(Node);r=h;printf("请输入数据:n”);for(i=1;i<=n ;i+)sca nf("%d

6、", &x); p=(Node*)malloc(sizeof(Node); p->data=x;r->n ext=p; r=p;r->n ext=NULL; return h;/*头部插入*/int CreatfromH(L in kList head)Lin kList p;ElemType x;puts("输入数据，输入-1000结束输入r?; while(1)sca nf("%d", &x);if(x!=-1000)p=(Node*)malloc(sizeof(Node); p_>data=x;p->n

7、 ext=head->n ext;head->n ext=p;else break;return 1;return 0;/*尾部插入*/Lin kList CreatfromT(Li nkList head)Lin kList p,q,t;ElemType x;q=head;t=head;puts("输入数据，输入-1000结束输入r?；while(1)sca nf("%d", &x);if(x!=-1000)p=(Node*)malloc(sizeof(Node); p->data=x;p-> next=NULL;t_>n

8、ext=p;t=p;return q;int In slist(L in kList *head,i nt i,ElemType x)Lin kList p,q;p=(*head);int j=0;while(p&&j<i-1)p=p->n ext;j+;if(!p|j>i-1)printf("插入位置不合法！");return 0;q=(Node*)malloc(sizeof(Node); q_>data=x;q_>n ext=p->n ext;p_>n ext=q; return 1;/输出void Output

9、(L in kList head)/*定义节点指针类型，并指向首元结点*/Lin kList p;p=head->n ext; while(p!=NULL)prin tf("n%d",p->data); p=p->n ext;prin tf("n ”);/*求表长*/int Len gthList(L in kList head)int i;Lin kList p;i=0;p=head->n ext; while(p!=NULL)i+;p=p->n ext; return i;/*查找*/int Locate1(L in kList

10、head,ElemType x)Lin kList p;int i=1;p=head->n ext;while(p!=NULL&&p->data!=x)p=p->n ext;i+; if(p=NULL) return 0;return i;int Locate2(L in kList head,i nt i)int j;Lin kList p;p=head;j=0；if(i<=1|j>i)return NULL; while(p-> next!=O&&j<i) j+;p=p->n ext;return p->

11、data;/*删除*/int Del(LinkList *head,int i)Lin kList p,q;int j=0; p=(*head); while(p-> next!=NULL&&j<i-1) p=p->n ext; j=j+；if(p=NULL&&j>i-1)printf("删除位置不合理!"); return 0;q=p->n ext;p->n ext=p->n ext- >n ext;free(q); return 1;/*合并两个单链表*/Lin kList merge(L

12、in kList La,L in kList Lb) Lin kList Lc;Lin kList q,p,r;p=La->n ext; q=Lb->n ext; Lc=La;Lc-> next=NULL;r=Lc;while(p!=NULL&&q!=NULL)if(p_>data<=q_>data)r->n ext=p;r=p;p=p->n ext;elser->n ext=q;r=q;q=q-> next;if(p)r->n ext=p;elser->n ext=q;free(Lb); return(L

13、c);void mai n()Lin kList head,La,Lb;int i;char zdg,y; ElemType x;while(zdg!=0)getch();system("CLS");puts("n");puts(' I* 知.puts("*puts("*puts("*puts("*0-退出3-输出6-删除);功能选择1-创建2-插入4-表长5-查找7-合并*");*");*");*"););puts(' prin tf("n&quo

14、t;); printf(”请选择功能:n");sea nf("%c", &zdg); switch(zdg)case'O':puts("nn");puts("puts("puts("puts("puts(" break;case'1':puts("n");* 使用，再见!*););*"););););puts('puts（"* 0-般创建 1-头部插入法2-尾部插入法*"）;);puts('

15、printf("请选择:n");scan f("%c", &y); y=getch();if(y='0')printf("输入数字的个数:n"); scan f("%d", &i);head=create(i);if(y='1')CreatfromH(head);printf("新的单链表为:");Output(head);if(y=2)printf("新的单链表为:"); Output(CreatfromT(head);bre

16、ak;case'2':puts("n");printf("请输入要插入的位置:n"); scan f("%d",&i);printf("请输入要插入的数据:n"); scan f("%d"，& x);if(I nslist(&head,i,x)!=0)printf("插入成功!");Output(head); break;case'3':puts("n"); printf("输入的数据为:n

17、");Output(head);break;case'4':puts("n");printf("长度为:%d",LengthList(head); break;case'5':puts("n"););puts(');puts("*1-按值查找2-按序号查找);puts('printf("请选择:n");scan f("%c", &y); y=getch();if(y='1')printf("请输

18、入要查找的元素:n"); scan f("%d", &x);if(Locate1(head,x)!=0)printf("查找成功！该元素的位置是%d",Locate1(head,x);elseprintf("无此元素，查找失败!");if(y=2)printf("请输入要查找的元素的位置:n");scan f("%d", &i);if(Locate2(head,i)!=0)printf("查找成功 该%d 号位置上的是 %d!",i,Locate2(head,i); elseprintf("无此元素，查找失败!");break;case'6':puts("n");printf("请输入你要删除的元素序号：”);scan f("%d",&i);Del(&head,i);Output(head);break;case'7':