201560140140--袁若飛--實(shí)驗(yàn)1：線性表地基本操作及其應(yīng)用

1、Zhongyuan University of Technology數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)1 ：線性表的基本操作及其應(yīng)用班級(jí)：RB軟工移151學(xué)號(hào)：201560140140:袁若飛實(shí)驗(yàn)一線性表一、實(shí)驗(yàn)?zāi)康?、幫助讀者復(fù)習(xí)C+語言程序設(shè)計(jì)中的知識(shí)。2、熟悉線性表的邏輯結(jié)構(gòu)。3、 熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以 熟悉鏈表的操作為側(cè)重點(diǎn)。二、實(shí)驗(yàn)容本次實(shí)驗(yàn)提供4個(gè)題目，每個(gè)題目都標(biāo)有難度系數(shù)，*越多難 度越大，題目一、二是必做題。題目三、題目四選作。三、實(shí)驗(yàn)準(zhǔn)備知識(shí)1、請(qǐng)簡(jiǎn)述線性表的基本特性和線性表的幾種基本操作的機(jī)制 答：線性表的基本特性是：對(duì)線性表中某個(gè)元素ai來說，稱其前面的元素ai

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

3、t（L,i,x）在表L的第i個(gè)位置上插入值為 x的元素。顯然，若表中的元素個(gè)數(shù)為n，則插入序號(hào)i應(yīng)滿足1<=i<=n+1。（6） 刪除元素List_delete（ L，i）刪除表L中序號(hào)為i的元素，顯然， 待刪除元素的序號(hào)應(yīng)滿足1<=i<=n。2、掌握線性表的邏輯結(jié)構(gòu)。3、掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4、熟練掌握線性表的插入、刪除等操作。四、實(shí)驗(yàn)容題目一：順序表的基本操作問題描述實(shí)現(xiàn)順序表的建立、求長(zhǎng)度，取元素、修改元素、插入、刪 除等基本操作?；疽螅?）依次從鍵盤讀入數(shù)據(jù)，建立順序表；（2）輸出順序表中的數(shù)據(jù)元素；（3）求順序表的長(zhǎng)度；（4）根據(jù)指定條件能夠取元素和

4、修改元素；（5）實(shí)現(xiàn)在指定位置插入和刪除元素的功能。測(cè)試數(shù)據(jù)由學(xué)生任意指定。運(yùn)行結(jié)果如下圖：1）實(shí)現(xiàn)刪除功能' ' D:C+ + Wcrb S缺“ h 吟艸 p 'TTWWW：1 2 3 4 5 & 7 e 911 L2 L3 14 15 IG 17 IS 19 2U輸入要?jiǎng)h除的記靈號(hào);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）實(shí)現(xiàn)取元素功能12 L3 1417 18 L? 2R鐵A茅取元素的.l¥號(hào)m斯取

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

6、匝序査.尬：能元素后的哽序表為；券與1_!8 直:！ L2 U 141E；丄呂：17 丄臓 *9 空 匕呂1* k亡屮 匸已 許t： JniiU4）實(shí)現(xiàn)插入功能< llUCDUeUCSU.CXE-PUfl ? 3 4 5 6 7 S ? Wil 12 1W 14 IS 1ft 17 18 If喻？'芟桂前亍霍:岀喻入要播旳世營(yíng)=卻恫入元素刪t)!：張入元翥辰乩順帶表商：1 Z 3 4 5 6 ? S ? IH 11 12 13 14 15 16 17 1R If ?B 14 Prus *網(wǎng) “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輸入要?jiǎng)h除的紀(jì)錄號(hào)："；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"下溢出錯(cuò)！"return false;/ if(i>L->listlen|iv=0)/ coutvv"刪除位置錯(cuò)！"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;輸岀表中元素用戶輸入刪除的記錄用刪除元素的子函數(shù)向前批量移動(dòng)元素刪除元素的子函數(shù)定義一個(gè)整型變量空表不能刪除元素返回false刪除元素不存在返回false向前批量移動(dòng)元素表長(zhǎng)度減1返回true表結(jié)構(gòu)變量的定義為表分配空間定義整型變量 賦值給表中的元素L->listlen=

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

