數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告一元多項(xiàng)式加減乘除(精)

1、PAGE PAGE 31多項(xiàng)式想加減與乘與升降序?qū)W 院 計(jì)算機(jī)科學(xué)與技術(shù) 專(zhuān) 業(yè) 信 息 安 全 學(xué) 號(hào) 201312070 學(xué) 生 姓 名 陶寶中 輔導(dǎo)教師姓名 2014年12月 22 日設(shè)計(jì)目的與內(nèi)容 了解數(shù)據(jù)結(jié)構(gòu)的與算法的設(shè)計(jì)方法，獨(dú)立分析和設(shè)計(jì)一元多項(xiàng)式加減與乘除的程序編碼，通過(guò)程序編寫(xiě)掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析，系統(tǒng)設(shè)計(jì)，程序編碼，測(cè)試等基本方法和技能，提高綜合運(yùn)用所學(xué)理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力，通過(guò)這次實(shí)踐將實(shí)驗(yàn)問(wèn)題中的所涉及的對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)他們進(jìn)行處理，掌握線除 。 任務(wù)與分析 本課題主要的目的是分別采用順序和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一元多項(xiàng)式的加法、減法和乘法。

2、并將操作結(jié)果分別按升序和降序輸出程序的主要功能一元多項(xiàng)式創(chuàng)建建立一元多項(xiàng)式的順序表和鏈?zhǔn)奖恚闯绦蛱崾据斎朊總€(gè)項(xiàng)數(shù)據(jù)結(jié)束創(chuàng)建。借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的關(guān)系，順序表中第i個(gè)位置表示一元多項(xiàng)式的第i項(xiàng)的系數(shù)為第i個(gè)位置存放的內(nèi)容，指數(shù)為i-1。創(chuàng)建一個(gè)一元多項(xiàng)式順序表，對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種情況進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減、相乘操作。用鏈表來(lái)表示只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)term項(xiàng)結(jié)構(gòu)和指向下一個(gè)節(jié)點(diǎn)的指針域，term又包括系數(shù)和指數(shù)兩個(gè)域分別存放該項(xiàng)的系數(shù)、。創(chuàng)建一元多項(xiàng)式鏈表，對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種可能情況

3、進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減、相乘操作。一元多項(xiàng)式的加法 對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)不相同的項(xiàng)，則分別復(fù)抄到和多項(xiàng)式中去。一元多項(xiàng)式的減法對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相減，若其差不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)不相同的項(xiàng)，將其按減法規(guī)則復(fù)抄到差多項(xiàng)式中去。一元多項(xiàng)式的乘法將乘法運(yùn)算分解為一系列的加法運(yùn)算利用兩個(gè)一元多項(xiàng)式相加的算法實(shí)現(xiàn)。一元多項(xiàng)式項(xiàng)的指數(shù)比較比較相鄰兩項(xiàng)的指數(shù)的大小。按升序排列時(shí)，前面項(xiàng)的指數(shù)大于后面項(xiàng)的指數(shù)就交換其項(xiàng)的位置。

4、按降序序排列時(shí)，后面項(xiàng)的指數(shù)大于前面項(xiàng)的指數(shù)就交換其項(xiàng)的位置。一元多項(xiàng)式運(yùn)算結(jié)果升降排序一元多項(xiàng)式運(yùn)算結(jié)果選擇調(diào)用降序或升序排序函數(shù)。一元多項(xiàng)式的輸出將選擇的運(yùn)算操作結(jié)果輸出。一元多項(xiàng)式的銷(xiāo)毀銷(xiāo)毀已建立的兩個(gè)多項(xiàng)式，釋放空間。3 程序運(yùn)行平臺(tái)VC+6.0。 編譯，鏈接，執(zhí)行。 Windows XP。4 總體設(shè)計(jì) 圖4。1 系統(tǒng)總體框架圖主 函 數(shù)創(chuàng)建多項(xiàng)式多項(xiàng)式加法多項(xiàng)式減法多項(xiàng)式乘法多項(xiàng)式升降序 多項(xiàng)式輸出5 程序類(lèi)的說(shuō)明 （1）Ploy結(jié)構(gòu)聲明typedef struct /順序表結(jié)構(gòu)聲明 int aN;/記錄多項(xiàng)式 int len;/記錄多項(xiàng)式的長(zhǎng)度Ploy; （2）term結(jié)構(gòu)聲明 t

