數(shù)據(jù)結(jié)構(gòu)一元多項式的運算

1、目 錄一、問題分析11.1 問題描述11.2 問題的數(shù)學(xué)模型11.3 構(gòu)造數(shù)據(jù)結(jié)構(gòu)1二、系統(tǒng)分析22.1 可行性研究22.2 系統(tǒng)結(jié)構(gòu)與主要功能模塊2三、系統(tǒng)設(shè)計43.1系統(tǒng)設(shè)計目的與要求43.2系統(tǒng)設(shè)計內(nèi)容43.3功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明4四、系統(tǒng)實現(xiàn)7五、調(diào)試及運行結(jié)果11六、收獲和體會12附錄131 問題分析1.1 問題描述設(shè)計一個n元多項式程序，并完成多項式的乘法運算。從實際的角度出發(fā)，這里設(shè)計的程序是基于一元n次多項式的數(shù)學(xué)模型。1.2 問題的數(shù)學(xué)模型在數(shù)學(xué)上，一個一元多項式Pn(x)可按升冪寫成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由n+1個系數(shù)惟一確

2、定，因此，在計算機里，它可用一個線性表P來表示：Pn=(a0,a1,a2,an)每一項的指數(shù)i隱含在其系數(shù)ai的序號里。多項式的乘法規(guī)則：多次運用單項式與多項式相乘的法則得到的計算時(a+b)(m+n)，先把(m+n)看成一個單項式，(a+b) 是一個多項式，運用單項式與多項式相乘的法則，得到(a+b)(m+n)=a(m+n)+b(m+n),然后再次運用單項式與多項式相乘的法則。1.3 構(gòu)造數(shù)據(jù)結(jié)構(gòu)通過分析多項式的特征，不難看出多項式是由單項式構(gòu)成的，而每個單項式都具有系數(shù)和指數(shù)，當(dāng)系數(shù)為0時，該項就失去了意義，在計算機內(nèi)要表示一個多項式，至少以下數(shù)據(jù)信息：系數(shù)信息、指數(shù)信息和指向下一個單項式

3、的指針。通過指針，我們就可以把多個單項式連接起來，形式一個多項式，需要說明的是從廣義的角度講，單項式也是一個多項式?；谝陨系姆治觯覀兌x多項式的數(shù)據(jù)結(jié)構(gòu)為如下結(jié)構(gòu)體形式：typedef struct Polynomial float coef;/系數(shù) int expn;/指數(shù) struct Polynomial *next;/指向下一個結(jié)點*Polyn,Polynomial; /Polyn為結(jié)點指針類型2 系統(tǒng)分析2.1 可行性研究該程序主要從技術(shù)的角度來分析可行性。技術(shù)上的可行性研究主要分析技術(shù)條件能否順利完成開發(fā)工作，硬、軟件能否滿足開發(fā)者的需要等。該系統(tǒng)采用了Windows XP操作

4、系統(tǒng)結(jié)合Visual C+ 6.0,TC 2.0等軟件開發(fā)平臺已成熟可行。硬件方面，科技飛速發(fā)展的今天，硬件更新的速度越來越快，容量越來越大，可靠性越來越高，其硬件平臺也比較能滿足此系統(tǒng)的需要。此外，還有經(jīng)濟可行性，用戶使用可行性，法律可行性等可行性研究，這里從簡省去。2.2 系統(tǒng)結(jié)構(gòu)與主要功能模塊從實現(xiàn)多項式式運算過程的角度來分析，至少需要這樣一些子功能模塊。如：1. 多項式創(chuàng)建功能；2. 多項式運算功能；3. 操作界面顯示功能；4. 銷毀多項式的功能；5. 多項式復(fù)制功能等。系統(tǒng)的整體流程和主要功能模塊如圖2-1所示開始輸入選擇顯示加法顯示功能表輸入pa系數(shù)、指數(shù)退出輸入pb系數(shù)、指數(shù)減法

