实验二单链表基本操作

1、word实验二单链表根本操作一实验目的1. 学会定义单链表的结点类型，实现对单链表的一些根本操作和具体 的函数定义，了解并掌握单链表的类定义以与成员函数的定义与调用。2. 掌握单链表根本操作与两个有序表归并、 单链表逆置等操作的实现。二实验要求1. 预习C语言中结构体的定义与根本操作方法。2对单链表的每个根本操作用单独的函数实现。3. 编写完整程序完成下面的实验内容并上机运行。4. 整理并上交实验报告。三实验内容1.编写程序完成单链表的如下根本操作：(1) 初始化单链表La。(2) 在La中第i个元素之前插入一个新结点。(3) 删除La中的第i个元素结点。(4) 在La中查找某结点并返回其位置

2、。(5) 打印输出La中的结点元素值。2 .构造两个带有表头结点的有序单链表 La、Lb，编写程序实现将La、 Lb合并成一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb、pc,其中pa, pb分别指 向La表与Lb表中当前待比拟插入的结点，pc指向Lc表中当前最后一个结 点。依次扫描La和Lb中的元素，比拟当前元素的值，将较小者到*pc之后, 如此重复直到La或Lb完毕为止，再将另一个链表余下的内容到 pc所指的 结点之后。3.构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。 即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点， 如此等等。四思考与提高

3、1. 如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2. 如何将一个带头结点的单链表 La分解成两个同样结构的单链表Lb， Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？10 / 101 编写程序完成单链表的如下根本操作：初始化单链表La。(2) 在La中第i个元素之前插入一个新结点(3) 删除La中的第i个元素结点。(4) 在La中查找某结点并返回其位置。打印输出La中的结点元素值。#in clude#in clude#i nclude #defi ne OK 1#defi ne ERROR 0 typedef int Status; typedef int

4、 ElemType;/定义存储结构typedef struct Lno deint data; /*每个元素数据信息*/struct Lnode *n ext; /*存放后继元素的地址 */ LNode,*L in kList;int mai n()void Create_L(L in kList &L,i nt n);void Prin t_L(Li nkList L);Status List In sert_L(L in kList &L,i nt i,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);Status

