1、韶關學院計算機科學學院數據結構課程設計題 目：一元多項式運算學生姓名：XXX學 號：XXXXXXXXXX專 業：計算機科學與技術班 級：XXXXXXX 指導教師姓名及職稱：XXX 講師 起止時間： 2012 年 2 月 2012 年 4 月1 需求分析1.1 課題背景及意義隨著計算機時代的到來與快速發展，計算機的處理運算能力遠遠超出了人們日常的運算能力。它以運行速度之快在人們的日常生活中大大地節約了人們的時間，并且準確度高。因此當人們面對多項式計算這類較復雜的計算問題時，計算機無疑是我們的好幫手。對此我們設計出多項式運算程序具有其意義。數據結構課程設計是一門實踐性的計算機課程，為了學好這門課程

2、，必須在掌握理論知識的同時，加強上機實踐。通過本課程的學習，能熟練掌握幾種基本數據結構的基本操作。能針對給定題目，選擇相應的數據結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現。同時，在設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。1.2 課題要求 A. 支持一元多項式的運算器B. 能夠正確輸入并顯示輸入多項式的每一項C. 要求將輸入的多項式F（X），G(X)可進行加，減，乘運算，并顯示結果D. 選做內容：除法和實現多項式的取反并實現取反之后的加減乘除運算1.3 軟件格式規定A輸入的形式 :按程序菜單的數字選擇輸入，并按提示輸入多項式。按照（系數 指數）的

3、格式進行輸入并以輸入（0 0）作為結束輸入的控制。 B. 程序所能達到的功能 :能夠進行多項式的輸入，顯示，加，減，乘，除，取反運算。C.輸出的形式:按照多項式的數學表達式的形式輸出，形如：F(x)=8X6+4X5-2X4-123X3-X1+10 D.測試的數據：1)、正確的輸入：以下是進行測試所要輸入的多項式：f(x)=8x6+4x5-2x4-123x3-x+10g(x)=2x3-5x2+x正確的運算結果：相加：f(x)+g(x)=8x6+4x5-2x4-121x3-5x2+10相減：f(x)-g(x)=8x6+4x5-2x4-125x3+5x2-2x+10相乘：=16x9-32x8-16x

4、7-232x6+613x5-125x4+25x3-51x2+10x相除：f(x)g(x)=4x3+12x2+27x 余數=-27x2-x+101.4 設計目標A. 軟件名稱：一元多項式運算器B. 軟件組成：XXXXXXX.exe（dos系統應用程序） C. 制作平臺及相關調試工具：Win32 ； Microsoft Visual Studio 2010D. 運行環境：dos/winxp/win7E. 性能特點：（1）運算器由一個可執行文件組成，具有以下特點:XXXXXXX.exe為dos系統應用程序，體積小，高效快捷，適用范圍廣，兼容性好。（2）輸入的多項式各項的系數為浮點型，指數為整型。（3

5、）XXXXXXX.exe（dos系統應用程序）的輸入和輸出形式：菜單數字選擇按回車鍵按要求輸入多項式選擇菜單對應運算法則的數字顯示運算結果或下級菜單（5）運行時間較短，精確度高，輸出形式整齊好看。（6）個別其他功能可進行再擴展。2 概要設計2.1問題解決的思路概述首先是確定結構化程序設計的流程圖，利用已學過的數據結構來構造二個存儲多項式的結構，接著把輸入，加，減，乘，除，取反運算分成五個主要的模塊：實現多項式輸入模塊、實現加法的模塊、實現減法的模塊、實現乘法的模塊、實現除法的模塊、實現多項式取反的模塊，然后各個模塊里面還要分成若干種情況來考慮并通過函數的嵌套調用來實現其功能。最后，編寫main

6、主函數以實現對多項式輸入輸出以及加、減、乘、除、取反操作，調試程序并將不足的地方加以修改?？偠灾?，就是先用自頂向下、逐步細化的設計方法來分析并畫出程序設計流程圖；然后用自下而上、逐步積累的設計方法來寫出程序。2.2 相關函數介紹說明 （1）程序定義的數據結構類型為線性表的鏈式存儲結構類型變量： typedef struct linknode（2）程序定義的其它函數：linnode *Sort(linnode *S);/多項式按指數從大到小排序linnode *Negate(linnode *head);/取反操作linnode *CreateList(); /創建多項式Void ShowLi

