數(shù)據(jù)結(jié)構(gòu) 一元多項式的計算

1、項目一 一元多項式的計算問題1.1設(shè)計題目與要求1.1.1設(shè)計題目1） 一元多項式計算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將 結(jié)果輸入；基本要求：在上交資料中請寫明：存儲結(jié)構(gòu)、多項式相加的基本過程的算法（可以使用程序 流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進(jìn)方法; 本程序關(guān)鍵點是如何將輸入的兩個多項式相加、相減操作。如何將輸入的一元多項式按指數(shù)的降序排列如何確定要輸入的多項式的項數(shù)；如何將輸入的兩個一元多項式顯示出來。如何將輸入的兩個一元多項式進(jìn)行相加操作。如何將輸入的兩個一元多項式進(jìn)行相減操作。本程序是通過鏈表實現(xiàn)一

2、元多項式的相加減操作。1.1.2、任務(wù)定義此程序需要完成如下的要求：將多項式按照指數(shù)降序排列建立并輸出，將兩個一元多項式進(jìn) 行相加、相減操作，并將結(jié)果輸入。a：輸入多項式的項數(shù)并建立多項式；b：輸出多項式，輸出形式分別為浮點和整數(shù)序列，序列按指數(shù)升序排列；c：多項式a和b相加，建立多項式a+b；d：多項式a和b相減，建立多項式a-b。e：多項式的輸出。1.2數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計：1.2.1數(shù)據(jù)結(jié)構(gòu)的選用A:基于鏈表中的節(jié)點可以動態(tài)生成的特點，以及鏈表可以靈活的添加或刪除節(jié)點的數(shù)據(jù)結(jié) 構(gòu)，為了實現(xiàn)任意多項式的加法，減法，因此選擇單鏈表的結(jié)構(gòu)體，它有一個系數(shù)，指數(shù)， 下一個指針3個元屬；例如，

3、圖1中的兩個線性鏈表分別表示一元多項式和一元多項式。從圖中可見，每個結(jié)點表示多項 式中的一項。圖1 多項式表的單鏈存儲結(jié)構(gòu)B：本設(shè)計使用了以下數(shù)據(jù)結(jié)構(gòu)： typedef struct node int xs; int zs;struct node * next;Dnode,* Dnodelist;C：設(shè)計本程序需用到八個模塊，用到以下八個子函數(shù)如下： 1.Dnodelist Creat_node(void)/*鏈表初始化*/2.int Insert_node(Dnodelist D,intDnodelistDnodelistDnodelistDnodelist/*系數(shù)*/*指數(shù)*/*next

4、指針*/xs,int zs)Creat_Dmeth(int length)Addresult(Dnodelist D1,Dnodelist D2)Subresult(Dnodelist D1,Dnodelist D2) select(Dnodelist D1,Dnodelist D2)/*插入函數(shù)*/*創(chuàng)建多項式*/*多項式相加*/*多項式相減*/*選擇函數(shù)*/7void Show(Dnodelist D)/*顯示(輸出)函數(shù)*/8void main ()主程序模塊調(diào)用鏈一元多項式的各種基本操作模塊。1.2.2多項式的輸入先輸入多項式的項數(shù)，采用尾插法的方式，輸入多項式中一個項的系數(shù)和指數(shù)，就

5、產(chǎn)生一個 新的節(jié)點，建立起它的右指針，并用頭節(jié)點指向它；1.2.3兩個多項式的加法“和多項式”鏈表中的結(jié)點無需另生成，而應(yīng)該從兩個多項式的鏈表中摘取。其運算 規(guī)則如下：假設(shè)指針A和B分別指向多項式a和多項式b中當(dāng)前進(jìn)行比較的某個結(jié)點，則比較兩個結(jié)點 中的指數(shù)項，有下列3種情況：指針A所指結(jié)點的指數(shù)值指針B所指結(jié)點的指數(shù)值，則應(yīng)摘取A指針?biāo)附Y(jié)點插入到“和 多項式”鏈表中去；指針A所指結(jié)點的指數(shù)值指針B所指結(jié)點的指數(shù)值，則應(yīng)摘取指針A所指結(jié)點插入到“和 多項式”鏈表中去；指針A所指結(jié)點的指數(shù)值=指針B所指結(jié)點的指數(shù)值，則將兩個結(jié)點中的系數(shù)相加，若和數(shù)不為零，則修改A所指結(jié)點的系數(shù)值，同時釋放B所

