实验二 单链表基本操作.doc

实验二 单链表基本操作一 实验目的1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二 实验要求1预习C语言中结构体的定义与基本操作方法。2对单链表的每个基本操作用单独的函数实现。3编写完整程序完成下面的实验内容并上机运行。4整理并上交实验报告。 三 实验内容1编写程序完成单链表的下列基本操作： (1)初始化单链表La。 (2)在La中第i个元素之前插入一个新结点。 (3)删除La中的第i个元素结点。 (4)在La中查找某结点并返回其位置。 (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逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）四 思考与提高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; /定义存储结构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);LinkList La;/创建单链表Laint 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); scanf(%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) LinkList 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; while(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个位置上的元素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&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结束为止，再将另一个链表余下的内容链接到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_L(LinkList &La, LinkList &Lb,LinkList &Lc);LinkList La,Lb,Lc;/创建单链表La,Lb,Lcint 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(-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-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=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; 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逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）#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;/创建单链表Laint n; printf(请输入链表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=(LinkList)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); /(正序实现)*/