7、st(linnode *head) ; /顯示多項式linnode *Copy(linnode *copy); /拷貝多項式（因為做減法運算時會破壞原來輸入的多項式）linnode *SearchList(linnode *head,int x);/查找函數Linnode *Mulr(linnode *s,linnode *p)/用一個節點去乘與一個多項式（輔助除法運算）Linnode *AddSame(linnode *head);/和并多項式的同類項linnode *Add(linnode *head1,linnode *head2); / 加法linnode *Mul(linnode *

8、head1,linnode *head2); / 乘法linnode *Sub(linnode *head1,linnode *head2); / 減法Void Div(linnode *head1,linnode *head2)/除法int main( )/主函數2.3 主程序的流程基函數調用說明（1）主程序的簡要流程圖選擇界面菜單對應操作的數字結束執行完選擇的功能后返回結果并回到程序主界面調用功能對應的函數main()圖1 主程序流程圖（2）各程序模塊之間的層次（調用）關系 輸入模塊“CreateList（）”，首先按提示逐項輸入多項式的每一項，當接收到“0 0”時終止輸入，此時調用“So

9、rt（）”進行按指數降序排列后直接返回多項式的鏈表頭指針。 加法運算模塊“Add（）”，首先將兩個多項式連接成一個多項式，再調用“AddSame（）”函數進行合并連接后的多項式的同類項并返回頭指針。減法運算程序模塊“Sub( )”，首先判斷多項式1是否為空，不為空時調用“SearchList（）”進行查找操作，查找到的結果與多項式1作減法后刪除多項式2中查找到的對應項。多項式2中剩余的項取反后連接到多項式1的尾部，再調用“AddSame（）”進行合并同類項操作并返回頭指針。 乘法運算程序模塊“Mul( )”， 首先判斷輸入的多項式兩個不為空時進行多項式相乘運算，并將結構存儲在新創建的多項式中。

10、再調用“AddSame（）”進行合并同類項后返回頭指針。除法運算模塊“Div”，首先判斷第一個多項式的最高次數大于或等于第二多項式的最高次數，然后再用第一個多項式的第一項去除于第二個多項式的第一項，所得的商的第一項，然后調用“Mulr（）”用商的第一項去乘第二個多項式，用第一個多項式減去乘得的多項式，所得的差多項式再與第二個多項式的最高指數項判斷。直到第二多項式的最高次數項大于與之判斷的多項式時結束運算，并調用“ShowList（）”輸出相應的結果。 顯示函數“ShowList（）”，首先調用“Sort（）”進行排序，再按格式輸出多項式的每一項。3 詳細設計3.1 多項式存儲的實現 多項式是由

11、若干項構成的一個數學式子，其每一項包含系數與指數。然而我們可以把每一項看成是一個節點，再由這些節點連接成多項式。根據所學數據結構，采用線性表的鏈式存儲來存儲多項式的每一個項的系數與指數。其結構為：typedef struct linknode /鏈表節點的結構體float coe; /系數int index; /指數struct linknode *next; linnode; 3.2 加減乘除算法 在多項式運算的程序設計中，每一部分都會調用一些其它函數來輔助完成運算（例如：對輸入的多項式進行排序，查找，合并等），在這里主要說明加減乘運算的程序設計，其它函數的程序設計和具體調用關系請查看程序清

12、單。3.2.1加法運算的實現開始 加法計算還是比較容易實現的，將兩個傳遞過來的多項式鏈表進行復制操作（加法運算會破壞原來兩個鏈表的結構），再將復制出來的兩鏈表進行連接操作，即將第一個多項式鏈表的尾指針next指向第二個鏈表的第一個節點，最后進行合并同類項操作。 復制兩個多項式連接兩個多項式合并連接好的多項式的同類項返回合并同類項后的多項式頭指針結束圖2 加法運算原理圖對于加法運算我們并不用考慮多項式是否為空的情況，為空時連接后合并同類項處理后仍然返回空的多項式。3.2.2減法運算的實現 多項式的減法與加法類似，先將傳遞進來的兩個多項式進行判斷是否為空，若被減數為空時，減數按逐項系數取反操作。不

