一元稀疏多項(xiàng)式計(jì)算器C語言課程設(shè)計(jì).docx

計(jì)算機(jī)學(xué)院軟件工程課程設(shè)計(jì)報(bào)告 學(xué)號(hào)2014-2015學(xué)年 第二學(xué)期1308210115軟件工程課程設(shè)計(jì)報(bào)告題目：一元稀疏多項(xiàng)式計(jì)算器專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)（2）班姓名：指導(dǎo)教師：成績(jī)：一、問題描述3二、 需求分析3三、概要設(shè)計(jì)4四、詳細(xì)設(shè)計(jì)5五、 源代碼6六 、程序測(cè)試18七、 使用說明24八、 課設(shè)總結(jié)25一、問題描述1.1基本要求（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列：n,c1,e1, c2,e2, cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù)，ci,ei,分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排序；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b；（5）計(jì)算多項(xiàng)式在x處的值。（6）計(jì)算器的仿真界面。1.2設(shè)計(jì)目的數(shù)據(jù)結(jié)構(gòu)是實(shí)踐性很強(qiáng)的課程。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用二、 需求分析2.1 設(shè)計(jì)開發(fā)環(huán)境： 軟件方面：系統(tǒng) windows 7 編程軟件：VC+ 6.02.2思路分析：一般情況下的一元n次多項(xiàng)式可寫成pn(x)=p1xe1+p2xe2+pmxem 其中，p1是指數(shù)為ei的項(xiàng)的非零系數(shù)，且滿足0e1e2em=n ,若用一個(gè)長(zhǎng)度為m且每個(gè)元素有兩個(gè)數(shù)據(jù)項(xiàng)（系數(shù)項(xiàng)和指數(shù)項(xiàng)）的線性表（p1,e1）,(p2,e2),(pm,em)）便可惟一確定多項(xiàng)式pn(x)。用兩個(gè)帶表頭結(jié)點(diǎn)的單鏈表分別存儲(chǔ)兩個(gè)多項(xiàng)式根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則：對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；只需要將第二個(gè)多項(xiàng)式的系數(shù)改為其相反數(shù)，然后根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則便可以得到其相應(yīng)的“差多項(xiàng)式” 三、概要設(shè)計(jì)菜單加法AddPolyn(ma,mb)減法SubtractPolyn(ma,mb)乘法MultiplyPolyn(ma,mb)求值ValuePolyn(ma,x)輸入Insert(Polyn p,Polyn h)除法DevicePolyn(ma,mb)輸出desktop()圖3-1功能模塊圖為實(shí)現(xiàn)上述程序功能，用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。元素類型，節(jié)點(diǎn)類型，和指針類型：typedef struct Polynomialint coe; /系數(shù)int exp;/指數(shù)struct Polynomial *next;*Polyn,Polynomial;各個(gè)模塊之間的調(diào)用如圖3-1所示，調(diào)用insert（）函數(shù)將輸入的多項(xiàng)式按降冪排列，通過主函數(shù)main（）中swith語句，選擇用戶所選擇的對(duì)應(yīng)的模塊，然后又模塊對(duì)應(yīng)的功能函數(shù)對(duì)用戶輸入的數(shù)據(jù)進(jìn)行相應(yīng)的操作，最后通過desktop（）模塊將最后結(jié)果輸出。四、詳細(xì)設(shè)計(jì)開始運(yùn)行多項(xiàng)式加法計(jì)算器退出求積、商求和（差）輸入多項(xiàng)式關(guān)閉運(yùn)行多項(xiàng)式相加求和（差）多項(xiàng)式求積、商建立2個(gè)多項(xiàng)式輸出結(jié)果輸出求和（差）結(jié)果按任意鍵退出圖4-1 功能實(shí)現(xiàn)流程圖4.1 輸入模塊用戶可通過本模塊來輸入一個(gè)多項(xiàng)式，在每次輸入一個(gè)多項(xiàng)式時(shí)，本模塊會(huì)先判斷誰否是第一次輸入，如果是，創(chuàng)建節(jié)點(diǎn)，如果不是則模塊會(huì)通過判斷本次輸入的數(shù)的指數(shù)與第一項(xiàng)輸入的指數(shù)的大小，如果第一項(xiàng)的指數(shù)較大，則剛輸入的這一項(xiàng)繼續(xù)與第二項(xiàng)比較指數(shù)，以此類推，如果發(fā)現(xiàn)剛輸入的這一項(xiàng)的指數(shù)比比較的這一項(xiàng)的指數(shù)要大，則插入比較項(xiàng)的前面。4.2 求和、差模塊用戶通過本模塊可以實(shí)現(xiàn)兩個(gè)多項(xiàng)式的求和或差值，此模塊先調(diào)用輸入模塊，進(jìn)行對(duì)兩個(gè)要運(yùn)算的多項(xiàng)式進(jìn)行初始化，并按降冪排列。然后將兩個(gè)多項(xiàng)式的冪進(jìn)行一個(gè)對(duì)比，如果第一個(gè)數(shù)的第一項(xiàng)的系數(shù)大于第二個(gè)多項(xiàng)式的第一個(gè)項(xiàng)的系數(shù)，那么直接將第一項(xiàng)賦值于剛開始創(chuàng)建的鏈表的第一項(xiàng)，作為答案的最后一項(xiàng)，反之亦然，如果第一個(gè)數(shù)的第一項(xiàng)，與第二個(gè)數(shù)的第一項(xiàng)的系數(shù)相同，那么將兩個(gè)數(shù)的系數(shù)與指數(shù)分別相加或者相減并將對(duì)應(yīng)值賦值給答案相對(duì)應(yīng)的項(xiàng)。以此類推。最后有輸出模塊輸出最后答案。4.3求積、商模塊用戶可通過該模塊實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相乘（相除），此模塊先調(diào)用輸入模塊，進(jìn)行對(duì)兩個(gè)要運(yùn)算的多項(xiàng)式的初始化，并按降冪排列。然后將第一個(gè)數(shù)的系數(shù)、指數(shù)與第二個(gè)數(shù)的系數(shù)、指數(shù)分別相乘（相除），相加（相減），并且賦值給答案相應(yīng)的系數(shù)、指數(shù)。完成后執(zhí)行第一個(gè)數(shù)的第一項(xiàng)與第二個(gè)數(shù)的第二項(xiàng)進(jìn)行相應(yīng)的操作.執(zhí)行完之后最后調(diào)用輸出模塊將結(jié)果輸出到屏幕上。4.4求值模塊用戶可通過此模塊實(shí)現(xiàn)多項(xiàng)式的求值，此模塊調(diào)用輸入模塊，完成相對(duì)應(yīng)的操作，然后需要用戶輸入此時(shí)變量的值，并且將變量的值賦值給變量，最后將答案通過輸出模塊輸出到屏幕上。五、 源代碼 鍵入文字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請(qǐng)輸入第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; /新建一個(gè)結(jié)點(diǎn)作為pa的后繼結(jié)點(diǎn)Polyn qb=pb-next; /新建一個(gè)結(jié)點(diǎn)作為pb的后繼結(jié)點(diǎn)hf=new Polynomial;hf-next=NULL;while(qa)/使用while循環(huán)，使得多項(xiàng)式的每項(xiàng)得以運(yùn)算qb=pb-next;while(qb)pf=new Polynomial;pf-coe=qa-coe*qb-coe;pf-exp=qa-exp+qb-exp;Insert(pf,hf);/調(diào)用插入函數(shù)，將新的結(jié)點(diǎn)插入到新建鏈表中，并合并同類項(xiàng)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; /建立頭結(jié)點(diǎn),存儲(chǔ)商quotient-next=NULL;remainder=new Polynomial; /建立頭結(jié)點(diǎn)，存儲(chǔ)余數(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 一元多項(xiàng)式的計(jì)算endl; cout*endl; cout* 1.輸出多項(xiàng)式a和b *endl; cout* 2.建立多項(xiàng)式a+b *endl; cout* 3.建立多項(xiàng)式a-b *endl;cout* 4.建立多項(xiàng)式a*b *endl;cout* 5.建立多項(xiàng)式a/b *endl;cout* 6.計(jì)算多項(xiàng)式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ù)，請(qǐng)稍后.key;switch (key)case1:input();cout多項(xiàng)式a：; PrintPolyn(ma); cout多項(xiàng)式b：; PrintPolyn(mb);break;case2:input();/pc=AddPolyn(pa,pb);cout多項(xiàng)式a：; PrintPolyn(ma); cout多項(xiàng)式b：; PrintPolyn(mb);cout多項(xiàng)式a+b：;PrintPolyn(AddPolyn(ma,mb);/DestroyPolyn(pc);break;case3:input();/pd=SubtractPolyn(pa,pb);cout多項(xiàng)式a：; PrintPolyn(ma); cout多項(xiàng)式b：; PrintPolyn(mb);cout多項(xiàng)式a-b：;PrintPolyn(SubtractPolyn(ma,mb);/DestroyPolyn(pd);break;case4:input();/pd=SubtractPolyn(pa,pb);cout多項(xiàng)式a：; PrintPolyn(ma); cout多項(xiàng)式b：; PrintPolyn(mb);cout多項(xiàng)式a*b：;PrintPolyn(MultiplyPolyn(ma,mb);/DestroyPolyn(pd);break;case5:input();/pd=SubtractPolyn(pa,pb);cout多項(xiàng)式a：; PrintPolyn(ma); cout多項(xiàng)式b：; PrintPolyn(mb);cout多項(xiàng)式a/b：;DevicePolyn(ma,mb);/DestroyPolyn(pd);break;case6:input();cout多項(xiàng)式a：; PrintPolyn(ma);coutx;result=ValuePolyn(ma,x);cout多項(xiàng)式a的值:resultendl;break;case7:DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:coutError!endl;coutendlendl;system(pause);六 、程序測(cè)試6.1測(cè)試軟件：Microsoft Visual C+ 6.06.2測(cè)試的數(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測(cè)試過程與結(jié)果：(1) A= 3x14-8x8+6x2+2 B=2x10+4x8-6x2 A+B=3x14+2x10-4x8+2圖6-1加法測(cè)試(2) A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A-B=9x14+3x10-x8+5x6-2 圖6-2減法測(cè)試圖(3)A= 5x6+4x5+3x4 B= 6x6+5x5 A*B =30x12+49x11+38x10+15x9 圖6-3乘法測(cè)試(4) A= 5x6+4x5+3x4 X=2 A=496圖6-4求值測(cè)試圖（5）A=2x2 B=x2+1A/B=2余數(shù)是-2；圖6-5除法測(cè)試圖七、 使用說明 程序開始運(yùn)行后，出現(xiàn)如圖界面：圖7-1界面初始圖 1、如果要進(jìn)行加法運(yùn)算，請(qǐng)輸入2，出現(xiàn) 請(qǐng)輸入a的項(xiàng)數(shù)：請(qǐng)輸入第一項(xiàng)的系數(shù)： 就是輸入第一個(gè)多項(xiàng)式的每一項(xiàng)的系數(shù)和指數(shù)。 注意：輸入是隨便輸入的。 如第一個(gè)多項(xiàng)式為5x5; 過程如下： 請(qǐng)輸入a的項(xiàng)數(shù)：1請(qǐng)輸入a的系數(shù)：5請(qǐng)輸入a的指數(shù)：5 接著輸入第2個(gè)多項(xiàng)式的每一項(xiàng)的系數(shù)和指數(shù)。 輸入完以后就直接顯示結(jié)果了：2、如果要進(jìn)行減法運(yùn)算，請(qǐng)輸入3，過程和輸入加法一樣，輸入個(gè)多項(xiàng)式即可。 3、如果要退出的話，請(qǐng)輸入7即可結(jié)束程序的運(yùn)行。八、 課設(shè)總結(jié)學(xué)完數(shù)據(jù)結(jié)構(gòu)線性表一章后做此題，自覺就想到用帶頭結(jié)點(diǎn)的單鏈表來存儲(chǔ)多項(xiàng)式，只需用結(jié)點(diǎn)記錄多項(xiàng)式的系數(shù)和指數(shù)，此數(shù)據(jù)結(jié)構(gòu)即節(jié)省空間又好進(jìn)行操作，且進(jìn)行運(yùn)算的主要設(shè)計(jì)思路也易想到，大體設(shè)計(jì)結(jié)構(gòu)在較短時(shí)間內(nèi)能夠完成。但當(dāng)設(shè)計(jì)到具體細(xì)節(jié)代碼時(shí)遇到了不少困難，主要困難是進(jìn)行結(jié)點(diǎn)操作時(shí)，對(duì)指針考慮得不夠細(xì)致，調(diào)試時(shí)常出現(xiàn)指針指錯(cuò)的情況，沒有認(rèn)真理清條件層次。完成此