链表的基本操作-数据结构实验报告

1、大学数据结构实验报告课程名称数据结构实验第(四)次实验实验名称链表的根本操作学生姓名于歌专业班级学号实验成绩指导老师(签名)日期2021年10月01日一、实验目的1 .学会定义单链表的结点类型,实现对单链表的一些根本操作和具体的函数定义,了解并掌握单链表的类定义以及成员函数的定义与调用.2 .掌握单链表根本操作及两个有序表归并、单链表逆置等操作的实现.二、实验要求1 .预习C语言中结构体的定义与根本操作方法.2 .对单链表的每个根本操作用单独的函数实现.3 .编写完整程序完成下面的实验内容并上机运行.4 .整理并上交实验报告.三、实验内容：1.编写程序完成单链表的以下根本操作：(1)初始化单链

2、表La(2)在La中插入一个新结点(3)删除La中的某一个结点(4)在La中查找某结点并返回其位置(5)打印输出La中的结点元素值(6)清空链表(7)销毁链表2构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、Lb合并成一个有序单链表Lco四、思考与提升：1 .如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2 .如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点？五、实验设计1.编写程序完成单链表的以下根本操作：(1)初始化单链表LaLinkListInitList()(inti,value

3、,n;LinkListH=(LinkList)malloc(sizeof(LNode);LinkListP=H;P->next=NULL;doprintf("请输入链表的长度:");scanf("%d",&n);if(n<=0)printf("输入有误请重新输入！n");while(n<=0);printf("请输入各个元素:n");for(i=0;i<n;i+)scanf("%d",&value);LinkListNEW=(LinkList)malloc

4、(sizeof(LNode);NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;printf("链表建立成功！n");returnH->next;(2)在La中插入一个新结点LinkListInsertList(LinkListL,inti,ElemTypevalue)LinkListh,q,t=NewLNode(t,value);intx=0;h=q=L;if(i=1)t->next=h,h=t;elsewhile(x+<i-2)q=q->next;t->next=q->

5、next;q->next=t;printf("插入成功！n");returnh;(3)删除La中的某一个结点LinkListDeleteList(LinkListL,inti)(LinkListh,q,de;intx=0;h=q=L;intt;if(i=1)h=h->next;else(while(x+<i-2)q=q->next;de=q->next;if(de->next=NULL)q->next=NULL;elseq->next=de->next;printf("删除成功！n");returnh

6、;(4)在La中查找某结点并返回其位置StatusLocateList(LinkListL,ElemTypevalue)(LinkListq=L;inti=0,t;while(q!=NULL)(i+;if(q->data=value)(printf("该结点在链表中的位置为第d4Vn",i);returnOK;q=q->next;printf("该链表中没有该结点！n");returnERROR;(5)打印输出La中的结点元素值StatusPrint(LinkListL)(LinkListq=L;printf("该链表的每个元素为:

7、n");while(q!=NULL)(printf("%8d",q->data);q=q->next;printf("n");returnOK;(6)清空链表LinkListEmptyList(LinkListL)(free(L->data);L->next=NULL;printf("清空成功！n");returnL;(7)销毁链表LinkListFreeList(LinkListL)(printf("释放成功！n");free(L);(8)主函数intmain()(LinkLis

8、tL=InitList();intn,i,j;Pr();scanf("%d",&n);while(n>0&&n<7)(switch(n)(case 1:printf("请输入要插入的结点的值和插入的位置:");scanf("%d%d",&i,&j);InsertList(L,j,i);break;case 2:printf("请输入要删除的结点的位置:");scanf("%d",&i);DeleteList(L,i);break;cas

9、e 3:printf("请输入要查找的结点的值:");scanf("%d",&i);LocateList(L,i);break;case 4:Print(L);break;case 5:EmptyList(L);break;case 6:FreeList(L);break;Pr();scanf("%d",&n);if(n=7)printf("退出成功！)；return0;2 .构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、Lb合并成一个有序单链表LcLinkListConnectList(L

10、inkListLa,LinkListLb)LinkListLc,a,b,c;a=La;b=Lb;if(La->data<Lb->data)Lc=La,a=a->next;elseLc=Lb,b=b->next;c=Lc;while(a!=NULL|b!=NULL)if(a=NULL)c->next=b,break;if(b=NULL)c->next=a;break;if(a->data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->nex

11、t,c=c->next;returnLc;3 .如果上面实验内容2中合并的表内不允许有重复的数据该如何操作LinkListConnectList(LinkListLa,LinkListLb)inti=1;LinkListLc,a,b,c,q,p;a=La;b=Lb;if(La->data<Lb->data)Lc=La;a=a->next;elseLc=Lb;b=b->next;c=Lc;while(a!=NULL|b!=NULL)if(a=NULL)c->next=b,break;if(b=NULL)c->next=a,break;if(a-&g

12、t;data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->next,c=c->next;c=Lc;q=c->next;while(q!=NULL)if(c->data=q->data)c->next=q->next;c=c->next;q=c->next;returnLc;4 .如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点？StatusPartList(L

13、inkListLc)(intn1=0,n2=0;LinkListLa,Lb,L;LinkLista,b;L=Lc;while(L!=NULL)(if(L->data%2=0)(if(n1=0)(a=La=L;L=L->next;)else(a->next=L;L=L->next;)else(if(n2=0)(b=Lb=L;L=L->next;)else(b->next=L;L=L->next;)a->next=NULL;b->next=NULL;returnOK;六、实验测试1.编写程序完成单链表的以下根本操作:口344bbb上成功IS66

14、789901005:?的何百：X值!45为箪4个1U0用人篇零1,Ai.iAAL2fi3BL>.,J.-2功结的的用除要时加人义工翳入盒SAm点中上膏表襄ss曾皆律四的的的中出衣嚼值卷位iiiii,Rs至S入八点S1HMLL工4-.-'.-.7.点tllniF用"rliSH娈的1L人小单表L2.3,4.5flr.11点船的寓siMSI点靛结功的的*中川曾Mi使！芳功入醯雪翳人成他加岬相甄.点中W0W凄SS匕匕百功的用f益人先出W凿人成LI2.I3.I4.S.ls.l7.ggqg七、总结附录1:源代码#include<stdio.h>#include<s

15、tdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;LinkListNewLNode(LNode*P,ElemTypedata)P=(LNode*)malloc(sizeof(LNode);P->data=data;P->next=NULL;returnP;LinkListInitList()inti,value,n;LinkListH

16、=(LinkList)malloc(sizeof(LNode);LinkListP=H;P->next=NULL;doprintf("请输入链表的长度:");scanf("%d",&n);if(n<=0)printf("输入有误请重新输入！n");while(n<=0);printf("请输入各个元素:n");for(i=0;i<n;i+)scanf("%d",&value);LinkListNEW=(LinkList)malloc(sizeof(LNod

17、e);NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;)printf("链表建立成功！n");returnH->next;)LinkListInsertList(LinkListL,inti,ElemTypevalue)(LinkListh,q,t=NewLNode(t,value);intx=0;h=q=L;if(i=1)(t->next=h;h=t;)else(while(x+<i-2)q=q->next;t->next=q->next;q->next=t;)p

18、rintf("插入成功！n");returnh;)LinkListDeleteList(LinkListL,inti)(LinkListh,q,de;intx=0;h=q=L;intt;if(i=1)h=h->next;else(while(x+<i-2)q=q->next;de=q->next;if(de->next=NULL)q->next=NULL;elseq->next=de->next;)printf("删除成功！n");returnh;)StatusLocateList(LinkListL,El

19、emTypevalue)(LinkListq=L;inti=0,t;while(q!=NULL)(i+;if(q->data=value)(printf("该结点在链表中的位置为第d4Vn",i);returnOK;)q=q->next;)printf("该链表中没有该结点！n");returnERROR;)StatusPrint(LinkListL)(LinkListq=L;printf("该链表的每个元素为:n");while(q!=NULL)(printf("%8d",q->data);q=

20、q->next;)printf("n");returnOK;)LinkListEmptyList(LinkListL)(free(L->data);L->next=NULL;printf("清空成功！n");returnL;)LinkListFreeList(LinkListL)(printf("释放成功！n");free(L);)voidPr()printf("n1.插入新结点n");printf("2.删除链表中的结点n");printf("3.查找结点n");printf("4.输出链表n");