大学数据结构实验报告课程名称数据结构实验第（四）次实验实验名称链表的基本操作学生姓名于歌专业班级学号实验成绩指导老师（签名）日期2018年10月01日一、实验目的1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容：1．编写程序完成单链表的下列基本操作：（1）初始化单链表La（2）在La中插入一个新结点（3）删除La中的某一个结点（4）在La中查找某结点并返回其位置（5）打印输出La中的结点元素值（6）清空链表（7）销毁链表2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
四、思考与提高：1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？五、实验设计1．编写程序完成单链表的下列基本操作：（1）初始化单链表LaLinkList InitList(){int i,value,n;LinkList H=(LinkList)malloc(sizeof(LNode));LinkList P=H;P->next=NULL;do{printf("请输入链表的长度:");scanf("%d",&n);if(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;}（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;else{while(x++<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;else{while(x++<i-2)q=q->next;de=q->next;if(de->next==NULL)q->next=NULL;elseq->next=de->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("该结点在链表中的位置为第%d个\n",i); return OK;}q=q->next;}printf("该链表中没有该结点！\n");return ERROR;}（5）打印输出La中的结点元素值Status 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(LinkList 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("请输入要删除的结点的位置:");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("退出成功！");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->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->next;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=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;}else{a->next=L;L=L->next;}}else{if(n2==0){b=Lb=L;L=L->next;}else{b->next=L;L=L->next;}}}a->next=NULL;b->next=NULL;return OK;}六、实验测试1．编写程序完成单链表的下列基本操作：七、总结附录1：源代码#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct LNode{ElemType data;struct LNode *next;} LNode,*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;do{printf("请输入链表的长度:");scanf("%d",&n);if(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;}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;}else{while(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(i==1)h=h->next;else{while(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("该结点在链表中的位置为第%d个\n",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("4.输出链表\n");printf("5.清空链表\n");printf("6.销毁链表\n");printf("7.退出\n");printf("请输入要使用的功能:");}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("请输入要删除的结点的位置:");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("退出成功！"); return 0;}。