13、為空時，被減數的每一項的指數去查找減數中與之對應的項，找到后并同類項相減，把值賦給被減數與之對應的同類項，再在減數中刪除查找到的那個項（節點）。徹底查找后，將減數剩余的節點取反后再連接到被減數的末尾，在進行合并同類項操作并返回頭指針。開始被減數是否為空 是被減數每一項查找減數與之對應的項 否 沒找到找到加法操作，并將值賦給被減數 被減數與減數取反后連接 合并同類項 結束 圖3 減法運算原理圖3.2.3乘法運算的實現開始 多項式的乘法運算，首先是判斷多項式都不為空，為空時直接輸出結過為0。否則將其中一個多項式的每一項去乘于另外個多項式的每一項，將乘得每一項的結果連接成一個完整的多項式，然后在對其

14、進行合并同類項操作。最后返回結果頭指針。判斷兩個多項式是否都為空多項式兩兩相乘 否 合并同類項 結束 是圖4 乘法運算原理圖3.2.4除法運算的實現 首先將相除的兩個多項式降序排列，兩個多項式為非空時。判斷被除數的最高次冪大于或等于除數的最高次冪，然后用被除數的第一項去除于除數的第一項所得商的第一項，在用所得商的這一項去乘除數的所有項所得的多項式與被減數作差，在用所得差作為被減數。循環上述步驟，當被減數最高次冪小于減數最高次冪是終止循環，輸出相應的結果。開始判斷兩個多項式是否都為空 判斷最高次冪被減數=減數 否相除得商的第一項 是 乘與被除數被除數減去所得多項式得到的結果作為被除數輸出商和余數

15、否 結束 是圖5 除法運算原理圖在程序設計時應注意: 由于在輸入多項式的時候就調用了Sort（）函數進行降序排序，因此在除法運算時并不需要從新排序。3.3 函數調用關系圖此函數調用關系圖主要描述了四則運算的實現、取反及實現各運算所要調用的函數，詳情還請看程序清單。Sort()排序ShowList()顯示輸出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索節點AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()Div除法運算Copy()備份Sub()減法運算AddSame()合并Sort

16、()排序Negate()取反Copy()備份Mul()乘法運算Add()加法運算CreateList()創建main（）選擇菜單圖6函數調用關系圖4 調試分析表1 調試過程情況表序號時間出現問題解決方法12012-3-25做除法時由于沒有考慮到當兩個多項式最高次冪相等的情況，出現了輸出結果錯誤的情況加入多項式最高次冪相等的判斷情況22010-3-30乘法算法指針沖突將乘法沒新建一個節點是next=NULL32010-4-5由于指針越界ShowList()算法錯誤加入next指針的約束條件42010-4-6部分未能相加調準節點的循環遍歷條件5 用戶使用說明（1）運行XXXXXXX.exe應用程序

17、后會出現主界面； （2）選擇輸入多項式，按下回車鍵；（3）按要求輸入兩個多項式，按下回車鍵；（4）選擇所要做的運算或操作，按下回車。圖7 主界面效果圖 6 測試結果應用程序測試結果：圖8 按1輸入多項式 圖9 輸入測試數據圖10 顯示輸入的測試多項式圖11 多項式相加圖12 多項式相減圖13 多項式相乘圖14 多項式相除圖15 多項式取反操作菜單參考文獻1陳元春，王中華等.實用數據結構M.北京：中國鐵道出版社，2011.22 C語言程序設計(第三版)-譚浩強附錄：程序清單本程序設計由101150130賀榮根.cpp組成#include stdlib.h#include iostreamtype

18、def struct linknode /定義節點的結構體float coe; int index;struct linknode *next; linnode; /定義節點類型linnkodelinnode *Sort(linnode *S) /多項式按降序排列linnode *z,*s;s=S;z=new linnode;z-next=NULL;while(S-next!=NULL)for(linnode *x=S-next;x-next!=NULL;x=x-next)if(S-next-indexnext-index) z-coe=x-next-coe; x-next-coe=S-nex

