1、要求完成如下功能：（1） 輸入并建立多項式creatpolyn()（2） 輸出多項式，輸出形式為整數序列，序列按指數升序排列printpolyn()（3） 多項式a和b相加，建立多項式a+b，輸出相加的多項式addpolyn()（4） 多項式a和b相減，建立多項式a-b，輸出相減的多項式subpolyn()用帶表頭結點的單鏈表存儲多項式。課 程 設 計學生姓名： 學 號： 專業班級： 課程名稱： 數據結構 學年學期： 指導教師： 目 錄1需求分析說明12概要設計說明33詳細設計說明54調試分析105用戶使用說明116課程設計總結127測試結果138參考書目169. 附錄1724數 據 結 構

2、課 程 設 計1 需求分析說明1.程序所能達到的功能是（1） 輸入并建立多項式creatpolyn()（2） 輸出多項式，輸出形式為整數序列，序列按指數升序排列printpolyn()（3） 多項式a和b相加，建立多項式a+b，輸出相加的多項式addpolyn()（4） 多項式a和b相減，建立多項式a-b，輸出相減的多項式subpolyn()用帶表頭結點的單鏈表存儲多項式。2輸入的形式和輸入值的范圍 ：本系統要輸入的數據主要是有多項式中每項的系數和指數，可以把它們定義為整形數據，既可以為整數也可以為非負整數，即有符號的整形數據，由于整形數據在內存里占用兩個字節，所以它的取值范圍為-327683

3、2767。其次還有就是選擇功能時，要輸入的功能號，它們是字符型數據，取值范圍是ASS|表中的字符。例如輸入的格式如下： 請輸入a的項數：3請輸入第一項的系數與指數：2，1請輸入第二項的系數和指數：5，8請輸入第三項的系數和指數：-3.1,11請輸入b的項數：3請輸入第一項的系數和指數：7，0請輸入第一項的系數和指數：5，8請輸入第三項的系數和指數：11,9* 多項式操作程序* A：輸出多項式a B：輸出多項式b * C：輸出a+b D：輸出a-b * F：退出程序 *請選擇操作：Ca+b=2x+5x8-3.1x11+7-5x8+11x9請選擇操作：Da-b=2x+5x8-3.1x11-7+5x

4、8-11x93.輸出的形式：本系統要輸出的是把創建好的第一個多項式和第二個多項式按指數升序排列，并把進行運算后的結果也按指數升序排列輸出，輸出形式如上面所示。4.測試數據正確的輸入及輸出結果：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2） (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)2 概要設計說明模塊調用圖：主函數多項式相加建立鏈表輸出多項式 1. 抽象數據類型的定義多項式的結點類型定義typedef struct Polynomial/多項式結點類型 float coef

5、; /多項式的系數 int expn; /多項式的指數 struct Polynomial *next;/指向下一個結點*Polyn,Polynomial;建立表示一元多項式的有序表Polyn CreatePolyn(Polyn head,int m)；銷毀一元多項式void DestroyPolyn(Polyn p)；返回一元多項式的項數void PrintPolyn(Polyn P)；完成多項式加法運算Polyn AddPolyn(Polyn pa,Polyn pb)；完成多項式相減運算Polyn SubtractPolyn(Polyn pa,Polyn pb)；2.主程序的流程（1）輸出

6、提示信息（2）輸入多項式項數（3） 輸入每項的系數和指數（4）輸出選擇操作的菜單（5） 根據選擇輸出多項式（6）釋放鏈表占用的內存空間（7）完成退出程序3.各程序模塊之間的層次（調用）關系本系統首先是創建多項式，在進行排序顯示，然后按提示輸入要實現的功能。此系統有五個模塊，它們的調用關系如下：在CreatePolyn函數中調用Insert;在main函數中調用CreatePolyn(pa,m). CreatePolyn(pb,n). PrintPolyn(pa). PrintPolyn(pb). AddPolyn(pa,pb). SubtractPolyn(pa,pb). DestroyPol

