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

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

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

3、屬；例如，圖1中的兩個(gè)線性鏈表分別表示一元多項(xiàng)式和一元多項(xiàng)式。從圖中可見，每個(gè)結(jié)點(diǎn)表示多項(xiàng)式中的一項(xiàng)。圖1 多項(xiàng)式表的單鏈存儲(chǔ)結(jié)構(gòu)B：本設(shè)計(jì)使用了以下數(shù)據(jù)結(jié)構(gòu)：typedef struct nodeint xs; /*系數(shù)*/int zs;/*指數(shù)*/struct node * next; /*next指針*/Dnode,* Dnodelist;C：設(shè)計(jì)本程序需用到八個(gè)模塊，用到以下八個(gè)子函數(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)建多項(xiàng)式*/4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項(xiàng)式相加*/5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多項(xiàng)式相減*/6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*選擇函數(shù)*/7void Show(Dnodelist D) /*顯示（輸出）函數(shù)*/8void main()主程序模塊調(diào)用鏈一元多項(xiàng)式的各種基本操作模塊。1.2.2 多項(xiàng)式的輸入 先輸入多項(xiàng)式的項(xiàng)數(shù)

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

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

7、入一一元多項(xiàng)式的項(xiàng)數(shù)n2YYN結(jié)束開始1：一元多項(xiàng)式的相加2：一元多項(xiàng)式的相減輸入n個(gè)非零項(xiàng)再輸入一一元多項(xiàng)式的項(xiàng)數(shù)依次輸入n個(gè)非零項(xiàng)調(diào)用加法Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項(xiàng)式相加*/)；再輸入一一元多項(xiàng)式的項(xiàng)數(shù)依次輸入n個(gè)非零項(xiàng)調(diào)用減法Dnodelist Subresult(Dnodelist D1,Dnodelist D2)輸出相加結(jié)果輸出相減結(jié)果Y圖3 主函數(shù)流程圖1.3 系統(tǒng)設(shè)計(jì)1.3.1 功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項(xiàng)式程序除了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è)計(jì)1.main（）函數(shù)main函數(shù)用來實(shí)現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運(yùn)算函數(shù)實(shí)現(xiàn)運(yùn)算功能。在main（

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

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

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

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

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

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

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

16、式，再將運(yùn)算結(jié)果輸出顯示。5.其它函數(shù)的介紹請(qǐng)參見附錄中詳細(xì)代碼1.5 調(diào)試及運(yùn)行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯(cuò)誤和警告，運(yùn)行結(jié)果經(jīng)過檢驗(yàn)為正確。下圖即為該程序運(yùn)行結(jié)果效果圖。圖中采用的是計(jì)算多項(xiàng)式2x2+3x1和3x2+2x3的加減兩種運(yùn)算進(jìn)行演示：1.6源程序詳見附錄附錄 一元多項(xiàng)式計(jì)算源代碼#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、多項(xiàng)式*/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) /*多項(xiàng)式相加*/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) /*多項(xiàng)式相減*/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ù)小（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-

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