5、乘法i=mi=mimim圖 2-13 系統(tǒng)設(shè)計3.1系統(tǒng)設(shè)計目的與要求通過多項式運算程序設(shè)計（用C語言實現(xiàn)），使我們進一步掌握和利用C語言進行結(jié)構(gòu)化程序設(shè)計的能力；進一步理解和運用結(jié)構(gòu)化程設(shè)計的思想和方法；初步掌握開發(fā)一個小型系統(tǒng)程序設(shè)計的基本方法；學(xué)會調(diào)試一個較長程序的基本方法；學(xué)會利用流程圖或N-S圖表示算法；以及掌握書寫課程設(shè)計開發(fā)文檔的能力（書寫課程設(shè)計報告）?？傊?，通過本課程設(shè)計加深對C語言及數(shù)據(jù)結(jié)構(gòu)課程所學(xué)知識的理解，進一步鞏固C語言語法規(guī)則，在程序中體現(xiàn)出算法的思想，提高程序的運行效率。學(xué)會編制結(jié)構(gòu)清晰、風(fēng)格良好、數(shù)據(jù)結(jié)構(gòu)適當(dāng)?shù)恼Z言程序，從而具備解決綜合性實際問題的能力。3.2系

6、統(tǒng)設(shè)計內(nèi)容多項式運算程序具有以下基本功能：1界面輸出，提示如何輸入數(shù)據(jù)。要求先輸入多項式的項數(shù)。2創(chuàng)建多項式。接收輸入的數(shù)據(jù)，并保存到鏈表中。3顯示程序的功能表，允許使用者選擇運算類型。4顯示已經(jīng)創(chuàng)建好的多項式。6實現(xiàn)加法運算。7實現(xiàn)減法運算。8實現(xiàn)乘法運算。9清除內(nèi)存內(nèi)容，銷毀創(chuàng)建的鏈表，退出程序。3.3功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項式程序除了main()函數(shù)外，主要有以下函數(shù)：void Insert(Polyn p,Polyn h)Polyn CreatePolyn(Polyn head,int m)void DestroyPolyn(Polyn p)void PrintPolyn(Po

7、lyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn MultiplyPolyn(Polyn pa,Polyn pb)下面對這些函數(shù)逐一介紹。3.3. 系統(tǒng)主要功能函數(shù)的詳細(xì)設(shè)計1.main（）函數(shù)main函數(shù)用來實現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算功能。在main（）函數(shù)中，定義m、n用來保存兩個多項式的項數(shù)，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個多項式的項數(shù)，隨后根

8、據(jù)項數(shù)創(chuàng)建兩個鏈表以保存多項式，再顯示出功能列表后通過if語句來實現(xiàn)功能的選擇，從而對整個程序流程進行控制。2. Polyn CreatePolyn(Polyn head,int m)該函數(shù)功能是創(chuàng)建新的多項式鏈表。int m保存的多項式的項數(shù)，使用for語句，控制輸入多項式的每一項。當(dāng)創(chuàng)建的鏈表長度為m時，將不再提示用戶繼續(xù)輸入多項式的系數(shù)和指數(shù)。在該函數(shù)中要用到分配空間的函數(shù)malloc()為新建鏈表分配空間。3. void DestroyPolyn(Polyn p)該函數(shù)的功能是銷毀掉創(chuàng)建的兩個鏈表，釋放內(nèi)存。以輔助退出程序。4. void Insert(Polyn p,Polyn h)

9、該函數(shù)功能：將新的節(jié)點p插入到現(xiàn)有鏈表的后面，并確保多項式的指數(shù)exp是升序。將s節(jié)點插入到head所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。5. Polyn AddPolyn(Polyn pa,Polyn pb)該函數(shù)功能：實現(xiàn)兩個多項式pa、pb相加，并將計算結(jié)果存儲于新建立的pc中，它的原理是將指數(shù)相同的單項式相加，系數(shù)相加后為0，則pa、pb的指針都后移。在加法計算中要求pa,與pb的冪次序都是升序，否則可能得到錯誤的結(jié)果。該函數(shù)調(diào)用了int compare(Polyn a,Polyn b)的結(jié)果，用來判斷多項式在同一指數(shù)下a、b是否有為系數(shù)為0。同樣也使用了malloc

10、()關(guān)鍵字，為新鏈表創(chuàng)建空間。6. int compare(Polyn a,Polyn b)該函數(shù)功能：判斷兩個多項式在同一指數(shù)下是否有其中一個為系數(shù)為0。用來輔助加法和乘法運算。7. Polyn SubtractPolyn(Polyn pa,Polyn pb)該函數(shù)功能：實現(xiàn)兩個多項式pa、pb相減，其原理根加法類似，將指數(shù)相同的指數(shù)相減。與加法不同的是在送在減法中，創(chuàng)建了新的鏈表來存放結(jié)果，并返回該鏈表的頭指針。8. void PrintPolyn(Polyn P)該函數(shù)功能：顯示多項式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤其是第一項的輸出，同時還有符號的控制。在輸出第一項時要判

11、斷是不是常數(shù)項，若是，則不要輸出字符x。9. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函數(shù)功能：實現(xiàn)兩個多項式相乘，A(X) * B(x) 。計算時運用單項式與多項式相乘的法則，然后再次運用單項式與多項式相乘的法則。4 系統(tǒng)實現(xiàn)該程序?qū)崿F(xiàn)了多項式的創(chuàng)建、多項式的加法、減法、乘法運算以及多項式的清除。為完成這些功能，還用到了一些輔助函數(shù)。下面討論重要函數(shù)具體實現(xiàn)過程及其參數(shù)的意義：1. Polyn CreatePolyn(Polyn head,int m)該函數(shù)的兩個參數(shù)，head表示為創(chuàng)建的鏈表的頭指針，m表示為鏈表的長度，即多項式的項數(shù)。定義int i計數(shù)

