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

实验1-2顺序表和链表基本操作_参考答案实验1-2顺序表和链表基本操作_参考答案实验1-2顺序表和链表基本操作_参考答案xxx公司实验1-2顺序表和链表基本操作_参考答案文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度实验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，插入后表仍然有序。五、实验结果顺序表源程序：#include<iostream>usingnamespacestd;constintMAXSIZE=8;//做有序表插入操作时，将8改为15typedefintDataType;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;cout<<"1:创建顺序表2:执行插入操作3:执行删除操作"<<endl; cout<<"4:执行输出操作5:执行查找操作6:执行排序操作"<<endl; cout<<"7:执行有序表的插入操作8:执行有序表的合并操作0:退出"<<endl; intn,i,x; cin>>n; switch(n) { case1: {Create_SeqList(L); break; } case2: {cout<<"请输入插入位置："; cin>>i; cout<<endl<<"请输入插入元素值："; cin>>x; cout<<endl;m=Insert_SeqList(L,x,i);if(m==1) cout<<"插入操作成功！"<<endl; else if(m==0) cout<<"插入位置不合法！"<<endl; else cout<<"发生溢出！"<<endl; break; } case3: { cout<<"请输入删除位置："; cin>>i; cout<<endl;m=Delete_SeqList(L,i);if(m==1) cout<<"删除操作成功！"<<endl; else if(m==0) cout<<"删除位置不合法！"<<endl; else cout<<"空表！"<<endl; break; } case4: { Show_SeqList(L); break; } case5: { cout<<"请输入所要查找的元素值："; cin>>x; cout<<endl;m=Locate_SeqList(L,x);if(m==0) cout<<"所查找元素不在顺序表中！"<<endl; else cout<<"所查找元素是顺序表的第"<<m<<"个元素！"<<endl; break; } case6: { Sort_SeqList(L); cout<<"排序操作完成！"<<endl; break; } case7: { cout<<endl<<"请输入插入元素值："; cin>>x; cout<<endl;m=Insert_SeqList_sort(L,x);if(m==1) cout<<"插入操作成功！"<<endl; else cout<<"发生溢出！"<<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; } }}voidInit_SeqList(SeqList&L)//创建空顺序表算法{ =0;}voidShow_SeqList(SeqListL)//顺序表输出算法{ if==0) cout<<"空表！"<<endl; else for(inti=0;i<;i++) cout<<[i]<<""; cout<<endl;}voidCreate_SeqList(SeqList&L)//顺序表创建算法{ cout<<"请输入元素个数:"; cin>>; cout<<"依次输入各个元素的值:"<<endl; for(inti=0;i<;i++) cin>>[i];}intInsert_SeqList(SeqList&L,DataTypex,inti)//顺序表的插入算法{ if(MAXSIZE<= return-1; if(i<1||i>+1) return0; for(intj=;j>=i-1;j--) [j+1]=[j]; [i-1]=x; ++; return1;}intDelete_SeqList(SeqList&L,inti)//顺序表的删除算法{ if==0) return-1; if(i<1||i> return0; for(intj=i;j<;j++) [j-1]=[j]; ; return1;}intLocate_SeqList(SeqListL,DataTypex)//顺序表的按值查找算法{ inti=0; while(i<&&[i]!=x) i++; if(i<) returni+1; else return0;}voidSort_SeqList(SeqList&L)//排序算法{ inti,k,j; DataTypetemp; for(i=0;i<;i++) { k=i; for(j=i+1;j<=-1;j++) if[j]<[k]) k=j; if(i!=k) { temp=[i]; [i]=[k]; [k]=temp; } }}intInsert_SeqList_sort(SeqList&L,DataTypex)//有序表的插入算法{ if(MAXSIZE<= return-1; inti=0; while(i<&&[i]<x) i++; for(intj=;j>=i;j--) [j+1]=[j]; [i]=x; ++; return1;}voidMerge(SeqListLA,SeqListLB,SeqList&LC)//两个有序顺序表的合并算法{ inti,j,k; i=j=k=0; while(i<&&j< { if[i]<[j]) { [k]=[i]; i++; k++; } else { [k]=[j]; j++; k++; } } while(i< { [k]=[i]; i++; k++; } while(j< { [k]=[j]; j++; k++; } =k;}输入输出结果：图1-1主菜单图1-2顺序表的创建和输出操作图1-3顺序表的插入操作图1-4顺序表的删除操作图1-5顺序表的排序操作图1-6有序表的插入操作图1-7两个有序表的合并操作单链表的源程序：#include"iostream"usingnamespacestd;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)//前插入法创建单链表的算法{ LNode*s; for(inti=1;i<=n;i++) { s=newLNode; cout<<"请输入第"<<i<<"个元素的值："; cin>>s->data; s->next=L->next; L->next=s; }}voidCreate2LinkList(LinkList&L,intn)//后插入法创建单链表的算法{ LNode*s,*r=L; for(inti=1;i<=n;i++) { s=newLNode; cout<<"请输入第"<<i<<"个元素的值："; cin>>s->data; r->next=s; r=s; } r->next=NULL;}voidPrintLinkList(LinkListL)//单链表的输出算法{ if(L->next==NULL) { cout<<"空表！"<<endl; return; } cout<<"当前单链表为："<<endl; LNode*p=L->next; while(p) { cout<<p->data<<""; p=p->next; } cout<<endl;}intInsertLinkList(LinkList&L,inti,DataTypex)//单链表的插入算法{ intj=0; LNode*p=L,*s; while(p&&j<i-1) { p=p->next; j++; } if(!p||j>i-1) return0; s=newLNode; s->data=x; s->next=p->next; p->next=s; return1;}intDeleteLinkList(LinkList&L,inti)//单链表的删除算法{ if(L->next==NULL) return-1; intj=0; LNode*p=L,*q; while((p->next!=NULL)&&(j<i-1)) { p=p->next; j++; } if((p->next==NULL)||(j>i-1)) return0; q=p->next; p->next=q->next; deleteq; return1;}voidSelect_Sort_LinkList(LinkList&L)//链表的排序算法（选择排序）{ if(L->next==NULL) { cout<<"空表，不需要排序！"<<endl; return; } LNode*p,*q,*s; DataTypetemp; if(L->next==NULL)return; for(p=L->next;p->next!=NULL;p=p->next) { s=p; for(q=p->next;q!=NULL;q=q->next) { if(q->data<s->data) s=q; } if(s!=p) { temp=s->data;s->data=p->data;p->data=temp; } } cout<<"排序成功！"<<endl;}voidInsert2(LinkListL,DataTypex)//有序表的插入{ LNode*p=L,*s; while(p->next!=NULL&&p->next->data<x) p=p->next; s=newLNode; s->data=x; s->next=p->next; p->next=s; cout<<"插入操作成功！"<<endl;}voidMerge(LinkListL1,LinkListL2,LinkList&L3)//两个有序表的合并算法{ LNode*p1,*p2,*p3,*s; p1=L1->next; p2=L2->next; L3=p3=newLNode; L3->next=NULL; while(p1&&p2) { s=newLNode; if(p1->data<p2->data) { s->data=p1->data; p1=p1->next; } else { s->data=p2->data; p2=p2->next; } p3->next=s; p3=s; } if(p1) p3->next=p1; if(p2) p3->next=p2;}voidmenu()//菜单函数{ LinkListL; Init_LinkList(L); intm; while(1) { cout<<"\n根据所做操作选择以下数字序号："<<endl;cout<<"1:前插入创建单链表2:尾插入创建单链表3:执行插入操作"<<endl; cout<<"4:执行删除操作5:执行输出操作6:执行排序操作"<<endl; cout<<"7:执行有序表的插入操作8:执行有序表的合并操作0:退出"<<endl; intn,i,x; cin>>n; switch(n) { case1: {cout<<"请输入结点个数："; cin>>i; Create1LinkList(L,i); PrintLinkList(L); break; } case2: {cout<<"请输入结点个数："; cin>>i; Create2LinkList(L,i); PrintLinkList(L); break; }case3: {cout<<"请输入插入位置："; cin>>i; cout<<endl<<"请输入插入元素值："; cin>>x; cout<<endl;if(InsertLinkList(L,i,x)==1) cout<<"插入操作成功！"<<endl; elsecout<<"插入位置不合法！"<<endl; break; }case4: {cout<<"请输入删除位置："; cin>>i; cout<<endl; m=DeleteLinkList(L,i);if(m==1) cout<<"删除操作成功！"<<endl; else if(m==-1) cout<<"空表！"<<endl; else