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

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

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

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

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

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

6、指數(shù)，建立表示一元多項式的有序鏈表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)/合并同類項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、順序存儲結(jié)構(gòu)一元多項式的創(chuàng)建程序源代碼：void GetPloy(Ploy *A)int i,coef,ex,maxe=0; char ch; printf(請輸入每個項的系數(shù)及對應(yīng)的指數(shù)，指數(shù)為負(fù)數(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(你輸入的項已經(jīng)存在，是否更新原數(shù)據(jù)？（Y/N）

8、);cinch; if(ch=Y|ch=y) A-aex=coef;printf(更新成功，請繼續(xù)輸入！n); elseprintf(請繼續(xù)輸入！n);else A-aex=coef;scanf(%d%d,&coef,&ex); A-len=maxe; return ;6.2 一元多項式的加法6.2.1 鏈?zhǔn)酱鎯啥囗検较嗉映绦蛟创a：polynomail addpolyn(polynomail pa,polynomail pb) /完成多項式相加運算，即：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 順序存儲的多項式相加程序源代碼：void ADD(Ploy A,Ploy B,Ploy *M)/*多項式A與多項式B相加，得到多項式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 一元多項式相減6.3.1鏈?zhǔn)酱鎯Φ亩囗検较鄿p程序源代碼：/*3、兩多項式相減*/polynomail subpolyn(polynomail pa,polynomail pb) /完成多項式相減運算，即：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)/合并同類項 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順序存儲的多項式相減程

15、序源代碼：void SUB(Ploy A,Ploy B,Ploy *M)/*多項式A與多項式B相減（A-B），得到多項式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 一元多項式相乘6.4.1鏈?zhǔn)酱鎯Φ亩囗検较喑顺绦蛟创a：polynomail mulpolyn(polynomail pa,polynomail pb) /完成多項式相乘運算，即：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)/合并同類項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順序存儲多項式相乘程序源代碼：void MU

18、L(Ploy A,Ploy B,Ploy *M)/*多項式A與多項式B相乘，得到多項式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一元多項式輸出結(jié)果按項的指數(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指向參與比較的最后一個，不斷向前移動 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指向參與比較的最后一個，不斷向前移動6.5.3順序由大到小排序程序源代碼：void PrintPloy1(Ploy A) /降序輸出順序一元多項式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次項 elseprintf( - %d,-A.a0);printf(n); return ;6.5.4順序由小到大排序程序源代碼：void

22、 PrintPloy2(Ploy A) /升序輸出順序一元多項式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)一元多項式的操作號不合法，請重新輸入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(請選擇你想進(jìn)行的順序存儲運算操作：n);cinn;while(n6)printf(輸入的順序操作號不對，請重新輸入n);cinn; switch(n)case 1:if(n=1) printf(更新兩個多項式：n);printf(請輸入多項

24、式A：n); GetPloy(&A); printf(請輸入多項式B：n); GetPloy(&B);printf(輸出兩個更新的一元多項式A、B，降冪輸出請按1，升冪輸出請按2！n);cinm; while(m2) printf(你輸入的輸出排序操作號不合法，請重新輸入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(降冪輸出請按1，升冪輸出請按2！n); cinm; while(m2) printf(你輸入的輸出排序操作號不合法，請重新輸入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、降冪輸出請按1，升冪輸出請2！n);cinm;while(m2) printf(你輸入的輸出排序操作號不合法，請重新輸入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(降冪輸出請按1，升冪輸出請2！n);cinm;while(m3) printf(你輸入輸出排序操作號不合法，請重新輸入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( *一元多項式鏈?zhǔn)酱鎯Φ幕?/p>

28、運算*n); printf( 1、創(chuàng)建兩個一元多項式請按1n); printf( 2、兩多項式相加得一新多項式請按2n); printf( 3、兩多項式相減得一新多項式請按3n); printf( 4、兩多項式相乘得一新多項式請按4n); printf( 5、銷毀已建立的兩個多項式請按5n); printf( 6、退出該子系統(tǒng)返回主菜單請按6n);printf( 7、退出該系統(tǒng)請按7n); printf( *n);printf(n);void link() /一元多項式鏈?zhǔn)酱鎯Φ膶崿F(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)酱鎯σ辉囗検竭\算的子系統(tǒng)n);Menulink();while(1)printf(請選擇你想進(jìn)行的鏈?zhǔn)酱鎯\算操作：n); scanf(%d,&n); switch(n)case 1:if(pa!=NULL) printf(已建立兩個一元多項式，請選擇其他操作!);break;printf(請輸入第一個多項式：n);printf(要輸入幾項：);scanf(%d,&m);while(m=0) printf(m不能為0，請重新輸入m：);scanf(%d,&m);pa=creatpolyn(pa,m)

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

31、bpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa=NULL) printf(請先創(chuàng)建兩個一元多項式!n);break; mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5: if(pa=NULL)printf(請先創(chuàng)建兩個一元多項式!n);break;delpolyn(pa,pb);pa=pb=NULL;printf(兩個一元多項式的銷毀成功!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