201560140140--袁若飛--實驗1：線性表地基本操作及其應用

1、Zhongyuan University of Technology數據結構實驗1 ：線性表的基本操作及其應用班級：RB軟工移151學號：201560140140:袁若飛實驗一線性表一、實驗目的1、幫助讀者復習C+語言程序設計中的知識。2、熟悉線性表的邏輯結構。3、 熟悉線性表的基本運算在兩種存儲結構上的實現，其中以 熟悉鏈表的操作為側重點。二、實驗容本次實驗提供4個題目，每個題目都標有難度系數，*越多難 度越大，題目一、二是必做題。題目三、題目四選作。三、實驗準備知識1、請簡述線性表的基本特性和線性表的幾種基本操作的機制 答：線性表的基本特性是：對線性表中某個元素ai來說，稱其前面的元素ai

2、-1為ai的直接前驅，稱其后前面的元素ai+1為ai的直接后繼。顯然，線性表中每個元素最多有一個直接前驅和一個直接后繼。 答：線性表的幾種基本操作的機制有六個：（1）初始化線性表initial_List（L）建立線性表的初始結構，即建空表。 這也是各種結構都可能要用的運算。（2 ）求表長度 List_le ngth（L）即求表中的元素個數。（3） 按序號取元素get_element（L,i）取出表中序號為i的元素。（4） 按值查詢List_locate（L,x）取出指定值為x的元素，若存在該元素， 則返回其地址；否則，返回一個能指示其不存在的地址值或標記。（5） 插入元素 List_inser

3、t（L,i,x）在表L的第i個位置上插入值為 x的元素。顯然，若表中的元素個數為n，則插入序號i應滿足1<=i<=n+1。（6） 刪除元素List_delete（ L，i）刪除表L中序號為i的元素，顯然， 待刪除元素的序號應滿足1<=i<=n。2、掌握線性表的邏輯結構。3、掌握線性表的鏈式存儲結構。4、熟練掌握線性表的插入、刪除等操作。四、實驗容題目一：順序表的基本操作問題描述實現順序表的建立、求長度，取元素、修改元素、插入、刪 除等基本操作?；疽螅?）依次從鍵盤讀入數據，建立順序表；（2）輸出順序表中的數據元素；（3）求順序表的長度；（4）根據指定條件能夠取元素和

4、修改元素；（5）實現在指定位置插入和刪除元素的功能。測試數據由學生任意指定。運行結果如下圖：1）實現刪除功能' ' D:C+ + Wcrb S缺“ h 吟艸 p 'TTWWW：1 2 3 4 5 & 7 e 911 L2 L3 14 15 IG 17 IS 19 2U輸入要刪除的記靈號;LO刪徐成功！田際后的幀.序齊力：1 2 3 4 5 6 7 3 y 11 12 L3 14 L& 16 17 13 19 刃 Press ar key to cOTiHrne.2）實現取元素功能12 L3 1417 18 L? 2R鐵A茅取元素的.l¥號m斯取

5、的元秉Lid孤兀壽應剔！取尤茶啟的順序恵鄧1 2 3 d b & 7 y ¥11 Id 1J 1< lb lb 17 18 IV 2H frat a 抽丫 koy to cantinuo3）實現查找功能占我叵走罰打師|-吞11H II*誇 1*1 IE 1$ t?If ?H輸入叢古7T孝誰H設元素個數最大為100聲明一個結構體來存放順序表定義存儲表中元素的數組定義表長度分量按序號求元素運算的子函數 聲明按值查詢元素的子函數 聲明插入元素的子函數 聲明刪除元素的子函數表結構變量的定義為表分配空間定義整型變量賦值給表中的元素填入刪除容定義表的長度杏亓,看咸;功I您元茶尼旳I

