一元稀疏多項式計算器C語言課程設計.docx

計算機學院軟件工程課程設計報告 學號2014-2015學年 第二學期1308210115軟件工程課程設計報告題目：一元稀疏多項式計算器專業(yè)：計算機科學與技術班級：計算機科學與技術（2）班姓名：指導教師：成績：一、問題描述3二、 需求分析3三、概要設計4四、詳細設計5五、 源代碼6六 、程序測試18七、 使用說明24八、 課設總結25一、問題描述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ù)結構是實踐性很強的課程。課程設計是加強學生實踐能力的一個強有力手段。課程設計要求學生在完成程序設計的同時能夠寫出比較規(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ù)，且滿足0e1e2em=n ,若用一個長度為m且每個元素有兩個數(shù)據(jù)項（系數(shù)項和指數(shù)項）的線性表（p1,e1）,(p2,e2),(pm,em)）便可惟一確定多項式pn(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)上述程序功能，用帶表頭結點的單鏈表存儲多項式。元素類型，節(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（）模塊將最后結果輸出。四、詳細設計開始運行多項式加法計算器退出求積、商求和（差）輸入多項式關閉運行多項式相加求和（差）多項式求積、商建立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)兩個多項式的求和或差值，此模塊先調用輸入模塊，進行對兩個要運算的多項式進行初始化，并按降冪排列。然后將兩個多項式的冪進行一個對比，如果第一個數(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í)行完之后最后調用輸出模塊將結果輸出到屏幕上。4.4求值模塊用戶可通過此模塊實現(xiàn)多項式的求值，此模塊調用輸入模塊，完成相對應的操作，然后需要用戶輸入此時變量的值，并且將變量的值賦值給變量，最后將答案通過輸出模塊輸出到屏幕上。五、 源代碼 鍵入文字6鍵入文字#include#include #include typedef struct Polynomialint coe; /系數(shù)int exp;/指數(shù)struct Polynomial *next;*Polyn,Polynomial; Polyn ma,mb;void Insert(Polyn p,Polyn h) if(p-coe=0) delete p; elsePolyn q1,q2;q1=h;q2=h-next;while(q2&p-expexp) 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-next=p;Polyn CreatePolyn(Polyn head,int m)int i;Polyn p;p=head=new Polynomial;head-next=NULL;for(i=0;im;i+)p=new Polynomial;cout請輸入第i+1p-coe;coutp-exp;Insert(p,head);return head;void 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) cout0; coutcoe0&flag!=1) coutcoe!=1&qa-coe!=-1)coutcoe; if(qa-exp=1) coutexp) coutXexp;elseif(qa-coe=1)if(!qa-exp) coutexp=1) coutX;else coutXexp;if(qa-coe=-1)if(!qa-exp) coutexp=1) cout-X; else cout-Xexp;qa=qa-next; flag+;coutexpb-exp) return 1;else if(!a|a-expexp) 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-exp=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;Polyn 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; /新建一個結點作為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(Polyn 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;temp1=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-next=NULL;remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb);pb=temp1;coutendlshangendl;/printf(t商：);PrintPolyn(quotient);coutyushunext; float result=0; while(p!=NULL) result+=(p-coe)*(float)pow(x,p-exp); p=p-next; return result; void desktop()system(cls);coutendlendlendl 一元多項式的計算endl; cout*endl; cout* 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的值 *endl;cout* 7.退出 *endl;cout*endlendl;cout執(zhí)行操作:;void input()int m,n;/Polyn pa,pb;coutm;ma=CreatePolyn(ma,m);coutendl;coutn;mb=CreatePolyn(mb,n);void main()/int m,n;float x,result;char key;/Polyn pa,pb;coutendlendlendlendl 歡迎您的使用！endl;cout 系統(tǒng)正在初始化數(shù)據(jù)，請稍后.key;switch (key)case1:input();cout多項式a：; PrintPolyn(ma); cout多項式b：; PrintPolyn(mb);break;case2:input();/pc=AddPolyn(pa,pb);cout多項式a：; PrintPolyn(ma); cout多項式b：; PrintPolyn(mb);cout多項式a+b：;PrintPolyn(AddPolyn(ma,mb);/DestroyPolyn(pc);break;case3:input();/pd=SubtractPolyn(pa,pb);cout多項式a：; PrintPolyn(ma); cout多項式b：; PrintPolyn(mb);cout多項式a-b：;PrintPolyn(SubtractPolyn(ma,mb);/DestroyPolyn(pd);break;case4:input();/pd=SubtractPolyn(pa,pb);cout多項式a：; PrintPolyn(ma); cout多項式b：; PrintPolyn(mb);cout多項式a*b：;PrintPolyn(MultiplyPolyn(ma,mb);/DestroyPolyn(pd);break;case5:input();/pd=SubtractPolyn(pa,pb);cout多項式a：; PrintPolyn(ma); cout多項式b：; PrintPolyn(mb);cout多項式a/b：;DevicePolyn(ma,mb);/DestroyPolyn(pd);break;case6:input();cout多項式a：; PrintPolyn(ma);coutx;result=ValuePolyn(ma,x);cout多項式a的值:resultendl;break;case7:DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:coutError!endl;coutendlendl;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+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、如果要進行減法運算，請輸入3，過程和輸入加法一樣，輸入個多項式即可。 3、如果要退出的話，請輸入7即可結束程序的運行。八、 課設總結學完數(shù)據(jù)結構線性表一章后做此題，自覺就想到用帶頭結點的單鏈表來存儲多項式，只需用結點記錄多項式的系數(shù)和指數(shù)，此數(shù)據(jù)結構即節(jié)省空間又好進行操作，且進行運算的主要設計思路也易想到，大體設計結構在較短時間內能夠完成。但當設計到具體細節(jié)代碼時遇到了不少困難，主要困難是進行結點操作時，對指針考慮得不夠細致，調試時常出現(xiàn)指針指錯的情況，沒有認真理清條件層次。完成此