數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告.doc

《數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告.doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告.doc（31頁珍藏版）》請在裝配圖網(wǎng)上搜索。

數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告實驗題目：一元多項式班級：193121姓名：鄒冠宏學(xué)號：20121002758指導(dǎo)老師：郭艷完成日期：2013/9/30一 問題分析1. 問題描述設(shè)計一個n元多項式程序，并完成多項式的加法，乘法運算。從實際的角度出發(fā)，這里設(shè)計的程序是基于一元n次多項式的數(shù)學(xué)模型。2、 功能需求1)構(gòu)造一個空的多項式。2)多項式插入新的一項。3）計算多項式的值。4）打印多項式。5）多項式合并同類項。6）多項式加法。7）多項式乘法。8)多項式減法二、概要設(shè)計 1問題分析在數(shù)學(xué)上，一個一元多項式Pn(x)可按升冪寫成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由n+1個系數(shù)惟一確定，因此，在計算機里，它可用一個線性表P來表示：Pn=(a0,a1,a2,an)每一項的指數(shù)i隱含在其系數(shù)ai的序號里。2數(shù)據(jù)模型設(shè)計一個單鏈表模型，動態(tài)分配空間，刻意隨時插入新的一項多項式加法規(guī)則：兩個具有相同指數(shù)的項合并，系數(shù)為0時把這一項省去，也就是刪除了這一節(jié)點。多項式的乘法規(guī)則：多次運用單項式與多項式相乘的法則得到的計算時(a+b)(c+d)，把(c+d)看成一個單項式，(a+b) 是一個多項式，運用單項式與多項式相乘的法則，得到(a+b)(c+d)=a(c+d)+b(c+d),然后再次運用單項式與多項式相乘的法則。3 構(gòu)造數(shù)據(jù)結(jié)構(gòu)通過分析多項式的特征，不難看出多項式是由單項式構(gòu)成的，而每個單項式都具有系數(shù)和指數(shù)，當(dāng)系數(shù)為0時，該項就失去了意義，在計算機內(nèi)要表示一個多項式，至少以下數(shù)據(jù)信息：系數(shù)信息、指數(shù)信息和指向下一個單項式的指針。通過指針，我們就可以把多個單項式連接起來，形式一個多項式，基于以上的分析，我們定義多項式的數(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é)點指針類型三、詳細設(shè)計 1一元多項式運算程序具有以下基本功能：1）界面輸出，提示如何輸入數(shù)據(jù)。要求先輸入多項式的項數(shù)。2）創(chuàng)建多項式。接收輸入的數(shù)據(jù)，并保存到鏈表中。3）顯示程序的功能表，允許使用者選擇運算類型。4）打印多項式。5）實現(xiàn)加法運算。7）實現(xiàn)乘法運算。6）清除內(nèi)存內(nèi)容，銷毀創(chuàng)建的鏈表，退出程序。2功能算法描述與數(shù)據(jù)結(jié)構(gòu)說明該多項式程序除了main()函數(shù)外，主要有以下函數(shù)：Polyn CreatePolyn(Polyn head,int m)void Insert(Polyn p,Polyn h)void PrintPolyn(Polyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn MultiplyPolyn(Polyn pa,Polyn pb)void DestroyPolyn(Polyn p)void CountPolyn(Polyn P,int k)3. 主要功能函數(shù)的詳細設(shè)計1）.main（）函數(shù)main函數(shù)是用來實現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算功能。在main（）函數(shù)中，定義m、n用來保存兩個多項式的項數(shù)，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個多項式的項數(shù)，隨后根據(jù)項數(shù)創(chuàng)建兩個鏈表以保存多項式，再顯示出功能列表后通過輸入數(shù)字來選擇來實現(xiàn)功能的選擇，從而達到對整個程序流程進行控制。2）. Polyn CreatePolyn(Polyn head,int m)該函數(shù)功能是創(chuàng)建新的多項式鏈表。int m保存的多項式的項數(shù)，使用for語句，控制輸入多項式的每一項。若創(chuàng)建的鏈表長度為m時，將不再提示用戶繼續(xù)輸入多項式的系數(shù)和指數(shù)。因為是從0項開始計算的。在該函數(shù)中要用到分配空間的函數(shù)malloc()為新建鏈表分配空間。而空間的長度要用sizeof（）。3）. void Insert(Polyn p,Polyn h)該函數(shù)功能：將新的節(jié)點p插入到現(xiàn)有鏈表的后面，并確保多項式的指數(shù)exp是升序。將s節(jié)點插入到head所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。對插入的位置要分情況討論。在頭，中，尾三處的插入。4）. int compare(Polyn a,Polyn b)該函數(shù)功能：判斷兩個多項式在同一指數(shù)下是否有其中一個為系數(shù)為0。根據(jù)不同情況來討論多項式的指數(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()關(guān)鍵字，為新鏈表創(chuàng)建分配空間。6）. void PrintPolyn(Polyn P)該函數(shù)功能：顯示多項式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤其是第一項的輸出，同時還有符號的控制。在輸出第一項時要判斷是不是常數(shù)項，若是，則不要輸出字符x。還有對系數(shù)的正負的判斷，若是正就輸出+，負則直接輸出。7）. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函數(shù)功能：實現(xiàn)兩個多項式相乘，F(xiàn)(X) * H(x) 。計算時運用單項式與多項式相乘的法則，然后再次運用單項式與多項式相乘的法則。對得到多項式進行合并。8）Polyn CountPolyn(Polyn p,int x) 此函數(shù)是用來輸出多項式的計算結(jié)果，要給x賦值，當(dāng)*next=Null時結(jié)束運算，輸出結(jié)果9）. void DestroyPolyn(Polyn p)該函數(shù)的功能是銷毀掉創(chuàng)建的兩個鏈表，釋放內(nèi)存。以輔助退出程序。有利于空間空域，如果不釋放沒用的內(nèi)存空間的話，內(nèi)存會被占用，最后導(dǎo)致內(nèi)存不足，甚至系統(tǒng)崩潰。4各函數(shù)的詳細設(shè)計該程序?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ù)，當(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) /查找插入位置 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). int compare(Polyn a,Polyn b)此函數(shù)是用來比較兩個多項式之間的系數(shù)大小。 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多項式非空/compare4）. 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=(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-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;/AddPolyn5）. Polyn MultiplyPolyn(Polyn pa,Polyn pb) 該函數(shù)同加法一樣，擁有相同的參數(shù)并且同樣將新建立的鏈表pf的指針返回，用來實現(xiàn)輸出乘法結(jié)果。下面給出關(guān)鍵代碼：Polyn 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(pf,hf);/調(diào)用Insert函數(shù)以合并指數(shù)相同的項 return hf;/MultiplyPolyn6）. void PrintPolyn(Polyn P)從升序依次輸出多項式，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)/系數(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+; /while printf(n);/PrintPolyn7）void CountPolyn(Polyn p)float num=0;int x;int i;float k=1;Polyn q=p-next;printf(輸入你對x賦的值);scanf(%d,&x);printf(a);if(q=NULL)return;while (q!=NULL)k=k*(q-coef);for(i=0;iexpn);i+)k=k*x;num=num+k;q=q-next;return num;四程序調(diào)試1界面顯示2功能測試五收獲和體會通過這次課程設(shè)計練習(xí)，我更深刻地理解了語言的精髓-指針的使用。完成整個程序設(shè)計有，對指針掌握的更加熟練。同時通過直接對鏈表的操作，加深了對數(shù)據(jù)結(jié)構(gòu)的理解和認識。并在完成課程設(shè)計的過程作主動查閱了相關(guān)資料，學(xué)到了不少課本上沒有的技術(shù)知識。編程是一件枯燥乏味工作，但是只要認真專研，我們會從中學(xué)到很多在課本上學(xué)不到或者無法在課堂上掌握的知識，同時也能從中感受到編程的樂趣。興趣是可以培養(yǎng)的，只要堅持下去，面對困難我們總能夠找到解決問題的方法。計算多項式的加、乘法運算和計算結(jié)果。該程序雖然不是很大，這次我還是由請教了幾位同學(xué)和參考了網(wǎng)上的類似的題目另外也需要提出的是在這次程序設(shè)計的過程中，非常感謝老師對我們的耐心指導(dǎo)。老師在教學(xué)過程中表現(xiàn)出來的對學(xué)術(shù)專研一絲不茍的精神讓我非常有收獲。六附錄#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); /系數(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 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)/銷毀多項式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)/系數(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+; /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，返回其頭指針 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-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，返回其頭指針 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ù)以合并指數(shù)相同的項 return hf;/MultiplyPolynvoid CountPolyn(Polyn p)/實現(xiàn)多項式的計算float num=0;int x;int i;float k=1;Polyn q=p-next;printf(輸入你對x賦的值);scanf(%d,&x);printf(a);if(q=NULL)return;while (q!=NULL)k=k*(q-coef);for(i=0;iexpn);i+)k=k*x;num=num+k;q=q-next;return num;/*主函數(shù)實現(xiàn)顯示與功能選擇*/int main() int m,n,flag=0;/m、n為分別為a、b兩個多項式的項數(shù) Polyn pa=0,pb=0,pc,pd,pf;/定義各式的頭指針，pa與pb在使用前付初值NULL /pc頭指針?biāo)诘亩囗検接迷诩臃ㄖ凶鳛榻Y(jié)果，pd用在加法中，pf乘法中 printf(*歡迎使用一元多項式運算程序*n); printf(請輸入第一個多項式a的項數(shù):); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立第一個多項式a printf(請輸入第二個多項式b的項數(shù):); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立第二個多項式b /輸出菜單 printf(*n); printf(情選擇您要進行的操作：nt1.輸出多項式a和bnt2.建立多項式a+bnt3.建立多項式a-bn); printf(t4.計算多項式a*b的值nt5.退出n); for(;flag=0) printf(n); scanf(%d,&flag); if(flag=1) printf(多項式a：);PrintPolyn(pa); printf(多項式b：);PrintPolyn(pb);continue; if(flag=2) pc=AddPolyn(pa,pb); printf(多項式a+b：);PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3) pd=SubtractPolyn(pa,pb); printf(多項式a-b：);PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) pf=MultiplyPolyn(pa,pb); printf(多項式a*b：);PrintPolyn(pf); DestroyPolyn(pf);continue; if(flag=5) pf=MultiplyPolyn(pa,pb); printf(多項式a*b：); CountPolyn(pf); DestroyPolyn(pf);continue; if(flag=6) break; if(flag6) printf(Error!n);continue; /for DestroyPolyn(pa); DestroyPolyn(pb); return 0;