5、ypedef struct /項(xiàng)的表示 float coef; /系數(shù) int expn; /指數(shù)term;（3）LNode結(jié)構(gòu)聲明typedef struct LNode term data; /term多項(xiàng)式值 struct LNode *next;LNode,*LinkList; /兩個(gè)類(lèi)型名typedef LinkList polynomail; /用帶頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式6 模塊分析 整個(gè)流程圖如圖所示：圖16.1 創(chuàng)建模塊6.1.1、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的一元多項(xiàng)式的創(chuàng)建程序源代碼：polynomail creatpolyn(polynomail P,int m) /輸入m項(xiàng)的系數(shù)和

6、指數(shù)，建立表示一元多項(xiàng)式的有序鏈表Ppolynomail r,q,p,s,Q;int i; P=(LNode*)malloc(sizeof(LNode); r=P;for(i=0;idata.coef,&s-data.expn); r-next=s;r=s;r-next=NULL;if(P-next-next!=NULL) for(q=P-next;q!=NULL/*&q-next!=NULL*/;q=q-next)/合并同類(lèi)項(xiàng)for(p=q-next,r=q;p!=NULL;)if(q-data.expn=p-data.expn)q-data.coef=q-data.coef+p-data.

7、coef;r-next=p-next;Q=p;p=p-next;free(Q);else r=r-next;p=p-next;return P;6.1.2、順序存儲(chǔ)結(jié)構(gòu)一元多項(xiàng)式的創(chuàng)建程序源代碼：void GetPloy(Ploy *A)int i,coef,ex,maxe=0; char ch; printf(請(qǐng)輸入每個(gè)項(xiàng)的系數(shù)及對(duì)應(yīng)的指數(shù)，指數(shù)為負(fù)數(shù)時(shí)標(biāo)志輸入結(jié)束！n); for(i=0;iai=0;scanf(%d%d,&coef,&ex); while(ex=0) if(exmaxe) maxe=ex;if(A-aex!=0)printf(你輸入的項(xiàng)已經(jīng)存在，是否更新原數(shù)據(jù)？（Y/N）

8、);cinch; if(ch=Y|ch=y) A-aex=coef;printf(更新成功，請(qǐng)繼續(xù)輸入！n); elseprintf(請(qǐng)繼續(xù)輸入！n);else A-aex=coef;scanf(%d%d,&coef,&ex); A-len=maxe; return ;6.2 一元多項(xiàng)式的加法6.2.1 鏈?zhǔn)酱鎯?chǔ)兩多項(xiàng)式相加程序源代碼：polynomail addpolyn(polynomail pa,polynomail pb) /完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa+Pbpolynomail s,newp,q,p,r;int j;p=pa-next;q=pb-next; newp=(LNod

9、e*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data)case -1: s-data.coef=p-data.coef;s-data.expn=p-data.expn;r-next=s; r=s;p=p-next;break;case 0: s-data.coef=p-data.coef+q-data.coef;if(s-data.coef!=0.0) s-data.expn=p-data.expn;r-next=s;r=s;p=p-next; q

10、=q-next; break;case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break;/switch/while6.2.2 順序存儲(chǔ)的多項(xiàng)式相加程序源代碼：void ADD(Ploy A,Ploy B,Ploy *M)/*多項(xiàng)式A與多項(xiàng)式B相加，得到多項(xiàng)式M*/int la=A.len,lb=B.len,i; M-len=lalb?la:lb; for(i=0;i=la&iai=A.ai+B.ai;while(iai=A.ai;i+; while(iai=B.ai;i+;

11、return;6.3 一元多項(xiàng)式相減6.3.1鏈?zhǔn)酱鎯?chǔ)的多項(xiàng)式相減程序源代碼：/*3、兩多項(xiàng)式相減*/polynomail subpolyn(polynomail pa,polynomail pb) /完成多項(xiàng)式相減運(yùn)算，即：Pa=Pa-Pbpolynomail s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data)case -1: s-da

12、ta.coef=p-data.coef;s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef;if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s;p=p-next; q=q-next; break;case 1: s-data.coef=-q-data.coef;s-data.expn=q-data.expn; r-next=s; r=s;q=q-next;/switch/whil

