1、精選優(yōu)質文檔-傾情為你奉上學號2016-2017學年 第二學期網絡工程課程設計報告題目：一元稀疏多項式計算器專業(yè)：網絡工程班級：網絡工程（3）班姓名：代應豪指導教師：代美麗成績：一、問題描述1.1基本要求（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列：n,c1,e1, c2,e2, cn,en,其中n是多項式的項數(shù)，ci,ei,分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排序；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式a-b；（5）計算多項式在x處的值。（6）計算器的仿真界面。1.2設計目的數(shù)據(jù)結構是實踐性很強的課程。課程設計是加強學生實踐能力的一個

2、強有力手段。課程設計要求學生在完成程序設計的同時能夠寫出比較規(guī)范的設計報告。嚴格實施課程設計這一環(huán)節(jié)，對于學生基本程序設計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用二、 需求分析2.1 設計開發(fā)環(huán)境： 軟件方面：系統(tǒng) windows 7 編程軟件：VC+ 6.02.2思路分析：一般情況下的一元n次多項式可寫成pn(x)=p1xe1+p2xe2+pmxem 其中，p1是指數(shù)為ei的項的非零系數(shù)，且滿足0e1<e2<<em=n ,若用一個長度為m且每個元素有兩個數(shù)據(jù)項（系數(shù)項和指數(shù)項）的線性表（p1,e1）,(p2,e2),(pm,em)）便可惟一確定多項式pn(

3、x)。用兩個帶表頭結點的單鏈表分別存儲兩個多項式根據(jù)一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應系數(shù)相加，若其和不為零，則構成“和多項式”中的一項；只需要將第二個多項式的系數(shù)改為其相反數(shù)，然后根據(jù)一元多項式相加的運算規(guī)則便可以得到其相應的“差多項式” 三、概要設計菜單加法AddPolyn(ma,mb)減法SubtractPolyn(ma,mb)乘法MultiplyPolyn(ma,mb)求值ValuePolyn(ma,x)輸入Insert(Polyn p,Polyn h)除法DevicePolyn(ma,mb)輸出desktop()圖3-1功能模塊圖為實現(xiàn)上述程序功能，

4、用帶表頭結點的單鏈表存儲多項式。元素類型，節(jié)點類型，和指針類型：typedef struct Polynomialint coe; /系數(shù)int exp;/指數(shù)struct Polynomial *next;*Polyn,Polynomial;各個模塊之間的調用如圖3-1所示，調用insert（）函數(shù)將輸入的多項式按降冪排列，通過主函數(shù)main（）中swith語句，選擇用戶所選擇的對應的模塊，然后又模塊對應的功能函數(shù)對用戶輸入的數(shù)據(jù)進行相應的操作，最后通過desktop（）模塊將最后結果輸出。四、詳細設計開始運行多項式加法計算器退出求積、商求和（差）輸入多項式關閉運行多項式相加求和（差）多項式

5、求積、商建立2個多項式輸出結果輸出求和（差）結果按任意鍵退出圖4-1 功能實現(xiàn)流程圖4.1 輸入模塊用戶可通過本模塊來輸入一個多項式，在每次輸入一個多項式時，本模塊會先判斷誰否是第一次輸入，如果是，創(chuàng)建節(jié)點，如果不是則模塊會通過判斷本次輸入的數(shù)的指數(shù)與第一項輸入的指數(shù)的大小，如果第一項的指數(shù)較大，則剛輸入的這一項繼續(xù)與第二項比較指數(shù)，以此類推，如果發(fā)現(xiàn)剛輸入的這一項的指數(shù)比比較的這一項的指數(shù)要大，則插入比較項的前面。4.2 求和、差模塊用戶通過本模塊可以實現(xiàn)兩個多項式的求和或差值，此模塊先調用輸入模塊，進行對兩個要運算的多項式進行初始化，并按降冪排列。然后將兩個多項式的冪進行一個對比，如果第一

6、個數(shù)的第一項的系數(shù)大于第二個多項式的第一個項的系數(shù)，那么直接將第一項賦值于剛開始創(chuàng)建的鏈表的第一項，作為答案的最后一項，反之亦然，如果第一個數(shù)的第一項，與第二個數(shù)的第一項的系數(shù)相同，那么將兩個數(shù)的系數(shù)與指數(shù)分別相加或者相減并將對應值賦值給答案相對應的項。以此類推。最后有輸出模塊輸出最后答案。4.3求積、商模塊用戶可通過該模塊實現(xiàn)兩個多項式的相乘（相除），此模塊先調用輸入模塊，進行對兩個要運算的多項式的初始化，并按降冪排列。然后將第一個數(shù)的系數(shù)、指數(shù)與第二個數(shù)的系數(shù)、指數(shù)分別相乘（相除），相加（相減），并且賦值給答案相應的系數(shù)、指數(shù)。完成后執(zhí)行第一個數(shù)的第一項與第二個數(shù)的第二項進行相應的操作.執(zhí)

7、行完之后最后調用輸出模塊將結果輸出到屏幕上。4.4求值模塊用戶可通過此模塊實現(xiàn)多項式的求值，此模塊調用輸入模塊，完成相對應的操作，然后需要用戶輸入此時變量的值，并且將變量的值賦值給變量，最后將答案通過輸出模塊輸出到屏幕上。五、 源代碼 專心-專注-專業(yè)#include<iostream.h>#include <stdlib.h>#include <math.h> typedef struct Polynomialint coe; /系數(shù)int exp;/指數(shù)struct Polynomial *next;*Polyn,Polynomial; Polyn ma

8、,mb;void Insert(Polyn p,Polyn h) if(p->coe=0) delete p; elsePolyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp) q1=q2;q2=q2->next;if(q2&&p->exp=q2->exp) q2->coe+=p->coe;delete p;if(!q2->coe) q1->next=q2->next;delete q2;else p->next=q2;q1-&g

9、t;next=p;Polyn CreatePolyn(Polyn head,int m)int i;Polyn p;p=head=new Polynomial;head->next=NULL;for(i=0;i<m;i+)p=new Polynomial;cout<<"請輸入第"<<i+1<<"項的系數(shù):"cin>>p->coe;cout<<" 指數(shù):"cin>>p->exp;Insert(p,head);return head;void

10、DestroyPolyn(Polyn p)Polyn t;while(p!=NULL)t=p;p=p->next;delete t;void PrintPolyn(Polyn Pm) Polyn qa=Pm->next; int flag=1;if(!qa) cout<<"0" cout<<endl;return; while (qa)if(qa->coe>0&&flag!=1) cout<<"+" if(qa->coe!=1&&qa->coe!=-1

11、)cout<<qa->coe; if(qa->exp=1) cout<<"X"else if(qa->exp) cout<<"X"<<qa->exp;elseif(qa->coe=1)if(!qa->exp) cout<<"1"else if(qa->exp=1) cout<<"X"else cout<<"X"<<qa->exp;if(qa->co

12、e=-1)if(!qa->exp) cout<<"-1" else if(qa->exp=1) cout<<"-X" else cout<<"-X"<<qa->exp;qa=qa->next; flag+;cout<<endl;int compare(Polyn a,Polyn b)if(a&&b)if(!b|a->exp>b->exp) return 1;else if(!a|a->exp<b->e

13、xp) return -1;else return 0;else if(!a&&b) return -1;else return 1;Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=new Polynomial;hc->next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;switch(compare(qa,qb)case 1:qc->coe=qa->coe;qc->e

14、xp=qa->exp;qa=qa->next;break;case 0: qc->coe=qa->coe+qb->coe;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;case -1:qc->coe=qb->coe;qc->exp=qb->exp;qb=qb->next;break; if(qc->coe!=0)qc->next=hc->next;hc->next=qc;hc=qc;else delete qc;return headc;Po

15、lyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p) p->coe*=-1;p=p->next;pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) p->coe*=-1;return pd;Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;/Polyn qa=pa->next; /新建一個結點作為pa的后繼結點Polyn qb=pb->next; /新

16、建一個結點作為pb的后繼結點hf=new Polynomial;hf->next=NULL;while(qa)/使用while循環(huán)，使得多項式的每項得以運算qb=pb->next;while(qb)pf=new Polynomial;pf->coe=qa->coe*qb->coe;pf->exp=qa->exp+qb->exp;Insert(pf,hf);/調用插入函數(shù)，將新的結點插入到新建鏈表中，并合并同類項qb=qb->next;qa=qa->next;return hf;/返回所得鏈表的頭指針void DevicePolyn(P

17、olyn pa,Polyn pb) Polyn quotient,remainder,temp1,temp2;Polyn qa=pa->next;Polyn qb=pb->next;quotient=new Polynomial; /建立頭結點,存儲商quotient->next=NULL;remainder=new Polynomial; /建立頭結點，存儲余數(shù)remainder->next=NULL;temp1=new Polynomial;temp1->next=NULL;temp2=new Polynomial;temp2->next=NULL;te

18、mp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp)temp2->next=new Polynomial;temp2->next->coe=(qa->coe)/(qb->coe);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,quotient);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2);qa=pa->next;temp2-&g