12、，當(dāng)inext=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;/CreatePolyn2. void Insert(Polyn p,Polyn h) 該函數(shù)具有兩個參數(shù)，用來實現(xiàn)鏈表的順序排列和合并相同的項。以下是實現(xiàn)插入的關(guān)鍵代碼： void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系數(shù)為0的話釋放結(jié)點 else/如果系數(shù)不為0 Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入

13、位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /將指數(shù)相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系數(shù)為0的話釋放結(jié)點 q1-next=q2-next;free(q2); else /指數(shù)為新時將結(jié)點插入 p-next=q2; q1-next=p; /Insert3. Polyn AddPolyn(Polyn pa,Polyn pb) 該函數(shù)有兩個參數(shù)，其類型均為polyn，分別表示要相加的兩個不同的多項式。其計算的結(jié)果存放在新建的pc所指向的鏈表中。函數(shù)中調(diào)用了int compare(Polyn a,P

14、olyn b)的結(jié)果。下面是實現(xiàn)加法的關(guān)鍵代碼：Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef

15、=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點 /while return headc;/A

16、ddPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/compare4. Polyn MultiplyPolyn(Polyn pa,Polyn pb) 該函數(shù)同加法一樣，擁有相同的參數(shù)并且同樣將新建立的鏈表pf的指針返回，用來實現(xiàn)輸出乘法結(jié)果。下面給出關(guān)鍵代碼：Pol

