数据结构

实验一单链表一、实验目的1、掌握用Vc++上机调试程序的基本方法；2、掌握单链表的建立、插入、删除以及相关操作。二、实验内容1、单链表的插入算法；2、单链表的删除算法；3、两个有序单链表合并成一个有序单链表的算法。三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、实验准备1、复习C语言中指针的用法，特别是结构体的指针的用法；2、了解单链表的概念，单链表的定义方法；3、掌握线性表在链式存储结构上实现基本操作：查找、插入、删除的算法；在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要注意以下内容：在实现查找的时候，首先要判断该单链表是否为空，其次要判断查找后的结果(查到时输出查到的数据，未查到时给出错误提示)。在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，其次要注意插入的时候语句的顺序不可颠倒，否则出错。在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。五、实验步骤1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素(1)通过键盘读取元素建立单链表；(2)指定一个位置，在此位置之前插入一个新元素；(3)指定一个位置，删除此位置元素。2、两个有序单链表合并成一个有序单链表的算法。(1)通过键盘读取元素建立2个有序单链表；(2)将二两个有序单链表合并成一个有序单链表；(3)输出合并后的单链表。六、实验参考代码1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素#includestdio.h#includestdlib.h#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;以下是建立单链表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head-next=NULL;printf(Pleaseinputlengthtocreatalist:\n);scanf(%d,&n);printf(Pleaseinputagroupofvaluesofthelist:\n);for(i=1;i=n;i++){p=(Lnode*)malloc(sizeof(Lnode));scanf(%d,&p-data);p-next=NULL;tail-next=p;tail=p;}printf(Alisthasbeencreatedsuccessfully!\n);}//以下是输出单链表voidOutputList_L(LinkListL){LinkListp=L-next;if(p==NULL){printf(\nNolist\n);return;}printf(Thelistis:\n);while(p){printf(%4d,p-data);p=p-next;}printf(\n);}//在第i个元素之前插入一个元素StatusListInsert_L(LinkListL,inti,ElemTypee){LinkListp,s;p=L;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s-data=e;s-next=p-next;p-next=s;returnOK;}StatusListDelete_L(LinkListL,inti,ElemType&e){LinkListp,q;intj=0;p=L;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;}voidmain(){LinkListL;intchoice,i;ElemTypee;choice=1;printf(Weshouldcreatealistfirst!);CreatList_L(L);OutputList_L(L);while(choice!=0){printf(\nmenu\n);printf(1insertaelem);printf(2deleteaelem);printf(3outputalist);printf(4exit);printf(\n------------------------------------------------------------------------------\n);printf(pleasechoice(1,2,3,4));scanf(%d,&choice);if(choice==0)break;elseif(choice==1){printf(Pleaseinputaposandavaluewhatyouwanttoinsert:\n);scanf(%d%d,&i,&e);if(ListInsert_L(L,i,e)){printf(Theinsertingactionhasbeendone!\n);OutputList_L(L);}elseprintf(Theinsertingposiserror!pleasedoagain!\n);}elseif(choice==2){printf(Pleaseinputaposwhatyouwanttodelete:\n);scanf(%d,&i);if(ListDelete_L(L,i,e)){printf(Thedeletingactionhasbeendone,thedeletedvalueis%d\n,e);OutputList_L(L);}elseprintf(Theposwhatyouwanttodeleteiserror!pleasedoagain!\n);}elseif(choice==3){OutputList_L(L);}elseif(choice!=0)printf(choiceerror\n);}}2、两个有序单链表合并成一个有序单链表的算法。实现提示：程序需要3个指针：pa,pb,pc，其中pa，pb分别指向La表、Lb表的首结点，用pa遍历La表，pb遍历Lb表，pc指向合并后的新表的最后一个结点（即尾结点），pc的初值指向La表的头结点。合并的思想是：先建立好两个链表La表和Lb表，然后依次扫描La和Lb中的元素，比较当前元素的值，将较小者链到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链到pc所指的结点之后。六、实验参考代码#includestdio.h#includestdlib.htypedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//以下是建立单链表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head-next=NULL;printf(Pleaseinputlengthtocreatalist\n);scanf(%d,&n);printf(Pleaseinputagroupofvaluesofthelist\n);for(i=1;i=n;i++){p=(Lnode*)malloc(sizeof(Lnode));scanf(%d,&p-data);p-next=NULL;tail-next=p;tail=p;}printf(Alisthasbeencreatedsuccessfully!\n);}//以下是输出单链表voidOutputList_L(LinkListL){LinkListp=L-next;if(p==NULL){printf(\nNolist\n);return;}printf(Thelistis:\n);while(p){printf(%4d,p-data);p=p-next;}printf(\n);}//以下将La和Lb表合并为Lc表voidMergeList(LinkList&Lc,LinkList&La,LinkList&Lb){LinkListpa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&&pb){if(pa-datapb-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);}//以下是主程序voidmain(){LinkListLa,Lb,Lc;printf(Weshouldcreatetwoincrementalandorderlylistsfirst!\n);printf(pleasecreataincrementalandorderlylistA:\n);CreatList_L(La);OutputList_L(La);printf(pleasecreataincrementalandorderlylistB:\n);CreatList_L(Lb);OutputList_L(Lb);MergeList(Lc,La,Lb);printf(Themergeingactionhasbeendone!\n);OutputList_L(Lc);}