數(shù)據(jù)結(jié)構(gòu)線性表多項式加減實驗報告

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

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

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

4、插法將結(jié)點插入基準多項式。2.1 存儲結(jié)構(gòu)北京郵電大學信息與通信工程學院第 3 頁3.5 最后一個結(jié)點指為空時間復雜度 O(n),空間復雜度 S(n)2、輸出多項式 、輸出多項式自然語言描述：1) 得到鏈表的結(jié)點個數(shù) n2) 設(shè)置工作指針 f 指向頭結(jié)點后一個節(jié)點3) 由于第一項前不需要加號，故單獨輸出第一項（f->coef）x^（f->exp）4) 之后移動 f 循環(huán)遍歷剩余的節(jié)點，逐項輸出+（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）時間復雜度 O(n)，空間復雜度 S(1)3、多項式相加 、多項式相加自然語言描述：1) 設(shè)有兩個多項式鏈表 A 和 B，設(shè)置工作指針 p 和 q 分別指向其第一項2) 若 p-&g

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

7、刪除 q 結(jié)點，并將 p、q 分別指向下一個位置繼續(xù)比較 5) （a）若 p 已指空，q 依然存在，則逐項將 q 復制至 A 鏈表的最后；（b）若 q 指空，則不需再進行操作。6) 當 p、q 均不存在，運算結(jié)束。偽代碼描述1. 初始化工作指針 p 和 q，以及 p 結(jié)點的前驅(qū)結(jié)點指針 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é)點加入到 A 鏈表 p 結(jié)點之前； 2.2.2 q 指向 B 鏈表下一個結(jié)點；2.3 否則：p->data.coef = p->data.coef + q->data.coef；2.3.1 若 p->data.coef 為 0，刪除 p 結(jié)點；2.3.2 p 指向下