6、指結(jié)點；反之，從多項式A的鏈 表中刪除相應(yīng)結(jié)點，并釋放指針A和B所指結(jié)點。例如，由圖2中的兩個鏈表表示的多項式 相加得到的“和多項式”鏈表如圖2所示，圖中的長方框表示已被釋放的結(jié)點。圖2相加得到的和多項式上述多項式的相加過程歸并兩個有序表的過程極其類似，不同之處僅在于，后者 在比較數(shù)據(jù)元素時只出現(xiàn)兩種情況。因此，多項式相加的過程也完全可以利用線性鏈表的基 本操作來完成。1.2.4流程圖（1）在主函數(shù)中調(diào)用函數(shù)進(jìn)行多項式的輸入、輸出，運用選擇語句來選擇加法、減法進(jìn)行 操作，流程圖如圖3：圖3 主函數(shù)流程圖1.3系統(tǒng)設(shè)計1.3.1功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項式程序除7main()函數(shù)外，主要有

7、以下函數(shù)：void Insert(Polyn p,Polyn h)Polyn CreatePolyn(Polyn head,int m)void DestroyPolyn(Polyn p)void PrintPolyn(Polyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn MultiplyPolyn(Polyn pa,Polyn pb)1.3.2系統(tǒng)主要功能函數(shù)的詳細(xì)設(shè)計main()函數(shù)main函數(shù)用來實現(xiàn)提示使用者輸入、顯

8、示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算功能。在main()函數(shù)中，定義m、n用來保存兩個多項式的項數(shù)，pa、pb、pc、pd、pf定義程序 所需鏈表的頭指針。在程序開始要求輸入兩個多項式的項數(shù)，隨后根據(jù)項數(shù)創(chuàng)建兩個鏈表以 保存多項式，再顯示出功能列表后通過if語句來實現(xiàn)功能的選擇，從而對整個程序流程進(jìn) 行控制。Polyn CreatePolyn(Polyn head,int m)該函數(shù)功能是創(chuàng)建新的多項式鏈表。intm保存的多項式的項數(shù)，使用for語句，控制輸入 多項式的每一項。當(dāng)創(chuàng)建的鏈表長度為m時，將不再提示用戶繼續(xù)輸入多項式的系數(shù)和指數(shù)。 在該函數(shù)中要用到分配空間的函數(shù)malloc()為新

9、建鏈表分配空間。void DestroyPolyn(Polyn p)該函數(shù)的功能是銷毀掉創(chuàng)建的兩個鏈表，釋放內(nèi)存。以輔助退出程序。void Insert(Polyn p,Polyn h)該函數(shù)功能：將新的節(jié)點？插入到現(xiàn)有鏈表的后面，并確保多項式的指數(shù)exp是升序。將s 節(jié)點插入到head所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。Polyn AddPolyn(Polyn pa,Polyn pb)該函數(shù)功能：實現(xiàn)兩個多項式pa、pb相加，并將計算結(jié)果存儲于新建立的pc中，它的原理 是將指數(shù)相同的單項式相加，系數(shù)相加后為0，則pa、pb的指針都后移。在加法計算中要 求pa,與pb的冪次

10、序都是升序，否則可能得到錯誤的結(jié)果。該函數(shù)調(diào)用了 int compare(Polyn a,Polyn b)的結(jié)果，用來判斷多項式在同一指數(shù)下a、b 是否有為系數(shù)為0。同樣也使用7malloc()關(guān)鍵字，為新鏈表創(chuàng)建空間。int compare(Polyn a,Polyn b)該函數(shù)功能：判斷兩個多項式在同一指數(shù)下是否有其中一個為系數(shù)為0。用來輔助加法和乘 法運算。Polyn SubtractPolyn(Polyn pa,Polyn pb)該函數(shù)功能：實現(xiàn)兩個多項式pa、pb相減，其原理根加法類似，將指數(shù)相同的指數(shù)相減。 與加法不同的是在送在減法中，創(chuàng)建了新的鏈表來存放結(jié)果，并返回該鏈表的頭指針

11、。void PrintPolyn(Polyn P)該函數(shù)功能：顯示多項式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤其是第一項 的輸出，同時還有符號的控制。在輸出第一項時要判斷是不是常數(shù)項，若是，則不要輸出字 符x。Polyn MultiplyPolyn(Polyn pa,Polyn pb)函數(shù)功能：實現(xiàn)兩個多項式相乘，A(X) * B(x)。計算時運用單項式與多項式相乘的法則， 然后再次運用單項式與多項式相乘的法則。1.4系統(tǒng)實現(xiàn)該程序?qū)崿F(xiàn)了多項式的創(chuàng)建、多項式的加法、減法、乘法運算以及多項式的清除。為完成這 些功能，還用到了一些輔助函數(shù)。下面討論重要函數(shù)具體實現(xiàn)過程及其參數(shù)的意義：鏈表