19、t-coe;S-next-coe=z-coe;z-index=x-next-index;x-next-index=S-next-index;S-next-index=z-index;S=S-next;return s;linnode *Negate(linnode *head) /多項式取反 linnode *p; p=head;while(head-next!=NULL)head-next-coe=-(head-next-coe);head=head-next;return p;linnode *CreateList() /創建線性表int n=0,z=1;linnode *p,*s,*he

20、ad;float coe;int index;head=new linnode;head-next=NULL;p=head;while(z) printf(ntt請輸入：); scanf(%f,&coe); scanf(%d,&index); getchar(); if(coe!=0|index!=0) s=new linnode; s-coe=coe; s-index=index; p-next=s; s-next=NULL; p=s; else z=0;return Sort(head);void ShowList(linnode *head)/ 顯示線性表linnode *P= Sort

21、(head);if(head-next=NULL)printf(多項式為空！ );else while(P-next!=NULL) if(P-next-coe)!=0)(P-next-coe)0?printf(+%5.2f ,P-next-coe):printf(%5.2f ,P-next-coe); (P-next-index)!=0?printf(X%d,P-next-index):printf(); P=P-next;linnode *Copy(linnode *copy) linnode *d,*head3,*a;d=new linnode;head3=d;if(copy-next!=

22、NULL)while(copy-next!=NULL)a=new linnode;a-coe=copy-next-coe;a-index=copy-next-index;d-next=a;a-next=NULL;d=a;copy=copy-next;return head3;elsereturn copy;linnode *SearchList(linnode *head,int x) /查找函數linnode *p;if(head!=NULL)p=head-next;while(p!=NULL&p-index!=x) p=p-next;if(p!=NULL)return p;elseretu

23、rn NULL;else return NULL;linnode *AddSame(linnode *head) /合并同類項linnode *heads,*s,*z;heads=head;while(head-next!=NULL)linnode *x=SearchList(head-next,head-next-index); /搜索相同節點if(x!=NULL)head-next-coe+=x-coe;for(s=head-next;(s-next-index)!=x-index;)s=s-next;s-next=x-next;delete x;else head=head-next;r

24、eturn heads;linnode *Sub(linnode *head1,linnode *head2) /多項式做減法函數,并向函數傳遞兩個鏈表（即兩個待相加的多項式）linnode *s,*p,*head3; /定義三個節點指針變量s=head1; head3=s; /用于存儲第一個傳進來的鏈表的頭指針p=head2;while(s-next!=NULL) /當第一個鏈表不為空時依次循環獲取每一個節點的index值linnode *z=SearchList(p,s-next-index); /用于搜索第一鏈表的每個節點的index值在第二鏈表中是否存在并返回其節點if(z!=NULL

25、) /條件為真是，即在第二鏈表中查找到與第一鏈表中相同index值的節點s-next-coe-=z-coe; while(p-next-index)!=z-index) /用于查找搜索到節點在第二鏈表中的位置p=p-next;p-next=z-next; delete z; /在第二鏈表中刪除查找到的節點 s=s-next; /頭指針向后移動for(s-next=head2-next;s-next!=NULL;s=s-next)s-next-coe=-(s-next-coe);return AddSame(head3); /返回第一鏈表的頭指針linnode *Add(linnode *hea

26、d1,linnode *head2) /多項式加法函數linnode *s,*p,*d,*a,*head3;s=head1;p=head2;d=new linnode;head3=d;while(s-next!=NULL)a=new linnode;a-coe=s-next-coe;a-index=s-next-index;d-next=a;a-next=NULL;d=a;s=s-next;while (p-next!=NULL)a=new linnode;a-coe=p-next-coe;a-index=p-next-index;d-next=a;a-next=NULL;d=a;p=p-ne

27、xt;return AddSame(head3); /合并同類項后返回linnode *Mul(linnode *s,linnode *p) /多項式作乘法運算函數，兩個參數用于傳進兩個待相乘的多項式鏈表linnode *head1,*head2,*head3,*n,*head4; /定義鏈表指針用于存儲多項式的節點指針head1=s; /將第一個用于存儲多項式的鏈表的頭指針賦值給head1head2=p; /將第二個用于存儲多項式的鏈表的頭指針賦值給head2head4=new linnode;/創建一個頭節點head4-next=NULL;head3=head4; /用于存儲新創建的鏈表的