5、 Find_L(LinkList L,int e);LinkList La;/创建单链表Laint n;printf(请输入链表La中的元素个数:n);scan f(%d, &n);Create_L(La ,n);/初始化单链表printf(”现在La中的元素为:n);Prin t_L(La);printf(-nn “);n);prin tf(现在准备插入元素，请输入插入位置与所插入元素的值int i,e;scanf(%d %d，&i,&e);List In sert_L(La,i,e);printf(”插入后La中的元素为：n);Prin t_L(La);printf(-nn “);prin

6、 tf(现在准备删除元素，请输入删除位置 n);scan f(%d, &i);ListDelete_L(La,i,e);printf(删除后La中的元素为:n);Prin t_L(La);printf(nn);printf(请输入所要查找元素的值:n);scan f(%d, &e);Fin d_L(La,e);printf(所要查找元素的位置为：dn,Fi nd_L(La,e); void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一个带头结点的单链线性表Lfo

7、r(i nt i=n ;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no de);printf(请输入链表La中的第d个元素:n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L-n ext =p;(逆序实现)/*Lin kList q=L; for(i nt i=1;in ext=p;p- next=NULL;q=q-n ext ;printf(”请输入链表La中的第d个元素:n,i);scan f(%d,&p-data);(正序实现)*/初始化单链表/输出单链表void Prin t_L(Li nkList

8、L)Lin kList p;p=L-n ext;while(p)prin tf(%d ,p-data );p=p-n ext;prin tf(n);/在单链表L的第i个位置前插入元素eStatus List In sert_L(L in kList &L,i nt i,ElemType e)Lin kList p=L;int j=0;while(p&jn ext; +j;if(!p|ji-1) return ERROR;Lin kList s=(L in kList)malloc(sizeof(LNode); s-data=e; s-n ext=p-n ext;p_n ext=s;return

9、 OK; /ListI nsert_L/删除单链表L中第i个位置上的元素Status ListDelete_L(LinkList &L,int i,ElemType &e) Lin kList p=L;int j=0;while( p- next & jn ext; +j;if(!p- next|ji-1)return ERROR;Lin kList q=p-n ext; p-n ext=q-n ext; e=q_data;free(q);return OK;/Li nkDelete_L/*查找元素并返回位置*/Status Fi nd_L(L in kList L,i nt e)Lin kL

10、ist p=L-n ext;int j=1;while(p-data!=e&p-n ext) p=p-n ext; j+;if(p-data=e) retur n j;elseprintf(无当前元素n);return ERROR;if(!p)printf(无当前元素n);return ERROR;/定位2 .构造两个带有表头结点的有序单链表 La、Lb,编写程序实现将La、Lb合并 成一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比拟插入的结点，pc指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比拟当前元素的值，将

11、较小者到*pc之后，如此重复直到La 或Lb完毕为止，再将另一个链表余下的内容到pc所指的结点之后。#in clude#in clude#i nclude #defi ne OK 1#defi ne ERROR 0typedef int Status;typedef int ElemType;/定义存储结构typedef struct Lno deint data; /*每个元素数据信息*/struct Lnode *n ext; /*存放后继元素的地址 */ LNode,*L in kList;void mai n()void Create_L(L in kList &L,i nt n);v

12、oid Prin t_L(Li nkList L);void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc);Lin kList La, Lb,Lc;创建单链表 La,Lb,Lcint n;printf(请输入链表La中的元素个数:n);scan f(%d, &n);Create_L(La ,n);/初始化单链表printf(”现在La中的元素为:n);Prin t_L(La);printf(请输入链表Lb中的元素个数:n);scan f(%d, &n);Create_L(Lb ,n);/初始化单链表printf(”现在Lb中的元素为:

13、n);Prin t_L(Lb);Create_L(Lc,O);printf(-nn “);printf(开始合并:n);MergeList_L(La, Lb,Lc);printf(-nn “);printf(合并后，Lc的元素为n);Prin t_L(Lc);void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一个带头结点的单链线性表Lfor(i nt i=n ;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no d

14、e);printf(请输入链表中的第d个元素：n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L_n ext =p;(逆序实现)/*Lin kList q=L;for(i nt i=1;in ext=p;p- next=NULL;q=q_n ext ;printf(请输入链表La中的第d个元素:n,i);scan f(%d,&p-data);/( 正序实现)*/初始化单链表有序单链表La和Lb的归并void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc)Lin kList pa=La-n ext;Li

15、n kList pb=Lb-n ext;Lin kList pc;Lc=pc=La;while (pa&pb)if (pa-datadata)pc-n ext=pa; pc=pa;pa=pa-n ext;else pc- n ext=pb; pc=pb;pb=pb-n ext; pc- n ext=pa?pa:pb;free(Lb);prin tf(ppppppppppppppp);/MergeList/输出单链表void Prin t_L(Li nkList L)Lin kList p;p=L-n ext;while(p)prin tf(%d ,p-data );p=p-n ext;prin

16、 tf(n);3构造一个单链表L,其头结点指针为head，编写程序实现将L逆置。即最后 一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。#in clude#in clude#i nclude /定义存储结构typedef struct Lno deint data; /*每个元素数据信息*/struct Lnode *n ext; /*存放后继元素的地址 */ LNode,*L in kList;void mai n()void Create_L(L in kList &L,i nt n);void Prin t_L(Li nkList L);void ReverseLis

17、t(L in kList L);LinkList La;/创建单链表Laint n;printf(”请输入链表La中的元素个数：n);scan f(%d, &n);Create_L(La ,n);/初始化单链表printf( 现在La中的元素顺序为:n); Prin t_L(La);printf(-nn “);ReverseList(La);printf(逆置后，La的元素顺序为:n);Prin t_L(La);void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一个带头结点的单链线性表Lfor(i nt i=n ;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no de);printf(请输入链表中的第d个元素：n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L-n ext =p;/(逆序实现)/*Lin kList q=L; for(i nt i=1;in ext=p;p- next=NULL;q=q-n ext ;printf(请输入链表La中的第d个元素:n,i);scan f(%d,&p-data);/( 正序实现)*/初始化单链表/