1、 課程設計報告 課程設計題目： 一元多項式計算 學生姓名： 汪世生 專 業： 軟件工程 班 級： 1521822z 學 號: 201520180325 指導教師： 徐洪珍 2016年 12月 23日第1頁目錄(Contents):(1).課程設計任務(2).實驗目的 第3頁實驗要求(1).主菜單運算流程圖 第4頁程序主流程圖(1).主要功能性函數(2).過程 第5頁實驗過程(1).算法代碼：加法，減法，乘法， 降冪算法，合并同類項算法(2) .時間復雜度：以上所有算法(3) .流程圖 ： 加法，減法，乘法 第619頁.算法思想(1)測試算法：減法，加法，乘法 第2022頁.測試結果 第23頁.

2、實驗體會及心得 第24頁.課程設計評分表 第2頁一：實驗要求1任務：（1）能夠按照指數降序排列建立并輸出多項式。（2）能夠完成兩個多項式的相加、相減，并將結果輸出；在上交資料中請寫明：存儲結構、多項式相加的基本過程的算法（可以使用程序流程圖） 、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法； （3）除此任務要求之外；增加了一個多項式相乘的功能。 （4）測試2個多項式：1： 3*X3 +2*X2+X 2：2*X2+X2. 實驗目的： （1）掌握鏈式存儲結構方法，熟悉鏈表的創建。 （2）掌握鏈表的排序的算法。 （3）掌握鏈表的插入與刪除的算法。 （4）設計合適的算法實現對兩

3、個多項式進行相加、相減與相乘的基本運算，并對程序的健壯性進行提高；第3頁開始二：程序主流程圖 結束是否退出顯示運算后的多項式指數相同的項數系數相加指數相同的項數系數相減兩個多項式各項相乘，然后對指數相同項合并同類項減法運算乘法運算運算菜單選項創建2個多項式定義函數名稱定義結構體 加法運算否否是第4頁三：實驗過程1 創建以下主要功能性函數 首先要創建以下各個功能性函數，同時提高程序的運算效率，減小時間的復雜度。 /typedef Ststus int;Status Create_polynomial(Linklist & L); /創建多項式的算法Status Sort(Linklist

4、 L,int n); /多項式降冪排序的算法Status Add_polynomial(Linklist L1,Linklist L2); /多項式加法的算法Status Sub_polynomial(Linklist L1,Linklist L2); /多項式減法的算法Status Mul_polynomial(Linklist L1,Linklist L2); /多項式相乘的算法Status Com_polynomial(Linklist L); /合并同類項的算法2 過程 先創建L1， L2兩個多項式，調用Sort() 函數進行各項降冪排序；然后調用各個函數進行加法、減法、乘法運算,在運

5、算的時候得到的每個非零項存儲在L3中，再對得到的L3進行輸出到顯示屏上。第5頁四：算法思想1 主要算法 Mul_polynomial(Linklist L1,Linklist L2); /多項式相乘的算法 Add_polynomial(Linklist L1,Linklist L2); /多項式加法的算法 Sub_polynomial(Linklist L1,Linklist L2); /多項式減法的算法 Sort(Linklist L,int n); /多項式降冪排序的算法 Com_polynomial(Linklist L); /合并同類項的算法2一元多項式的乘法運算L1*L2=L3已知L

6、1，L2先從其中一個多項式的第一項開始分別與第二個多項式的每一項相乘，系數相乘指數相加；此算法采用嵌套while()循環，先從一個多項式的頭結點p開始與第二個多項式的每一項相乘，將相乘后的各個非零數據建立新的結點插入到新的L3鏈表中，直到第一個多項式p=NULL的時候結束。然后對相乘后的數據進行合并同類項，也就是指數相同的項系數相加，這里的算法主要運用刪除結點的算法，對指數相同的的項系數相加，然后刪除后一個結點。（1） 乘法運算流程圖（下頁）：第6頁已知兩個多項式L1與L2 輸出未合并同類項的相乘后的多項式調用Mul_poly()函數進行多項式相乘對相乘后的多項式調用Com_poly()函數合

