實(shí)驗(yàn)1-2順序表和鏈表基本操作-參考答案

1、實(shí)驗(yàn)1-2順序表和鏈表基本操作 參考答案第 2頁 實(shí)驗(yàn) 1、2：線性表的應(yīng)用參考代碼 一、實(shí)驗(yàn)預(yù)備知識(shí) 1復(fù)習(xí) C 中編寫函數(shù)的相關(guān)內(nèi)容。 2 復(fù)習(xí)如何用主函數(shù)將多個(gè)函數(shù)連在一起構(gòu)成 一個(gè) C 完整程序。 二、實(shí)驗(yàn)?zāi)康?1掌握線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2熟練運(yùn)用線性表在順序存儲(chǔ)方式下的初始化、 創(chuàng)建、輸出、插入和刪除運(yùn)算 3熟練運(yùn)用線性表在鏈?zhǔn)酱鎯?chǔ)方式下的創(chuàng)建、 輸出、插入和刪除運(yùn)算 三、實(shí)驗(yàn)要求 1編寫初始化并創(chuàng)建線性表和輸出線性表的算 法。 2編寫對(duì)線性表插入和刪除運(yùn)算算法，要判斷 位置的合法性和溢出問題。 3編寫有序表的插入和刪除運(yùn)算算法。 4編寫一個(gè)主函數(shù)，將上面函數(shù)連在一起，構(gòu) 成

2、一個(gè)完整的程序。 5將實(shí)驗(yàn)源程序調(diào)試并運(yùn)行，寫出輸入、輸出 結(jié)果，并對(duì)結(jié)果進(jìn)行分析。 第 3頁 四、實(shí)驗(yàn)內(nèi)容 順序表實(shí)驗(yàn)內(nèi)容： 1給定的線性表為 L= （12，25，7，42，19， 38），元素由鍵盤輸入。 2初始化并建立順序表。 （開辟的存儲(chǔ)空間大小 為 8） 3編寫順序表輸出算法。 4依次插入 3、 21、15、99 四個(gè)數(shù)，分別插入 在第 1、8、4 和 12 位置，每插入一次都要輸出一次 順序表。 5刪除第 1，第 9 和第 12個(gè)位置上的元素，每 刪除一個(gè)元素都要輸出一次順序表。 6編寫一個(gè)排序算法，對(duì)線性表中元素從小到 大排列。 7向有序表分別插入 20和 50，插入后表仍然有

3、序。（修改開辟的存儲(chǔ)空間大小為 15） 單鏈表實(shí)驗(yàn)內(nèi)容： 1給定的線性表為 L= （12，25，7，42，19， 38），元素由鍵盤輸入。 2建立一個(gè)帶表頭結(jié)點(diǎn)的單鏈表（前插入法和 尾插入法均可）。 3編寫單鏈表輸出算法。 第 4頁 4依次插入 3、 21、15、99 四個(gè)數(shù)，分別插入 在第 1、8、4 和 12 位置，每插入一次都要輸出一次 單鏈表。 5刪除第 1，第 9 和第 12個(gè)位置上的元素，每 刪除一個(gè)元素都要輸出一次單鏈表。 6編寫一個(gè)排序算法，對(duì)鏈表中元素從小到大 排列。 7向有序鏈表分別插入 20和 50，插入后表仍然 有序。 五、實(shí)驗(yàn)結(jié)果 順序表源程序： #include u

4、sing namespace std; const int MAXSIZE=8; /做有序表插入操作時(shí)， 將 8 改為 15 typedef int DataType; typedef struct DataType dataMAXSIZE; int length; SeqList; void Init_SeqList(SeqList &L);/ 創(chuàng)建空順序表算 法 void Show_SeqList(SeqList L);/ 順序表輸出算法 void Create_SeqList(SeqList &L);/ 順序表創(chuàng)建算 法 第 5頁 int Insert_SeqList(S

5、eqList &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 &

6、amp;LC);/ 兩個(gè)有序順序表的合并算法 void menu(); /菜單算法 void main() menu(); void menu()/ 菜單算法 SeqList L; Init_SeqList(L); int m; while(1) coutn 根據(jù)所做操作選擇以下數(shù)字序號(hào)： endl; cout1: 創(chuàng)建順序表 2: 執(zhí) 第 6頁 行插入操作 3: 執(zhí)行刪除操作 endl; cout4: 執(zhí)行輸出操作 5:執(zhí)行查 找操作 6:執(zhí)行排序操作 endl; cout7: 執(zhí)行有序表的插入操作 8:執(zhí)行有 序表的合并操作 0:退出 n; switch (n) case 1:第 7頁 C

7、reate_SeqList(L); couti; coutendlx; coutendl; m=Insert_SeqList(L,x,i); if (m=1) cout 插入操作成功！ endl; else if (m=0) cout 插 入 位 置 不 合 法 ！ else cout 發(fā)生溢出！ endl; break; break; case 2: endl; 第 8頁 case 3: couti; coutendl; m=Delete_SeqList(L,i); if (m=1) cout 刪除操作成功！ endl; else if (m=0) cout 刪 除 位 置 不 合 法 ！

