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

1、課程設(shè)計（論文）目 錄一、問題分析 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é)果 12六、收獲和體會 13附錄 14課程設(shè)計（論文）1問題分析1.1問題描述設(shè)計一個n元多項式程序，并完成多項式的乘法運算。從實際的角度出發(fā)，這里 設(shè)計的程序是基丁一元n次多項式的數(shù)學(xué)模型。1.2問題的數(shù)學(xué)模型在數(shù)學(xué)上，一個一元多項式 Pn(x)可按升籍寫成：Pn(x)=a 0+a1 x+a2

2、 xA2 +an xAn-1 .它由n+1個系數(shù)惟一確定，因此，在計算機里，它可用一個線性表 P來表示： Pn=(a0,a1,a2, On尸項的指數(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ù)，當系數(shù)為0時，該項就失去了意義，在計算機內(nèi)要表示一個多

3、項式， 至少以下數(shù)據(jù)信息：系數(shù)信息、指數(shù)信息和指向下一個單項式的指針。通過指針，我 們就可以把多個單項式連接起來，形式一個多項式，需要說明的是從廣義的角度講， 單項式也是一個多項式?；∫陨系姆治觯覀兌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ā)工作，硬、

4、軟件能否滿足開發(fā)者的需要等。該系統(tǒng)采用了 WindowsXP 操作系統(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所示#

5、美冬理掌夜S課程設(shè)計(論文)圖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)適當?shù)腃語言程序，從而具備解決綜合性實際

