實習一線性表及其應(yīng)用(題目：一元稀疏多項式的加法運算)

1、實習一 線性表及其應(yīng)用 (題目：一元稀疏多項式的加法運算 )一、需求分析1. 輸入并建立兩個多項式；2. 多項式 a 與 b 相加，建立和多項式 c ；3. 輸出多項式abc。輸出格式：比如多項式 a為：A(X)=C1xe1 +c2xe2+ CmXem其中，Ci和ei分別為第i項的系數(shù)和指數(shù)，且各項按指數(shù)的升幕排列，即0eKe2vvem。多項式bc類似輸出。4 測試數(shù)據(jù)( 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)實習一 線性表及 其應(yīng)用題目：一元稀疏多項式的加法運算 實習時間： 2012/9/20.10.12一、需求分析1. 輸入并建立兩個多項式；2. 多項式a與b相加，建立和多項式c；3. 輸出多項式abc。輸出格式：比如多項式 a為：A(X)=C1xe1 +c2xe2+ CmXem其中，Ci和ei分別為第i項的系數(shù)和指數(shù)，且各項按指數(shù)的升幕排列，即0eKe2vvem。多項式bc類似輸出。4 測試數(shù)據(jù)( 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)二、設(shè)計1. 設(shè)計思想(1 )存儲結(jié)構(gòu) 用帶頭結(jié)點的單鏈表存儲多項式。三個多項式鏈表中都只存儲非零系數(shù)項。若多項式a與b中指數(shù)相等的兩項相加后，系數(shù)為零，則在和多項式C中不存儲該指數(shù)項。(2)主要算法基本思想 按照鏈表的基本操作，初始化三個鏈表，在兩個鏈表中按指數(shù)由小到大分別 插入a和b的多項式(系數(shù)和指數(shù))，將多項式a的鏈表復(fù)制給多項式C的鏈表, 再調(diào)用求和函數(shù)( b 的鏈表和 c 的鏈表相加)，將求和的結(jié)果插入到 c 的鏈表中 (作為多項式C)最后輸出多項式a, b, C三個多項式。【1】插入

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

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

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

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

8、，則在該節(jié)點前插入q-XiShu=XiShu;q-ZhiShu=ZhiShu;q-neXt=NULL;q-neXt=p-neXt;p-neXt=q;return 1;【2】求和函數(shù)：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】輸出函數(shù)(系數(shù)為 0 的項已被刪除)：int ListGet(SLNode *head)/輸出SLNode *p; p=head-next;/ 判斷頭結(jié)點為空的輸出/ 判斷頭結(jié)點非空/

11、多項式第一項的輸出/ 當指數(shù)為時，只輸出系數(shù) 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)/ 系數(shù)為 1 時輸出 Xzhishui 或 xif(p-zhishu=1)printf(x);else printf(x%dp-zhishu);else if(p-xishu=-1) / 系數(shù)為-1 時輸出-Xzhishui或-Xif(p-zhishu=1)printf(-x);else printf(-x%dp

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