6、匝序査.尬：能元素后的哽序表為；券與1_!8 直:！ L2 U 141E；丄呂：17 丄臓 *9 空 匕呂1* k亡屮 匸已 許t： JniiU4）實現插入功能< llUCDUeUCSU.CXE-PUfl ? 3 4 5 6 7 S ? Wil 12 1W 14 IS 1ft 17 18 If喻？'芟桂前亍霍:岀喻入要播旳世營=卻恫入元素刪t)!：張入元翥辰乩順帶表商：1 Z 3 4 5 6 ? S ? IH 11 12 13 14 15 16 17 1R If ?B 14 Prus *網 “y W mnMnu«J源代碼(加注釋)#include<stdio.h&

7、gt;#include <iostream.h>#include <malloc.h>#define maxlen 100/typedef struct/ int datamaxlen;/int listlen;/seqlist;void get_element(seqlist *L,int I,int *x); / int List_locate(seqlist L,int I,int x);/bool List_insert(seqlist *L,int I,int x);/bool List_delete(seqlist *L,int I);/void main(

8、) seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i;/for(i=1;i<=20;i+)/L->datai-1=i;/L->listlen=20;/coutvv"刪除前的順序表:n"for(i=1;i<=L->listlen;i+)/ coutv<L->datai-1vv""cout<v"n輸入要刪除的紀錄號："；cin>>i;/if(List_delete(L,i)/ cout<<"n刪

9、除成功！刪除后的順序表為:n"for(i=1;i<=L->listlen;i+)/ cout<<L->datai-1vv""bool List_delete(seqlist *L,int i)/ int j;/if(L->listlen<=0)/ coutvv"下溢出錯！"return false;/ if(i>L->listlen|iv=0)/ coutvv"刪除位置錯！"return false;/else for(j=i;jv=L->listlen-1;j+)

10、 /L->dataj-1=L->dataj;L->listlen-;/return true;/void main() seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i;/for(i=1;iv=20;i+)/L->datai-1=i;輸岀表中元素用戶輸入刪除的記錄用刪除元素的子函數向前批量移動元素刪除元素的子函數定義一個整型變量空表不能刪除元素返回false刪除元素不存在返回false向前批量移動元素表長度減1返回true表結構變量的定義為表分配空間定義整型變量 賦值給表中的元素L->listlen=

11、20;/coutvv"取元素前的順序表:n" for(i=1;i<=L->listlen;i+)/ coutv<L->datai-1vv"" cout«"n輸入要取元素的序號："定義表的長度輸岀表中元素cin>>i;/if(get_element( L, i)/ cout<v"n取元素成功！取元素后的順序表為for(i=1;i<=L->listlen;i+) cout<<L->datai-1vv""用戶輸入要取元素的記錄 用

12、取元素的子函數:n"bool get_element(seqlist *L,int i)/ int x;if(i<1|i>L->listlen)/ coutvv"下溢出錯！"/return false;else x=L->datai-1;/coutvv"n 所取的元素n"coutvvxvv" "/return true;void main()取元素的子函數要取的元素不存在空表無元素取岀相應元素輸岀對應元素 seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist);

13、 / int i,x,a;/for(i=1;iv=20;i+)/L->datai-1=i;L->listlen=20;/coutvv"查找元素前的順序表:n"for(i=1;iv=L->listlen;i+)/ coutvvL->datai-1vv""表結構變量的定義 為表分配空間 定義三個整型變量 賦值給表中的元素定義表的長度輸岀表中元素cout<v"n輸入要查元素cin»x;a=List_locate(L,x);/用戶輸入查找的記錄if(a!=O) cout<<"n 查元素成功！

14、查元素后的順序表為：n"coutvvavv""cout<<"n取元素后的順序表為:n"/for(i=1;iv=L->listlen;i+)/ coutvvL->datai-1vv""取元素后的順序輸岀表中元素else coutvv"n查無此元素成功!int List_locate(seqlist *L,int x)/ int i;/for(i=0;ivL->listlen;i+)/ if(L->datai=x) return(i+1);return(O);/void main()

15、 seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i,x,a;/for(i=1;iv=20;i+)/L->datai-1=i;/L->listlen=20;/coutvv"插入元素前的順序表:n" for(i=1;iv=L->listlen;i+)/:n"按值查詢元素的子函數定義一個整型變量依次比較各個元素/找到元素X的位置返回其序號未找到則返回0值表結構變量的定義 為表分配空間 定義三個整型變量 賦值給表中的元素 填入插入容定義表的長度輸岀表中元素用戶輸入插入的記錄用戶輸入插入的位置

16、 coutvvL->datai-1vv"coutvv"n輸入要插的元素:" cin>>x;/coutvv"n輸入要插的位置:" cin>>i;/a=List_insert(L,i,x);if(a=1) cout<<"n插入元素成功！:n"cout<<"n插入元素后的順序表為:n"for(i=1;i<=L->listlen;i+) coutv<L->datai-1vv""/輸岀表中元素else if(a=0)c

17、outvv"溢出，不能插入！coutvv"插入位置錯!elseint List_insert(seqlist *L,int i,int x)/溢出，不能插入插入元素的子函數int j;/coutvv"溢出，不能插入！"return 0;/溢出，不能插入返回else if(iv1|i>L->listlen+1) coutvv"插入位置錯！"/插入圍錯return -1 ;/返回并結束elsefor(j=L->listlen-1;j>=i-1;j-)/往后移動元素L->dataj+1= L->dataj

18、;L->datai-1=x;/填入插入的元素L->listlen+;/修改表長度return 1;/返回定義一個整型變量if(L->listlen=maxlen)題目二：單鏈表的基本操作問題描述實現帶頭結點的單鏈表的建立、 插入、刪除等單鏈表的基本操作。 基本要求求長度，取元素、修改元素、（1）依次從鍵盤讀入數據，建立帶頭結點的單鏈表;（2）輸出單鏈表中的數據元素（3）求單鏈表的長度；（4）根據指定條件能夠取元素和修改元素；（5）實現在指定位置插入和刪除元素的功能。測試數據由學生任意指定。創(chuàng)建單鏈表讀入數據：1 2 3 4 5 4 2輸出單鏈表中數據為：1 2 3 4 5 4

19、 2 返回單鏈表長度：7在5前面插入數據元素：1 2 3 4 4 5 4 2刪除第一個數據元素：2 3 45 4 2 修改最后一個數據元素：1 234 5 4 1設計分析：從上面的問題描述可以知道我們要實現的操作：“依次從 鍵盤讀入數據，建立帶頭結點的單鏈表，然后就是對此單鏈表 的一些基本操作如增刪改查等”，對此我們設計出了一個單鏈 表用于存放數據，所以對數據應該采用的是鏈式存儲結構。每 個元素之間的關系，可通過在每個節(jié)點當中設置一個指針來存 放下一個元素的地址來體現。其次就是基本操作就是對此單鏈 表中數據存儲結構的更改，通過調用鏈表指針操作其存儲地址。于是可以聲明結構類型為：typedef

20、struct LNodeElemType data;struct LNode *n ext;LNode,*Li nkList;1. 先動態(tài)創(chuàng)建一個單向循環(huán)鏈表，每個節(jié)點包含數據的地址和 指向下一個節(jié)點的地址。2. 查找單鏈表的頭節(jié)點并返回其地址，依次從鍵盤輸入數據并 把它們的地址返回。3. 根據單鏈表的頭結點的地址依次輸出單鏈表中數據元素，并 返回單鏈表的長度。4. 從單鏈表中刪除出數據元素的節(jié)點，并返回新的單向循環(huán)鏈 表的頭指針的值。5. 利用預定義的指針指向指定位置插入或刪除單鏈表中的數 據元素。運行結果如下圖:1）實現建立單鏈表功能I *D!C+W/orkiparet&stlDe

21、bu.gteEtl .exe*O-iHdJ > 1包建氐謙加，讀兀骯5-遍歷，&獲取扶度，7-修改 你必須先刨建單槌裘車槌妄創(chuàng)建M3.26 8 2 3 65畢槌表創(chuàng)楚咸功請輸A像董羅迪郭盍的或置和直 中閭用空格隔尸例如1 22）實現輸出功能3）實現鏈表長度功能'D：C t 十 Wq rkS pa cct-3tlC*cb u. cxc'位人 気話入插 血返必丄整輸TE5S輸記爭 時A你1單月Y冒廠h期 AK旳核2B期O 教干 4-康元臺5-遍歷，7-修改中間用寧格隔開。創(chuàng)如I 1 24）實現取元素功能J |>tCk +Wo斤 KE*TWTrOt 篇也站E萄畫

22、1遼的躁便腐應的STT：-玫i 2-tD，3-靳誦* 4譙元素，5-遍歷，&-巒長庫.7-ti1"± 5 1單池入U.：生咸MH 腳護幅霖輕腑于-353-Sij魏W孵翳魁+<p5）實現修改功能 'D：匚+ .¥0七知帀于-茁軾譏>?01馮護社1尸強"I諳苕搔偵避苴亍的操舊上蟲工曙亍|卜逋£, 1到也2-JfetD. 3-lf 4請元養(yǎng)逅歷&翹玄瓷卡代 你必預先血K單鉗表.中間用主格隔開。例如1 2華鏈表創(chuàng)建咸功！中間用空槪瞭例如1212 5 3源代碼(加注釋)#include<stdio.h>#i

23、nclude<malloc.h>#define List_lnit_Size 100#define Listincrement 10#define ElemType int#define null 0typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void main()void Create(LinkList & L);void Insert(LinkList &L,int i,ElemType e);void Delete(LinkList & L,int i);El

24、emType GetElem(LinkList & L,int i);void Output(LinkList & L);int GetLength(LinkList & L);void Modify(LinkList &L,int i,ElemType elem);LinkList l;int choose,location,value,times=O,createTimes=O,insertTimes=O;printf("請選擇你要執(zhí)行的操作對應的數字：n0-退出，1-創(chuàng)建，2-添加，3-刪除，4-讀元素，5-遍歷，6-獲取長度，7-修改n&quo

25、t;);printf("你必須先創(chuàng)建單鏈表n");scanf("%d", &choose);while(choose!=0)if(choose=1)Create(l);else if(choose=2)printf("請輸入你要添加元素的位置和值，中間用空格隔開。例如：1 2n");if(insertTimes=0)printf("切記：位置必須為1n");insertTimes+;elseprintf("切記：位置要大于 0，并且小于 %dn",GetLength(l);scanf(&

26、quot;%d %d",&location,&value);Insert(l,location,value);else if(choose=3)printf("請輸入你要刪除元素的位置：n");printf(" 切記：位置要大于 0，并且小于 %dn",GetLength(l); scanf("%d",&location);Delete(l,location);else if(choose=4)printf("請輸入你要讀的數據的位置：n");printf(" 切記：位置

27、要大于 0，并且小于 %dn",GetLength(l); scanf("%d",&location);printf("%dn",GetElem(l,location);else if(choose=5)Output(l);else if(choose=6)printf("%dn",GetLength(l);elseprintf("請輸入你要修改元素的位置和修改后的值，中間用空格隔開。例如：1 2n");printf("切記：位置要大于0,并且小于 %dn",GetLength

28、(l);ElemType e1=0;scanf("%d %d",location,e1);Modify(l,location,e1);+times;if(times%10=0)printf("請選擇你要執(zhí)行的操作對應的數字：n0-退出，1-創(chuàng)建，2-添加，3-刪除，4-讀元素，5-遍歷，6-獲取長度n");printf("請確認你已經創(chuàng)建單鏈表，如果沒有的話，請首先創(chuàng)建！”)；scanf("%d", &choose);void Create(LinkList & L)L=(LinkList)malloc(si

29、zeof(LNode);建立帶頭節(jié)點的單鏈表L->next=null;printf("單鏈表創(chuàng)建成功！n");void Insert(LinkList &L,int i,ElemType e)在第 i 個位置插入元素LinkList p,s;p=L;int j=0;while(p&&j<i-1)p=p->next ;/獲得位置i處的指針+j;printf("元素插入成功！n");if(p&&(j=i-1)s=(LinkList)malloc(sizeof(LNode);s->data=e;s

30、->next=p->next;p_>next=s;printf(”元素插入成功！n");void Delete(LinkList & L,int i)LinkList p=L,p1=p->next;int j=0;if(p->next&&i >0)while(p1 &&j<i-1)p=p1;p1=p->next;+j;if(j=i-1)p->next=p1->next;printf("元素刪除成功！n");else1！ n");printf("元

31、素刪除失敗，因為你輸入的位置小于ElemType GetElem(LinkList & L,int i)LinkList p=L->next;int j=1;ElemType e;while(p&&j<i)p=p->next;+j;if(p&&(j=i)/此單鏈表有頭指針，索引和下標一致e=p->data;printf("成功獲取元素！");return e;void Output(LinkList & L)LinkList p=L->next;printf(”單鏈表中的元素分別為：”)；whil

32、e(p)printf("%d ",p->data);p=p_>next;printf("n");int GetLength(LinkList & L)LinkList p=L;int j=0;while(p)p=p->next;+j;return j;void Modify(LinkList &L,int i,ElemType elem)LinkList p=L->next;int j=1;ElemType e;while(p&&j<i)p=p->next;+j;if(p&&am

33、p;(j=i)/此單鏈表有頭指針，索引和下標一致p->data=elem;printf(" 修改元素成功！ n");elseprintf("修改元素失敗!n");題目三：約瑟夫環(huán)（*）問題描述約瑟夫（Joseph）問題的一種描述是：編號為 1,2,n的n 個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開 始任選一個正整數作為報數上限值 m從第一個人開始按順時針 方向自1開始順序報數，報到m時停止報數。報m的人出列，將 他的密碼作為新的m值，從他在順時針方向上的下一個人開始重 新從1報數，如此下去，直至所有人全部出列為止。試設計一個 程序求

34、出出列順序。基本要求利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序印出 各人的編號。測試數據由學生任意指定。女口： m的初值為20; n的值為7;密碼：3，1，7，2，4，8,4；（正確的輸出結果應為6，1, 4, 7, 2, 3, 5）。（報告上要求寫出多批數據測試結果）實現提示程序運行后首先要求用戶輸入初始報數上限值 m人數n,（設 n< 30）。然后輸入各人的密碼。選作容向上述程序中添加在順序結構上實現的部分。運行結果如下圖：約瑟夫環(huán)實現功能o;2 85lo5_y 2 2 s 2 s ? = 1池迫焉S蟲曙囹帀用憩密密密總型雋 “rtlJn/= J -/Tl IJTTJi -1

35、1 JTTJL frw ,JTT r* JfTT JTl f .-l 2 3 4 5 6 7 8- 9 u 1 2 3 4 5 & 孑 p g _u請輸入開始位直，請輸入幵抬密碼：13£516 丄 §717丄丄 2012461415PfeM宮 any Ikey t.口 cont i olie 哄川L；!- R J去亠一源代碼(加注釋)#include <stdlib.h>#include <stdio.h>#include <Math.h>typedef struct nodeint number;int password;str

36、uct node* next;Node,*Linklist;Linklist CreateLinklist(int amount) int i;Node *s=NULL,*r=NULL;Linklist L=NULL,R=NULL;for(i=0;i<amount;i+)s=(Node*)malloc(sizeof(Node);if(s=NULL)printf(”空間申請失敗r);exit(O);s->number=i+1;s->password=rand()%10+1;printf("%4d 的密碼 %4dn",s->number,s->pa

37、ssword);if(i=0)L=s;r=s;else r->next=s;r=s; R=r;r->next=L;return(R);void DeleteLinklist(Linklist R,int start,int amount,int num)Node *position=NULL,*p=NULL,*q=NULL;int i,k,secret;position=R;secret=start;for(i=num;i<=amount;i+)p=position;for(k=1;k<secret;k+)p=p->next;q=p->next;p->

38、next=q->next;secret=q->password;printf("%5d",q->number);if(i%10=0)printf("n");position=p;free(q);int main()int amount,start,num;Linklist R=NULL;printf("n 請輸入總人數：");scanf("%d", &amount);R=CreateLinklist(amount);printf("n請輸入開始位置：");scanf(&

39、quot;%d", &start);printf("n請輸入開始密碼：");scanf("%d",&num);DeleteLinklist(R,start,amount,num);return(1);題目四：多項式的表示及相加(* )問題描述設計一個算法，以實現一元稀疏多項式的加法運算?；疽?1) 輸入并建立多項式；(2) 輸出多項式，輸出形式為整數序列：n, c1，e1, c2,e2, , , en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數降序排列；(3) 多項式a和b相加，建立多項式a+b。測

40、試數據由學生任意指定。實現提示用帶表頭結點的單鏈表存儲多項式。選作容多項式a和b相減，建立多項式a-b。運行結果如下圖：多項式相加實現功能：'D：C + + WorkS p a cetest4.D eb uqtest4.exe'AB*- A E W 鑲疇湘 頂多多式 多多項L 2+2.5i+3. 2i 3-2. 5x 5-1. 2+2. 5x3. 2x 3+2. 5x 5+5. -29x342. 5x+l. 25. 4z" 10+2. 5z"5+3- 2i*3+2. 5i5. 4za 10+6.'3+5xtc cantiniie.4kT+102源代碼

41、：(加注釋)/ 文件名：exp2-7.cpp#include <stdio.h>#include <malloc.h>#define MAX 20/多項式最多項數typedef structdouble coef;/定義存放多項式的數組類型/系數int exp;/指數 PolyArrayMAX;typedef struct pnodedouble coef;/定義單鏈表結點類型/系數int exp;/指數struct pnode *next; PolyNode;void DispPoly(PolyNode *L)bool first=true;/輸岀多項式/first為

42、true表示是第一項PolyNode *p=L->next; while (p!=NULL)if (first) first=false;else if (p->coef>0) printf("+");if (p->exp=0)printf("%g",p->coef);else if (p_>exp=1) printf("%gx",p->coef);elseprintf("%gxA%d",p->coef,p->exp);p=p->next;printf(&

43、quot;n");/銷毀單鏈表void DestroyList(PolyNode *&L) PolyNode *p=L,*q=p->next;while (q!=NULL)free(p);p=q; q=p->next;free(p);尾插法建表 void CreateListR(PolyNode *&L,PolyArray a,int n) / PolyNode *s,*r;int i;L=(PolyNode *)malloc(sizeof(PolyNode);/ 創(chuàng)建頭結點L->next=NULL;r=L;for (i=0;i<n;i+)r始

44、終指向終端結點，開始時指向頭結點s=(PolyNode *)malloc(sizeof(PolyNode);創(chuàng)建新結點s->coef=ai.coef; s->exp=ai.exp; r->next=s;r=s;r->next=NULL;/將*s插入*r之后/終端結點next域置為NULLvoid Sort(PolyNode *&head)/按exp域遞減排序求兩有序集合的并/創(chuàng)建頭結點/復制結點/復制結點PolyNode *p=head->next,*q,*r;if (p!=NULL)r=p->next; p->next=NULL;p=r;wh

45、ile (p!=NULL) r=p->next; q=head;/若原單鏈表中有一個或以上的數據結點r保存*p結點后繼結點的指針/構造只含一個數據結點的有序表r保存*p結點后繼結點的指針while (q->next!=NULL && q->next->exp>p->exp)q=q->next;/在有序表中找插入*p的前驅結點*qp->next=q->next; / 將*p 插入到 *q 之后q->next=p;p=r；void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) / PolyNode *pa=ha->next,*pb=hb->next,*s,*tc; double c;hc=(PolyNode *)malloc(sizeof(PolyNode);tc=hc;while (pa!=NULL && pb!=NULL)if (pa->exp>pb->exp)s=(PolyNode *)malloc(sizeof(PolyNode); s_>exp=pa_>exp;s_>coef=pa_>coef; tc-&g