7、yn(pa). DestroyPolyn(pb)3 詳細設計說明1.設計中定義的所有數據類型偽碼算法(1)多項式建立的算法該算法是用來創建多項式鏈表。首先要創建一個結點，并用一個指針指向它，并給它進行初始化void CreatPolyn(polynomial &p,int m)/輸入m項的系數和指數，建立一元多項式的有序鏈表pInitList(p); h=GetHead(p);e.coef=0.0;e.expn=-1; SetCurElem(h,e);/設置頭結點的數據元素for(i=1;inext; int flag=1;/項數計數器 if(!q) putchar(0); /若多項式為空，輸

8、出0 printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系數大于0且不是第一項 if(q-coef!=1&q-coef!=-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-coe

9、f=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);(3)多項式加法的算法該模塊是實現兩個多項式相加的算法。要求兩個多項式的指數從小到大的排列順序。 void AddPolyn(polynomial &pa,polynomial &pb) /多項式加法 ha=GetHead(pa);hb=GetHead(pb); /ha和hb分別指向pa和pb的頭結點 qa=NexPos(pa,ha);qb=NexPos(pb,hb);

10、/qa和qb分別指向和中當前結點 while(qa&qb) /qa和qb均非空 a=GetCurElem(qa);b=GetCurElem(qb); /a/和b為表中當前比較元素 switch(*cmp(a,b)case -1: /多項式pa中當前結點的指數較小 Ha=qa; qa=NexPos(pa,ha);case 0: /兩者的指數相等 sum=a.coef+b. coef; if(sum!=0.0) /修改多項式pa中當前結點的系數值 SetCurElem(qa,sum); ha=qa; else /刪除多項式pa中當前結點 DelFirst(ha,qa);FreeNode(qa);D

11、elFirst(hb,qb);FreeNode(qb); qb=NexPos(pb,qb);qa=NexPos(pa,ha);break;case 1: /多項式pb中當前結點的指數較小 DelFirst(hb,qb); InFirst(ha,qb); qb=NexPos(pb,hb); ha=NexPos(pa,ha); break if(!ListEmpty(pb) Append(pa.qb); /鏈接pb中剩余結點FreeNode(hb); /釋放pb的頭結點(4)多項式減法的算法該模塊是實現兩個多項式相減，它的設計思想和多項式相加類似，只是實現有點差別。 void SubtractPo

12、lyn(Polyn pa,Polyn pb) /求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=p-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=p-coef*=-1;return pd;2、主程序和其它主要函數 void main() int m,n,a,x;Char flag; Polyn pa=0,pb=0,pc; float ValuePolyn(Polyn head,int x) vo

13、id DestroyPolyn(Polyn p) Polyn q1,q2; q1=p-next; while(q1-next) free(q1) q1=q2;q2=q2-next; 4 調試分析 （1）、調試過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析 問題1：在進行多項式減法時，沒有真正的實現該功能，即有些多項式的系數并沒有變化。 原因：在進行最后插入處理時，沒有改變多項式的系數變為相反數。 解決方法：加了一條語句，即q-coef*=-1. 問題2：在進行多項式顯示時，出現了加號和減號同時顯示的錯誤，并且最后一想后面還帶有加號。 原因：在輸入時沒有考慮正負號顯示問題。 解決方

14、法：在結點系為負時，不要輸出正號，控制最后一個加號，只要加一條語句，即if(p-next=NULL).（2）、算法的時間復雜度和空間復雜度的分析，改進設想該算法的核心算法是多項式的排序算法和加減算法，排序算法的時間復雜度為O(n*n),而實現多項式加法的時間復雜度為O(n),所以本程序的時間復雜度為O(n*n).其中n為多項式的項數。由于多項式的排序算法和加減算法中只使用了一些簡單變量和指針變量，它的空間復雜度為O(1). 改進思想：在實現加減法過程中可以把第二多項式所占的存儲空間釋放掉，這樣便于存儲空間的回收。還有在顯示多項式時可以采取更簡潔的方式，類似于指數方式顯示形式。5 用戶使用說明1

15、本程序的運行環境為Visualc+6.02進入演示程序后，即顯示文本方式的用戶界面：3按照提示輸入需要測試的數據4選擇相應的操作，輸入對應的操作6 課程設計總結數據結構雖然已經學了一個學期，但有許多知識還不是很清楚，許多數據結構中的程序需要c語言的添加才能執行。通過課程設計對這些知識也有了更深的理解和很好的掌握。許多困惑，有許多已經通過實際操作解決了，并能夠深刻認識，但也有很多沒有明白。通過課程設計，明白到了原來開發一個小小的實用系統，是需要考慮到很多方面的問題的，許多程序在運行時有很多小錯誤，在不仔細的情況下是不容易發現及改正的，這些都是要在實踐中摸索的，另外就是要把錯誤總結，有許多錯誤或者

16、陷阱是平時自己陷進去的，因此很深刻，但也有些錯誤或者陷阱是自己還沒有接觸或者犯過的，這就應該看多些別人的總結，使自己不犯這些錯誤。不讓自己掉進這些陷阱。這樣長期總結，會對自己有很大的幫助。由于時間原因程序到目前為止，還并不健壯，在對輸入小數時，還需要進一步改進。不過通過這次課程設計，我體會到了理論與實際的差別，不僅要學習理論知識，還要勤動手，多實踐。我感覺到要真正做出一個程序并不是很容易，但只需用心去做，總會有收獲，特別是當我遇到問題去問老師，問同學，想盡辦法去解決。對于數據結構有了更深層次的理解,循環隊列中對邊界條件的處理,滿足什么條件為隊滿,滿足什么條件為隊空。在以后的學習中我會更加注意各

17、個方面的能力的協調發展，選擇一兩門技術進行深入研究，成為一個既可以統籌全局，又有一定技術專長的優秀的程序開發人員。7 測試結果1. (2x+5x8-3.1x11)+(7-5x8+11x9)的測試結果： 請輸入a的項數：3請輸入第一項的系數與指數：2 1請輸入第二項的系數和指數：5 8請輸入第三項的系數和指數：-3.1 11請輸入b的項數：3請輸入第一項的系數和指數：7 0請輸入第一項的系數和指數：5 8請輸入第三項的系數和指數：11 9* 多項式操作程序* A：輸出多項式a B：輸出多項式b * C：輸出a+b D：輸出a-b * E：退出程序 *請選擇操作：Ca+b=2x+5x8-3.1x1

18、1+7-5x8+11x92. (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)的測試結果： 請輸入a的項數：4請輸入第一項的系數與指數：6 O請輸入第二項的系數和指數：-3 1請輸入第三項的系數和指數：4.4 2請輸入第四項的系數和指數：請輸入b的項數：4請輸入第一項的系數和指數：-6 0請輸入第一項的系數和指數：-3 1請輸入第三項的系數和指數：5.4 2請輸入第四項的系數和指數：7.8 15* 多項式操作程序* A：輸出多項式a B：輸出多項式b * C：輸出a+b D：輸出a-b * E：退出程序 *請選擇操作：D a-b=12-x2-1.2x9-7.8x1

19、53. (x+x2+x3)+0的測試結果： 請輸入a的項數：3請輸入第一項的系數與指數：1 1請輸入第二項的系數和指數：1 2請輸入第三項的系數和指數：1 3請輸入b的項數：0* 多項式操作程序* A：輸出多項式a B：輸出多項式b * C：輸出a+b D：輸出a-b * E：退出程序 *請選擇操作：C a+b=x+x2+x34. (x+x3)-(-x-x-3)的測試結果： 請輸入a的項數：2請輸入第一項的系數與指數：1 1請輸入第二項的系數和指數：1 3請輸入b的項數：2請輸入第一項的系數和指數：-1 1請輸入第一項的系數和指數：-1 -3* 多項式操作程序* A：輸出多項式a B：輸出多項

20、式b * C：輸出a+b D：輸出a-b * E：退出程序 *請選擇操作：D a-b=x-3+2x+x38 參考書目1數據結構，湯文兵，華東理工大學出版社2數據結構習題與解析，李春葆，清華大學出版社3C語言課程設計案例精編，郭翠英，中國水利出版社4BAIDU搜索9 附錄帶注釋的源代碼：/頭文件#include#include#include/定義多項式的項typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if

21、(p-coef=0) free(p);/系數為0的話釋放結點 else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnq2-expn)/查找插入位置 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;Polyn CreatePolyn(Polyn head,int m)/建立一個

22、頭指針為head、項數為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調用Insert函數插入結點 return head;void DestroyPolyn(Polyn p)/銷毀多項式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;void PrintPolyn(Pol

23、yn 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!=-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

24、); 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+; printf(n);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

25、if(!a&b) return -1;/a多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空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

26、); 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; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當相加系數為0時，釋放該結點 return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa