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

計算機學院軟件工程課程設計報告 學號2014-2015學年 第二學期1308210115軟件工程課程設計報告題目：一元稀疏多項式計算器專業(yè)：計算機科學與技術班級：計算機科學與技術（2）班姓名：指導教師：成績：一、問題描述3二、 需求分析3三、概要設計4四、詳細設計5五、 源代碼6六 、程序測試18七、 使用說明24八、 課設總結25一、問題描述1.1基本要求（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數序列：n,c1,e1, c2,e2, cn,en,其中n是多項式的項數，ci,ei,分別是第i項的系數和指數，序列按指數降序排序；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式a-b；（5）計算多項式在x處的值。（6）計算器的仿真界面。1.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是指數為ei的項的非零系數，且滿足0e1e2em=n ,若用一個長度為m且每個元素有兩個數據項（系數項和指數項）的線性表（p1,e1）,(p2,e2),(pm,em)）便可惟一確定多項式pn(x)。用兩個帶表頭結點的單鏈表分別存儲兩個多項式根據一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數相同的項，對應系數相加，若其和不為零，則構成“和多項式”中的一項；只需要將第二個多項式的系數改為其相反數，然后根據一元多項式相加的運算規(guī)則便可以得到其相應的“差多項式” 三、概要設計菜單加法AddPolyn(ma,mb)減法SubtractPolyn(ma,mb)乘法MultiplyPolyn(ma,mb)求值ValuePolyn(ma,x)輸入Insert(Polyn p,Polyn h)除法DevicePolyn(ma,mb)輸出desktop()圖3-1功能模塊圖為實現上述程序功能，用帶表頭結點的單鏈表存儲多項式。元素類型，節(jié)點類型，和指針類型：typedef struct Polynomialint coe; /系數int exp;/指數struct Polynomial *next;*Polyn,Polynomial;各個模塊之間的調用如圖3-1所示，調用insert（）函數將輸入的多項式按降冪排列，通過主函數main（）中swith語句，選擇用戶所選擇的對應的模塊，然后又模塊對應的功能函數對用戶輸入的數據進行相應的操作，最后通過desktop（）模塊將最后結果輸出。四、詳細設計開始運行多項式加法計算器退出求積、商求和（差）輸入多項式關閉運行多項式相加求和（差）多項式求積、商建立2個多項式輸出結果輸出求和（差）結果按任意鍵退出圖4-1 功能實現流程圖4.1 輸入模塊用戶可通過本模塊來輸入一個多項式，在每次輸入一個多項式時，本模塊會先判斷誰否是第一次輸入，如果是，創(chuàng)建節(jié)點，如果不是則模塊會通過判斷本次輸入的數的指數與第一項輸入的指數的大小，如果第一項的指數較大，則剛輸入的這一項繼續(xù)與第二項比較指數，以此類推，如果發(fā)現剛輸入的這一項的指數比比較的這一項的指數要大，則插入比較項的前面。4.2 求和、差模塊用戶通過本模塊可以實現兩個多項式的求和或差值，此模塊先調用輸入模塊，進行對兩個要運算的多項式進行初始化，并按降冪排列。然后將兩個多項式的冪進行一個對比，如果第一個數的第一項的系數大于第二個多項式的第一個項的系數，那么直接將第一項賦值于剛開始創(chuàng)建的鏈表的第一項，作為答案的最后一項，反之亦然，如果第一個數的第一項，與第二個數的第一項的系數相同，那么將兩個數的系數與指數分別相加或者相減并將對應值賦值給答案相對應的項。以此類推。最后有輸出模塊輸出最后答案。4.3求積、商模塊用戶可通過該模塊實現兩個多項式的相乘（相除），此模塊先調用輸入模塊，進行對兩個要運算的多項式的初始化，并按降冪排列。然后將第一個數的系數、指數與第二個數的系數、指數分別相乘（相除），相加（相減），并且賦值給答案相應的系數、指數。完成后執(zhí)行第一個數的第一項與第二個數的第二項進行相應的操作.執(zhí)行完之后最后調用輸出模塊將結果輸出到屏幕上。4.4求值模塊用戶可通過此模塊實現多項式的求值，此模塊調用輸入模塊，完成相對應的操作，然后需要用戶輸入此時變量的值，并且將變量的值賦值給變量，最后將答案通過輸出模塊輸出到屏幕上。五、 源代碼 鍵入文字6鍵入文字#include#include #include typedef struct Polynomialint coe; /系數int exp;/指數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);/調用插入函數，將新的結點插入到新建鏈表中，并合并同類項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; /建立頭結點，存儲余數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)正在初始化數據，請稍后.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測試的數據：(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余數是-2；圖6-5除法測試圖七、 使用說明 程序開始運行后，出現如圖界面：圖7-1界面初始圖 1、如果要進行加法運算，請輸入2，出現 請輸入a的項數：請輸入第一項的系數： 就是輸入第一個多項式的每一項的系數和指數。 注意：輸入是隨便輸入的。 如第一個多項式為5x5; 過程如下： 請輸入a的項數：1請輸入a的系數：5請輸入a的指數：5 接著輸入第2個多項式的每一項的系數和指數。 輸入完以后就直接顯示結果了：2、如果要進行減法運算，請輸入3，過程和輸入加法一樣，輸入個多項式即可。 3、如果要退出的話，請輸入7即可結束程序的運行。八、 課設總結學完數據結構線性表一章后做此題，自覺就想到用帶頭結點的單鏈表來存儲多項式，只需用結點記錄多項式的系數和指數，此數據結構即節(jié)省空間又好進行操作，且進行運算的主要設計思路也易想到，大體設計結構在較短時間內能夠完成。但當設計到具體細節(jié)代碼時遇到了不少困難，主要困難是進行結點操作時，對指針考慮得不夠細致，調試時常出現指針指錯的情況，沒有認真理清條件層次。完成此