12、初始化函數(shù)Creat_node()帶有頭結(jié)點的頭指針指向空(NULL)。多項式數(shù)據(jù)的創(chuàng)建函數(shù)Creat_Dmeth()當(dāng)鏈表初始化成功后，開始創(chuàng)建多項式。分別循環(huán)輸入兩個多項式的系數(shù)和指數(shù)，其中 要用到插入函數(shù)。數(shù)據(jù)的插入函數(shù)Insert_node()當(dāng)創(chuàng)建多項式時，要用到此函數(shù)，即利用插入的方式將多項式的數(shù)據(jù)連接起來。再輸入 一組數(shù)據(jù)后，程序自動調(diào)用此函數(shù)，插入時也進(jìn)行著排序，從表頭的next開始，一一比較 指數(shù)大小，直到大于或等于當(dāng)前指向的數(shù)據(jù)或遍歷完所有數(shù)據(jù)時停止，然后開始鏈表中數(shù)值 的插入，如果相等則直接將指數(shù)相加，如果大于就將新數(shù)據(jù)插入到當(dāng)前指向的前面，否則將 新數(shù)據(jù)插入到最后。多項

13、式的顯示函數(shù)Show()從多項式表頭的next開始，直到指向空(NULL)，將系數(shù)與指數(shù)一一顯示。選擇運算方式的函數(shù)select()三種選擇：1為相加，2為相減，每一種選擇調(diào)用相應(yīng)的運算函數(shù)。多項式的運算函數(shù)：新建鏈表存儲計算后的多項式1、多項式相加Addresult()創(chuàng)建兩個指針分別指向兩個多項式表頭的next，分別使用兩個while函數(shù)獨自循環(huán)， 遍歷各自的每一組數(shù)據(jù)，每遍歷一次都將系數(shù)與指數(shù)存儲到新建多項式的鏈表中。因為存儲 時利用到插入函數(shù)，而插入函數(shù)中有相同指數(shù)的系數(shù)相加功能，所以直接將兩個多項式的數(shù) 據(jù)依次插入到新的多項式中即可完成多項式相加。2、多項式相減Subresult()

14、創(chuàng)建兩個指針分別指向兩個多項式表頭的next，以兩個指針同時不為空為條件循環(huán)遍 歷，如果當(dāng)前多項式1的指數(shù)小于多項式2,則將當(dāng)前多項式2的系數(shù)置負(fù)，指數(shù)不變，存 入新建多項式中，指向多項式2的指針指向下一個；如果如果當(dāng)前多項式1的指數(shù)大于多項 式2,則將當(dāng)前多項式1的系數(shù)指數(shù)不變，存入新建多項式中，指向多項式1的指針指向下 一個；否則將多項式1的系數(shù)減去2的系數(shù)后存入新建多項式中，指數(shù)不變存入，再將兩個 指針同時指向下一個。結(jié)束循環(huán)后判斷是哪一個多項式遍歷完了，將未遍歷完的多項式剩下 的數(shù)據(jù)全部插入到新建多項式中。主函數(shù)main()創(chuàng)建兩個多項式的鏈表并且初始化，分別調(diào)用相應(yīng)的多項式創(chuàng)建函數(shù)，

