設計程序以實現(xiàn)任意兩個高次多項式的加法和乘法運算

1、 王帆 用設計程序以實現(xiàn)任意兩個高次多項式的加法和乘法運算 第頁 共34頁 設計程序以實現(xiàn)任意兩個高次多項式的加法和乘法運算 學生姓名：王帆 指導老師：張建明 摘 要 本課程設計主要解決任意兩個高次多項式的乘法運算。所設計的數據結構應盡可能節(jié)省存儲空間，程序的運行時間應盡可能少。從題目看出所設計的程序應能達到的功能，設計好的程序要滿足以上兩點。在數據輸入方面可以根據一元高次多項式的特征，從左到右開始，按每一項指數、系數的順序輸入。這里要留意一個問題，因為要相乘的多項式項數是未知的，所以選擇什么樣的存儲方式在本課程設計中尤為重要，這也是本程序好壞的一個評定。程序通過調試運行，初步實現(xiàn)了設計目標，

2、并且經過適當完善后，將可以應用在商業(yè)中解決實際問題。 關鍵詞 高次多項式；加法；乘法；時間復雜度；空間復雜度 1 問題分析和任務定義1.1 任務定義 設計程序以實現(xiàn)任意兩個高次多項式的乘法運算。要求： （1）所設計的數據結構應盡可能節(jié)省存儲空間。（2）程序的運行時間應盡可能少。 從題目看出所設計的程序應能達到的功能，設計好的程序要滿足以上兩點。在數據輸入方面可以根據一元高次多項式的特征，從左到右開始，按每一項指數、系數的順序輸入。這里要留意一個問題，因為要相乘的多項式項數是未知的，所以選擇什么樣的存儲方式在課程設計中尤為重要，這也是本程序好壞的一個評定。 設計算法（程序）測試用例： 圖1-1

3、圖1-2 圖1-1 為正確的輸出結果，圖1-2 為錯誤的輸出結果1.2 要解決的問題（1） 怎樣實現(xiàn)兩個多項式的乘法？（2） 相乘后若有指數相同的項用什么方法合并？（3） 使用什么數據結構來滿足盡可能節(jié)省存儲空間的要求？（4） 用什么方法來輸出表達式？2概要設計和數據結構的選擇2.1 數據結構的選擇本程序選擇的數據結構是單鏈表，原因如下：鏈表的定義：（1） 鏈表是有限個具有相同數據類型的數據元素的集合，D=ai/i=1,2,，n;ai為數據元素。（2） 數據元素之間的關系R=/ai,ai+1D。（3） 數據元素ai 在存儲器中占用任意的、連續(xù)或不連續(xù)的物理存儲區(qū)域。動態(tài)鏈表： 當需要插入數據元

4、素時，臨時動態(tài)地為其申請一個存儲空間，而不是將結點放在一個定義的數組中，刪除數據元素時，可以釋放該數據元素所占用的空間，即可以根據表的實際需要臨時動態(tài)的分配存儲空間以存儲表中的數據元素。單鏈表是有限個具有相同數據類型的數據元素組成的鏈表且該鏈表的每一個結點只有一個指針域。帶頭結點的單鏈表是在單鏈表的第一個結點之前加一個同類型的結點，目的是為了使鏈表有一致的描述。本程序解決的是兩多項式相乘的問題，多項式的項數本身就是不確定的，而且相乘后的多項式可能含有指數相同的問題，這時就需要合并，合并后其中的一項就沒有用了需要刪除，不然就浪費內存空間。基于以上幾點所以采用了鏈表。鏈表具有動態(tài)生成，靈活添加或刪

5、除結點的特點，盡可能節(jié)省存儲空間。2.2 結構圖圖2-1圖2-1 即為本程序的結構圖2.3 下面是針對本程序專門定義的數據結構類型 結點的數據類型如下：typedef struct Pnodeint coef; /系數指針int exp; /指數指針struct Pnode*next;polynode;數據結構的設計思想：鏈表中的每一個結點存放多項式的一個系數非0 項。它包含三個域,分別存放放該項的系數、指數以及指向下一個多項式結點的指針。 如圖2-2 所示為多項式鏈表結點的結構。系數 指數 指針圖2-2例如2-3 所示，多項式的單鏈表表示如下 圖2-32.4 流程圖 圖2-4圖2-4為主函數