12、取元素的子函數(shù):n"bool get_element(seqlist *L,int i)/ int x;if(i<1|i>L->listlen)/ coutvv"下溢出錯(cuò)！"/return false;else x=L->datai-1;/coutvv"n 所取的元素n"coutvvxvv" "/return true;void main()取元素的子函數(shù)要取的元素不存在空表無元素取岀相應(yīng)元素輸岀對(duì)應(yīng)元素 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""表結(jié)構(gòu)變量的定義 為表分配空間 定義三個(gè)整型變量 賦值給表中的元素定義表的長(zhǎng)度輸岀表中元素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"按值查詢?cè)氐淖雍瘮?shù)定義一個(gè)整型變量依次比較各個(gè)元素/找到元素X的位置返回其序號(hào)未找到則返回0值表結(jié)構(gòu)變量的定義 為表分配空間 定義三個(gè)整型變量 賦值給表中的元素 填入插入容定義表的長(zhǎng)度輸岀表中元素用戶輸入插入的記錄用戶輸入插入的位置

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"插入位置錯(cuò)!elseint List_insert(seqlist *L,int i,int x)/溢出，不能插入插入元素的子函數(shù)int j;/coutvv"溢出，不能插入！"return 0;/溢出，不能插入返回else if(iv1|i>L->listlen+1) coutvv"插入位置錯(cuò)！"/插入圍錯(cuò)return -1 ;/返回并結(jié)束elsefor(j=L->listlen-1;j>=i-1;j-)/往后移動(dòng)元素L->dataj+1= L->dataj

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

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

20、struct LNodeElemType data;struct LNode *n ext;LNode,*Li nkList;1. 先動(dòng)態(tài)創(chuàng)建一個(gè)單向循環(huán)鏈表，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)的地址和 指向下一個(gè)節(jié)點(diǎn)的地址。2. 查找單鏈表的頭節(jié)點(diǎn)并返回其地址，依次從鍵盤輸入數(shù)據(jù)并 把它們的地址返回。3. 根據(jù)單鏈表的頭結(jié)點(diǎn)的地址依次輸出單鏈表中數(shù)據(jù)元素，并 返回單鏈表的長(zhǎng)度。4. 從單鏈表中刪除出數(shù)據(jù)元素的節(jié)點(diǎn)，并返回新的單向循環(huán)鏈 表的頭指針的值。5. 利用預(yù)定義的指針指向指定位置插入或刪除單鏈表中的數(shù) 據(jù)元素。運(yùn)行結(jié)果如下圖:1）實(shí)現(xiàn)建立單鏈表功能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)楚咸功請(qǐng)輸A像董羅迪郭盍的或置和直 中閭用空格隔尸例如1 22）實(shí)現(xiàn)輸出功能3）實(shí)現(xiàn)鏈表長(zhǎng)度功能'D：C t 十 Wq rkS pa cct-3tlC*cb u. cxc'位人 気話入插 血返必丄整輸TE5S輸記爭(zhēng) 時(shí)A你1單月Y冒廠h期 AK旳核2B期O 教干 4-康元臺(tái)5-遍歷，7-修改中間用寧格隔開。創(chuàng)如I 1 24）實(shí)現(xiàn)取元素功能J |>tCk +Wo斤 KE*TWTrOt 篇也站E萄畫

