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

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

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

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

5、ypedef struct /項的表示 float coef; /系數 int expn; /指數term;（3）LNode結構聲明typedef struct LNode term data; /term多項式值 struct LNode *next;LNode,*LinkList; /兩個類型名typedef LinkList polynomail; /用帶頭結點的有序鏈表表示多項式6 模塊分析 整個流程圖如圖所示：圖16.1 創建模塊6.1.1、鏈式存儲結構的一元多項式的創建程序源代碼：polynomail creatpolyn(polynomail P,int m) /輸入m項的系數和

6、指數，建立表示一元多項式的有序鏈表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、順序存儲結構一元多項式的創建程序源代碼：void GetPloy(Ploy *A)int i,coef,ex,maxe=0; char ch; printf(請輸入每個項的系數及對應的指數，指數為負數時標志輸入結束！n); for(i=0;iai=0;scanf(%d%d,&coef,&ex); while(ex=0) if(exmaxe) maxe=ex;if(A-aex!=0)printf(你輸入的項已經存在，是否更新原數據？（Y/N）

8、);cinch; if(ch=Y|ch=y) A-aex=coef;printf(更新成功，請繼續輸入！n); elseprintf(請繼續輸入！n);else A-aex=coef;scanf(%d%d,&coef,&ex); A-len=maxe; return ;6.2 一元多項式的加法6.2.1 鏈式存儲兩多項式相加程序源代碼：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鏈式存儲的多項式相減程序源代碼：/*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鏈式存儲的多項式相乘程序源代碼：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一元多項式輸出結果按項的指數排序6.5.1鏈式由小到大排序圖6.6.1鏈式升序流程圖void 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鏈式由大到小排序圖6.6.2鏈式降序流程圖程序源代碼：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(你輸入的輸出新創一元多項式的操作號不合法，請重新輸入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(請選擇你想進行的順序存儲運算操作：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(已成功退出該系統，謝謝你的使用！n);exit(-2); break; 6.6.3鏈式子系統程序源代碼：void Menulink()printf(n); printf( *一元多項式鏈式存儲的基本

28、運算*n); printf( 1、創建兩個一元多項式請按1n); printf( 2、兩多項式相加得一新多項式請按2n); printf( 3、兩多項式相減得一新多項式請按3n); printf( 4、兩多項式相乘得一新多項式請按4n); printf( 5、銷毀已建立的兩個多項式請按5n); printf( 6、退出該子系統返回主菜單請按6n);printf( 7、退出該系統請按7n); printf( *n);printf(n);void link() /一元多項式鏈式存儲的實現polynomail pa=NULL,pb=NULL;polynomail p,q;polynomail add

29、p=NULL,subp=NULL,mulp=NULL;int n,m;printf(已進入鏈式存儲一元多項式運算的子系統n);Menulink();while(1)printf(請選擇你想進行的鏈式存儲運算操作：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(請先創建兩個一元多項式!n);break;addp=addpolyn(pa,pb);printpolyn(addp);break;case 3:if(pa=NULL) printf(請先創建兩個一元多項式!n);break;subp=su

31、bpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa=NULL) printf(請先創建兩個一元多項式!n);break; mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5: if(pa=NULL)printf(請先創建兩個一元多項式!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(已成功退出該系統，謝謝你的使用！n);exit(-2);break;/swit