6、的流程圖 圖2-5 圖2-5為plcreate 多項式鏈表生成函數的流程圖圖2-6圖2-6為置空函數流程圖圖2-7圖2-7為output 輸出多項式函數的流程圖圖2-8圖2-8 為多項式相乘函數流程圖圖2-9圖2-9 為合并指數相同項函數的流程圖2.5 各程序模塊之間的層次（調用）關系 在執(zhí)行主函數時先調用plcreate 生成要相乘的多項式，存儲在兩個動態(tài)鏈表中，然后調用output 函數輸出兩個多項式，繼續(xù)執(zhí)行相乘函數，相乘后調用置空函數將相乘的鏈表刪除。然后，檢驗是否有指數相同的項，如果沒有則調用output 函數輸出結果，否則調執(zhí)行合并函數將指數項相同的合并，調用output 函數輸出

7、結果。3 詳細設計和編碼3.1 算法思想 先將兩個已知的多項式的指數和系數存放在指定鏈表中在執(zhí)行乘法運算。乘法運算的過程是將A 式中的第一項與B 式的每一項相乘，在將A 式的第二項與B 式的每一項相乘，依次下去直到A 式的所有項與B 式乘完為止。將相乘后所得的指數、系數存在預先建好的C 鏈表中。 C 鏈表中如果有指數相同的項就需要合并，合并時將結果放在前一個項中，將后一項刪除。這里需要將c 鏈表中的每一項都要對比一遍，這里就要發(fā)揮指針的作用了。首先定義3個指針，x、y、z，x、y 指向首元素結點z 指向第二個結點，用z 結點中指數項與x 結點的指數項比較，如果不同指針z 向后移，若相同則將z

8、結點的系數加到x 上去然后將z 所在結點空間釋放，并且指針z 后移。直到指針z 指向空后，將指針x 后移一項，并令z 指向x 的下一項，然后按上述步驟依次執(zhí)行，直到x 指向空結束。這里指針y 是z 的前驅結點他的作用是合并后結點空間釋放結點空間將此結點的前后兩項鏈接起來。本程序核心部分全部是運用while 循環(huán)語句實現(xiàn)的。3.2 算法描述例分別用單鏈表表示，并描述相乘過程。AB 圖3-1圖3-1 為A、B 兩多項式的鏈表表示A qB 圖3-2如圖3-2 所示，P=A-next; q=B-next;指針p，q 分別指向多項式的首元素節(jié)點，A B C 圖3-3 依次執(zhí)行 x=p-coef*q-co

9、ef;y=p-exp+q-expk=(polynode*)malloc(sizeof(polynode);k為暫存相乘結果的動態(tài)鏈表k-coef=x;k-exp=y; k-next=NULL; m-next=k; m=k;m 是c 鏈表的指針,繼續(xù)執(zhí)行q=q-next; 圖3-3 所示C 圖3-4 圖3-4 為多項式執(zhí)行到q-next=NULL 時的結果 PA B 圖3-5當執(zhí)行到q-next=NULL 時，指針p 后移，指針q 指向B 鏈表的首元素結點，繼續(xù)以上循環(huán)。如圖3-5 所示 圖3-6當q 指向空時，多項式相乘結束所有數據存入c 鏈表如圖3-6 所示。這樣就完成了乘法運算，相乘后的C

10、 鏈表還可能出現(xiàn)指數相同的項，這時就需要合并。例圖3-7 所示，A、B 兩式相乘結果如下圖3-7用u、d 指向頭結點，e 指向第二個結點，圖3-7 所示圖3-8u 指針跟隨e 指針，當d-exp=e-exp 時，將e 指針所指項的系數加到d 指針所指項上去。并將e 當前所指項刪除。圖3-8 所示。 r=e; /將相同項的后一項e賦予*r d-coef+=e-coef; /后項系數與前項系數相加 u-next=e-next; /將指針e所前一項指針指向e的后一項 e=e-next; free(r); /釋*r結點空間圖3-9這樣就完成了一次合并。C 鏈表變?yōu)閳D3-10 圖3-10 繼續(xù)按上述方法

