实验二-单链表实现

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

实验报告课程名称数据结构课程设计实验项目单链表的实现实验仪器PC机一台学院_____信息管理学院_______专业电子商务班级/学号___电子商务1401______学生姓名____________实验日期___12.27_______成绩_______________________指导教师_________________北京信息科技大学信息管理学院(课程上机）实验报告实验课程名称：数据结构课程设计专业:电子商务班级:商务1401学号:姓名:成绩：实验名称单链表的实现实验地点小营学院机房实验时间12.291.实验目的:1）理解线性表的逻辑特点；2）掌握单链表的定义及C语言实现；3）熟练掌握在单链表中实现各种基本操作;4）掌握使用单链表解决一些简单应用问题的编程.

11.实验要求：1)学时为4学时；2）在上机前完成源程序；3）能在机器上正确、调试运行程序；4）本实验需提交实验报告；5）实验报告文件命名方法:实验2_xx班_学号后两位_姓名。doc2.实验内容和步骤:1)基于单链表实现线性表的以下操作:a)在表头插入元素b)在表尾插入元素c)在指定的位置i插入元素d)删除操作e)查找元素f)求表长度g)清空操作h)判断线性表是否为空i)按位序打印线性表中的元素2)单链表的简单应用:a)调用基本操作编写算法删除第i个开始的k个元素；b)计算单链表中值为x的元素的个数;c)将x插入到单链表的适当位置上，以保持单链表中元素的有序性；d)将线性表元素进行就地逆置e)将两个单链表合并为一个单链表。

21.实验过程：1)基于单链表实现线性表的以下操作：在表头插入元素intInsert_First（LinkList*Head_pointer，ElemTypex）{Node＊p;P=(LinkList)malloc(sizeof(Node)）；if(p==NULL)returnOverFlow;p->data=x;p-〉next=＊Head_pointer;*Head_pointer=p；ReturnOK；｝在表尾插入元素intInsert_Last(LinkList＊Head_pointer，ElemTypex）｛Node＊p，＊q;P=（LinkList）malloc(sizeof(Node）);if(p==NULL)returnOverFlow；p—〉data=x;p->next=NULL;q=*Head_pointer；if(q==NULL）*Head_pointer=p；else{while（q—>next！=NULL)q=q—〉next；q->next=p；

3}ReturnOK;}在指定的位置i插入元素intInsert_i（LinkList*Head_pointer,ElemTypex,inti）Node＊p,＊q；P=（LinkList）malloc（sizeof（Node));if(p==NULL）returnOverFlow；p—〉data=x;if(i==0）{p—〉next=＊Head_pointer；＊Head_pointer=p;returnOK;}else｛q=＊Head_pointer;while(q->next！=NULL＆&i〉1){q=q->next;i—-；}if（q！=NULL)p-〉next=q—〉next;q—〉next=p；returnOK；}returnError；｝｝删除操作intDelete_LinkList(LinkList*Head_pointer，ElemTypex)

4Node*p,*q；p=＊Head_pointer；if(p—〉data==x）｛＊Head_pointer=（＊Head_pointer)—>next;free(p）;returnOK;｝q=p;p=p-〉next;}｝returnError;}查找元素LinkListLocation_LinkList（LinkListHead，ElemTypex)｛LinkListp;p=Head;while（p!=NULL）{if(p->data==x）break;p=p-〉next；}returnp;}求表长度intLength_LinkList（LinkListHead）｛Node*p；intsum=0；p=Head;while(p！=NULL）{sum++;

5p=p—〉next;}returnsum；｝清空操作voidSetNull_LinkList(LinkList＊Head_pointer）｛Node*p,＊q;p=*Head_pointer;while（p！=NULL)q=p；p=p-〉next；free（q);｝*Head_pointer=NULL;}判断线性表是否为空voidIfNull_LinkList(LinkList*Head_pointer）{if(*Head_pointer==NULL）returnTrue;elsereturnFalse；}按位序打印线性表中的元素voidShow_LinkList（LinkListHead）{Node＊p；printf（"

6”);p=Head；if(p==NULL)printf("

7空表!”）;while（p!=NULL)

8｛printf("％d"，p—>data);p=p-〉next;}｝2）单链表的简单应用：调用基本操作编写算法删除第i个开始的k个元素；计算单链表中值为x的元素的个数;将x插入到单链表的适当位置上，以保持单链表中元素的有序性;将线性表元素进行就地逆置将两个单链表合并为一个单链表.1.调用基本操作编写算法删除第i个开始的k个元素；＃include"stdio。h"＃include”stdlib。h”typedefstructnode{intdata;structnode＊next;}Node，*LinkList;voidDelete_LinkList（LinkList＊Head_pointer，inti,intk）{intj=i+k-1；Node＊p,*q,＊m,*n；q=*Head_pointer；while(q->next!=NULL&&i>1)｛n=q；q=q-〉next；i--；}p=*Head_pointer;while（p-〉next!=NULL＆＆j〉1）｛p=p—〉next；j-—;｝while(q!=p）{m=q；q=q—〉next;free（m);｝n—>next=p—>next;free(p）;}

9intinsert_First(LinkList＊Head_pointer，intx）{Node＊p;p=(LinkList）malloc(sizeof(Node）)；if（p==NULL)return—1；p—>data=x;p->next=*Head_pointer;*Head_pointer=p;return1;}voidShow_LinkList（LinkListHead){Node*p；printf(”

10");p=Head;if(p==NULL）printf("

11NULL”）;while(p！=NULL)｛printf（"%d”,p->data);p=p-〉next;｝}intmain(){intm;inti，k；LinkListHead；Head=NULL；scanf（"%d%d",＆i，&k）;for(m=0；m〈7;m++）if（！insert_First(＆Head,m)）break;Show_LinkList(Head）；Delete_LinkList(&Head,i，k）;Show_LinkList(Head）；return0;}2。计算单链表中值为x的元素的个数＃include"stdio.h"#include”stdlib。h”typedefstructnode{

12intdata；structnode＊next;｝Node，＊LinkList;intLocation_LinkList（LinkListHead,intx)｛Node*p;intsum=0;p=Head；while（p！=NULL)｛if(p—>data==x)sum++;p=p-〉next；}returnsum;}intinsert_First(LinkList*Head_pointer,intx）{Node*p；p=(LinkList)malloc（sizeof（Node)）;if(p==NULL)return—1；p->data=x;p—〉next=＊Head_pointer；*Head_pointer=p;return1；}voidShow_LinkList(LinkListHead)｛Node＊p;printf（"

13”);p=Head;if（p==NULL)printf（"

