1、实验二单链表基本操作实验二 单链表基本操作一 实验目的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表的偶数结点?1编写程序完成单链表的下列基本操作:(1)初始化单链表La。(2)在La中第i个元素之前插入一个新结点。(3)删除La中的第i个元素结点。(4)在La中查找某结点并返回其位置。(5)打印输出La中的结点元素值。#include#include#include #define OK 1#define ERROR 0typedef int Status;typedef int ElemType; /定义存储结
4、构typedef struct Lnode int data; /*每个元素数据信息*/struct Lnode *next; /*存放后继元素的地址*/ LNode,*LinkList;int main() void Create_L(LinkList &L,int n); void Print_L(LinkList L); Status ListInsert_L(LinkList &L,int i,ElemType e); Status ListDelete_L(LinkList &L,int i,ElemType &e); Status Find_L(LinkList L,int e);
5、 LinkList La;/创建单链表La int n; printf(请输入链表La中的元素个数:n); scanf(%d,&n); Create_L(La,n);/初始化单链表 printf(现在La中的元素为:n); Print_L(La); printf(-nn); printf(现在准备插入元素,请输入插入位置及所插入元素的值n); int i,e; scanf(%d %d,&i,&e); ListInsert_L(La,i,e); printf(插入后La中的元素为:n); Print_L(La); printf(-nn); printf(现在准备删除元素,请输入删除位置n); s
6、canf(%d,&i); ListDelete_L(La,i,e); printf(删除后La中的元素为:n); Print_L(La); printf(-nn); printf(请输入所要查找元素的值:n); scanf(%d,&e); Find_L(La,e); printf(所要查找元素的位置为:%dn,Find_L(La,e);void Create_L(LinkList &L,int n) int j=1; L=(LinkList)malloc(sizeof(Lnode); L-next =NULL;/先建立一个带头结点的单链线性表L for(int i=n;i0;-i) LinkL
7、ist p=(LinkList)malloc(sizeof(Lnode); printf(请输入链表La中的第%d个元素:n,j+); scanf(%d,&p-data); p-next=L-next; L-next =p; /(逆序实现)/* LinkList q=L; for(int i=1;inext=p; p-next=NULL; q=q-next ; printf(请输入链表La中的第%d个元素:n,i); scanf(%d,&p-data); /(正序实现)*/初始化单链表/输出单链表void Print_L(LinkList L) LinkList p; p=L-next; wh
8、ile(p) printf(%d ,p-data ); p=p-next; printf(n);/在单链表L的第i个位置前插入元素eStatus ListInsert_L(LinkList &L,int i,ElemType e) LinkList p=L; int j=0; while(p&jnext; +j; if(!p|ji-1) return ERROR; LinkList s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK; /ListInsert_L/删除单链表L中第i个位置上
9、的元素Status ListDelete_L(LinkList &L,int i,ElemType &e) LinkList p=L; int j=0; while( p-next & jnext; +j; if(!p-next|ji-1) return ERROR; LinkList q=p-next; p-next=q-next; e=q-data; free(q); return OK;/LinkDelete_L/*查找元素 并返回位置*/Status Find_L(LinkList L,int e) LinkList p=L-next; int j=1; while(p-data!=e
10、&p-next) p=p-next; j+; if(p-data=e) return j; else printf(无当前元素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中的元素,比较当前元素的值,将较小者链接到*pc之后,如此重复直到La或Lb结束为止,再将另一个
11、链表余下的内容链接到pc所指的结点之后。 #include#include#include #define OK 1#define ERROR 0typedef int Status;typedef int ElemType;/定义存储结构typedef struct Lnode int data; /*每个元素数据信息*/struct Lnode *next; /*存放后继元素的地址*/ LNode,*LinkList;void main() void Create_L(LinkList &L,int n); void Print_L(LinkList L); void MergeList_
12、L(LinkList &La, LinkList &Lb,LinkList &Lc); LinkList La,Lb,Lc;/创建单链表La,Lb,Lc int n; printf(请输入链表La中的元素个数:n); scanf(%d,&n); Create_L(La,n);/初始化单链表 printf(现在La中的元素为:n); Print_L(La); printf(请输入链表Lb中的元素个数:n); scanf(%d,&n); Create_L(Lb,n);/初始化单链表 printf(现在Lb中的元素为:n); Print_L(Lb); Create_L(Lc,0); printf(-
13、nn); printf(开始合并:n); MergeList_L(La, Lb,Lc); printf(-nn); printf(合并后,Lc的元素为n); Print_L(Lc); void Create_L(LinkList &L,int n) int j=1; L=(LinkList)malloc(sizeof(Lnode); L-next =NULL;/先建立一个带头结点的单链线性表L for(int i=n;i0;-i) LinkList p=(LinkList)malloc(sizeof(Lnode); printf(请输入链表中的第%d个元素:n,j+); scanf(%d,&p
14、-data); p-next=L-next; L-next =p; /(逆序实现)/* LinkList q=L; for(int i=1;inext=p; p-next=NULL; q=q-next ; printf(请输入链表La中的第%d个元素:n,i); scanf(%d,&p-data); /(正序实现)*/初始化单链表/有序单链表La和Lb的归并void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc) LinkList pa=La-next; LinkList pb=Lb-next; LinkList pc; Lc=pc=L
15、a; 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; free(Lb); printf(ppppppppppppppp);/MergeList/输出单链表void Print_L(LinkList L) LinkList p; p=L-next; while(p) printf(%d ,p-data ); p=p-next; printf(n);3构造一个单链表L,其头结点指针为head,编写程序实现将L逆置。(即最
16、后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。)#include#include#include /定义存储结构typedef struct Lnode int data; /*每个元素数据信息*/struct Lnode *next; /*存放后继元素的地址*/ LNode,*LinkList;void main() void Create_L(LinkList &L,int n); void Print_L(LinkList L); void ReverseList(LinkList L); LinkList La;/创建单链表La int n; printf(请输
17、入链表La中的元素个数:n); scanf(%d,&n); Create_L(La,n);/初始化单链表 printf(现在La中的元素顺序为:n); Print_L(La); printf(-nn); ReverseList(La); printf(逆置后,La的元素顺序为:n); Print_L(La); void Create_L(LinkList &L,int n) int j=1; L=(LinkList)malloc(sizeof(Lnode); L-next =NULL;/先建立一个带头结点的单链线性表L for(int i=n;i0;-i) LinkList p=(LinkLi
18、st)malloc(sizeof(Lnode); printf(请输入链表中的第%d个元素:n,j+); scanf(%d,&p-data); p-next=L-next; L-next =p; /(逆序实现)/* LinkList q=L; for(int i=1;inext=p; p-next=NULL; q=q-next ; printf(请输入链表La中的第%d个元素:n,i); scanf(%d,&p-data); /(正序实现)*/初始化单链表/输出单链表void Print_L(LinkList L) LinkList p; p=L-next; while(p) printf(%d ,p-data ); p=p-next; printf(n);void ReverseList(LinkList L) LinkList p,q;p=L-next;L-next=NULL;while(p!=NULL) q=p-next; /*q指针保留p-next得值*/p-next=L-next;L-next=p; /*将p结点头插入到单链表L中*/p=q; /*p指向下一个要插入的结点*/
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2