28、頭指針if(head1-next!=NULL&head2-next!=NULL) /兩個多項式不為空時for(;head1-next!=NULL;head2=p,head1=head1-next) /此循環用于實現多項式中的乘法運算for(;head2-next!=NULL;head2=head2-next) /此循環用于實現多項式中的乘法運算 n=new linnode; /新建一個節點用于存儲多項式相乘之后每一項的結果n-coe=(head1-next-coe*head2-next-coe); /系數相乘n-index=(head1-next-index+head2-next-index)

29、; /指數相加head3-next=n;n-next=NULL;head3=n; return AddSame(head4);elsereturn head4;linnode *Mulr(linnode *s,linnode *p) /一個節點乘與整個多項式（輔助除法運算）linnode *head2,*n,*head1,*head;head2=new linnode;head2-next=NULL;head=head2;head1=p;while(p-next!=NULL&s-coe!=0)n=new linnode;n-coe=s-coe*p-next-coe;n-index=s-inde

30、x+p-next-index;n-next=NULL;head2-next=n;head2=n;p=p-next;p=head1;return head;void Div(linnode *head1,linnode *head2) /除法linnode *temp1,*head3,*head4,*z;temp1=new linnode;temp1-next=NULL;head3=temp1; /商while(head1!=NULL&head1-next!=NULL&head1-next-index=head2-next-index) /判斷指數大小z=new linnode;z-coe=he

31、ad1-next-coe/head2-next-coe;z-index=head1-next-index-head2-next-index;temp1-next=z;z-next=NULL;temp1=z;head4=Mulr(z,head2);linnode *head5=head1;while(head1-next!=NULL)head1=head1-next;head4=Negate(head4); /取反head1-next=head4-next;head1=AddSame(head5); /合并while(head1-next!=NULL&head1-next-coe=0)head1

32、=head1-next; printf(nF(X)/G(X);printf(n商：);ShowList(head3);printf(n余數：);ShowList(head1);int main() system(color 0B);int choice,j=1;linnode *head1,*head2,*add,*sub,*mul,*copy1,*copy2;add=new linnode;sub=new linnode;mul=new linnode;head1=new linnode; head2=new linnode;copy1=new linnode;copy2=new linno

33、de;head1-next=NULL; head2-next=NULL;head1-index=NULL; head2-index=NULL;add-next=NULL;sub-next=NULL;mul-next=NULL;copy1-next=NULL;copy2-next=NULL;while(j)printf(n);printf(ntt 多項式運算 );printf(ntt*); printf(ntt*);printf(ntt* 1-輸入多項式 *);printf(ntt* 2-顯 示 *);printf(ntt* 3-相 加 *);printf(ntt* 4-相 減 *);print

34、f(ntt* 5-相 乘 *);printf(ntt* 6-相 除 *);printf(ntt* 7-多項式取反 *);printf(ntt* 0-退 出 *);printf(ntt*); printf(ntt*);printf(ntt 請選擇菜單號（0-6）進行操作:);scanf(%d,&choice);getchar();if(choice=1)head1-next=NULL; head2-next=NULL;printf(ntt請逐個輸入第1個多項式的結點，以“0 0”作為結束標記! n); head1=CreateList();printf(ntt請逐個輸入第2個多項式的結點，以“0

35、 0”作為結束標記! n); head2=CreateList(); system(cls); printf(n多項式成功輸入，請選擇計算方式！);elseif(choice=2) system(cls);printf(n多項式1：F(X)=);ShowList(head1);printf(n多項式2：G(X)=);ShowList(head2);elseif(choice=3) system(cls); if(head1-next!=NULL|head1-next!=NULL) add=Add(head1,head2); printf(n多項式：F(X)+G(X)=); ShowList(add); else printf(請輸入多項式！);elseif(choice=4) system(cls); if(head1-next!=NULL|head1-next!=NULL