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

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

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

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

5、，采用尾插法的方式，輸入多項式中一個項的系數和指數，就產生一個新的節點，建立起它的右指針，并用頭節點指向它；1.2.3 兩個多項式的加法 “和多項式”鏈表中的結點無需另生成，而應該從兩個多項式的鏈表中摘取。其運算規則如下：假設指針A和B分別指向多項式a和多項式b中當前進行比較的某個結點，則比較兩個結點中的指數項，有下列3種情況：指針A所指結點的指數值<指針B所指結點的指數值，則應摘取A指針所指結點插入到“和多項式”鏈表中去；指針A所指結點的指數值>指針B所指結點的指數值，則應摘取指針A所指結點插入到“和多項式”鏈表中去；指針A所指結點的指數值=指針B所指結點的指數值，則將兩個結點中

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

7、入一一元多項式的項數n2YYN結束開始1：一元多項式的相加2：一元多項式的相減輸入n個非零項再輸入一一元多項式的項數依次輸入n個非零項調用加法Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/)；再輸入一一元多項式的項數依次輸入n個非零項調用減法Dnodelist Subresult(Dnodelist D1,Dnodelist D2)輸出相加結果輸出相減結果Y圖3 主函數流程圖1.3 系統設計1.3.1 功能算法描述與數據結構說明該多項式程序除了main()函數外，主要有以下函數：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 系統主要功能函數的詳細設計1.main（）函數main函數用來實現提示使用者輸入、顯示功能列表、調用其他運算函數實現運算功能。在main（

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

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

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

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

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

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

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

16、式，再將運算結果輸出顯示。5.其它函數的介紹請參見附錄中詳細代碼1.5 調試及運行結果該程序在VC6.0中調試通過，沒有錯誤和警告，運行結果經過檢驗為正確。下圖即為該程序運行結果效果圖。圖中采用的是計算多項式2x2+3x1和3x2+2x3的加減兩種運算進行演示：1.6源程序詳見附錄附錄 一元多項式計算源代碼#include<stdio.h>#include<stdlib.h>typedef struct nodeint xs;int zs;struct node * next;Dnode,* Dnodelist; /*定義結構體*/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) /*插入函數*/Dnodelist p;Dnodelist q;Dnodelist r;p=D;while(p->next) r=p;p=p->next;if(zs=p->zs) /*指數相等，系數直接相加，結束*/p->xs=p->xs+xs;return 1;else if(zs>p-&

18、gt;zs) /*指數大于當前數據的，將數據插入當前數據之前，結束*/q=Creat_node();q->xs=xs;q->zs=zs;r->next=q;q->next=p;return 1;/*while(p->next)*/q=Creat_node(); /*要插入的數據指數最小，直接插入至鏈表最后*/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) /*創建

19、多項式*/int i,m,n;Dnodelist D;D=Creat_node();for(i=0;i<length;i+) /*以三組數據為例*/scanf("%d,%d",&m,&n);Insert_node(D,m,n); /*調用插入函數，將輸入的系數指數插入鏈表*/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; /*直接插入數據，利用插入函數可完成該功能*/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) /*指數小（1的數據在2中不存在），直接插入*/x=-(q->xs); /*由于是式1減式2，所以系數置負*/z=q->zs;Insert_node(D,x,z);q=q->next;else if(p->zs)>(q->zs) /*指數大（2的數據在1中不存在），直接插入*/ x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;else /*指數相同的先將系數相減，再插入*/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; /*將未遍歷完的數據直接插入*/return D;Dnodelist select(Dnodelist D1,Dnodelist D2) /*選擇函數*/Dnodelist D;int s; printf(" 一元多項式的計算 n"); printf("*Menu*n"); printf("* 1 多項式相加 2 多項式相減 *n"); printf("*n");scanf("%d",&s);switc