1、實習一 線性表及其應用 (題目：一元稀疏多項式的加法運算 )一、需求分析1. 輸入并建立兩個多項式；2. 多項式 a 與 b 相加，建立和多項式 c ；3. 輸出多項式abc。輸出格式：比如多項式 a為：A(X)=C1xe1 +c2xe2+ CmXem其中，Ci和ei分別為第i項的系數和指數，且各項按指數的升幕排列，即0eKe2vvem。多項式bc類似輸出。4 測試數據( 1 ) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)( 2) (x+x100)+(x100+x200)=(x+2x100+x200)( 3) (2x+5x8-3x11)+(7-5x8+11x9

2、)=(7+2x+11x9-3x11)實習一 線性表及 其應用題目：一元稀疏多項式的加法運算 實習時間： 2012/9/20.10.12一、需求分析1. 輸入并建立兩個多項式；2. 多項式a與b相加，建立和多項式c；3. 輸出多項式abc。輸出格式：比如多項式 a為：A(X)=C1xe1 +c2xe2+ CmXem其中，Ci和ei分別為第i項的系數和指數，且各項按指數的升幕排列，即0eKe2vvem。多項式bc類似輸出。4 測試數據( 1 ) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)( 2) (x+x100)+(x100+x200)=(x+2x100+x200

3、)( 3) (2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)二、設計1. 設計思想(1 )存儲結構 用帶頭結點的單鏈表存儲多項式。三個多項式鏈表中都只存儲非零系數項。若多項式a與b中指數相等的兩項相加后，系數為零，則在和多項式C中不存儲該指數項。(2)主要算法基本思想 按照鏈表的基本操作，初始化三個鏈表，在兩個鏈表中按指數由小到大分別 插入a和b的多項式(系數和指數)，將多項式a的鏈表復制給多項式C的鏈表, 再調用求和函數( b 的鏈表和 c 的鏈表相加)，將求和的結果插入到 c 的鏈表中 (作為多項式C)最后輸出多項式a, b, C三個多項式?！?】插入

4、函數：設計按多項式指數的從小到大插入。從第一個元素開始 判斷，直到遇到比插入元素更大的指數或鏈表尾為止，再進行插入操作?！?】求和函數：先將多項式a的鏈表復制給多項式C的鏈表，在b的鏈 表不為空的前提下，將b中的各項的指數與C中各項的指數比較大小。(1) 若相等，就將該項的系數相加，和不為零就將C 中該項的系數替換 為其和(何若為零則刪除該節點)。(2) 若 b 中的指數大，就在 C 鏈表該節點之前插入 b 項的此節點。(3) 若 b 中的指數小，就一直查找到 C 鏈表尾。再將多余的 b 鏈表一起 復制給C鏈表?！?】輸出函數(系數為 0 的項已被刪除)： 多項式第一項若為正數，無需符號，其余

5、項帶符號輸出(定義一個開關變量)(1) 系數為a,指數b為O的項輸出(a)。( 2)系數 a 為 1，指數 b 為 1 的項輸出( x)。(3) 系數a為1,指數b不為1的項輸出(xb)( 4)系數 a 為-1,指數 b 為 1 的項輸出( -x)。(5) 系數a為-1,指數b不為1的項輸出(-xb)。(6) 系數a不為1或-1,指數b不為O或1的項輸出(axb)2. 設計表示( 1)函數調用關系圖mainListInitiate ListInsert ListAdd ListGet( 2)函數接口規格說明VOid LiStlnitiate(SLNode *head)/*初始化以 head為頭

6、指針的單鏈表 */int ListInsert(SLNode *headDaTatype xishuDaTatype zhishu) /在* 單鏈 表中按指數的由小到大順序插入多項式的指數和系數 */int LiStAdd(SLNode*head1SLNode*head2SLNode*head3)/以 head1 為 頭指針的單鏈表與以head2為頭指針的單鏈表相加等于以head3為頭指針的單鏈 表*/lnt LiStGet(SLNode*head) /* 輸出以 head 為頭指針的單鏈表 */3. 實現注釋 (即各項功能的實現程度)( 1)根據輸入的 n 值建立多項式 a, b 的單鏈表；

