实验1-2顺序表和链表基本操作参考答案_第1页
实验1-2顺序表和链表基本操作参考答案_第2页
实验1-2顺序表和链表基本操作参考答案_第3页
实验1-2顺序表和链表基本操作参考答案_第4页
实验1-2顺序表和链表基本操作参考答案_第5页
已阅读5页,还剩14页未读, 继续免费阅读

下载本文档

kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

kok电子竞技:文档简介

1、实验1、2:线性表的应用参考代码一、实验预备知识1复习C中编写函数的相关内容。2复习如何用主函数将多个函数连在一起构成一个C完整程序。二、实验目的1掌握线性表的顺序和链式存储结构2熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算3熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算三、实验要求1编写初始化并创建线性表和输出线性表的算法。2编写对线性表插入和删除运算算法,要判断位置的合法性和溢出问题。3编写有序表的插入和删除运算算法。4编写一个主函数,将上面函数连在一起,构成一个完整的程序。5将实验源程序调试并运行,写出输入、输出结果,并对结果进行分析。四、实验内容顺序表

2、实验内容: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、)。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

4、;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);/顺序表

5、的按值查找算法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根据所做操作选择以

6、下数字序号:"<<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&

7、lt;<"请输入插入位置:" 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<<"发生溢出!"<<

8、;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);

9、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<<"

10、排序操作完成!"<<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);

11、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:"<<

12、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+)c

13、out<<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)/顺

14、序表的插入算法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.dat

15、aj-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 i+1;elsereturn 0;void Sort_SeqList(SeqList &L) /排序算法int i,k,j;DataType temp;for(i=0;i<L.length-1;i+)k=i;for(j=i+1;j<=L.length -1;j

16、+)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;int Insert_SeqList_sort(SeqList &L,DataType x)/有序表的插入算法if(MAXSIZE<=L.length)return -1;int i=0;while(i<L.length&&L.datai<x)i+;for(int j=L.length-1;j>=i;j-)L.dataj+1=L.dataj;L.datai=x;L.lengt

17、h+;return 1;void Merge(SeqList LA,SeqList LB,SeqList &LC)/两个有序顺序表的合并算法int i,j,k;i=j=k=0;while(i<LA.length&&j<LB.length)if(LA.datai<LB.dataj)LC.datak=LA.datai;i+;k+;elseLC.datak=LB.dataj;j+;k+;while(i<LA.length)LC.datak=LA.datai;i+;k+;while(j<LB.length)LC.datak=LB.dataj;j+;

18、k+;LC.length=k;输入输出结果:图1-1主菜单图1-2顺序表的创建和输出操作图1-3 顺序表的插入操作图1-4顺序表的删除操作图1-5顺序表的排序操作图1-6有序表的插入操作图1-7两个有序表的合并操作单链表的源程序:#include "iostream"using namespace std;typedef int DataType;typedef struct nodeDataType data;struct node *next;LNode,*LinkList;void Init_LinkList(LinkList &L);/创建空单链表void

19、Create1LinkList(LinkList &L,int n);/前插入法创建单链表的算法void Create2LinkList(LinkList &L,int n);/后插入法创建单链表的算法void PrintLinkList(LinkList L);/单链表的输出算法int InsertLinkList(LinkList &L,int i,DataType x);/单链表的插入算法int DeleteLinkList(LinkList &L,int i);/单链表的删除算法void Select_Sort_LinkList(LinkList &am

20、p;L);/链表的排序算法(选择排序)void Insert2(LinkList L,DataType x);/有序表的插入void Merge(LinkList L1,LinkList L2,LinkList &L3);/两个有序表的合并算法void menu();/菜单函数int main()menu(); return 0;void Init_LinkList(LinkList &L)/创建空单链表L=new LNode;L->next=NULL;void Create1LinkList(LinkList &L,int n)/前插入法创建单链表的算法LNod

21、e *s;for(int i=1;i<=n;i+)s=new LNode;cout<<"请输入第"<<i<<"个元素的值:"cin>>s->data;s->next=L->next;L->next=s;void Create2LinkList(LinkList &L,int n)/后插入法创建单链表的算法LNode *s,*r=L;for(int i=1;i<=n;i+)s=new LNode;cout<<"请输入第"<<

22、;i<<"个元素的值:"cin>>s->data;r->next=s;r=s;r->next=NULL;void PrintLinkList(LinkList L)/单链表的输出算法if(L->next=NULL)cout<<"空表!"<<endl;return;cout<<"当前单链表为:"<<endl;LNode *p=L->next;while(p)cout<<p->data<<" &qu

