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

1、項(xiàng)目一 一元多項(xiàng)式的計(jì)算問題1.1設(shè)計(jì)題目與要求設(shè)計(jì)題目1）一元多項(xiàng)式計(jì)算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；基本要求：在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(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)一元多

2、項(xiàng)式的相加減操作。、任務(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ì):數(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è)元屬；例如，圖1中的兩個(gè)線性鏈表分

3、別表示一元多項(xiàng)式 k：沁總餞曲;矢沙和一元多項(xiàng)式' ：。從圖中可見，每個(gè)結(jié)點(diǎn)表示多項(xiàng)式中的一項(xiàng)。圖i多項(xiàng)式表的單鏈存儲(chǔ)結(jié)構(gòu)B:本設(shè)計(jì)使用了以下數(shù)據(jù)結(jié)構(gòu)：typedef struct no deint xs;/*系數(shù) */int zs;/* 指數(shù) */struct node * n ext;/*n ext指針 */ Dn ode,* Dn odelist;C:設(shè)計(jì)本程序需用到八個(gè)模塊，用到以下八個(gè)子函數(shù)如下:鏈表初始化*/插入函數(shù)*/ 創(chuàng)建多項(xiàng)式*/ 多項(xiàng)式相加*/ 多項(xiàng)式相減*/ 選擇函數(shù)*/ 顯示(輸出)函數(shù)*/1. Dn odelist Creat_ no de(void)/*2.

4、i nt In sert_ no de(D no delist D,i nt xs,i nt zs)/*3. D nodelist Creat_Dmeth( int len gth)/*4. Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*5. Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*6. D nodelist select(D nodelist D1,D no delist D2) /*7void Show(D nodelist D)/*8void mai n()主程序模塊調(diào)用鏈一元多

5、項(xiàng)式的各種基本操作模塊。多項(xiàng)式的輸入先輸入多項(xiàng)式的項(xiàng)數(shù)，采用尾插法的方式， 輸入多項(xiàng)式中一個(gè)項(xiàng)的系數(shù)和指數(shù)，就產(chǎn)生一個(gè)新的節(jié)點(diǎn)，建立起它的右指針，并用頭節(jié)點(diǎn)指向它；兩個(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)的

6、指數(shù)值=指針B所指結(jié)點(diǎn)的指數(shù)值，則將兩個(gè)結(jié)點(diǎn)中的系數(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）在主函數(shù)中調(diào)用函數(shù)進(jìn)行多項(xiàng)式的輸入、輸出，運(yùn)用選擇語句來選擇加法、減法進(jìn)行 操作，流程圖如圖 3：開始依次輸入

7、 n個(gè)非零/輸出相減結(jié) /結(jié)束圖3 主函數(shù)流程圖1.3 系統(tǒng)設(shè)計(jì)功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項(xiàng)式程序除了 main() 函數(shù)外，主要有以下函數(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 MultiplyP

8、olyn(Polyn pa,Polyn pb)系統(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 ()函數(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ù)，使用f

9、or語句，控制輸入多項(xiàng)式的每一項(xiàng)。當(dāng)創(chuàng)建的鏈表長度為 m時(shí)，將不再提示用戶繼續(xù)輸入多項(xiàng)式的系數(shù)和指數(shù)。 在該函數(shù)中要用到分配空間的函數(shù) malloc() 為新建鏈表分配空間。3. void DestroyPolyn(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ù)功能

10、：實(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)用了 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 Subtra

11、ctPolyn(Polyn pa,Polyn pb)該函數(shù)功能：實(shí)現(xiàn)兩個(gè)多項(xiàng)式 pa、 pb 相減，其原理根加法類似，將指數(shù)相同的指數(shù)相減。 與加法不同的是在送在減法中，創(chuàng)建了新的鏈表來存放結(jié)果，并返回該鏈表的頭指針。8. void PrintPolyn(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) 。

12、計(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_node()帶有頭結(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ù)， 即利用插入的方式將多

13、項(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()從多項(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)式相加

14、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è)指針分別指向兩個(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è)； 如果如果

15、當(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)算方式，再將運(yùn)算結(jié)果輸出顯示。5.其它函數(shù)的介紹請(qǐng)參見附錄I中詳細(xì)代碼1.5調(diào)試及運(yùn)行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯(cuò)誤和警告，運(yùn)行結(jié)果經(jīng)過檢驗(yàn)為正確。下圖即為該

16、程序運(yùn)行結(jié)果效果圖。示：圖中采用的是計(jì)算多項(xiàng)式2xA2+3xA1和3xA2+2xA3的加減兩種運(yùn)算進(jìn)行演1.6源程序詳見附錄I附錄I 一元多項(xiàng)式計(jì)算源代碼#include<stdio.h>#include<stdlib.h> typedef struct nodeint xs;int zs;struct node * next;定義結(jié)構(gòu)體 */鏈表初始化 */Dnode,* Dnodelist; /*Dnodelist Creat_node(void) /* Dnodelist D;D=(Dnodelist)malloc(sizeof(Dnode); if(D)D-&g

17、t;next=NULL;return D;int Insert_node(Dnodelist D,int xs,int zs) Dnodelist p;Dnodelist q;Dnodelist r; p=D; while(p->next) r=p; p=p->next; if(zs=p->zs) /*/*插入函數(shù) */指數(shù)相等，系數(shù)直接相加，結(jié)束*/p->xs=p->xs+xs;return 1;指數(shù)大于當(dāng)前數(shù)據(jù)的，將數(shù)據(jù)插入當(dāng)前數(shù)據(jù)之前，結(jié)束*/ else if(zs>p->zs) /*q=Creat_node();q->xs=xs;q-&g

18、t;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)建多項(xiàng)式 */int i,m,n;Dnodelist D;D=Creat_node();for(i=0;i<leng

19、th;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;while(q)x=q->xs;z=q->zs;Insert_node(D,x,z);q=q

20、->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&&q)if(p->zs)<(q->zs) /*x=-(q->x

21、s); /* z=q->zs; Insert_node(D,x,z); q=q->next;else if(p->zs)>(q->zs) /*x=p->xs;z=p->zs;Insert_node(D,x,z); p=p->next;else /*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,

22、x,z);指數(shù)?。?1 的數(shù)據(jù)在 2 中不存在），直接插入 */由于是式 1 減式 2，所以系數(shù)置負(fù) */指數(shù)大（ 2的數(shù)據(jù)在 1 中不存在），直接插入 */指數(shù)相同的先將系數(shù)相減，再插入 */p=p->next; while(q)x=-(q->zs);z=q->zs;Insert_node(D,x,z); q=q->next; /* return D;將未遍歷完的數(shù)據(jù)直接插入 */Dnodelist select(Dnodelist D1,Dnodelist D2) /*Dnodelist D;int s;printf("一元多項(xiàng)式的計(jì)算printf("*Menu*n"); printf("* 1多項(xiàng)式相加2printf("*n");選擇函數(shù) */n");多項(xiàng)式相減 *n"）;scanf("%d",&s);switch(s)case 1:D=Addresult(D1