实验二-单链表基本操作

实验二单链表基本操作一实验目的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中的结点元素值。#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0typedefintStatus;typedefintElemType;//定义存储结构typedefstructLnode{intdata;/*每个元素数据信息*/structLnode*next;/*存放后继元素的地址*/}LNode,*LinkList;intmain(){voidCreate_L(LinkList&L,intn);voidPrint_L(LinkListL);StatusListInsert_L(LinkList&L,inti,ElemTypee);StatusListDelete_L(LinkList&L,inti,ElemType&e);StatusFind_L(LinkListL,inte);LinkListLa;//创建单链表Laintn;printf(请输入链表La中的元素个数:\n);scanf(%d,&n);Create_L(La,n);//初始化单链表printf(现在La中的元素为:\n);Print_L(La);printf(-------------------------------------\n\n);printf(现在准备插入元素，请输入插入位置及所插入元素的值\n);inti,e;scanf(%d%d,&i,&e);ListInsert_L(La,i,e);printf(插入后La中的元素为:\n);Print_L(La);printf(-------------------------------------\n\n);printf(现在准备删除元素，请输入删除位置\n);scanf(%d,&i);ListDelete_L(La,i,e);printf(删除后La中的元素为:\n);Print_L(La);printf(-------------------------------------\n\n);printf(请输入所要查找元素的值:\n);scanf(%d,&e);Find_L(La,e);printf(所要查找元素的位置为:%d\n,Find_L(La,e));}voidCreate_L(LinkList&L,intn){intj=1;L=(LinkList)malloc(sizeof(Lnode));L-next=NULL;//先建立一个带头结点的单链线性表Lfor(inti=n;i0;--i){LinkListp=(LinkList)malloc(sizeof(Lnode));printf(请输入链表La中的第%d个元素:\n,j++);scanf(%d,&p-data);p-next=L-next;L-next=p;}//(逆序实现)/*LinkListq=L;for(inti=1;i=n;i++){LinkListp=(LinkList)malloc(sizeof(Lnode));q-next=p;p-next=NULL;q=q-next;printf(请输入链表La中的第%d个元素:\n,i);scanf(%d,&p-data);}//(正序实现)*/}//初始化单链表//输出单链表voidPrint_L(LinkListL){LinkListp;p=L-next;while(p){printf(%d,p-data);p=p-next;}printf(\n);}//在单链表L的第i个位置前插入元素eStatusListInsert_L(LinkList&L,inti,ElemTypee){LinkListp=L;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;LinkLists=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}//ListInsert_L//删除单链表L中第i个位置上的元素StatusListDelete_L(LinkList&L,inti,ElemType&e){LinkListp=L;intj=0;while(p-next&&ji-1){p=p-next;++j;}if(!p-next||ji-1)returnERROR;LinkListq=p-next;p-next=q-next;e=q-data;free(q);returnOK;}//LinkDelete_L/*查找元素并返回位置*/StatusFind_L(LinkListL,inte){LinkListp=L-next;intj=1;while(p-data!=e&&p-next){p=p-next;j++;}if(p-data==e)returnj;else{printf(无当前元素\n);returnERROR;}if(!p){printf(无当前元素\n);returnERROR;}}//定位2.构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0typedefintStatus;typedefintElemType;//定义存储结构typedefstructLnode{intdata;/*每个元素数据信息*/structLnode*next;/*存放后继元素的地址*/}LNode,*LinkList;voidmain(){voidCreate_L(LinkList&L,intn);voidPrint_L(LinkListL);voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc);LinkListLa,Lb,Lc;//创建单链表La,Lb,Lcintn;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(-------------------------------------\n\n);printf(开始合并:\n);MergeList_L(La,Lb,Lc);printf(-------------------------------------\n\n);printf(合并后，Lc的元素为\n);Print_L(Lc);}voidCreate_L(LinkList&L,intn){intj=1;L=(LinkList)malloc(sizeof(Lnode));L-next=NULL;//先建立一个带头结点的单链线性表Lfor(inti=n;i0;--i){LinkListp=(LinkList)malloc(sizeof(Lnode));printf(请输入链表中的第%d个元素:\n,j++);scanf(%d,&p-data);p-next=L-next;L-next=p;}//(逆序实现)/*LinkListq=L;for(inti=1;i=n;i++){LinkListp=(LinkList)malloc(sizeof(Lnode));q-next=p;p-next=NULL;q=q-next;printf(请输入链表La中的第%d个元素:\n,i);scanf(%d,&p-data);}//(正序实现)*/}//初始化单链表//有序单链表La和Lb的归并voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){LinkListpa=La-next;LinkListpb=Lb-next;LinkListpc;Lc=pc=La;while(pa&&pb){if(pa-data=pb-data){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//输出单链表voidPrint_L(LinkListL){LinkListp;p=L-next;while(p){printf(%d,p-data);p=p-next;}printf(\n);}3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）#includestdio.h#includestdlib.h#includemalloc.h//定义存储结构typedefstructLnode{intdata;/*每个元素数据信息*/structLnode*next;/*存放后继元素的地址*/}LNode,*LinkList;voidmain(){voidCreate_L(LinkList&L,intn);voidPrint_L(LinkListL);voidReverseList(L