14NULL”)；while（p!=NULL）｛printf(”％d

15",p—〉data)；p=p->next；}｝intmain（){intm，x,sum;LinkListHead；

16Head=NULL;scanf（”%d",&x)；for(m=0;m<7；m++）if(!insert_First（＆Head,m）)break;Show_LinkList(Head）；sum=Location_LinkList(Head，x）；printf（"%d

17"，sum)；return0;}3.将x插入到单链表的适当位置上，以保持单链表中元素的有序性#include”stdio.h"#include"stdlib.h"typedefstructnode｛intdata;structnode*next；｝Node,＊LinkList;intLocation_LinkList(LinkListHead,intx）｛Node＊p；intsum=0;p=Head；while（p！=NULL）{if(p->data<=x）sum++;p=p—>next；｝returnsum；}intinsert_i（LinkList＊Head_pointer，intx，inti){Node*p，*q；p=（LinkList)malloc(sizeof（Node））；if(p==NULL)return—1；p-〉data=x;if(i==0）｛p->next=＊Head_pointer；＊Head_pointer=p;return1;

18}else{q=＊Head_pointer；while（q—〉next!=NULL＆＆i〉1）{q=q—>next；i——；}if（q!=NULL）{p—〉next=q—〉next;q-〉next=p;return1;｝return-2；}}voidShow_LinkList(LinkListHead)｛Node*p;printf(”

19”）;p=Head;if（p==NULL）printf("

20NULL");while（p!=NULL){printf（"％d”,p—>data);p=p-〉next；}｝intmain（）｛inti，a[7］={10，20，30,40,50，60,70｝;intx，sum;LinkListHead;Head=NULL;scanf("%d”,＆x)；for（i=0；i〈7;i++)if(insert_i（＆Head,a［i]，i)！=1）break;Show_LinkList（Head);sum=Location_LinkList（Head，x);if(insert_i(＆Head,x,sum）！=1)printf（”fail!

21")；Show_LinkList(Head);return0；}

224。将线性表元素进行就地逆置＃include"stdio.h”#include”stdlib。h"typedefstructnode｛intdata;structnode*next;}Node,*LinkList；LinkListop_LinkList（LinkListHead）{Node＊p,＊q;p=Head;Head=NULL；while（p）｛q=p;p=p—>next;q—>next=Head;Head=q；｝returnHead;｝intinsert_First(LinkList＊Head_pointer，intx）{Node*p;p=(LinkList）malloc（sizeof(Node））;if（p==NULL)return—1；p->data=x;p—〉next=*Head_pointer;＊Head_pointer=p；return1；}voidShow_LinkList（LinkListHead)｛Node*p;printf（"

23”)；p=Head；if(p==NULL）printf（”

24NULL”）；while(p！=NULL)｛printf（”%d

25",p—>data);p=p—〉next；

26｝}intmain(）{intm;LinkListHead；LinkListHL;Head=NULL；for(m=0；m〈7；m++)if(!insert_First（＆Head,m))break;Show_LinkList(Head）;HL=op_LinkList（Head）；Show_LinkList(HL）;return0；｝5.将两个单链表合并为一个单链表＃include”stdio。h”#include"stdlib.h"typedefstructnode{intdata；structnode＊next；｝Node,＊LinkList;voidcontact(LinkListHead，LinkListHT）｛Node＊p;p=Head;while（p-〉next）p=p-〉next；p-〉next=HT；｝intinsert_First(LinkList＊Head_pointer,intx)｛Node*p；p=（LinkList)malloc(sizeof（Node));if（p==NULL）return-1;p—>data=x；p-〉next=*Head_pointer；*Head_pointer=p;return1；｝voidShow_LinkList(LinkListHead）

27{Node*p;printf(”

28”);p=Head；if（p==NULL)printf("

29NULL"）；while(p！=NULL）｛printf("％d”,p-〉data）;p=p—>next;｝}intmain(）{intm;LinkListHead；LinkListHT;Head=NULL；HT=NULL;for(m=0;m〈20;m++)if(!insert_First(＆Head,m))break；for(m=0；m〈10；m++）if(！insert_First（＆HT,m))break；Show_LinkList（Head）;Show_LinkList（HT）；contact(Head,HT）;Show_LinkList（Head);return0；}1.实验总结：理解线性表的逻辑特点；掌握了单链表的定义及C语言实现。但是还有很多不清楚的地方运行时有许多错误。说明：1.实验名称、实验目的、实验内容、实验要求由教师确定,实验前由教师事先填好，然后作为实验报告模版供学生使用；2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；

301.源程序、代码、具体语句等,若表格空间不足时可作为附录另外附页。