23、ot;p=p->next;cout<<endl;int InsertLinkList(LinkList &L,int i,DataType x)/单链表的插入算法int j=0;LNode *p=L,*s;while(p&&j<i-1)p=p->next;j+;if(!p|j>i-1)return 0;s=new LNode;s->data=x;s->next =p->next ;p->next =s;return 1;int DeleteLinkList(LinkList &L,int i)/单链表的

24、删除算法if(L->next =NULL)return -1;int j=0;LNode *p=L,*q;while(p->next !=NULL)&&(j<i-1)p=p->next ;j+;if(p->next=NULL)|(j>i-1)return 0;q=p->next ;p->next =q->next ;delete q;return 1;void Select_Sort_LinkList(LinkList &L)/链表的排序算法(选择排序)if(L->next =NULL)cout<<

25、"空表,不需要排序!"<<endl;return;LNode *p,*q,*s;DataType temp;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<<"

26、排序成功!"<<endl;void Insert2(LinkList L,DataType x)/有序表的插入LNode *p=L,*s;while(p->next!=NULL&&p->next->data<x)p=p->next;s=new LNode;s->data=x;s->next=p->next;p->next=s;cout<<"插入操作成功!"<<endl;void Merge(LinkList L1,LinkList L2,LinkList &a

27、mp;L3)/两个有序表的合并算法LNode *p1,*p2,*p3,*s;p1=L1->next ;p2=L2->next ;L3=p3=new LNode;L3->next =NULL;while(p1&&p2)s=new LNode;if(p1->data <p2->data )s->data =p1->data ;p1=p1->next ;elses->data =p2->data ;p2=p2->next ;p3->next =s;p3=s;if(p1)p3->next =p1;if(

28、p2)p3->next =p2;void menu()/菜单函数LinkList L;Init_LinkList(L);int m;while(1)cout<<"n根据所做操作选择以下数字序号:"<<endl; cout<<"1:前插入创建单链表 2:尾插入创建单链表 3:执行插入操作"<<endl;cout<<"4:执行删除操作 5:执行输出操作 6:执行排序操作"<<endl;cout<<"7:执行有序表的插入操作 8:执行有序表的

29、合并操作 0:退出"<<endl;int n,i,x;cin>>n;switch (n)case 1: cout<<"请输入结点个数:"cin>>i; Create1LinkList(L,i); PrintLinkList(L);break;case 2: cout<<"请输入结点个数:"cin>>i; Create2LinkList(L,i); PrintLinkList(L);break; case 3: cout<<"请输入插入位置:"

30、cin>>i;cout<<endl<<"请输入插入元素值:"cin>>x;cout<<endl; if (InsertLinkList(L,i,x)=1)cout<<"插入操作成功!"<<endl;else cout<<"插入位置不合法!"<<endl;break; case 4: cout<<"请输入删除位置:"cin>>i;cout<<endl;m=DeleteLink

31、List(L,i); if (m=1)cout<<"删除操作成功!"<<endl;elseif(m=-1)cout<<"空表!"<<endl;elsecout<<"删除位置不合法!"<<endl;break; case 5: PrintLinkList(L);break; case 6: Select_Sort_LinkList(L);break; case 7:cout<<endl<<"请输入插入元素值:"cin>

32、;>x;cout<<endl; Insert2(L,x);break;case 8: LinkList L1,L2,L3; Init_LinkList(L1);Init_LinkList(L2);Init_LinkList(L3);cout<<"创建有序表1:"<<endl;cout<<"请输入结点个数:"cin>>i; Create2LinkList(L1,i);Select_Sort_LinkList(L1);cout<<"创建有序表2:"<<

33、;endl;cout<<"请输入结点个数:"cin>>i; Create2LinkList(L2,i);Select_Sort_LinkList(L2); cout<<"有序表1:"<<endl;PrintLinkList(L1); cout<<"有序表2:"<<endl; PrintLinkList(L2); Merge(L1,L2,L3);cout<<"合并后:"<<endl;PrintLinkList(L3);break; case 0:return;输入输出结果:图2-1主菜单图2-2创建单链表(用头插入法)图2-3创建单链表(用尾插入法)图2-4单链表的插入操作图2-5单链表的插入操作(插入位置不合法情况)图2-6单链表的删除操作图2-7单链表的删除操作(删除位置不合法情况)图2-8单链表的排序操作图2-9有序表的插入操作图2-10两个有序表的合并操作建议:代码较长,为了方便阅读和调试,可写成多文件结构!第19页

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论