數據結構一元多項式的運算參考模板

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

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

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

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

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

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

7、lyn(Polyn 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)下面對這些函數逐一介紹。3.3. 系統(tǒng)主要功能函數的詳細設計1.main（）函數main函數用來實現提示使用者輸入、顯示功能列表、調用其他運算函數實現運算功能。在main（）函數中，定義m、n用來保存兩個多項式的項數，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個多項式的

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

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

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

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

12、nt i計數，當inext=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調用Insert函數插入結點 return head;/CreatePolyn2. void Insert(Polyn p,Polyn h) 該函數具有兩個參數，用來實現鏈表的順序排列和合并相同的項。以下是實現插入的關鍵代碼： void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系數為0的話釋放結點 else/如果系數不為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) /將指數相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系數為0的話釋放結點 q1-next=q2-next;free(q2); else /指數為新時將結點插入 p-next=q2; q1-next=p; /Insert3. Polyn AddPolyn(Polyn pa,Polyn pb) 該函數有兩個參數，其類型均為polyn，分別表示要相加的兩個不同的多項式。其計算的結果存放在新建的pc所指向的鏈表中。函數中調用了int compare(Pol

14、yn a,Polyn b)的結果。下面是實現加法的關鍵代碼：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);/建立頭結點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: q

15、c-coef=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);/當相加系數為0時，釋放該結點 /while return he

16、adc;/AddPolynint 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) 該函數同加法一樣，擁有相同的參數并且同樣將新建立的鏈表pf的指針返回，用來實現輸出乘法結果。下面給出關鍵

17、代碼：Polyn MultiplyPolyn(Polyn pa,Polyn pb) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 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; I

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

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

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

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

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

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

24、!=-1)/系數非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;

25、flag+; /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/*以下函數實現加法*/Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a

26、+b，返回其頭指針 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 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-co

27、ef+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);/當相加系數為0時，釋放該結點 /while return headc;/AddPolyn/*以下函數實現減法*/Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a

28、+b，返回其頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢復pb的系數 p-coef*=-1; return pd;/SubtractPolyn/*以下函數實現乘法*/Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項式a*b，返回其頭指針(該函數實現乘法) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 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);/調用Insert函數以