11、直到將鏈表中所有同類項合并完為止。 d圖3-11 當d-next=NULL 時結束。如3-11 所示。 （1）設指針p、q 分別為指向A、B 的首元素結點，用p-coef 乘q-coef,p-exp+q-exp,并令指針p 后移。 （2）當q-next 為空時，指針p 向后移一位，指針q 繼續(xù)從B 鏈表的第一項開始，執(zhí)行p-coef 乘q-coef,p-exp 加q-exp.每執(zhí)行一次指針p 后移。 （3）重復（1）、（2）步，直到p-next 為空后，結束。將乘出結果存入C 鏈表。合并時用兩個指針指向C 鏈表，一個指針跟隨另一個當作后一個指針前驅指針，這樣合并后釋放就容易將前后結點鏈接上。綜

12、合以上分析，兩個高次多項式相乘的算法如下： polynode *p,*q,*m,*k,*d,*e,*r,*u;int x,y; /m,d,e,r,u指向C鏈表的指針 p=A-next; q=B-next; /p,q分別指向A和B多想失戀表中的第一個結點 C=（polynode*）malloc(sizeof(polynode); C-next=NULL; /建立空多項式單鏈表用來儲存多項式相乘結果 m=C; while(p!=NULL) /當A鏈表不為空時 while(q!=NULL) /當B鏈表不為空時 k=(polynode*)malloc(sizeof(polynode); /k為暫存相乘

13、結果的動態(tài)鏈表 x=p-coef*q-coef;/系數相乘 y=p-exp+q-exp;/指數相加 k-coef=x;k-exp=y; k-next=NULL; /建立空鏈表 m-next=k; m=k; /將結果放入C鏈表中 q=q-next; q=B-next; p=p-next; printf(n未合并前多項式為:n); output(C); /輸出未合并前多項式 合并同類項 d=C-next; /d指向C鏈表的頭結點 while(d!=NULL) /當C鏈表不為空時 u=d; e=u-next; /u指向*e的前驅結點 while(e!=NULL) /當e結點不為空時，執(zhí)行 if(d-

14、exp=e-exp) /后面的項與前面的項指數相同時 r=e; /將相同項中的后一項指針e賦予*r d-coef+=e-coef; /后項系數與前項系數相加 u-next=e-next; /將指針e所有前一項指針指向e的后一端 e=e-next; free(r); /釋*r結點空間 i=1; else e=e-next; u=u-next; /*e，*u分別指向下一項 d=d-next; if(i!=1) printf(n沒有指數相同的項。n); else Printf(n合并后n); output(C); Printf(n) getch() 用尾插法生成多項式鏈表的算法如下： polynod

15、e *plcreate() polynote *H,*R,*S; int c, e; H=(polynote*)malloc(sizeof(polynote); H-exp=-1; H-next=HULL; R=H; scanf(%d%d,&c,&e); while(e!=-1) S=(polynode*)malloc(sizeof(polynode); S-coef=c; S-exp=e; S-next=NULL; R=S; scanf(%d%d,%c,%e); return H; 這個算法是按照課本上介紹的尾插法建鏈表算法加以修改而成。將沒用的鏈表刪除以防浪費存儲空間。算法如下： poly

16、node *setnull(polynode *L) polynode *a,*b,*c; a=L; b=L-next; while(b!=NULL) c=b; L-next=b-next; b=b-next; free(c); return L; Output 輸出函數。 void output (polynode *h) /輸出多項式函數 h=h-nxt; if(h!=NULL) /當多項式不為空時輸出 if(h-coef!=0) /輸出多項式的第一項 if(h-exp!=0) /指數不為零時 printf(%dx%d,h-coef,h-exp); else printf(%d,h-coe

17、f); /指數為零時 else printf(0); h=h-next; /第二項以后 while(h!=HULL) /當多項式不為空時，執(zhí)行此循環(huán) if(h-coef0) /系數大于零時 if(h-exp!=0) printf(+%dx%d,h-coef,h-exp); else printf(+%d,h-coef); if(h-coefexp!=0) printf(%dx%d,h-coef,h-exp); else printf(%d,h-coef); if(h-coef=0) printf(); /系數等于零時 h=h-next以上就是按照題目功能要求和數據結構要求，編寫算法和各程序模塊

18、代碼。4 上機調試4.1 調試中遇到的問題和解決方法圖4-1 1 在開始設計output 函數時，當輸入數據系數為負數是就出現(xiàn)了圖4-1 所示+、- 號同時出現(xiàn)在表達式中。當時output 函數如下 void output(polynode *h) h=h-next; while(h!=HULL) if(h-next!=HULL) if(h-exp!=0) printf(%d%d+,h-coef,h-exp); else printf(%d+,h-coef); else if(h-exp!=0) printf(%d%d,h-coef,h-exp); else printf(%d,h-coef)

19、; h=h-next; 當時我沒想到判斷系數正負問題，所以才出現(xiàn)以上情況 ，在程序中曾加一個if 語句判別h-coef 大于0、小于0、還是等于0，判別之后在進行輸出改后為：while (n!=NULL) if(h-coef0) /系數大于零時 if(h-exp!=0) printf(+%dx%d,h-coef,h-exp); else printf(+%d,h-coef); if(h-coefexp1=0) printf(%dx%d,h-coef,h-exp); else printf(%d,h-coef); if(h-coef=0) printf(); /系數等于零時 h=h-next;圖

20、4-2 圖4-2 修改后輸出結果 2 當程序執(zhí)行到合并指數相同項時就出現(xiàn)了錯誤。調試后發(fā)現(xiàn)執(zhí)行完第一次while 循環(huán)后指向c 鏈表的指針e 不在存儲空間中，導致無法判斷while 循環(huán)，仔細檢查后，發(fā)現(xiàn)合并時將e 指針所指結點釋放后，沒有給他指定新的結點。把指針e 后移一位，這樣就解決了問題。4.2 時間空間復雜度的計算若多項式A 有n 項,多項式B 有m 項，則兩多項式相乘時為m*n ,接下來檢驗是否有同類項檢查方法是每一項都要對比所以為(m*n)!,時間復雜度為O（m*n+(m*n）!)由于各個算法是基于動態(tài)鏈表而建成的，所以各算法的空間性能均較好。4.3 設計體會 這個題目不是很難，但

21、是一開始自己卻覺的非常的吃力，不知從那里入手,下面是我這次課程設計的一些感想：（1）通過本設計實驗又將數據結構中的鏈表的知識重新溫習了一遍，并且自己能夠獨立設計一些東西，學會了在設計實驗過程時的基本步驟?；旧夏軌蛴袟l理的解決這些問題。（2）在課程設計中遇到了很多的問題，都是以前沒有發(fā)現(xiàn)的，這些問題涉及的方面很多，有的是c 語言基礎的，也有最近學習的數據結構的知識。通過本次課程設計，讓我發(fā)現(xiàn)了自己的不足。自己在學習知識上面的漏洞。希望通過彌補這些發(fā)現(xiàn)的漏洞，提高自己的專業(yè)知識水平。（3）設計過程中的解決問題的方法，讓我明白了如何學習會更有效。如何學習才不會耽誤太多的時間。也學會了解決問題的一般

22、方法：向老師、同學請教，借助網絡等等。（4）實驗過程中也走了很多的彎路，由于在開始設計的時候思路不是很清晰，對于一些問題不能很好的提出解決問題的方法，在設計過程中，代碼總是重復的修改，在很多問題上，代碼并不時最優(yōu)的。相信在以后的學習中，隨著知識的增多，問題會逐漸得到解決?？傊?，我付出了許多時間，換來的是用任何東西都不能比的財富，別人搶不走，因為他是知識。因為自己知識有限所以程序不是很好，但它是我自己一步一步編寫出來。只有好好學習，自己將來才有出路。5 測試結果及其分析圖5-1圖5-1 兩多項式相乘后沒有指數相同項輸出的結果圖5-2 兩多項式相乘后有指數相同項合并后輸出的結果圖5-2 6 用戶使

23、用說明（1）給出任意兩個高次多項式，只需按照多項式從左到右依次輸入系數值、指數值，當輸入指數值為-1 時結束。（由于程序設計的缺陷系數指數都要輸入所以結束之前系數值可隨便輸入不影響運算結果。（2）程序中指數、系數定義的是整型，所以表達式中系數值、指數值不能超出整型范圍。（3）輸入是正數直接輸入，負數要加負號。指數不能選擇-1。參考文獻1王昆侖,李紅等編著. 數據結構與算法. 北京:中國鐵道出版社,2007.2蘇仕華等編著. 數據結構課程設計. 北京：機械工業(yè)出版社 ,2005.3蘇仕華編著. 數據結構與算法解析. 合肥:中國科學技術大學出版社,2004.4郭嵩山等著. 國際大學生程序設計競賽例

24、題解. 北京:電子工業(yè)出版社,2008.5劉大有,唐海鷹等編著. 數據結構. 北京:高等教育出版社,2001.6徐孝凱編著.數據結構實用教程. 北京: 清華大學出版社,1999.7嚴蔚敏,陳文博編著. 數據結構及算法教程. 北京: 清華大學出版社,2001.8劉振安,劉燕君等編著. C 程序設計課程設計. 北京: 機械出版社,2004.9胡學鋼. 數據結構與算法設計指導. 北京: 清華大學出版社, 1999.附錄：程序源代碼/ 程序名稱：GCDXS.CPP / 程序功能：實現(xiàn)任意兩個高次多項式的加法和乘法運算/ 程序作者：王帆/* 多項式加法和乘法示例 */ #include #include

25、 #include using namespace std; /定義多項式的項類 class term public: int coef; /多項式系數 int exp; /多項式指數 /初始化項的系數和指數 term( int c=0,int e=0):coef(c),exp(e) ; /定義多項式類 class PolyArith private: list m_poly_list_first; /存儲第一個多項式 list m_poly_list_second; /存儲第二個多項式 list m_poly_list_result; /用以存儲運算結果 /多項式私有成員函數,用以乘法時的調

26、用 list Poly_add(list&poly_list_first, list&poly_list_second) list poly_list_result; / /用以存儲運算結果 list:iterator iter_first = poly_list_first.begin(); list:iterator iter_second = poly_list_second.begin(); /該while循環(huán)針對兩個鏈表迭代器都沒有指到結尾的情形 while(iter_first != poly_list_first.end()& iter_second != poly_list_s

27、econd.end() term t_temp; term t_first = (term)*iter_first; term t_second = (term)*iter_second; if(t_first.expt_second.exp) poly_list_result.push_back(t_first); iter_first+; else if(t_second.expt_first.exp) poly_list_result.push_back(t_second); iter_second+; else t_temp.coef=t_first.coef+t_second.coe

28、f; t_temp.exp=t_first.coef; poly_list_result.push_back(t_temp); iter_first+; iter_second+; /該for循環(huán)針對第一個多項式的迭代器沒有指到結尾 /第二個指到結尾的情形 for(;iter_first != poly_list_first.end();iter_first+) poly_list_result.push_back(*iter_first); /該for循環(huán)針對第二個多項式的迭代器沒有指到結尾 /第一個指到結尾的情形 for(;iter_second!=poly_list_second.end

29、();iter_second+) poly_list_result.push_back(*iter_second); return poly_list_result; public: /輸入函數，用以輸入多項式 void Poly_input() int n; cout請輸入第一個多項式的項數：n; cout按降冪輸入第一個多項式的每一項的系數和指數：; coutendl; for(int i=1;i=n;i+) term t_temp; cout請輸入第i 項系數和指數,以enter為界：; coutt_temp.coef; cint_temp.exp; m_poly_list_first.

30、push_back(t_temp); n = 0; cout請輸入第二個多項式的項數：n; cout按降冪輸入第二個多項式的每一項的系數和指數：; coutendl; for(int j=1;j=n;j+) term t_temp; cout請輸入第j 項系數和指數，以enter為界：; coutt_temp.coef; cint_temp.exp; m_poly_list_second.push_back(t_temp); /輸出函數，用以輸出多項式 void Poly_output() /用以指向輸出多項式的第一個元素 list:iterator iter = m_poly_list_re

31、sult.begin(); /輸出多項式的每一項 for(;iter!=m_poly_list_result.end();) term t_temp=*iter; coutt_temp.coefxt_temp.exp; if(+iter!=m_poly_list_result.end() cout+; coutendl; /加法函數，其基本思想同上邊的私有成員函數Poly_add() /此處不帶參數，多項式運算對象為私有數據成員 void Poly_add() list:iterator iter_first = m_poly_list_first.begin(); list:iterator

32、 iter_second = m_poly_list_second.begin(); while(iter_first != m_poly_list_first.end()& iter_second != m_poly_list_second.end() term t_temp; term t_first=(term)*iter_first; term t_second = (term)*iter_second; if(t_first.expt_second.exp) m_poly_list_result.push_back(t_first); iter_first+; else if(t_second.expt_first.exp) m_poly_list_result.push_back(t_second); iter_second+; else t_temp.coef=t_first.coef+t_second.coef; t_temp.exp=t_first.exp; m_poly_list_result.push_back(t_temp); iter_first+; iter_second+; for(;iter_first != m_poly_list_first.end();iter_first+) m_poly_list_result.push_b