實驗1-2順序表和鏈表基本操作參考答案

1、實驗1、2：線性表的應用參考代碼一、實驗預備知識1復習C中編寫函數(shù)的相關內容。2復習如何用主函數(shù)將多個函數(shù)連在一起構成一個C完整程序。二、實驗目的1掌握線性表的順序和鏈式存儲結構2熟練運用線性表在順序存儲方式下的初始化、創(chuàng)建、輸出、插入和刪除運算3熟練運用線性表在鏈式存儲方式下的創(chuàng)建、輸出、插入和刪除運算三、實驗要求1編寫初始化并創(chuàng)建線性表和輸出線性表的算法。2編寫對線性表插入和刪除運算算法，要判斷位置的合法性和溢出問題。3編寫有序表的插入和刪除運算算法。4編寫一個主函數(shù)，將上面函數(shù)連在一起，構成一個完整的程序。5將實驗源程序調試并運行，寫出輸入、輸出結果，并對結果進行分析。四、實驗內容順序表

2、實驗內容：1給定的線性表為L=（12，25，7，42，19，38），元素由鍵盤輸入。2初始化并建立順序表。（開辟的存儲空間大小為8）3編寫順序表輸出算法。4依次插入3、21、15、99四個數(shù)，分別插入在第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四個數(shù)，分別插入在第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);/創(chuàng)建空順序表算法void Show_SeqList(SeqList L);/順序表輸出算法void Create_SeqList(SeqList &L);/順序表創(chuàng)建算法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根據(jù)所做操作選擇以

6、下數(shù)字序號："<<endl;cout<<"1:創(chuàng)建順序表 2:執(zhí)行插入操作 3:執(zhí)行刪除操作"<<endl;cout<<"4:執(zhí)行輸出操作 5:執(zhí)行查找操作 6:執(zhí)行排序操作"<<endl;cout<<"7:執(zhí)行有序表的插入操作 8:執(zhí)行有序表的合并操作 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<<"發(fā)生溢出！"<<

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<<"發(fā)生溢出！"<<endl; break; case 8: SeqList L1,L2,L3; Init_SeqList(L1);

11、Init_SeqList(L2); Init_SeqList(L3); cout<<"創(chuàng)建有序表1："<<endl; Create_SeqList(L1); Sort_SeqList(L1); cout<<"創(chuàng)建有序表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)/創(chuàng)建空順序表算法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)/順序表創(chuàng)建算法cout<<"請輸入元素個數(shù):"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順序表的創(chuàng)建和輸出操作圖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);/創(chuàng)建空單鏈表void

19、Create1LinkList(LinkList &L,int n);/前插入法創(chuàng)建單鏈表的算法void Create2LinkList(LinkList &L,int n);/后插入法創(chuàng)建單鏈表的算法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();/菜單函數(shù)int main()menu(); return 0;void Init_LinkList(LinkList &L)/創(chuàng)建空單鏈表L=new LNode;L->next=NULL;void Create1LinkList(LinkList &L,int n)/前插入法創(chuàng)建單鏈表的算法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)/后插入法創(chuàng)建單鏈表的算法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()/菜單函數(shù)LinkList L;Init_LinkList(L);int m;while(1)cout<<"n根據(jù)所做操作選擇以下數(shù)字序號："<<endl; cout<<"1:前插入創(chuàng)建單鏈表 2:尾插入創(chuàng)建單鏈表 3:執(zhí)行插入操作"<<endl;cout<<"4:執(zhí)行刪除操作 5:執(zhí)行輸出操作 6:執(zhí)行排序操作"<<endl;cout<<"7:執(zhí)行有序表的插入操作 8:執(zhí)行有序表的

29、合并操作 0:退出"<<endl;int n,i,x;cin>>n;switch (n)case 1: cout<<"請輸入結點個數(shù)："cin>>i; Create1LinkList(L,i); PrintLinkList(L);break;case 2: cout<<"請輸入結點個數(shù)："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=DeleteLinkList(L,i); if (m=1)cout<<"刪除操作成功！"<<endl;elseif(m=-1)cout<<"空表