8、endl; else cout 空表！ endl; break; case 4: Show_SeqList(L); break; case 5: coutx; coutendl; m=Locate_SeqList(L,x); if (m=0) 第 9頁 cout 所查找元素不在順序表中！ endl; else cout 所查找元素是順序表的第 m 個(gè)元素！ endl; break; case 6: Sort_SeqList(L); cout 排序操作完成！ endl; break; case 7: coutendlx; coutendl; m=Insert_SeqList_sort(L,x);

9、 if (m=1) cout 插入操作成功！ endl; else cout 發(fā)生溢出！ endl; break; case 8: 第 10頁 SeqList L1,L2,L3; Init_SeqList(L1); 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);

10、cout 有序表 2： endl; Show_SeqList(L2); Merge(L1,L2,L3); cout 合并后： endl; Show_SeqList(L3); break; case 0: return; void Init_SeqList(SeqList &L)/ 創(chuàng)建空順序表算 法 第 11頁 L.length=0; void Show_SeqList(SeqList L)/ 順序表輸出算法 if(L.length=0) cout 空表！ endl; else for(int i=0;iL.length;i+) coutL.datai ; coutendl; void

11、 Create_SeqList(SeqList &L)/ 順序表創(chuàng)建算 法 coutL.length; cout 依次輸入各個(gè)元素的值 :endl; for(int i=0;iL.datai; int Insert_SeqList(SeqList &L,DataType x,int i)/ 順序表的插入算法 if(MAXSIZE flsw吐楚 /(一crlod-snb s)4snb S0)00C一 宀 H una) 匸+LI46U 一_| xLep_J 32ep_JL+=2ep1 (丄vHd L 丄o)UQ_i也壬)04 ouna) (L+IU6U - KCOL 吐窘二(X e

12、dAlcgecrl Isnbesxsnbesleool -u 一 =una) !6UQ_J 32令亍?=2令1 (+6u1vrH=UD04 ouna) 6U1A=VW Vuna) SHH 6U1)七 第 14頁 表的按值查找算法 int i=0; while(iL.length&L.datai!=x) i+; if(iL.length ) return i+1; else return 0; void Sort_SeqList(SeqList &L) / 排序算法 int i,k,j; DataType temp; for(i=0;iL.length-1;i+) k=i; fo