15、創(chuàng)建成功后選擇 運算方式，再將運算結(jié)果輸出顯示。5.其它函數(shù)的介紹請參見附錄I中詳細(xì)代碼1.5調(diào)試及運行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯誤和警告，運行結(jié)果經(jīng)過檢驗為正確。下圖即為該程序 運行結(jié)果效果圖。圖中采用的是計算多項式2x2+3x1和3x2+2x3的加減兩種運算進(jìn)行演示：Duicua.eii1: s and Sett元爭惠雖式日-算，目直號a前.入昇頊1.式|自勺可|親0鎘入多項式1系數(shù).指數(shù).孕組）2 2 3 1新入?yún)㈨椢?的組數(shù);云項式*效,招婁以組-元多項式的計岸*1多項式相力n2多項 式和減割HHXWHHXK XX XX HXXXHXXXH XX X H H X K XX

16、 X H X H XX XX XX與加結(jié)果系數(shù)，指教，二+*Pt*cs3 ansi kcv continueBBSGt *C z DaciuLen 3 and Setl ing-sl&dMinist ratorYDebugX.-元妾娘式ti岸=ckc 輸多正式的狙淞：偷入多頁-3系救,指我；任組LX LI輸入多項式3的組數(shù),愉入冬項式2系效，指數(shù)；3,2 2,3元客項）盤丁十第* i專m.式扣加2多m式相域*箱誠結(jié)果系數(shù)指數(shù) K：U1 Press anj/ ko to continue1.6源程序詳見附錄I附錄I 一元多項式計算源代碼#include #include typedef stru

17、ct node int xs; int zs; struct node * next; Dnode,* Dnodelist;/*定義結(jié)構(gòu)體*/Dnodelist Creat_node(void)/*鏈表初始化*/ Dnodelist D; D=(Dnodelist)malloc(sizeof(Dnode); if(D) D-next=NULL; return D; int Insert_node(Dnodelist D,int xs,int zs)/*插入函數(shù)*/ Dnodelist p; Dnodelist q; Dnodelist r; p=D; while(p-next) r=p; p=

18、p-next; if(zs=p-zs)/*指數(shù)相等，系數(shù)直接相加，結(jié)束*/ p-xs=p-xs+xs; return 1; else if(zsp-zs) /*指數(shù)大于當(dāng)前數(shù)據(jù)的，將數(shù)據(jù)插入當(dāng)前數(shù)據(jù)之前，結(jié)束*/ q=Creat_node(); q-xs=xs; q-zs=zs; r-next=q; q-next=p; return 1; /*while(p-next)*/ q=Creat_node();/*要插入的數(shù)據(jù)指數(shù)最小，直接插入至鏈表最后*/q-xs=xs;q-zs=zs;q-next=p-next;p-next=q;return 1;free(p);free(q);free(r);

19、Dnodelist Creat_Dmeth(int length)/*創(chuàng)建多項式*/int i,m,n;Dnodelist D;D=Creat_node();for(i=0;inext;q=D2-next;while(q)x=q-xs;z=q-zs;Insert_node(D,x,z);q=q-next;while(p)x=p-xs;z=p-zs;Insert_node(D,x,z);p=p-next;/*直接插入數(shù)據(jù)，利用插入函數(shù)可完成該功能*/return D; Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多項式相減*/ Dnodeli

20、st D; Dnodelist p,q; int x,z; D=Creat_node(); p=D1-next; q=D2-next; while(p&q) if(p-zs)zs)/*指數(shù)小(1的數(shù)據(jù)在2中不存在)，直接插入*/ x=-(q-xs);/*由于是式1減式2,所以系數(shù)置負(fù)*/z=q-zs; Insert_node(D,x,z); q=q-next; else if(p-zs)(q-zs) /*指數(shù)大(2的數(shù)據(jù)在1中不存在)，直接插入*/ x=p-xs; z=p-zs; Insert_node(D,x,z); p=p-next; else/*指數(shù)相同的先將系數(shù)相減，再插入*/ z=q-zs; x=(p-xs)-(q-xs); Insert_node(D,x,z); p=p-next; q=q-next; /*while(p&q)*/ while(p) x=p-xs; z=p-zs; Insert_node(D,x,z); p=p-next; while(q) x=-(q-zs);z=q-zs;Insert_node(D,x,z);q=q-next;/*將未遍歷完的數(shù)據(jù)直接插入*/return D;Dnodelist select(Dnodelist D1,Dnodelist D2)/*選擇函數(shù)*/Dnodelist D;int s;printf(一元多項式