《实验二单链表基本操作》由会员分享，可在线阅读，更多相关《实验二单链表基本操作（9页珍藏版）》请在金锄头文库上搜索。
1、实验二单链表基本操作一实验目的1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体 的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二实验要求1. 预习C语言中结构体的定义与基本操作方法。2. 对单链表的每个基本操作用单独的函数实现。3. 编写完整程序完成下面的实验内容并上机运行。4. 整理并上交实验报告。三实验内容1. 编写程序完成单链表的下列基本操作：(1) 初始化单链表La。(2) 在La中第1个元素之前插入一个新结点。(3) 删除La中的第1个元素结点。(4) 在La中查找某结点并返回其位置。(
2、5) 打印输出La中的结点元素值。2 构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、 Lb合并成一个有序单链表Leo合并思想是：程序需要3个指针：pa、pb、pc,其中pa, pb分别指 向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结 点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*戸。 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到 pc所指的结点之后。3. 构造一个单链表L,其头结点指针为head,编写程序实现将L逆置。 (即最后一个结点变成第一个结点，原來倒数第二个结点变成第二个结点, 如此等等。)!1!思
3、考与提高1-如果上面实验内容2中合并的表内不允许有重复的数据该如何操作?2. 如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb, Lc,使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？1.编写程序完成单链表的下列基本操作：(1) 初始化单链表Lao(2) 在La中第1个元素之前插入一个新结点。(3) 删除La中的第1个元素结点。(4) 在La中查找某结点并返回其位置。(5) 打印输出La中的结点元素值。# iiiclude# mclude#include #define OK 1#define ERROR 0tvpedef int Status; tvpedef mt
4、ElemType;定义存储结构tvpedef struct Lnodemt data; /*每个元素数据信息*/stmct Lnode *next; /*存放后继元素的地址*/ LNode,*LinkList;mt mam()void Create_L(LnikList &Ljnt n);void Priiit_L(LuikList L);Status ListInseit_L(LuikList &L,int i,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);Status Fmd_L(LuikList L.iiit
5、 e);LinkList La;创建单链表Laint n;pmitf(”请输入链表La中的元素个数:n”)；scanfC%d”,&n);Create_L(La,n);/初始化单链表printf(“现在La中的元素为:n”);Print_L(La);pnntf(Mniin);pmitf(”现在准备插入元素，请输入插入位置及所插入元素的值n”); int i,e;scanf(H%cl&e);ListIiisert_L(La4,e);插入后La中的元素为An”);Print_L(La);W1);pmitfc现在准备删除元素，请输入删除位置n”)； scanf(H%df&i);ListDelete_L
6、(Laj,e);printf(删除后La中的元素为:n”);Print_L(La);pnntf(Mniin);pmitf(”请输入所要查找元素的值:n”)；scanf(H%df&e);Find_L(La,e);pmirff所要查找元素的位置为dgFind_L(La);void Create_L(LinkList &Ljnt n)intj=l;L=(LuikList)malloc(sizeof(Lnode);L-next =NULL;/先建立一个带头结点的单链线性表L for(int i=n;i0;-i)LnikList p=(LnikList)nialloc(sizeof(Lnode); pn
7、ntf(”请输入链表La中的第4个元素:n”j+); scanf(H%d,&p-data);p-next=L next;L-next =p; (逆序实现)LuikList q=L; fbr(mt i=l;inext=p;p-next=NULL;q=q-next;printfT请输入链表La中的第d个元素AnJ);scanf(n%d,&p-data);/(正序实现)*/初始化单链表输出单链表void Prmt_L(LnikList L)LuikList p;p=L-next;wlule(p)printf(M%d H,p-data);p=p-next;pimtfCXii);在单链表L的第个位置前插
8、入元素eStatus ListInsert_L(LuikList &L.iiit i,ElemType e)LinkList p=L;mtj=0;wliile(p&jnext; +j;if(!p|ji-l) return ERROR:LinkList s=(LiiikList)malloc(sizeof(LNode); s-data=e; s-next=p-next;next=s;return OK; /./ListIiisert_L删除单链表L中第1个位置上的元素Status ListDelete_L(LuikList &Ljnt i,ElemType &e)LinkList p=L; mt
9、j=0;wliile( p-next & jnext; +j;if(!p-next|ji-l) return ERROR; LinkList q=p-next; p-next=q-next; e=q-data;free(q); return OK; 7LuikDelete_L/*查找元素并返回位置*/Status Fmd_L(LnikList L.iiit e)LinkList p=L-next;wliile(p-data!=亡&p-next)p=p-next;J+;if(p-data=e) return j;elseprintf(无当前元素Xu)； return ERROR;if(!p)pr
10、intf(无当前元素Xu)； return ERROR; 定位2 构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、Lb合并成 一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb pc,其中pa, pb分别指向La表与 Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。依次扫描 La和Lb中的元素，比较当前元素的值，将较小者链接到*戸。之后，如此重复直 到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。# iiiclude# mclude#include #define OK 1#define ERROR 0tvpedef int S
11、tatus;tvpedef int ElemType;定义存储结构tvpedef struct Lnodemt data; /*每个元素数据信息*/stmct Lnode *next; /*存放后继元素的地址*/ LNode,*LinkList;void main()void Create_L(LnikList &Ljnt n);void Prmt_L(LuikList L);void MergeList_L(LuikList &L* LnikList &LbLuikList &Lc)；LinkList La,LbXc/创建单链表 La.Lb.Lcint n;pmitf(”请输入链表La中的元
12、素个数An”)；scanf(H%df&n);Create_L(La,n);/初始化单链表 pmitf(”现在La中的元素为:n”)；Print_L(La);pnntfClW输入链表Lb中的元素个数An”)；scanf(H%df&n);Create_L(Lb,n);/初始化单链表pmitf(”现在Lb中的元素为:n”)；PnnCL(Lb);Cieate_L(Lc,O);pnntf(Miinn);pnntf(”开始合并:n”)；MeigeList_L(La, Lb.Lc);pnntf(Miinn);prmtf(”合并后，Lc的元素为11”)；Print_L(Lc);void Create_L(Li
13、nkList &Ljnt n)intj=l;L=(LuikList)malloc(sizeof(Lnode);L-next =NULL先建立一个带头结点的单链线性表L fbr(int i=n;i0;i)LnikList p=(LnikList)nialloc(sizeof(Lnode); pnntf(”请输入链表中的第4个元素:n”,j+); scanf(H%d&p-data);next=L next;L-next =p; (逆序实现)LuikList q=L;LuikList p=(LuikList)malloc (sizeof(Lnode); q-next=p;p-next=NULL;q=
14、q-next;pnntf(”请输入链表La中的第4个元素scanf(%d,&p-data);/(正序实现)*/初始化单链表有序单链表和Lb的归并void MergeList_L(LnikList &La, LnikList &Lb,LuikList &Lc) LinkList pa=La-next;LinkList pb=Lb-next;LinkList pc;Lc=pc=La;while (pa&pb)if (pa-datadata) pc-next=pa; pc=pa;pa=pa-next;else pc-next=pb; pc=pb;pb=pb-next; pc-next=pa?pa:pb;fiee(Lb);pnntf(” ppppppppppppppp”)；/MergeList输出单链表void
