數(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 nodeint xs; /*系數(shù)*/int zs;/*指數(shù)*/struct node * next; /*next指針*/Dnode,* Dnodelist;C：設(shè)計本程序需用到八個模塊，用到以下八個子函數(shù)如下：1.Dnodelist Creat_node(void) /*鏈表初始化*/2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函數(shù)*/3.Dnodel

4、ist Creat_Dmeth(int length) /*創(chuàng)建多項式*/4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多項式相減*/6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*選擇函數(shù)*/7void Show(Dnodelist D) /*顯示（輸出）函數(shù)*/8void main()主程序模塊調(diào)用鏈一元多項式的各種基本操作模塊。1.2.2 多項式的輸入 先輸入多項式的項數(shù)

5、，采用尾插法的方式，輸入多項式中一個項的系數(shù)和指數(shù)，就產(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é)點中

6、的系數(shù)相加，若和數(shù)不為零，則修改A所指結(jié)點的系數(shù)值，同時釋放B所指結(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：1輸

7、入一一元多項式的項數(shù)n2YYN結(jié)束開始1：一元多項式的相加2：一元多項式的相減輸入n個非零項再輸入一一元多項式的項數(shù)依次輸入n個非零項調(diào)用加法Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/)；再輸入一一元多項式的項數(shù)依次輸入n個非零項調(diào)用減法Dnodelist Subresult(Dnodelist D1,Dnodelist D2)輸出相加結(jié)果輸出相減結(jié)果Y圖3 主函數(shù)流程圖1.3 系統(tǒng)設(shè)計1.3.1 功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項式程序除了main()函數(shù)外，主要有以下函數(shù)：void Insert(Polyn p,Polyn

8、 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è)計1.main（）函數(shù)main函數(shù)用來實現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算功能。在main（

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

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

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

12、Polyn P)該函數(shù)功能：顯示多項式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤其是第一項的輸出，同時還有符號的控制。在輸出第一項時要判斷是不是常數(shù)項，若是，則不要輸出字符x。9. 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ù)的意義：（1）鏈表初始化函數(shù)Creat_nod

13、e()帶有頭結(jié)點的頭指針指向空（NULL）。（2）多項式數(shù)據(jù)的創(chuàng)建函數(shù)Creat_Dmeth()當(dāng)鏈表初始化成功后，開始創(chuàng)建多項式。分別循環(huán)輸入兩個多項式的系數(shù)和指數(shù)，其中要用到插入函數(shù)。（3）數(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ù)插入到最后。（4）多項式的顯示函數(shù)Show

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

15、別指向兩個多項式表頭的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ù)全部插入到新建多項式中。（7）主函數(shù)main()創(chuàng)建兩個多項式的鏈表并且初始化，分別調(diào)用相應(yīng)的多項式創(chuàng)建函數(shù)，創(chuàng)建成功后選擇運算方

16、式，再將運算結(jié)果輸出顯示。5.其它函數(shù)的介紹請參見附錄中詳細(xì)代碼1.5 調(diào)試及運行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯誤和警告，運行結(jié)果經(jīng)過檢驗為正確。下圖即為該程序運行結(jié)果效果圖。圖中采用的是計算多項式2x2+3x1和3x2+2x3的加減兩種運算進(jìn)行演示：1.6源程序詳見附錄附錄 一元多項式計算源代碼#include<stdio.h>#include<stdlib.h>typedef struct nodeint xs;int zs;struct node * next;Dnode,* Dnodelist; /*定義結(jié)構(gòu)體*/Dnodelist Creat_nod

17、e(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=p->next;if(zs=p->zs) /*指數(shù)相等，系數(shù)直接相加，結(jié)束*/p->xs=p->xs+xs;return 1;else if(zs>p-&

18、gt;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);Dnodelist Creat_Dmeth(int length) /*創(chuàng)建

19、多項式*/int i,m,n;Dnodelist D;D=Creat_node();for(i=0;i<length;i+) /*以三組數(shù)據(jù)為例*/scanf("%d,%d",&m,&n);Insert_node(D,m,n); /*調(diào)用插入函數(shù)，將輸入的系數(shù)指數(shù)插入鏈表*/return D;Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->next

20、;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) /*多項式相減*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->next;while(p&a

21、mp;&q)if(p->zs)<(q->zs) /*指數(shù)?。?的數(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-

22、>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(" 一元多項式的計算 n"); printf("*Menu*n"); printf("* 1 多項式相加 2 多項式相減 *n"); printf("*n");scanf("%d",&s);switc