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

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

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

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

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

7、根據(jù)提示輸入每項(xiàng)的系數(shù) 和指數(shù)。(2) 可不按指數(shù)大小順序任意輸入多項(xiàng)式的每項(xiàng)(整數(shù)項(xiàng))。(3) 按數(shù)學(xué)格式輸出ab兩多項(xiàng)式，然后再輸出相加后的和C的多項(xiàng)式4. 詳細(xì)設(shè)計(jì)【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é)點(diǎn)指數(shù)大，則比較鏈表下一個(gè)q=(SLNode*)malloc(SiZeof(SLNode);/ 鏈表中節(jié)點(diǎn)指數(shù)小

8、，則在該節(jié)點(diǎn)前插入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;/ 剩余項(xiàng)的接到 C鏈表的尾部return 1;【3】輸出函數(shù)(系數(shù)為 0 的項(xiàng)已被刪除)：int ListGet(SLNode *head)/輸出SLNode *p; p=head-next;/ 判斷頭結(jié)點(diǎn)為空的輸出/ 判斷頭結(jié)點(diǎn)非空/

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

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