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

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

2、(1)初始化单链表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)初始化单链表lalinklist initlist

3、()int i,value,n;linklist h=(linklist)malloc(sizeof(lnode);linklist p=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);linklis

4、t new = (linklist)malloc(sizeof(lnode);new->data=value;p->next=new;new->next=null;p=new;printf(" 链表建立成功！ n");return h->next;( 2)在la 中插入一个新结点linklist insertlist(linklist l,int i,elemtype value)linklist h,q,t=newlnode(t,value);int x=0;h=q=l;if(i=1)t->next=h, h=t;elsewhile(x+&l

5、t;i-2)q=q->next;t->next=q->next;q->next=t;printf(" 插入成功！ n");return h;3）删除la 中的某一个结点linklist deletelist(linklist l,int i)linklist h,q,de;int x=0;h=q=l;int t;if(i=1)h=h->next;elsewhile(x+<i-2)q=q->next;de=q->next;if(de->next=null)q->next=null;elseq->next=de-

6、>next;printf(" 删除成功！ n");return h;( 4)在la 中查找某结点并返回其位置status locatelist(linklist l,elemtype value)linklist q=l;int i=0,t;while(q!=null)i+;if(q->data=value)printf("该结点在链表中的位置为第d4vn",i)；return ok;q=q->next;printf(" 该链表中没有该结点！ n");return error;( 5)打印输出la 中的结点元素值st

7、atus print(linklist l)linklist q=l;printf(" 该链表的每个元素为 :n");while(q!=null)printf("%8d",q->data);q=q->next;printf("n");return ok;( 6)清空链表linklist emptylist(linklist l)free(l->data);l->next=null;printf(" 清空成功！ n");return l;( 7)销毁链表linklist freelist(li

8、nklist l)printf(" 释放成功！ n");free(l);( 8)主函数int main()linklist l=initlist();int n,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("请输入要

9、删除的结点的位置:");scanf("%d",&i);deletelist(l,i);break;case 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(" 退出成功！ ")

10、;return 0;2构造两个带有表头结点的有序单链表la、 lb ，编写程序实现将la 、 lb 合并成一个有序单链表lclinklist connectlist(linklist la,linklist lb)linklist lc,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->

11、;data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->next,c=c->next;return lc;3 .如果上面实验内容2中合并的表内不允许有重复的数据该如何操作 linklist connectlist(linklist la,linklist lb)int i=1;linklist lc,a,b,c,q,p;a=la;b=lb;if(la->data<lb->data)lc=la;a=a->next;elselc=lb;b=b->nex

12、t;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->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

13、=c->next;return lc;4 .如何将一个带头结点的单链表la分解成两个同样结构的单链表lb, lc,使 得lb中只含la表中奇数结点,lc中含有la表的偶数结点？status partlist(linklist lc)int n1=0,n2=0;linklist la,lb,l;linklist a,b;l=lc;while(l!=null)if(l->data%2=0)if(n1=0)a=la=l;l=l->next; elsea->next=l;l=l->next; elseif(n2=0)b=lb=l;l=l->next; elseb-&

14、gt;next=l;l=l->next;a->next=null;b->next=null;return ok;六、实验测试1.编写程序完成单链表的下列基本操作:口34 4b bb 上成功is6 678990100 5:?的何百：x值! 45为箪4个1u045用人 篇 零1,ai.iaal2fi3bl>.,j.-2 功结 的的 用除 要时加人义工翳入盒sam点中上膏表襄ss曾 皆律 四的 的的中 出衣 嚼值 卷位i iiii,rs至s入八点s1hmll工4-.-'.-.7.点tllnif用"r li s h娈的1l 人小单表 l2.3,4.5flr.1

15、1点船的寓 si msi点 靛结 功的 的*中 川曾mi使！芳功 入醯雪翳人成 他加岬相甄.点中w0w凄ss匕匕 百 功 的 用 f 益人先出w凿人成li2.i3.i4.s.ls.l7.ggqg七、总结附录 1 ：源代码#include<stdio.h>#include<stdlib.h>#define ok 1#define error 0#define overflow -2typedef int elemtype;typedef int status;typedef struct lnodeelemtype data;struct lnode *next; lno

16、de,*linklist;linklist newlnode(lnode *p,elemtype data)p = (lnode *)malloc(sizeof(lnode);p->data = data;p->next = null;return p;linklist initlist()int i,value,n;linklist h=(linklist)malloc(sizeof(lnode);linklist p=h;p->next=null;doprintf(" 请输入链表的长度:");scanf("%d",&n);i

17、f(n<=0)printf("输入有误请重新输入！ n");while(n<=0);printf(" 请输入各个元素 :n");for(i=0; i<n; i+)scanf("%d",&value);linklist new = (linklist)malloc(sizeof(lnode);new->data=value;p->next=new;new->next=null;p=new;printf(" 链表建立成功！ n");return h->next;link

18、list insertlist(linklist l,int i,elemtype value)linklist h,q,t=newlnode(t,value);int x=0;h=q=l;if(i=1)t->next=h;h=t;elsewhile(x+<i-2)q=q->next;t->next=q->next;q->next=t;printf(" 插入成功！ n");return h;linklist deletelist(linklist l,int i)linklist h,q,de;int x=0;h=q=l;int t;if

19、(i=1)h=h->next;elsewhile(x+<i-2)q=q->next;de=q->next;if(de->next=null)q->next=null;elseq->next=de->next;printf(" 删除成功！ n");return h;status locatelist(linklist l,elemtype value)linklist q=l;int i=0,t;while(q!=null)i+;if(q->data=value)printf("该结点在链表中的位置为第d4vn&

20、quot;,i)；return ok;q=q->next;printf(" 该链表中没有该结点！ n");return error;status print(linklist l)linklist q=l;printf(" 该链表的每个元素为 :n");while(q!=null)printf("%8d",q->data);q=q->next;printf("n");return ok;linklist emptylist(linklist l)free(l->data);l->next=null;printf(" 清空成功！ n");return l;linklist freelist(linklist l)printf(" 释放成功！ n");free(l);void pr()printf("n1. 插入新结点 n");printf("2. 删除链表中的结点 n");printf("3.查找结点n");printf(&qu