13、ewhile(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next;while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL;if(newp-next!=NULL&newp-next-next!=NULL)/合并同類(lèi)項(xiàng) for(q=ne

14、wp-next;q!=NULL;q=q-next)for(p=q-next,r=q;p!=NULL;)if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next;p=p-next; printf(升序 1 , 降序 2n); printf(選擇:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;6.3.2順序存儲(chǔ)的多項(xiàng)式相減程

15、序源代碼：void SUB(Ploy A,Ploy B,Ploy *M)/*多項(xiàng)式A與多項(xiàng)式B相減（A-B），得到多項(xiàng)式M*/ int la=A.len,lb=B.len,i; M-len=lalb?la:lb; for(i=0;i=la&iai=A.ai-B.ai; while(iai=A.ai;i+; while(iai=0-B.ai;i+; return ; 6.4 一元多項(xiàng)式相乘6.4.1鏈?zhǔn)酱鎯?chǔ)的多項(xiàng)式相乘程序源代碼：polynomail mulpolyn(polynomail pa,polynomail pb) /完成多項(xiàng)式相乘運(yùn)算，即：Pa=Pa*Pbpolynomail s,n

16、ewp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next)for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn+q-data.expn; r-next=s; r=s; r-next=NULL; printf(升序 1 , 降序 2n); printf(選擇:); sc

17、anf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp);for(;i!=0;i-)for(q=newp-next;q-next!=NULL;q=q-next)/合并同類(lèi)項(xiàng)for(p=q;p!=NULL&p-next!=NULL;p=p-next)if(q-data.expn=p-next-data.expn)q-data.coef=q-data.coef+p-next-data.coef;r=p-next;p-next=p-next-next; free(r);return newp;6.4.2順序存儲(chǔ)多項(xiàng)式相乘程序源代碼：void MU

18、L(Ploy A,Ploy B,Ploy *M)/*多項(xiàng)式A與多項(xiàng)式B相乘，得到多項(xiàng)式M*/int i,j; for(i=0;iai=0; for(i=0;i=A.len;i+)for(j=0;jai+j+=A.ai*B.aj; M-len=A.len+B.len; return ; 6.5一元多項(xiàng)式輸出結(jié)果按項(xiàng)的指數(shù)排序6.5.1鏈?zhǔn)接尚〉酱笈判驁D6.6.1鏈?zhǔn)缴蛄鞒虉Dvoid arrange1(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p-next!=NULL;p=p-next); r=p;

19、for(h=pa;h-next!=r;)/大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向參與比較的最后一個(gè)，不斷向前移動(dòng) 6.5.2鏈?zhǔn)接纱蟮叫∨判驁D6.6.2鏈?zhǔn)浇敌蛄鞒虉D程序源代碼：void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p

20、-next!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向參與比較的最后一個(gè)，不斷向前移動(dòng)6.5.3順序由大到小排序程序源代碼：void PrintPloy1(Ploy A) /降序輸出順序一元多項(xiàng)式int i; printf( %dx%d ,A.aA.len,A.l

21、en); for(i=A.len-1;i=1;i-) if(A.ai=0) ;else if(A.ai=1) printf( + x%d ,i);else if(A.ai=-1) printf( - x%d ,i);else if(A.ai0) printf(+ %dx%d ,A.ai,i); else printf(- %dx%d ,-A.ai,i); if(A.a0=0) ;else if(A.a00) printf( + %d,A.a0);/打印x的0次項(xiàng) elseprintf( - %d,-A.a0);printf(n); return ;6.5.4順序由小到大排序程序源代碼：void