6、問題的能力。3.2系統(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

7、(Polyn p)#課程設(shè)計(論文)void PrintPolyn(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)下面對這些函數(shù)逐一介紹。3.3.系統(tǒng)主要功能函數(shù)的詳細設(shè)計1. main ()函數(shù)main函數(shù)用來實現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算 功能。在main ()函數(shù)中，定義 m n用來保存兩個多項式的項數(shù)，pa、pb、pc

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

9、表，釋放內(nèi)存。以輔助退出程序。4. void Insert(Polyn p,Polyn h)該函數(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,貝Upa、pb的指針都后移。在加法計算中要求pa,與pb的籍次序都是升序，否則可能得到錯誤的結(jié)果。該函數(shù)調(diào)用了 int compare(Polyn a,

10、Polyn b)的結(jié)果，用來判斷多項式在同一指 數(shù)下a、b是否有為系數(shù)為0。同樣也使用了 malloc()關(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ù)功能：顯示多項式

11、鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤 其是第一項的輸出，同時還有符號的控制。在輸出第一項時要判斷是不是常數(shù)項，若 是，則不要輸出字符X 09. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函數(shù)功能：實現(xiàn)兩個多項式相乘， A(X) * B(x)。計算時運用單項式與多項式相 乘的法則，然后再次運用單項式與多項式相乘的法則。74系統(tǒng)實現(xiàn)該程序?qū)崿F(xiàn)了多項式的創(chuàng)建、多項式的加法、減法、乘法運算以及多項式的活除。 為完成這些功能，還用到了一些輔助函數(shù)。下面討論重要函數(shù)具體實現(xiàn)過程及其參數(shù)的意義：1. Polyn CreatePolyn(Polyn head,in

12、t m)該函數(shù)的兩個參數(shù)，head表示為創(chuàng)建的鏈 表的頭指針，m表示為鏈表的長度，即多項式的項數(shù)。定義int i計數(shù)，當i<m時，for 語句反復(fù)提示用戶輸入該多項式的每一項的指數(shù)和系數(shù)，并保存。當 i=m時，輸入完 畢，該鏈表也創(chuàng)建完畢。詳細的實現(xiàn)過程如下：Polyn CreatePolyn(Polyn head,int m)int i;/用來計數(shù)Polyn p;/定義一個p鏈表p=head=(Polyn)malloc(sizeof(struct Polynomial);head->next=NULL;for(i=0;i<m;i+)p=(Polyn)malloc(sizeo

13、f(struct Polynomial);/ 建立新結(jié)點以接收數(shù)據(jù)printf("請輸入第%d項的系數(shù)與指數(shù):",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); 調(diào)用Insert函數(shù)插入結(jié)點return head;/CreatePolyn2. void Insert(Polyn p,Polyn h)該函數(shù)具有兩個參數(shù)，用來實現(xiàn)鏈表的順序排歹U和 合并相同的項。以下是實現(xiàn)插入的關(guān)鍵代碼：void Insert(Polyn p,Polyn h)if(p->coef=

14、0) free(p);系數(shù)為0的話釋放結(jié)點else/如果系數(shù)不為0Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn)查找插入位置課程設(shè)計（論文）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-&g

15、t;next=q2;q1->next=p;/Insert3. Polyn AddPolyn(Polyn pa,Polyn pb)該函數(shù)有兩個參數(shù)，其類型均為 polyn,分 別表示要相加的兩個不同的多項式。其計算的結(jié)果存放在新建的pc所指向的鏈表中。函數(shù)中調(diào)用了 int compare(Polyn a,Polyn 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=(Pol

16、yn)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->coef;qc->expn=qa->expn;qa=qa->

17、;next;qb=qb->next;break;case -1:(qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;/switchif(qc->coef!=0)qc->next=hc->next;hc->next=qc;hc=qc;else free(qc);/緇相加系數(shù)為0時，釋放該結(jié)點/whilereturn headc;/AddPolynint compare(Polyn a,Polyn b)(if(a&&b)if(!b|a->expn>b-&

18、gt;expn) return 1;else if(!a|a->expn<b->expn) 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)鍵代碼：Polyn MultiplyPolyn(Polyn pa,Polyn pb)P

19、olyn 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;Inser

20、t(pf,hf);/調(diào)用Insert函數(shù)以合并指數(shù)相同的項return hf;/MultiplyPolyn5. 其它函數(shù)的介紹請參見附錄中詳細代碼115調(diào)試及運行結(jié)果該程序在VC6.0中調(diào)試通過，沒有錯誤和警告，運行結(jié)果經(jīng)過檢驗為正確。以下圖5-1即為該程序運行結(jié)果效果圖。圖中采用的是計算多項式4xA5+2xA2+3x和xA10+7xA2的加減乘三種運算進行演示:1B*4X5+9XA2*3X15 TX A12 *3X11+28XA7+14XIX蘆兀多 式孑呈 序:M* 有 K ：M XX K 請瑜入篡1項的系數(shù)與指數(shù)W 2 請輸入第2項的系數(shù)與指數(shù)=1 10頊的系數(shù)與擔(dān)數(shù)W 2項的系數(shù)與清數(shù)總

21、 3項的系數(shù)與市數(shù)二4輸入兩個多項式的每項值提示功能選擇5-16收獲和體會通過這次課程設(shè)計練習(xí)，使我更深刻地理解了c語言的精髓-指針的使用完成整個程序設(shè)計有，對指針掌握的更加熟練。同時通過直接對鏈表的操作，加深了對數(shù)據(jù)結(jié)構(gòu)的理解和認識。并在完成課程設(shè) 計的過程作主動查閱了相關(guān)資料，學(xué)到了不少課本上沒有的技術(shù)知識。經(jīng)過這次課程設(shè)計，我深刻認識到算法在程序設(shè)計中的重要性，一個完整的程序 總是由若干個函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。編程是一件枯燥乏味工作，但是只要認真專研，我們會從中學(xué)到很多在課本上學(xué) 不到或者無法在課堂上掌握的知識，同時也能從中感受到編程的樂趣。興趣是可以培 養(yǎng)的，

22、只要堅持下去，面對困難我們總能夠找到解決問題的方法。計算多項式的加、減、乘法運算-該程序雖然不是很大，這次還是由幾位同 學(xué)合作才完成這一任務(wù)。在這個小組中我是組長，通過分工與合作，使我充分認識到 在項目團隊開發(fā)過程中合作的重要性，也更加理解了溝通協(xié)作能力在軟件開發(fā)行業(yè)中 的重要性。另外也需要提出的是在這次程序設(shè)計的過程中，非常感謝老師對我們的耐心指 導(dǎo)。老師在教學(xué)過程中表現(xiàn)出來的對學(xué)術(shù)專研一絲不茍的精神讓我非常有收獲。同樣 也是老師的嚴格要求才使得小組成員能夠順利的完成任務(wù)。課程設(shè)計(論文)附錄#include<stdio.h>#include<malloc.h>/*/

23、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);系數(shù)為0的話釋放結(jié)點else/如果系數(shù)不為0Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn)查找插入位置q1=q2;q2=q2->next;i

24、f(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 head,int m)(/建立一個頭指針為 head 項數(shù)為m的一元多項 式在主程序初始時，先輸入的多項式中的項數(shù)m、n在這里為m。主程序中的pa、

25、pb在此為headint i;/用來計數(shù)Polyn p;/定義一個p鏈表p=head=(Polyn)malloc(sizeof(struct Polynomial);head->next=NULL;for(i=0;i<m;i+)p=(Polyn)malloc(sizeof(struct Polynomial);/ 建立新結(jié)點以接收數(shù)據(jù)printf("請輸入第%d項的系數(shù)與指數(shù):",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); 調(diào)用Insert函數(shù)插入結(jié)點

26、return head;/CreatePolyn/*以下函數(shù)實現(xiàn)多項式的銷毀*/void DestroyPolyn(Polyn p)/ 銷毀多項式 pPolyn 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) ( /若多項式為空，輸出0putchar('0');printf(&quo

27、t;n");return;while (q)(if(q->coef>0&&flag!=1) putchar('+'); / 系數(shù)大丁 0 且不是第一項if(q->coef!=1&&q->coef!=-1)/ 系數(shù)非 1 或-1 的普通情況printf("%g",q->coef);if(q->expn=1) putchar('X');else if(q->expn) printf("XA%d",q->expn);elseif(q->

28、;coef=1)if(!q->expn) putchar('1');else if(q->expn=1) putchar('X');else printf("XA%d",q->expn);if(q->coef=-1)if(!q->expn) printf("-T');else if(q->expn=1) printf("-X");else printf("-XA%d",q->expn);q=q->next;flag+;/whileprin

29、tf("n");/PrintPolyn在下面的輔助乘法和加法運算*/* int compare(Polyn a,Polyn b)(if(a&&b)if(!b|a->expn>b->expn) return 1;else if(!a|a->expn<b->expn) return -1;else return 0;else if(!a&&b) return -1;/a多項式已空，但 b多項式非空else return 1;/b多項式已空，但a多項式非空/compare/*以下函數(shù)實現(xiàn)加法*/Polyn Add

30、Polyn(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=qa->coef;qc->exp

31、n=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;/switchif(qc->coef!=0)qc->next=hc->next;hc->next=qc;hc=qc;else free(qc)

32、;/當相加系數(shù)為0時，釋放該結(jié)點/whilereturn headc;/AddPolyn/*以下函數(shù)實現(xiàn)減法*/Polyn SubtractPolyn(Polyn pa,Polyn pb)求解并建立多項式 a+b,返回其頭指釘Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p)/將pb的系數(shù)取反19p->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/

33、*以下函數(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ù)以合并指數(shù)相同的項return hf;/*/MultiplyPolyn主函數(shù)實現(xiàn)顯示與功能選擇*/