7、并同類項其他運算輸出合并同類項后的相乘后的多項式退出？否是退出？否是結束（2）乘法運算算法的代碼：其時間復雜度為: T(n)=O(L1*L2)，L1與L2分別為兩項多項式的項數。 Status Mul_polynomial(Linklist L1,Linklist L2) /多項式相乘int a=0,n=0; /a是一個哨兵，n用于統計相乘后的項數Linklist p1,p2,p; Linklist L3; /L3用于存儲相乘后的多項式L3=(Linklist)malloc(sizeof(LNode);L3->next=NULL;第7頁p1=L1;p1=p1->next;p2=L2

8、;p2=p2->next;while(p1!=NULL)while(p2!=NULL)n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef*p2->coef;p->expn=p1->expn+p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;p1=p1->next;p2=L2->next;Sort(L3,n); /對相乘后的多項式調用Sort()降冪函數cout<<"兩多項式相乘為(未合并同類項

9、)"Show_polynomial(L3); /對相乘后的多項式輸出Com_polynomial(L3,n); /調用Com_poly()函數合并同類項cout<<"兩多項式相乘 (合并同類項后)顯示如下:n"L3=L3->next;while(L3) /對相乘后的多項式輸出if(L3->coef!=0)if(L3->coef)>0 && a!=0)第8頁cout<<" + "cout<<L3->coef<<"*X"<<

10、L3->expn;elsecout<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK;3 一元多項式加法運算 L1+L2=L3 它從兩個多項式的頭部開始，兩個多項式L1，L2的某一項都不為空時，如果指數相等的話，系數就應該相加；相加的和不為零的話，用頭插法建立一個新的節點插入到L3中。p1的指數小于p2的指數的話就應該復制p2的節點到L3中。P1的指數大于p2的指數的話，就應該復p1節點到

11、L3中。當L2多項式空，L1多項式不為空時，將L1剩余項插入到L3中。當L1多項式空，第L2多項式不為空時，將L2剩余項插入到L3中。（1）加法運算流程圖（后頁）：第9頁已知兩個多項式L1與L2調用Add_poly()函數進行相加 輸出相加后的多項式其他運算是否退出是否退出否否是是結束 （2）加法運算算法代碼:其時間復雜度 T(n)=O(L1+L2) ，L1與L2各為兩個多項式的項數。Status Add_polynomial(Linklist L1,Linklist L2) /多項式的加法L1+L2int a=0,n=0;Linklist p,p1,p2,pd;Linklist L3; /用

12、于存儲相加后的多項式p1=L1->next;p2=L2->next;L3=(Linklist)malloc(sizeof(LNode); L3->next=NULL;while(p1!=NULL && p2!=NULL)第10頁if(p1->expn<p2->expn) /L2項中指數大于L1項中指數，插入L2項n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p2->coef;p->expn=p2->expn;p->next=L3->next;L3->next

13、=p;p2=p2->next;else if(p1->expn>p2->expn) /L1項中指數大于L2項中指數，插入L1項n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;else /L2項中指數等于L1項中指數，系數相加pd=(Linklist)malloc(sizeof(LNode);pd->coef=p1->coef+p2->

14、coef;pd->expn=p1->expn;if(pd->coef!=0)n+;p=(Linklist)malloc(sizeof(LNode);第11頁p->coef=pd->coef;p->expn=pd->expn; p->next=L3->next;L3->next=p;p1=p1->next;p2=p2->next;elsep1=p1->next;p2=p2->next;delete pd;while(p1!=NULL) /插入L1剩余項p=(Linklist)malloc(sizeof(LNode

15、);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next; L3->next=p;p1=p1->next;if(p2!=NULL) /插入L1剩余項p=(Linklist)malloc(sizeof(LNode);p->coef=p2->coef;p->expn=p2->expn;p->next=L3->next;第12頁 L3->next=p;p2=p2->next;cout<<"相加后多項式為:"L3=L3->

16、next; while(L3)if(L3->coef)>0 && a!=0)cout<<" + "cout<<L3->coef<<"*X"<<L3->expn;elsecout<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK; 4一元多項式的減法運算L1-L2=L3

17、它從兩個多項式的頭部開始，兩個多項式L1，L2的某一項都不為空時，如果指數相等的話，系數就應該相減；相減的值不為零的話，用頭插法建立一個新的節點插入到L3中。p1的指數小于p2的指數的話就應該復制p2的節點到L3中，并且該項系數取相反數。P1的指數大于p2的指數的話，就應該復p1第13頁節點到L3中。當L2多項式空，L1多項式不為空時，將L1剩余項插入到L3中。當L1多項式空，第L2多項式不為空時，將L2剩余項插入到L3中，并把所有項系數取相反數。已知兩個多項式L1與L2（1）減法運算流程圖：調用Sub-poly()函數進行相減 其他運算輸出相減后的多項式是否退出否否是否退出 是是 結束（2）

18、減法運算算法代碼：其時間復雜度為 T(n)=O(L1+L2) ，L1與L2各為兩個多項式的項數。Status Sub_polynomial(Linklist L1,Linklist L2) /多項式的減法L1-L2 int a=0,n=0; /a是一個哨兵，n用于統計項數Linklist p,p1,p2,pd;第14頁p1=L1->next;p2=L2->next;L3=(Linklist)malloc(sizeof(LNode); /用于存儲相減后的多項式L3->next=NULL;while(p1!=NULL && p2!=NULL)if(p1->e

19、xpn<p2->expn) /L2項中指數大于L1項中指數，插入L2項 ，且系數取相反數 n+;p=(Linklist)malloc(sizeof(LNode);p->coef=-(p2->coef);p->expn=p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;else if(p1->expn>p2->expn) /L1項中指數大于L2項中指數，插入L1項 n+;p=(Linklist)malloc(sizeof(LNode);p->coef=p1->

20、coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;else /L2項中指數等于L1項中指數，系數相加第15頁pd=(Linklist)malloc(sizeof(LNode);pd->coef=p1->coef-p2->coef;pd->expn=p1->expn;if(pd->coef!=0)n+;p=(Linklist)malloc(sizeof(LNode);p=pd; p->next=L3->next; L3->next=p

21、;p1=p1->next;p2=p2->next;elsep1=p1->next;p2=p2->next;delete pd;while(p1!=NULL) /L1非空，插入剩余項p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;第16頁while(p2!=NULL) /L2非空，插入剩余項，且系數取相反數p=(Linklist)malloc(sizeof(LN

22、ode);p->coef= -(p2->coef);p->expn=p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;cout<<"相減后多項式為:"L3=L3->next; while(L3)if(L3->coef)>0 && a!=0)cout<<" + "cout<<L3->coef<<"*X"<<L3->expn;elsecou

23、t<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK;第17頁5. 對各個多項式進行降冪排序的算法 時間復雜度為: T(n)=O(n*n) ,n為多項式L的項數。Status Sort(Linklist L,int n) /多項式降冪的算法int a;float b;Linklist p;p=L;p=p->next;for(i=1;i<n;i+)for(j=i;j<n;j+)

24、if(p->expn)<(p->next->expn)a=p->expn; /交換指數p->expn=p->next->expn; p->next->expn=a;b=p->coef; /交換系數p->coef=p->next->coef;p->next->coef=b;p=p->next;p=L->next;return OK;第18頁6. 合并同類項算法 注意:這個算法只進行一次合并同類項，需要在這個函數外加一個for循環，最 大次數為這個多項式的項數。 時間復雜度為: T(n)=O

25、(n*n)，n為多項式L的項數 Status Com_polynomial(Linklist L,int n) /對多項式進行合并同類項Linklist p;int i;for(i=0;i<n;i+) /最多有n項相同，n為項數p=L;p=p->next;while(p->next) if(p->expn=p->next->expn) /若指數相同，則系數相加，刪除后一項p->coef=p->coef+p->next->coef; p->next=p->next->next;p=p->next;elsep=p->next;return OK; 第19頁五：測試結果1 創建多項式；用戶從鍵盤輸入項數，然后輸入每個項的系數與指數創建兩個多項式 L1: 3*X3+2*X2+X L2: 2*X2+X2 顯示這兩個多項式