17、yn MultiplyPolyn(Polyn pa,Polyn pb) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(

18、pf,hf);/調(diào)用Insert函數(shù)以合并指數(shù)相同的項 return hf;/MultiplyPolyn5.其它函數(shù)的介紹請參見附錄中詳細(xì)代碼.5 調(diào)試及運行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯誤和警告，運行結(jié)果經(jīng)過檢驗為正確。以下圖5-1即為該程序運行結(jié)果效果圖。圖中采用的是計算多項式4x5+2x2+3x和x10+7x2的加減乘三種運算進行演示：輸入兩個多項式的每一項值提示功能選擇進行三則運算的結(jié)果圖5-16 收獲和體會通過這次課程設(shè)計練習(xí)，使我更深刻地理解了語言的精髓-指針的使用。完成整個程序設(shè)計有，對指針掌握的更加熟練。同時通過直接對鏈表的操作，加深了對數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識。并在完成

19、課程設(shè)計的過程作主動查閱了相關(guān)資料，學(xué)到了不少課本上沒有的技術(shù)知識。經(jīng)過這次課程設(shè)計，我深刻認(rèn)識到算法在程序設(shè)計中的重要性，一個完整的程序總是由若干個函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。編程是一件枯燥乏味工作，但是只要認(rèn)真專研，我們會從中學(xué)到很多在課本上學(xué)不到或者無法在課堂上掌握的知識，同時也能從中感受到編程的樂趣。興趣是可以培養(yǎng)的，只要堅持下去，面對困難我們總能夠找到解決問題的方法。計算多項式的加、減、乘法運算-該程序雖然不是很大，這次還是由幾位同學(xué)合作才完成這一任務(wù)。在這個小組中我是組長，通過分工與合作，使我充分認(rèn)識到在項目團隊開發(fā)過程中合作的重要性，也更加理解了溝通協(xié)作能力在

20、軟件開發(fā)行業(yè)中的重要性。另外也需要提出的是在這次程序設(shè)計的過程中，非常感謝老師對我們的耐心指導(dǎo)。老師在教學(xué)過程中表現(xiàn)出來的對學(xué)術(shù)專研一絲不茍的精神讓我非常有收獲。同樣也是老師的嚴(yán)格要求才使得小組成員能夠順利的完成任務(wù)。附錄#include#include/*/typedef struct Polynomial float coef;/系數(shù) int expn;/指數(shù) struct Polynomial *next;/指向下一個結(jié)點*Polyn,Polynomial; /Polyn為結(jié)點指針類型/*/void Insert(Polyn p,Polyn h) if(p-coef=0) free(p)

21、; /系數(shù)為0的話釋放結(jié)點 else/如果系數(shù)不為0 Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /將指數(shù)相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系數(shù)為0的話釋放結(jié)點 q1-next=q2-next; free(q2); else /指數(shù)為新時將結(jié)點插入 p-next=q2; q1-next=p; /Insert/*以下函數(shù)實現(xiàn)建立一個多項式*/Polyn CreatePolyn(Polyn

22、 head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式/在主程序初始時，先輸入的多項式中的項數(shù)m、n 在這里為m。主程序中的pa、pb在此為head int i;/用來計數(shù) Polyn p;/定義一個p鏈表 p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;/CreatePolyn/*以下函數(shù)實現(xiàn)多項式的銷毀*/void DestroyPolyn(Polyn p)/

23、銷毀多項式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指針后移 q2=q2-next; /*以下函數(shù)實現(xiàn)顯示輸出多項式* */void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/項數(shù)計數(shù)器 if(!q) /若多項式為空，輸出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 if(q-coef!=1&q-coef!=-1)/

24、系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+;

25、 /while printf(n);/PrintPolyn/*在下面的輔助乘法和加法運算*/int compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/compare/*以下函數(shù)實現(xiàn)加法*/Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其

26、頭指針 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-

27、coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點 /while return headc;/AddPolyn/*以下函數(shù)實現(xiàn)減法*/Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其

28、頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢復(fù)pb的系數(shù) p-coef*=-1; return pd;/SubtractPolyn/*以下函數(shù)實現(xiàn)乘法*/Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項式a*b，返回其頭指針(該函數(shù)實現(xiàn)乘法) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf);/調(diào)用Insert函數(shù)以合