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

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

2、第 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（

4、n）。.任课教师评语：教师签字：年月日注：每学期至少有一次设计性实验。每学期结束请任课教师按时按量统一交到教学秘书处。源程序文件名及组成文件：#include,#include,#include,#include.算法设计思想算法描述#include#include#include#include#define TRUE 1#define FALSE 0typedef int ElemType;typedef struct NodeElemType data;struct Node * next;Node,*LinkList;/* 初始化 */void Init(LinkList *head)

5、*head=(LinkList)malloc(sizeof(Node);(*head)-next=NULL;LinkList create(int n)LinkList h,r,p;int x,i;h=(Node*)malloc(sizeof(Node);r=h;printf( 请输入数据 :n);for(i=1;idata=x;r-next=p;r=p;r-next=NULL;return h;/* 头部插入 */int CreatfromH(LinkList head)LinkList p;ElemType x;puts(输入数据，输入-1000 结束输入 !);while(1)scanf

6、(%d,&x);.if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-next=head-next;head-next=p;else break;return 1;return 0;/* 尾部插入 */LinkListCreatfromT(LinkList head)LinkList p,q,t;ElemType x;q=head;t=head;puts(输入数据，输入-1000 结束输入 !);while(1)scanf(%d,&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-n

7、ext=NULL;t-next=p;t=p;return q;int Inslist(LinkList *head,int i,ElemType x)LinkList p,q;p=(*head);int j=0;while(p&jnext;j+;if(!p|ji-1)printf( 插入位置不合法！);.return 0;q=(Node*)malloc(sizeof(Node);q-data=x;q-next=p-next;p-next=q;return 1;/ 输出void Output(LinkList head)/* 定义节点指针类型，并指向首元结点*/LinkList p;p=head

8、-next;while(p!=NULL)printf(n%d,p-data);p=p-next;printf(n);/* 求表长 */int LengthList(LinkList head)int i;LinkList p;i=0;p=head-next;while(p!=NULL)i+;p=p-next;return i;/* 查找 */int Locate1(LinkList head,ElemType x)LinkList p;int i=1;p=head-next;while(p!=NULL&p-data!=x)p=p-next;i+;.if(p=NULL)return 0;retu

9、rn i;int Locate2(LinkList head,int i)int j;LinkList p;p=head;j=0;if(ii)return NULL;while(p-next!=0&jnext;return p-data;/* 删除 */int Del(LinkList *head,int i)LinkList p,q;int j=0;p=(*head);while(p-next!=NULL&jnext;j=j+;if(p=NULL&ji-1)printf( 删除位置不合理!);return 0;q=p-next;p-next=p-next-next;free(q);retur

10、n 1;/* 合并两个单链表*/LinkList merge(LinkList La,LinkList Lb)LinkList Lc;LinkList q,p,r;.p=La-next;q=Lb-next;Lc=La;Lc-next=NULL;r=Lc;while(p!=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);void main()LinkList head,La,Lb;int i;char

11、zdg,y;ElemType x;while(zdg!=0)getch();system(CLS);puts(n);puts(*);puts(*功能选择*);puts(*0- 退出1-创建2-插入*);puts(*3- 输出4-表长5-查找*);puts(*6- 删除7-合并*);puts(*);printf(n);printf( 请选择功能 :n);.scanf(%c,&zdg);switch(zdg)case0:puts(nn);puts(*);puts(*);puts(*谢谢使用，再见！*);puts(*);puts(*);break;case1:puts(n);puts(*);puts

12、(*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);printf( 新的单链表为:);Output(head);if(y=2)printf( 新的单链表为 :);Output(CreatfromT(head);break;case2:puts(n);printf( 请输入要插入的位置:n);scanf(%d,&i);printf( 请输入要插入的数

13、据: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,LengthList(head);break;case5:puts(n);puts(*);puts(*1- 按值查找2- 按序号查找*);puts(*);printf( 请选择 :n);scanf(%c,&y);y=getch();if(y=1)printf( 请输入要查找的元素

14、: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