13、r(j=i+1;j=L.length -1;j+) if(L.data jL.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(iL.length&L.datai=i;j-) 第 15頁 L.dataj+1=L.dataj; L.datai=x; L.length+; return

14、1; void Merge(SeqList LA,SeqList LB,SeqList &LC)/ 兩個(gè)有序順序表的合并算法 +M 匸+一 二二 Jsepvl蘭Jsepol sJSepmlv 三 2ep1)七 (IU6U 一mlv 遠(yuǎn)Oe$6uv-I K9L 匸+ 一 xgep.vl蘭epl (6U.V1壬弓 宀 宀 +M 匸+ Nep.al蘭epl 第仃頁 k+; while(jLBe ngth) LC.datak=LB.dataj; j+； k+; LC.le ngth=k; 輸入輸出結(jié)果： 圖1-1主菜單 L2 25 7 42 19 Ji - - H J F 二-*rr3J 無一

15、!M序 做順薯 所建芳- - -f ff f 值3 3 的9 9 :6:6素丄 數(shù)vbvb2 2 B Be e? ? 元J JT TT TMM I I * * r r - - : : ! ! J JI I L:L:4:4:7:7:L L 請(qǐng)依1212 選擇以下數(shù)宇序號(hào)： 話k査艾嵯 捅所做操生 tei 頑仃有序表 第 18頁 圖1-2順序表的創(chuàng)建和輸出操作 請(qǐng)輸入插入位置：4 請(qǐng)輸入插入元素值：第 發(fā)生溢出！ 圖1-3順序表的插入操作 SS 操缶序 以 JLJn4li12J1 號(hào)!rr 序龍 4 詹 表 入t 插 査有 -!-丁 =7.二 f ff fl lf fi i B 3 3請(qǐng)輸入刪除位

16、置：9 刪除位置不合法! 選擇以下數(shù)宇序號(hào) J 4 ?：棚亍有序表高插入操作8：刪亍有序表馬合井操作 4 12 25 ? 42 19 36 21 ffls 紅 US圖1-4順序表的刪除操作 根堀逆做圜選擇嘆下數(shù)字序號(hào) 兒刪亍倉序表由插入撫作 排序操作完成! 根瑪所做操生選擇藥F數(shù)字序號(hào) 熾輔黯插入操作 7 12 19 21 2S 膈I爲(wèi)作 3S 42 亠予2 5 2 5 ff ff ew表 Its序 做JiJi薯 所題迄仃 根1 :4:7:1 :4:7: 做順薯 所建行仃 H H 狠1 :1 :4:4:7:7:生 選擇以下數(shù)字序號(hào) 2：；：； 擊擂入操作醫(yī) 12 25 7 42 19 入找序2

17、121 播查有 J J- -UUUU仃 8 8 丸3 3養(yǎng)表 8W -廠-丁 JJ 第 19頁 圖1-5順序表的排序操作 請(qǐng)輸入插入元素值；50 插入操作成功！ 圖1-6有序表的插入操作 創(chuàng)建弟莊養(yǎng)丄= 感甦籍的值: 2 4 6 7 有序裘 13 5 7 2 4 6 7 合并后: 12 3 4 圖1-7兩個(gè)有序表的合并操作 單鏈表的源程序： #i nclude iostream 根1;4:7:7 所做操生選擇以下數(shù)字序號(hào); 購繍合并操作 醤 1 - -bLrbLr 7 7 二Jr1Jr1 next=NULL; void Create1LinkList(LinkList &L,int n

18、)/ 前插 入法創(chuàng)建單鏈表的算法 LNode *s; for(int i=1;i=n;i+) s=new LNode; cout 請(qǐng)輸入第 is-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; 第 22頁 cout 請(qǐng)輸入第 is-data; r-next=s; r=s; r-next=NULL; void PrintLinkList(LinkList L)/ 單鏈表的

19、輸出算 法 if(L-next=NULL) cout 空表！ endl; return; cout 當(dāng)前單鏈表為： next; while(p) coutdatanext; coutendl; int InsertLinkList(LinkList &L,int X)/單鏈表的插入算法 int j=0; LNode *p=L,*s; while(p&jnext; j+; if(!p|ji-1) i,DataType 第 23頁 return 0; s=new LNode; s-data=x; s-next =p-next ; p-next =s; return 1; int D

20、eleteLinkList(LinkList &L,int i)/ 單鏈表的 刪除算法 if(L-next =NULL) return -1; int j=0; LNode *p=L,*q; while(p-next !=NULL)&(jnext ; j+; if(p-next=NULL)|(ji-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 空表，不

21、需要排序！ next=NULL) return; for(p=L-next;p-next!=NULL;p=p-next) 鏈表的 第 24頁 s=p; for(q=p-next;q!=NULL;q=q-next) if(q-datadata) s=q; if(s!=p) temp=s-data; s-data=p-data; p-data=temp; cout 排序成功！ next!=NULL&p-next-datanext; s=new LNode; s-data=x; s-next=p-next; p-next=s; cout 插入操作成功！ next ; p2=L2-next ;

22、 L 3=p3=new LNode; L 3-next =NULL; while(p1&p2) s=new LNode; if(p1-data 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; void menu()/ 菜單函數(shù) L2,LinkList 第 26頁 L inkList L; Init_LinkList(L); int m; while(1) coutn 根據(jù)所

23、做操作選擇以下數(shù)字序號(hào)： endl; cout1: 前插入創(chuàng)建單鏈表 2: 尾 插入創(chuàng)建單鏈表 3: 執(zhí)行插入操作 endl; cout4: 執(zhí)行刪除操作 5: 執(zhí)行輸出 操作 6:執(zhí)行排序操作 endl; cout7: 執(zhí)行有序表的插入操作 8: 執(zhí)行有 序表的合并操作 0:退出 n; switch (n) case 1: couti; Create1LinkList(L,i); PrintLinkList(L); break; case 2: couti; Create2LinkList(L,i); PrintLinkList(L); break; case 3: couti; coute

24、ndlx; coutendl; if (InsertLinkList(L,i,x)=1) cout 插入操作成功！ endl; else 第 28頁 cout 插 入 位 置 不 合 法！ endl; break; case 4: cout一 -AA30- e e- -sese OOC7A-崖弗目確夕吟并 AAendrAAendr break case 5 Prin 產(chǎn) inkLisf(LX break case p se-easorfLinkLisf(LX break- W3曰 第 32頁 case 7: coutendlx; coutendl; Insert2(L,x); break; c

25、ase 8: LinkList L1,L2,L3; Init_LinkList(L1); Init_LinkList(L2); Init_LinkList(L3); cout 創(chuàng)建有序表 1： endl; couti; Create2LinkList(L1,i); Select_Sort_LinkList(L1); cout 創(chuàng)建有序表 2：endl; couti; Create2Li nkList(L2,i); Select_Sort_Li nkList(L2); cout 有序表 1: endl; Prin tL in kList(L1); cout 有序表 2: endl; Prin tLi nkList(L2); Merge(L1,L2,L3); cout 合并后： ! 序 2 2 5 5 OB OB 字 數(shù) 作 T T 操 以表AJ AJ 1 1插 xsl xsl 操創(chuàng)律 做有 據(jù)前盹竝 ex ex 根