实验1-2顺序表和链表基本操作-参考答案讲解

第1页实验1、2：线性表的应用参考代码一、实验预备知识1．复习C中编写函数的相关内容。2．复习如何用主函数将多个函数连在一起构成一个C完整程序。二、实验目的1．掌握线性表的顺序和链式存储结构2．熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算3．熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算三、实验要求1．编写初始化并创建线性表和输出线性表的算法。2．编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。3．编写有序表的插入和删除运算算法。4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。5．将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。四、实验内容顺序表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。2．初始化并建立顺序表。（开辟的存储空间大小为8）3．编写顺序表输出算法。4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次顺序表。5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次顺序表。6．编写一个排序算法，对线性表中元素从小到大排列。7．向有序表分别插入20和50，插入后表仍然有序。（修改开辟的存储空间大小为15）单链表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。2．建立一个带表头结点的单链表（前插入法和尾插入法均可）。3．编写单链表输出算法。4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次单链表。5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次单链表。6．编写一个排序算法，对链表中元素从小到大排列。7．向有序链表分别插入20和50，插入后表仍然有序。五、实验结果顺序表源程序：#includeiostreamusingnamespacestd;constintMAXSIZE=8;//做有序表插入操作时，将8改为15typedefintDataType;第2页typedefstruct{DataTypedata[MAXSIZE];intlength;}SeqList;voidInit_SeqList(SeqList&L);//创建空顺序表算法voidShow_SeqList(SeqListL);//顺序表输出算法voidCreate_SeqList(SeqList&L);//顺序表创建算法intInsert_SeqList(SeqList&L,DataTypex,inti);//顺序表的插入算法intDelete_SeqList(SeqList&L,inti);//顺序表的删除算法intLocate_SeqList(SeqListL,DataTypex);//顺序表的按值查找算法voidSort_SeqList(SeqList&L);//顺序表的排序算法intInsert_SeqList_sort(SeqList&L,DataTypex);//有序表的插入算法voidMerge(SeqListLA,SeqListLB,SeqList&LC);//两个有序顺序表的合并算法voidmenu();//菜单算法voidmain(){menu();}voidmenu()//菜单算法{SeqListL;Init_SeqList(L);intm;while(1){cout\n根据所做操作选择以下数字序号：endl;cout1:创建顺序表2:执行插入操作3:执行删除操作endl;cout4:执行输出操作5:执行查找操作6:执行排序操作endl;cout7:执行有序表的插入操作8:执行有序表的合并操作0:退出endl;intn,i,x;cinn;switch(n){case1:{Create_SeqList(L);break;}case2:{cout请输入插入位置：;cini;第3页coutendl请输入插入元素值：;cinx;coutendl;m=Insert_SeqList(L,x,i);if(m==1)cout插入操作成功！endl;elseif(m==0)cout插入位置不合法！endl;elsecout发生溢出！endl;break;}case3:{cout请输入删除位置：;cini;coutendl;m=Delete_SeqList(L,i);if(m==1)cout删除操作成功！endl;elseif(m==0)cout删除位置不合法！endl;elsecout空表！endl;break;}case4:{Show_SeqList(L);break;}case5:{cout请输入所要查找的元素值：;cinx;coutendl;m=Locate_SeqList(L,x);if(m==0)cout所查找元素不在顺序表中！endl;elsecout所查找元素是顺序表的第m个元素！endl;break;第4页}case6:{Sort_SeqList(L);cout排序操作完成！endl;break;}case7:{coutendl请输入插入元素值：;cinx;coutendl;m=Insert_SeqList_sort(L,x);if(m==1)cout插入操作成功！endl;elsecout发生溢出！endl;break;}case8:{SeqListL1,L2,L3;Init_SeqList(L1);Init_SeqList(L2);Init_SeqList(L3);cout创建有序表1：endl;Create_SeqList(L1);Sort_SeqList(L1);cout创建有序表2：endl;Create_SeqList(L2);Sort_SeqList(L2);cout有序表1：endl;Show_SeqList(L1);cout有序表2：endl;Show_SeqList(L2);Merge(L1,L2,L3);cout合并后：endl;Show_SeqList(L3);break;}case0:return;}}第5页}voidInit_SeqList(SeqList&L)//创建空顺序表算法{L.length=0;}voidShow_SeqList(SeqListL)//顺序表输出算法{if(L.length==0)cout空表！endl;elsefor(inti=0;iL.length;i++)coutL.data[i];coutendl;}voidCreate_SeqList(SeqList&L)//顺序表创建算法{cout请输入元素个数:;cinL.length;cout依次输入各个元素的值:endl;for(inti=0;iL.length;i++)cinL.data[i];}intInsert_SeqList(SeqList&L,DataTypex,inti)//顺序表的插入算法{if(MAXSIZE=L.length)return-1;if(i1||iL.length+1)return0;for(intj=L.length-1;j=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length++;return1;}intDelete_SeqList(SeqList&L,inti)//顺序表的删除算法{if(L.length==0)return-1;if(i1||iL.length)return0;for(intj=i;jL.length;j++)L.data[j-1]=L.data[j];L.length--;return1;第6页}intLocate_SeqList(SeqListL,DataTypex)//顺序表的按值查找算法{inti=0;while(iL.length&&L.data[i]!=x)i++;if(iL.length)returni+1;elsereturn0;}voidSort_SeqList(SeqList&L)//排序算法{inti,k,j;DataTypetemp;for(i=0;iL.length-1;i++){k=i;for(j=i+1;j=L.length-1;j++)if(L.data[j]L.data[k])k=j;if(i!=k){temp=L.data[i];L.data[i]=L.data[k];L.data[k]=temp;}}}intInsert_SeqList_sort(SeqList&L,DataTypex)//有序表的插入算法{if(MAXSIZE=L.length)return-1;inti=0;while(iL.length&&L.data[i]x)i++;for(intj=L.length-1;j=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.length++;return1;}voidMerge(SeqListLA,SeqListLB,SeqList&LC)//两个有序顺序表的合并算法{第7页inti,j,k;i=j=k=0;while(iLA.length&&jLB.length){if(LA.data[i]LB.data[j]){LC.data[k]=LA.data[i];i++;k++;}else{LC.data[k]=LB.data[j];j++;k++;}}while(iLA.length){LC.data[k]=LA.data[i];i++;k++;}while(jLB.length){LC.data[k]=LB.data[j];j++;k++;}LC.length=k;}输入输出结果：图1-1主菜单第8页图1-2顺序表的创建和输出操作图1-3顺序表的插入操作图1-4顺序表的删除操作第9页图1-5顺序表的排序操作图1-6有序表的插入操作图1-7两个有序表的合并操作单链表的源程序：第10页#includeiostreamusingnamespacestd;typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LNode,*LinkList;voidInit_LinkList(LinkList&L);//创建空单链表voidCreate1LinkList(LinkList&L,intn);//前插入法创建单链表的算法voidCreate2LinkList(LinkList&L,intn);//后插入法创建单链表的算法voidPrintLinkList(LinkListL);//单链表的输出算法intInsertLinkList(LinkList&L,inti,DataTypex);//单链表的插入算法intDeleteLinkList(LinkList&L,inti);//单链表的删除算法voidSelect_Sort_LinkList(LinkList&L);//链表的排序算法（选择排序）voidInsert2(LinkListL,DataTypex);//有序表的插入voidMerge(LinkListL1,LinkListL2,LinkList&L3);//两个有序表的合并算法voidmenu();//菜单函数intmain(){menu();return0;}voidInit_LinkList(LinkList&L)//创建空单链表{L=newLNode;L-next=NULL;}voidCreate1LinkList(LinkList&L,intn)//前插入