22、 PrintPloy2(Ploy A) /升序輸出順序一元多項(xiàng)式int i=0; while(A.ai=0) +i; if(i=0) printf(%d,A.ai); else if(A.ai=1) printf(x%d,i);else if(A.ai=-1) printf(-x%d,i); else printf(%dx%d,A.ai,i);for(+i;i1) printf( + %dx%d,A.ai,i); else if(A.aim;while(mm)printf(你輸入的輸出新創(chuàng)一元多項(xiàng)式的操作號(hào)不合法，請(qǐng)重新輸入n);cinm;switch(m)case 1:if(m=1) pri

23、ntf(A降=); PrintPloy1(A); printf(n); printf(B降=); PrintPloy1(B);break;case 2:if(m=2)printf(A升=);PrintPloy1(A);printf(n);printf(B升=);PrintPloy1(B);break;Menushunxu();while(1) printf(請(qǐng)選擇你想進(jìn)行的順序存儲(chǔ)運(yùn)算操作：n);cinn;while(n6)printf(輸入的順序操作號(hào)不對(duì)，請(qǐng)重新輸入n);cinn; switch(n)case 1:if(n=1) printf(更新兩個(gè)多項(xiàng)式：n);printf(請(qǐng)輸入多項(xiàng)

24、式A：n); GetPloy(&A); printf(請(qǐng)輸入多項(xiàng)式B：n); GetPloy(&B);printf(輸出兩個(gè)更新的一元多項(xiàng)式A、B，降冪輸出請(qǐng)按1，升冪輸出請(qǐng)按2！n);cinm; while(m2) printf(你輸入的輸出排序操作號(hào)不合法，請(qǐng)重新輸入n); cinm; switch(m)case 1:if(m=1) printf(A降=);PrintPloy1(A);printf(n);printf(B降=);PrintPloy1(B);break;case 2:if(m=2) printf(A升=);PrintPloy1(A);printf(n);printf(B升=)

25、;PrintPloy1(B);break;break;case 2:if(n=2)ADD(A,B,&M); printf(降冪輸出請(qǐng)按1，升冪輸出請(qǐng)按2！n); cinm; while(m2) printf(你輸入的輸出排序操作號(hào)不合法，請(qǐng)重新輸入n); cinm; switch(m)case 1:if(m=1) printf(ADD降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(ADD升=);PrintPloy2(M);printf(n);break;break;case 3: if(n=3)SUB(A,B,&M);printf(

26、降冪輸出請(qǐng)按1，升冪輸出請(qǐng)2！n);cinm;while(m2) printf(你輸入的輸出排序操作號(hào)不合法，請(qǐng)重新輸入n); cinm; switch(m)case 1:if(m=1) printf(SUB降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(SUB升=);PrintPloy2(M);printf(n);break;break;case 4: if(n=4)MUL(A,B,&M);printf(降冪輸出請(qǐng)按1，升冪輸出請(qǐng)2！n);cinm;while(m3) printf(你輸入輸出排序操作號(hào)不合法，請(qǐng)重新輸入n); c

27、inm;switch(m)case 1:if(m=1) printf(MUL降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(MUL升=);PrintPloy2(M);printf(n);break;break;case 5:if(n=5)printf(返回主菜單n);Menu(); break; case 6:if(n=6)printf(已成功退出該系統(tǒng)，謝謝你的使用！n);exit(-2); break; 6.6.3鏈?zhǔn)阶酉到y(tǒng)程序源代碼：void Menulink()printf(n); printf( *一元多項(xiàng)式鏈?zhǔn)酱鎯?chǔ)的基本

28、運(yùn)算*n); printf( 1、創(chuàng)建兩個(gè)一元多項(xiàng)式請(qǐng)按1n); printf( 2、兩多項(xiàng)式相加得一新多項(xiàng)式請(qǐng)按2n); printf( 3、兩多項(xiàng)式相減得一新多項(xiàng)式請(qǐng)按3n); printf( 4、兩多項(xiàng)式相乘得一新多項(xiàng)式請(qǐng)按4n); printf( 5、銷(xiāo)毀已建立的兩個(gè)多項(xiàng)式請(qǐng)按5n); printf( 6、退出該子系統(tǒng)返回主菜單請(qǐng)按6n);printf( 7、退出該系統(tǒng)請(qǐng)按7n); printf( *n);printf(n);void link() /一元多項(xiàng)式鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)polynomail pa=NULL,pb=NULL;polynomail p,q;polynomail add

29、p=NULL,subp=NULL,mulp=NULL;int n,m;printf(已進(jìn)入鏈?zhǔn)酱鎯?chǔ)一元多項(xiàng)式運(yùn)算的子系統(tǒng)n);Menulink();while(1)printf(請(qǐng)選擇你想進(jìn)行的鏈?zhǔn)酱鎯?chǔ)運(yùn)算操作：n); scanf(%d,&n); switch(n)case 1:if(pa!=NULL) printf(已建立兩個(gè)一元多項(xiàng)式，請(qǐng)選擇其他操作!);break;printf(請(qǐng)輸入第一個(gè)多項(xiàng)式：n);printf(要輸入幾項(xiàng)：);scanf(%d,&m);while(m=0) printf(m不能為0，請(qǐng)重新輸入m：);scanf(%d,&m);pa=creatpolyn(pa,m)

30、;printpolyn(pa);printf(請(qǐng)輸入第二個(gè)多項(xiàng)式：n); printf(要輸入幾項(xiàng)：); scanf(%d,&m);while(m=0) printf(m不能為0，請(qǐng)重新輸入m：);scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb);break;case 2:if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式!n);break;addp=addpolyn(pa,pb);printpolyn(addp);break;case 3:if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式!n);break;subp=su

31、bpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式!n);break; mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5: if(pa=NULL)printf(請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式!n);break;delpolyn(pa,pb);pa=pb=NULL;printf(兩個(gè)一元多項(xiàng)式的銷(xiāo)毀成功!n);break;case 6:if(addp!=NULL) p=addp;while(p!=NULL)q=p;p=p-next;free(q);if(subp!=NULL)p=subp;while(p!=NULL) q=p; p=p-next; free(q);printf(返回主菜單n);Menu();break;case 7:if(addp!=NULL) p=addp;while(p!=NULL)q=p;p=p-next;free(q);if(subp!=NULL)p=subp;while(p!=NULL) q=p; p=p-next; free(q);printf(已成功退出該系統(tǒng)，謝謝你的使用！n);exit(-2);break;/swit