7、根據提示輸入每項的系數 和指數。(2) 可不按指數大小順序任意輸入多項式的每項(整數項)。(3) 按數學格式輸出ab兩多項式，然后再輸出相加后的和C的多項式4. 詳細設計【1】插入函數：int LiStl nsert(SLNode *headDaTatype XiShuDaTatyPe ZhiShU)插入SLNode *p*q;p=head;while(p-neXt!=NULL)if(p-neXt-ZhiShu)ZhiShu)break;/ 比較指數大小p=p-neXt;/ 鏈表中節點指數大，則比較鏈表下一個q=(SLNode*)malloc(SiZeof(SLNode);/ 鏈表中節點指數小

8、，則在該節點前插入q-XiShu=XiShu;q-ZhiShu=ZhiShu;q-neXt=NULL;q-neXt=p-neXt;p-neXt=q;return 1;【2】求和函數：int LiStAdd(SLNode*head1SLNode*head2SLNode*head3)SLNode *p*q*S*r;int n=0;p=head1;q=head2;S=head3;while(p-neXt!=NULL)/先將 a 存入 c 中r=(SLNode*)malloc(SiZeof(SLNode);r-ZhiShu=p-neXt-ZhiShu;r-XiShu=p-neXt-XiShu;r-ne

9、Xt=NULL;S-neXt=r;p=p-neXt;s=s-next;s=head3; while(s-next!=NULL &q-next!=NULL )WhiIe(s- next!=NULL & s-n ext-zhishun ext-zhishu)搜尋 s=s-next;if(s-next!=NULL)n=1;if(n)if( s-next-zhishu=q-next-zhishu ) if(s-next-xishu+q-next-xishu!=0)s-next-xishu=s-next-xishu+q-next-xishu; s=s-next;eIse s-next=s-next-ne

10、xt;eIse r=(SLNode*)maIIoc(sizeof(SLNode);r-zhishu=q-next-zhishu; r-xishu=q-next-xishu; r-next=s-next; s-next=r; s=s-next;/ 插入q=q-next;n=0;if(q-next!=NULL&s-next=NULL)s-next=q-next;/ 剩余項的接到 C鏈表的尾部return 1;【3】輸出函數(系數為 0 的項已被刪除)：int ListGet(SLNode *head)/輸出SLNode *p; p=head-next;/ 判斷頭結點為空的輸出/ 判斷頭結點非空/

11、多項式第一項的輸出/ 當指數為時，只輸出系數 xishuint kaiguan=1; if(p=NULL)printf(0n);while(p!=NULL) if(kaiguan=1)if(p-zhishu=0)printf(%dp-xishu);else if(p-xishu=1)/ 系數為 1 時輸出 Xzhishui 或 xif(p-zhishu=1)printf(x);else printf(x%dp-zhishu);else if(p-xishu=-1) / 系數為-1 時輸出-Xzhishui或-Xif(p-zhishu=1)printf(-x);else printf(-x%dp

12、-zhishu);else if(p-xishu0)/ 系數大于 0 時if(p-zhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu);else if(p-xishuzhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu); kaiguan=0;else/多項式的其余項都前帶符號輸出if(p-zhishu=0)if(p-xishu!=0) printf(+%dp-xishu);else if(p-xishu=1)if(p-zhishu=1)printf(+x)

13、;else printf(+x%dp-zhishu);else if(p-xishu=-1)if(p-zhishu=1)printf(-x);else printf(-x%dp-zhishu);else if(p-xishu0) / 系數大于 0 時，系數前面帶 “ +” if(p-zhishu=1)printf(+%dxp-xishu);else printf(+%dx%dp-xishup-zhishu);else if(p-xishuzhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu);p=p-next;printf(n

14、);return 1;三、調試分析1. 調試過程中遇到的主要問題是如何解決的； 調試過程中存在少許 C 語言的基礎語法錯誤，經獨立仔細觀察和調試修改正確， 最大的難題是將各多項式按數學格式輸出，經過很多次的調試，還是存在錯誤， 向同學請教，仍不能解決，最后重新修改算法，最終達到輸出要求。部分錯誤：2. 時間和空間復雜度的分析；【1】插入函數：時間0(n2)空間0(n)【2】求和函數：時間0(m+n)空間0(m+n)【3】輸出函數(系數為O的項已被刪除)：時間0(n)空間0(1)3. 改進設想；(1) 求和函數：將多項式a的鏈表復制給多項式C的鏈表，再調用求和函數(b 的鏈表和C的鏈表相加)，將求和的結果插入到 C的鏈表中(作為多項式C)O修改思路：將多項式a的各項先與多項b的各項比較，運算后再插入多項式 C 的鏈表，(由于ab多項式已按指數由小到大排序)修改后時間復雜度降低。(2) 輸出函數：設計按數學格式輸出時，算法多樣。4. 經驗和體會等。深刻體會到多動手的重要性，只有多動手編程，才能熟練靈活的掌握C語言基礎知識，才能更好的理解掌握數據結構的精髓。 從而避免基礎語法錯誤，讓代 碼變得更簡潔高效。如此才能準確高