22、1遼的躁便腐應(yīng)的STT：-玫i 2-tD，3-靳誦* 4譙元素，5-遍歷，&-巒長(zhǎng)庫.7-ti1"± 5 1單池入U(xiǎn).：生咸MH 腳護(hù)幅霖輕腑于-353-Sij魏W孵翳魁+<p5）實(shí)現(xiàn)修改功能 'D：匚+ .¥0七知帀于-茁軾譏>?01馮護(hù)社1尸強(qiáng)"I諳苕搔偵避苴亍的操舊上蟲工曙亍|卜逋£, 1到也2-JfetD. 3-lf 4請(qǐng)?jiān)B(yǎng)逅歷&翹玄瓷卡代 你必預(yù)先血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("請(qǐng)選擇你要執(zhí)行的操作對(duì)應(yīng)的數(shù)字：n0-退出，1-創(chuàng)建，2-添加，3-刪除，4-讀元素，5-遍歷，6-獲取長(zhǎng)度，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("請(qǐng)輸入你要添加元素的位置和值，中間用空格隔開。例如：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("請(qǐng)輸入你要?jiǎng)h除元素的位置：n");printf(" 切記：位置要大于 0，并且小于 %dn",GetLength(l); scanf("%d",&location);Delete(l,location);else if(choose=4)printf("請(qǐng)輸入你要讀的數(shù)據(jù)的位置：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("請(qǐng)輸入你要修改元素的位置和修改后的值，中間用空格隔開。例如：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("請(qǐng)選擇你要執(zhí)行的操作對(duì)應(yīng)的數(shù)字：n0-退出，1-創(chuàng)建，2-添加，3-刪除，4-讀元素，5-遍歷，6-獲取長(zhǎng)度n");printf("請(qǐng)確認(rèn)你已經(jīng)創(chuàng)建單鏈表，如果沒有的話，請(qǐng)首先創(chuàng)建！”)；scanf("%d", &choose);void Create(LinkList & L)L=(LinkList)malloc(si

29、zeof(LNode);建立帶頭節(jié)點(diǎn)的單鏈表L->next=null;printf("單鏈表創(chuàng)建成功！n");void Insert(LinkList &L,int i,ElemType e)在第 i 個(gè)位置插入元素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、素刪除失敗，因?yàn)槟爿斎氲奈恢眯∮贓lemType 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)/此單鏈表有頭指針，索引和下標(biāo)一致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)/此單鏈表有頭指針，索引和下標(biāo)一致p->data=elem;printf(" 修改元素成功！ n");elseprintf("修改元素失敗!n");題目三：約瑟夫環(huán)（*）問題描述約瑟夫（Joseph）問題的一種描述是：編號(hào)為 1,2,n的n 個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開 始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m從第一個(gè)人開始按順時(shí)針 方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將 他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重 新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè) 程序求

34、出出列順序?；疽罄脝蜗蜓h(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序印出 各人的編號(hào)。測(cè)試數(shù)據(jù)由學(xué)生任意指定。女口： m的初值為20; n的值為7;密碼：3，1，7，2，4，8,4；（正確的輸出結(jié)果應(yīng)為6，1, 4, 7, 2, 3, 5）。（報(bào)告上要求寫出多批數(shù)據(jù)測(cè)試結(jié)果）實(shí)現(xiàn)提示程序運(yùn)行后首先要求用戶輸入初始報(bào)數(shù)上限值 m人數(shù)n,（設(shè) n< 30）。然后輸入各人的密碼。選作容向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。運(yùn)行結(jié)果如下圖：約瑟夫環(huán)實(shí)現(xià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請(qǐng)輸入開始位直，請(qǐng)輸入幵抬密碼：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(”空間申請(qǐng)失敗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 請(qǐng)輸入總?cè)藬?shù)：");scanf("%d", &amount);R=CreateLinklist(amount);printf("n請(qǐng)輸入開始位置：");scanf(&

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

40、試數(shù)據(jù)由學(xué)生任意指定。實(shí)現(xiàn)提示用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。選作容多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。運(yùn)行結(jié)果如下圖：多項(xiàng)式相加實(shí)現(xiàn)功能：'D：C + + WorkS p a cetest4.D eb uqtest4.exe'AB*- A E W 鑲疇湘 頂多多式 多多項(xiàng)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/多項(xiàng)式最多項(xiàng)數(shù)typedef structdouble coef;/定義存放多項(xiàng)式的數(shù)組類型/系數(shù)int exp;/指數(shù) PolyArrayMAX;typedef struct pnodedouble coef;/定義單鏈表結(jié)點(diǎn)類型/系數(shù)int exp;/指數(shù)struct pnode *next; PolyNode;void DispPoly(PolyNode *L)bool first=true;/輸岀多項(xiàng)式/first為

42、true表示是第一項(xiàng)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)建頭結(jié)點(diǎn)L->next=NULL;r=L;for (i=0;i<n;i+)r始

44、終指向終端結(jié)點(diǎn)，開始時(shí)指向頭結(jié)點(diǎn)s=(PolyNode *)malloc(sizeof(PolyNode);創(chuàng)建新結(jié)點(diǎn)s->coef=ai.coef; s->exp=ai.exp; r->next=s;r=s;r->next=NULL;/將*s插入*r之后/終端結(jié)點(diǎn)next域置為NULLvoid Sort(PolyNode *&head)/按exp域遞減排序求兩有序集合的并/創(chuàng)建頭結(jié)點(diǎn)/復(fù)制結(jié)點(diǎn)/復(fù)制結(jié)點(diǎn)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;/若原單鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn)r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針/構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針while (q->next!=NULL && q->next->exp>p->exp)q=q->next;/在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*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