实验1-2顺序表和链表基本操作_参考答案
实验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>using namespace std;const int MAXSIZE=8; /做有序表插入操作时,将8改为15typedef int DataType;typedef structDataType dataMAXSIZE;int length;SeqList;void Init_SeqList(SeqList &L);/创建空顺序表算法void Show_SeqList(SeqList L);/顺序表输出算法void Create_SeqList(SeqList &L);/顺序表创建算法int Insert_SeqList(SeqList &L,DataType x,int i);/顺序表的插入算法int Delete_SeqList(SeqList &L,int i);/顺序表的删除算法int Locate_SeqList(SeqList L,DataType x);/顺序表的按值查找算法void Sort_SeqList(SeqList &L);/顺序表的排序算法int Insert_SeqList_sort(SeqList &L,DataType x);/有序表的插入算法void Merge(SeqList LA,SeqList LB,SeqList &LC);/两个有序顺序表的合并算法void menu(); /菜单算法void main() menu(); void menu()/菜单算法 SeqList L; Init_SeqList(L); int m; while(1) cout<<"n根据所做操作选择以下数字序号:"<<endl;cout<<"1:创建顺序表 2:执行插入操作 3:执行删除操作"<<endl;cout<<"4:执行输出操作 5:执行查找操作 6:执行排序操作"<<endl;cout<<"7:执行有序表的插入操作 8:执行有序表的合并操作 0:退出"<<endl; int n,i,x; cin>>n; switch (n) case 1: Create_SeqList(L); break;case 2: 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; case 3: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;case 4: Show_SeqList(L); break;case 5:cout<<"请输入所要查找的元素值:" cin>>x; cout<<endl; m=Locate_SeqList(L,x); if (m=0) cout<<"所查找元素不在顺序表中!"<<endl; else cout<<"所查找元素是顺序表的第"<<m<<"个元素!"<<endl; break;case 6: Sort_SeqList(L); cout<<"排序操作完成!"<<endl; break;case 7: cout<<endl<<"请输入插入元素值:" cin>>x; cout<<endl; m=Insert_SeqList_sort(L,x); if (m=1) cout<<"插入操作成功!"<<endl; else cout<<"发生溢出!"<<endl; break; case 8: SeqList L1,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; case 0: return;void Init_SeqList(SeqList &L)/创建空顺序表算法L.length=0;void Show_SeqList(SeqList L)/顺序表输出算法if(L.length=0)cout<<"空表!"<<endl;elsefor(int i=0;i<L.length;i+)cout<<L.datai<<" "cout<<endl;void Create_SeqList(SeqList &L)/顺序表创建算法cout<<"请输入元素个数:"cin>>L.length;cout<<"依次输入各个元素的值:"<<endl;for(int i=0;i<L.length;i+)cin>>L.datai;int Insert_SeqList(SeqList &L,DataType x,int i)/顺序表的插入算法if(MAXSIZE<=L.length)return -1;if(i<1|i>L.length+1)return 0;for(int j=L.length-1;j>=i-1;j-)L.dataj+1=L.dataj;L.datai-1=x;L.length+;return 1;int Delete_SeqList(SeqList &L,int i)/顺序表的删除算法if(L.length =0)return -1;if(i<1|i>L.length)return 0;for(int j=i;j<L.length;j+)L.dataj-1=L.dataj;L.length-;return 1;int Locate_SeqList(SeqList L,DataType x)/顺序表的按值查找算法int i=0;while(i<L.length&&L.datai!=x) i+;if(i<L.length )return