數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表多項(xiàng)式加減實(shí)驗(yàn)報(bào)告

1、北京郵電大學(xué)信息與通信工程學(xué)院第 1 頁(yè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)： 實(shí)驗(yàn)一 ——線(xiàn)性表日 期： 2013 年 10 月 28 日1． 實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康?實(shí)驗(yàn)?zāi)康?、 熟悉 C++語(yǔ)言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法2、 學(xué)習(xí)指針、模板類(lèi)、異常處理的使用3、 掌握線(xiàn)性表的操作的實(shí)現(xiàn)方法4、 學(xué)習(xí)使用線(xiàn)性表解決實(shí)際問(wèn)題的能力實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)內(nèi)容利用線(xiàn)性表實(shí)現(xiàn)一個(gè)一元多項(xiàng)式 Polynomialf(x) = a0 + a1x

2、+ a2x2 + a3x3 + … + anxn Polynomial 的結(jié)點(diǎn)結(jié)構(gòu)如下：struct term{float coef; //系數(shù)int expn; //指數(shù)};要求：1、 能夠?qū)崿F(xiàn)一元多項(xiàng)式的輸入和輸出2、 能夠進(jìn)行一元多項(xiàng)式相加3、 能夠進(jìn)行一元多項(xiàng)式相減4、 能夠計(jì)算一元多項(xiàng)式在 x 處的值5、 能夠計(jì)算一元多項(xiàng)式的導(dǎo)數(shù)（選作）6、 能夠進(jìn)行一元多項(xiàng)式相乘（選作）7、 編寫(xiě)測(cè)試 main()函數(shù)測(cè)試線(xiàn)性表

3、的正確性2. 程序分析考慮到數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，因?yàn)槎囗?xiàng)式是線(xiàn)性結(jié)構(gòu)因此選擇線(xiàn)性表，而本次實(shí)驗(yàn)中涉及到多項(xiàng)式的加減，要進(jìn)行節(jié)點(diǎn)的添加或者刪除，用順序表顯然不能滿(mǎn)足要求，而且由于不知道多項(xiàng)式的項(xiàng)數(shù)，很容易造成空間的浪費(fèi)，當(dāng)兩個(gè)多項(xiàng)式指數(shù)相差很遠(yuǎn)時(shí)，操作要移動(dòng)很多項(xiàng)，步驟很麻煩繁瑣。綜上，我選擇了單鏈表，每個(gè)節(jié)點(diǎn)有三個(gè)部分，分別儲(chǔ)存系數(shù)、指數(shù)、和指針，這樣在計(jì)算加減或者指數(shù)不等時(shí)，只需要簡(jiǎn)單的摘連加鏈即可，而且不會(huì)造成空間的太多浪費(fèi)。每次利用尾

4、插法將結(jié)點(diǎn)插入基準(zhǔn)多項(xiàng)式。2.1 存儲(chǔ)結(jié)構(gòu)北京郵電大學(xué)信息與通信工程學(xué)院第 3 頁(yè)3.5 最后一個(gè)結(jié)點(diǎn)指為空時(shí)間復(fù)雜度 O(n),空間復(fù)雜度 S(n)2、輸出多項(xiàng)式 、輸出多項(xiàng)式自然語(yǔ)言描述：1) 得到鏈表的結(jié)點(diǎn)個(gè)數(shù) n2) 設(shè)置工作指針 f 指向頭結(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)3) 由于第一項(xiàng)前不需要加號(hào)，故單獨(dú)輸出第一項(xiàng)（f->coef）x^（f->exp）4) 之后移動(dòng) f 循環(huán)遍歷剩余的節(jié)點(diǎn)，逐項(xiàng)輸出+（f->coef）x^（

5、f->exp）偽代碼描述：1.term*f= first->next；2．輸出（f->coef）x^（f->exp）3.循環(huán) n-1 次3.1 f=f->next;3.2 輸出+（f->coef）x^（f->exp）時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 S(1)3、多項(xiàng)式相加 、多項(xiàng)式相加自然語(yǔ)言描述：1) 設(shè)有兩個(gè)多項(xiàng)式鏈表 A 和 B，設(shè)置工作指針 p 和 q 分別指向其第一項(xiàng)2) 若 p-&g

6、t;expexp，則結(jié)點(diǎn) p 保留不變，p 指向 A 鏈表的下一個(gè)結(jié)點(diǎn)繼續(xù)比較。3) 若 p->exp>q->exp，則結(jié)點(diǎn) q 應(yīng)為結(jié)果中的一個(gè)結(jié)點(diǎn)，將 q 結(jié)點(diǎn)加入到 p 結(jié)點(diǎn)之前，q結(jié)點(diǎn)指向下一個(gè)位置，繼續(xù)比較。4) 若 p->exp=q->exp，則 p 與 q 所指為同類(lèi)項(xiàng)，則為以下兩種情況：（a） 合并的系數(shù)為 0，則刪除 p 結(jié)點(diǎn)（b） 合并的系數(shù)不為 0，將其重新賦予 p 結(jié)點(diǎn)兩結(jié)點(diǎn)合并后可

7、刪除 q 結(jié)點(diǎn)，并將 p、q 分別指向下一個(gè)位置繼續(xù)比較 5) （a）若 p 已指空，q 依然存在，則逐項(xiàng)將 q 復(fù)制至 A 鏈表的最后；（b）若 q 指空，則不需再進(jìn)行操作。6) 當(dāng) p、q 均不存在，運(yùn)算結(jié)束。偽代碼描述1. 初始化工作指針 p 和 q，以及 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針 p_prior；2. 若 p 和 q 都不為空，則循環(huán)如下操作：2.1 若 p->data.exp data.exp，則 p_prior = p;

8、 p = p->next;2.2 否則，若 p->data.exp > q->data.exp，則：2.2.1 將 q 結(jié)點(diǎn)加入到 A 鏈表 p 結(jié)點(diǎn)之前； 2.2.2 q 指向 B 鏈表下一個(gè)結(jié)點(diǎn)；2.3 否則：p->data.coef = p->data.coef + q->data.coef；2.3.1 若 p->data.coef 為 0，刪除 p 結(jié)點(diǎn)；2.3.2 p 指向下