19、t;next=NULL;remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb);pb=temp1;cout<<endl<<"shang"<<endl;/printf("t商：");PrintPolyn(quotient);cout<<"yushu"<<endl;/printf("t余數(shù)：");PrintPolyn(remainder);float ValuePolyn(Polyn head,floa

20、t x)Polyn p; p=head->next; float result=0; while(p!=NULL) result+=(p->coe)*(float)pow(x,p->exp); p=p->next; return result; void desktop()system("cls");cout<<endl<<endl<<endl<<" 一元多項式的計算"<<endl; cout<<"*"<<endl; cout&

21、lt;<"* 1.輸出多項式a和b *"<<endl; cout<<"* 2.建立多項式a+b *"<<endl; cout<<"* 3.建立多項式a-b *"<<endl;cout<<"* 4.建立多項式a*b *"<<endl;cout<<"* 5.建立多項式a/b *"<<endl;cout<<"* 6.計算多項式a的值 *"<<en

22、dl;cout<<"* 7.退出 *"<<endl;cout<<"*"<<endl<<endl;cout<<"執(zhí)行操作:"void input()int m,n;/Polyn pa,pb;cout<<"請輸入多項式a的項數(shù):"cin>>m;ma=CreatePolyn(ma,m);cout<<endl;cout<<"請輸入多項式b的項數(shù):"cin>>n;mb=Cre

23、atePolyn(mb,n);void main()/int m,n;float x,result;char key;/Polyn pa,pb;cout<<endl<<endl<<endl<<endl<<" 歡迎您的使用！"<<endl;cout<<" 系統(tǒng)正在初始化數(shù)據(jù)，請稍后."<<endl; _sleep(3*1000);system("cls");while(key)desktop();cin>>key;switch (

24、key)case'1':input();cout<<"多項式a：" PrintPolyn(ma); cout<<"多項式b：" PrintPolyn(mb);break;case'2':input();/pc=AddPolyn(pa,pb);cout<<"多項式a：" PrintPolyn(ma); cout<<"多項式b：" PrintPolyn(mb);cout<<"多項式a+b："PrintPoly

25、n(AddPolyn(ma,mb);/DestroyPolyn(pc);break;case'3':input();/pd=SubtractPolyn(pa,pb);cout<<"多項式a：" PrintPolyn(ma); cout<<"多項式b：" PrintPolyn(mb);cout<<"多項式a-b："PrintPolyn(SubtractPolyn(ma,mb);/DestroyPolyn(pd);break;case'4':input();/pd=Sub

26、tractPolyn(pa,pb);cout<<"多項式a：" PrintPolyn(ma); cout<<"多項式b：" PrintPolyn(mb);cout<<"多項式a*b："PrintPolyn(MultiplyPolyn(ma,mb);/DestroyPolyn(pd);break;case'5':input();/pd=SubtractPolyn(pa,pb);cout<<"多項式a：" PrintPolyn(ma); cout<&

27、lt;"多項式b：" PrintPolyn(mb);cout<<"多項式a/b："DevicePolyn(ma,mb);/DestroyPolyn(pd);break;case'6':input();cout<<"多項式a：" PrintPolyn(ma);cout<<"輸入x的值：x="cin>>x;result=ValuePolyn(ma,x);cout<<"多項式a的值:"<<result<<

28、;endl;break;case'7':DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:cout<<"Error!"<<endl;cout<<endl<<endl;system("pause");六 、程序測試6.1測試軟件：Microsoft Visual C+ 6.06.2測試的數(shù)據(jù)：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10x6+

29、5 B=2x14+3x8+5x6+7(3) A*B A= 5x6+4x5+3x4 B= 6x6+5x5 (4) A= 5x6+4x5+3x4 X=2(5) A/B A=2x2 B=x2+16.3測試過程與結果：(1) A= 3x14-8x8+6x2+2 B=2x10+4x8-6x2 A+B=3x14+2x10-4x8+2圖6-1加法測試(2) A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A-B=9x14+3x10-x8+5x6-2 圖6-2減法測試圖(3)A= 5x6+4x5+3x4 B= 6x6+5x5 A*B =30x12+49x11+38x10+15x9 圖6-3乘法測試(4) A= 5x6+4x5+3x4 X=2 A=496圖6-4求值測試圖（5）A=2x2 B=x2+1A/B=2余數(shù)是-2；圖6-5除法測試圖七、 使用說明 程序開始運行后，出現(xiàn)如圖界面：圖7-1界面初始圖 1、如果要進行加法運算，請輸入2，出現(xiàn) 請輸入a的項數(shù)：請輸入第一項的系數(shù)： 就是輸入第一個多項式的每一項的系數(shù)和指數(shù)。 注意：輸入是隨便輸入的。 如第一個多項式為5x5; 過程如下： 請輸入a的項數(shù)：1請輸入a的系數(shù)：5請輸入a的指數(shù)：5 接著輸入第2個多項式的每一項的系數(shù)和指數(shù)。 輸入完以后就直接顯示結果了：2、如果要進行減法