一元多項式的計算課程設(shè)計報告

合肥學(xué)院

計算機科學(xué)與技術(shù)系課程設(shè)計報告2008?2009學(xué)年第二學(xué)期課程程序設(shè)計語言II課程設(shè)計課程設(shè)計名稱多項式的計算學(xué)生姓名王建敏學(xué)號0804013029專業(yè)班級計算機科學(xué)與技術(shù)（3）班指導(dǎo)教師張貫虹汪彩梅2009年6月一、課程設(shè)計題目：多項式（單項鏈表的應(yīng)用）二、分析與設(shè)計程序的基本功能（1）建立多項式（2）輸出多項式（3）刪除多項式以釋放空間（4）刪除多項式中的某一項（5）將多項式合并同類項（6）拷貝多項式（7）將多項式按指數(shù)升序排列（8）判斷兩多項式是否相等（9）兩個多項式相加，建立并輸出和多項式（10）兩個多項式相減，建立并輸出差多項式（11）兩個多項式相乘，建立并輸出積多項式（12）兩個多項式相除，建立并輸出商多項式算法設(shè)計本程序主要應(yīng)用了鏈表，結(jié)構(gòu)體和類模板。用結(jié)構(gòu)體來定義多項式的結(jié)點（即每一項），它包含三個域，分別存放該項的系數(shù)、指數(shù)以及指向下一項結(jié)點的指針；用鏈表來存儲多項式，為了節(jié)省空間，只存儲多項式中系數(shù)非0的項，用多項式鏈表類來實現(xiàn)設(shè)定的程序的基本功能。涉及的主要算法有：（1）使用尾插法創(chuàng)建多項式，即從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表尾上，直到讀入結(jié)束標志（某一項的系數(shù)為零）為止。（2）輸出一個非空的多項式鏈表，不要輸出最后一項，即輸入系數(shù)為零的結(jié)束項，用if……else語句判斷。（3）刪除整個多項式是一項一項的刪，使用鏈表刪除其結(jié)點的方法，使用free（）函數(shù)釋放存儲空間。在刪除非空的多項式的某一項時，定義k來找到要刪除的那一項的位置，再使用delete將其刪除。（4）在對多項式合并同類項時，主要有兩點，一是看兩項指數(shù)是否相等，若相等則合并成一項，二是看兩項系數(shù)和是否為零，若為零則去掉這兩項。在對多項式排序時，先合并同類項，再按指數(shù)值從小到大排序。（5）在拷貝多項式時使用重載函數(shù)，將系數(shù)和指數(shù)都拷貝給新的多項式。（6）在判斷兩多項式是否相等時，先分別對兩多項式進行排序，再從頭項開始，一項一項的比較其系數(shù)和指數(shù)，一旦有一個不相等就結(jié)束，即這兩多項式不相等，否則相等。（7）計算多項式加減，其算法思想是相同的。以多項式加法為例，先對兩多項式排序，再將兩多項式的每一項逐項相加，在相加之前，先比較兩項的指數(shù)是否相等，若相等則將系數(shù)相加，再判斷系數(shù)是否為零，若為零則刪除，否則存儲在和多項式中。若兩項指數(shù)不相等，當(dāng)多項或a指數(shù)大于多項式pb指數(shù)時，則將pa結(jié)點副本插入到和多項式PolyC尾部；當(dāng)pa指數(shù)小于pb指數(shù)時，則將pb結(jié)點副本插入到和多項式PolyC尾部，最后插入剩余結(jié)點。計算多項式乘法時，先判斷兩多項式是否為空，若為空，則返回乘多項式，否則要先對兩多項式進行合并排序，先將兩多項式的第一項相乘，即系數(shù)相乘，指數(shù)相加，其值作為乘多項式的第一結(jié)點，其后使用雙重循環(huán)將一多項式的每一項與另一多項式的每一項分別相乘，結(jié)果存到乘多項式中。計算多項式除法時，同樣要判斷兩多項式是否為空，只要有一為空，則直接返回空，否則將一多項式整個除以另一多項式，系數(shù)相除，指數(shù)相減，結(jié)果存到商多項式中。3.系統(tǒng)總框圖4.定義的主要函數(shù)及說明CreatePoly()創(chuàng)建多項式鏈表OutputPoly()輸出多項式DestroyPoly()完全刪除多項式DelPoly()刪除多項式中的某一項EqualPoly()判斷兩多項式是否相等MergePoly()-將多項式和并同類項SortPoly()將多項式按升序排列PolyAdd()多項式和的計算PolySub()多項式差的計算PolyMutiply()多項式積的計算PolyDivide()多項式商的計算三、系統(tǒng)實施源程序代碼(見后附錄)上機調(diào)試過程調(diào)試中遇到的主要問題問題一：開始用類來定義多項式鏈表的結(jié)點，即typedefstructPolyNode{}PolyNode,*PolyList，并將三個數(shù)據(jù)域設(shè)為私有成員，系統(tǒng)報錯。問題二：將多項式類的析構(gòu)函數(shù)體寫為：~Polynomial(){deletehead;deleterear;deleteLength;}，系統(tǒng)報錯。問題三：在記錄多項式項數(shù)Length時，在創(chuàng)建多項式的函數(shù)體內(nèi)，寫成：Length=n-1,編譯通過，可運行結(jié)果不正確，多了一項。問題四：在多項式類中所定義的兩個多項式的加減乘除及判斷是否相等這些功能函數(shù)本來用的是友元函數(shù)(也應(yīng)該用友元函數(shù))，例對多項式的加法用的是函數(shù)friendPolyListPolyAdd(PolyList&PolyA,PolyList&PolyB)系統(tǒng)報錯。問題五：在程序運行過程中出現(xiàn)錯誤errorC2955:'Polynomial':useofclasstemplaterequirestemplateargumentlist。解決問題解決題一：根據(jù)錯誤提示發(fā)現(xiàn)多項式類成員函數(shù)的實現(xiàn)不能訪問結(jié)點類的私有成員，在結(jié)點類里添加一個友元類friendclassPolynomial，運行后還是有錯誤，經(jīng)過反復(fù)修改，根據(jù)提示意識到自己不能解決typedef在類模板中的正確使用，導(dǎo)致反復(fù)不能運行，最后將多項式鏈表的結(jié)點用結(jié)構(gòu)體來定義，即用typedefstructPolyNode{}PolyNode,*PolyList，運行最終正確。解決題二：根據(jù)錯誤提示將析構(gòu)函數(shù)改為：~Polynomial(){deletehead;deleterear;}，運行對。解決題三：根據(jù)運行的錯誤結(jié)果將錯誤代碼改為：Length=n-2，運行正確。解決題四:據(jù)錯誤提示應(yīng)該是PolyA本是指針成員，在前加上地址運算符&會出錯，且PolyList非類名，故系統(tǒng)報錯。將&全部去掉，運行仍錯誤，反復(fù)對其修改，都不能運行，最后將友元函數(shù)改為普通函數(shù)，如上面的加法函數(shù)改為PolyListPolyAdd(PolyListPolyA,PolyListPolyB),運行正確(雖然不該在多項式類中定義這樣的函數(shù)，因為這些功能并非多項式的基本行為，但畢竟個人能力有限，只希望以后掌握更多的知識來進行彌補)。解決題五：根據(jù)錯誤指示位置發(fā)現(xiàn)在使用類模板的地方出現(xiàn)了問題，誤將voidPolynomial<T>::MergePoly(PolyListPoly)寫為voidPolynomial::MergePoly(PolyListPoly)，了解到在實現(xiàn)模板類的成員函數(shù)時，要加上<T>來限制。算法改進設(shè)想自己的課程設(shè)計還不夠完善，有些功能未設(shè)計到，有很多需要改進的地方，現(xiàn)列舉以下幾個改進設(shè)想：設(shè)想一：希望可以對某一個多項式進行插入一項或插入另一個多項式。設(shè)想二：用類來定義多項式鏈表的結(jié)點，添加構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)等基本類函數(shù)，使用友元類訪問結(jié)點的私有成員。設(shè)想三：對兩個多項式間的加減乘除及判斷是否相等使用友元函數(shù)來實現(xiàn)，因為這些功能并非多項式的行為。設(shè)想四：希望可以用磁盤文件輸入數(shù)據(jù)，并完整的清晰的將運行結(jié)果進行保存。設(shè)想五：希望自己做的系統(tǒng)界面更加美觀、實用，令讀者運行快樂。設(shè)想六：可以用重載函數(shù)來實現(xiàn)多項式間的加減乘除運算，重載運算符“+、一、X、\”，但也必須使用友元函數(shù)來寫。經(jīng)驗與體會雖然課程設(shè)計做的不夠完善，但在設(shè)計的過程中受益匪淺，通過查資料等學(xué)到了很多以前不知道或不太會應(yīng)用的知識，主要包括以下幾點：對typedef的應(yīng)用有了新的認識。如typedefint*bom將int另命名為*bom，則用bom定義的類型為int指針類型的指針，例如bomn，則n為int型的指針。typedef有利于程序的通用和移植。最主要的是對單向鏈表的使用有了更深刻的了解和掌握，因為多項式的計算要求用單向鏈表來實現(xiàn)，所以在做課程設(shè)計之前通過網(wǎng)上找資料，查參考書及問輔導(dǎo)老師等對單向鏈表的使用比以前掌握的更加到位，并且能夠靈活運用，通篇幾乎用的都是單向鏈表，這是受益的一大重點。更正了對運算符delete的使用，以前一直以為delete可以刪除一切基本數(shù)據(jù)類型的數(shù)據(jù)，以釋放它們的空間，可運行報錯。通過查看課本發(fā)現(xiàn)delete是用來刪除由new建立的對象，釋放指針所指向的內(nèi)存空間，格式為：delete指針名，這可以與運算符new一起記憶，new的功能是動態(tài)分配內(nèi)存。對重載運算符的使用也比以前更加深入，本程序是使用了重載賦值運算符“=”，來實現(xiàn)對多項式的拷貝，深記重載函數(shù)的一般語法形式為：函數(shù)類型operator運算符（形參表）｛函數(shù)體｝。由于課程設(shè)計中要求使用模板，為了正確使用模板，學(xué)習(xí)了很多關(guān)于模板使用的方法及注意事項，促使我對類模板的使用有了更深一步的理解，牢記在類模板以外定義成員函數(shù)，需采用以下的形式：（模板參數(shù)表用classT或typenameT，常用前者。）template＜模板參數(shù)表〉類型名類名＜T＞::函數(shù)名（參數(shù)表）5）不足之處本程序最大的不足便在于計算多項式的加減乘除和判斷兩多項式是否相等未使用友元函數(shù)，雖然程序仍能正確運行，但從本質(zhì)上講，不用友元函數(shù)是不正確的，因為這些功能并非單個多項式所具有的行為。本程序另一不足之處在于對磁盤文件的處理不規(guī)范，它只能存儲程序運行結(jié)果所輸出的多項式，而不能存儲多項式前的說明文字，如對某一多項式進行合并同類項，屏幕上顯示的是“合并后的PolyA為：6xA3+3.5xA7”，但文件里保存的只是“6xA3+3.5xA7”，讓旁觀者不清楚這是什么函數(shù)功能運行的結(jié)果。這些不足主要是因為自己對知識的掌握不是很牢固，不能正確靈活運用所學(xué)知識。針對這些不足，我以后要認真學(xué)習(xí)這些不足的知識，深刻理解并掌握它們。測試結(jié)果及其分析運行說明：運行程序后，先出現(xiàn)以下主菜單:（說明：界面縮小了）幫助請按創(chuàng)建一元多項式請按輸出一元多項式請按修改一元多項式請按拷貝一元多項式請按重新創(chuàng)建多項式請技進入多項式運算菜單請按退出系統(tǒng)請按Q〈Quit〉四"D:\MyDocijJTients\學(xué)習(xí)\C++學(xué)習(xí)、課程設(shè)計\Debug\Polynonnal.exe歡迎進入一元多項式計算程序-%O洪O洪O米O米O淤O洪O洪O米O洪O送※云※※※※※※※※云云※※米米※※※送送※※云※※※※※※※去※※米?「-送O送O淤O淤O淤O洪O云O洪O米O淤O米.※※※※云※※※※※云云※※米米※※※送送※※米※※.※※※※※云※去※.睛按照菜單指示選擇操作:上面有提示語句，分別按照這些提示語句進行選擇，就會出現(xiàn)相應(yīng)的菜單。-I口|x選WWW示的的物的物指式式式式式單項項項項項-I口|x選WWW示的的物的物指式式式式式單項項項項項蒙多多多富照人A-A-A-人一志S3D:\MyDoci-unents\學(xué)習(xí)\C++學(xué)習(xí)'課程設(shè)計\Debug\Polynomial.exe幫助此一元多項式計算系統(tǒng)的主要功能為：〈1〉對于一個多項式，可以進行創(chuàng)建，輸出，刪除，修改及拷貝；〈2〉對于兩個多項式，可以判斷是否相等，并進行加減乘除基本運算。希望進入此系統(tǒng)的人能夠獲得需要的信息，謝謝使用！隋輸入R返回主菜單嘴聯(lián)照菜單指示選擇操作:4）創(chuàng)建PolyA多項式函‘D:\MyDocuinents\學(xué)習(xí)"C++學(xué)習(xí)、課程設(shè)計\Detiug\PolynojTiial.exew5）先輸出PolyA并記錄項數(shù)，再刪除PolyA4）對剛未刪除的PolyA修改，進入修改菜單函D:\HtyDucmients、?學(xué)習(xí)'C++?學(xué)習(xí)'課程設(shè)計\Debug\Polynomial.exe-|i5|X晴按照菜單指示選擇操作：4XXXXXXMXXJ<X1O<KJ<喧了又尤迎i井/、￥多工Si式修改.序HXXXXXNXXXXNXNNJC★★★★★★★★★★★★★★★★★gmgNXXXXNXNXXXKNXXXXNXNXXXKXXXNXXXXNXNXXXKXXXNXXXXNXNXXXKXXX★★★★☆☆☆☆統(tǒng)項項出系一某退除并察刪富女■■■■dESQ☆☆☆☆★★★★KXXXKNK*HXKNKXXXKNK*HXKNKXXXKNK*HXKN隋技照菜單指示選擇操作：d隋輸入肝刪除第幾項：2刪除后J<JPolyA為：2xA3+4xA3+3.5xA7情管照房單指示選擇操作："冶并后的PolyA^：6xA3+3.5xA7情按照葦單指示選擇操作：S腓序后的Pol伸為：3.5xA7+6xA3睛按照菜單指示選擇操作：.-|n|x|5）拷貝PolyA,再創(chuàng)建一個PolyB多項式并輸出-|n|x|四D:\MyDocuinentsl學(xué)習(xí)\C++學(xué)習(xí)'.課程設(shè)計\Debug\P口lynDmial.exe按照葦單指示選擇操作：5貝后的Poly7^：3.5xA7+6xA3乏照葦單指示選擇操作：6N入多項式的真項的系數(shù)和指數(shù)：N入多項式的害項的系數(shù)和由數(shù)：斤入多項式的害項的系數(shù)和魚數(shù)：亦入多項式的害項的系數(shù)和瑁數(shù):亦入多項式的竄5項的系數(shù)和輅數(shù)：g的PolyB^J：2xA5+4.5xA3+9x^7+56）進入多項式運算菜單（加減乘除及判斷兩多項式是否相等）

SD:\MyDgumwt或?qū)W習(xí)\C++^習(xí)k課程設(shè)liADmbugW口lynonaalMKm-Hxl主一冬棗枚棗仗按^fll'lH請請請請相磐秋*綻式之之之之苗布系項式式式式主出多項項項項回退兩多多多多返接斷^直■■,■■■■■■明二」：I按nsNDRQ情按照￥單指示選枝操作"F兩個多項式不相霸草攜照萊單指示選擇操作；aPolvfi+Po1VB：12.5xA7*2xA5+5.5xA4+10.5xA3值按照菜單指示選擇操作：sPolyfi-PolyB:-5,5xA7+-2xA5+-5.5xA4+l.5xA3草按照菜單指示選擇操作：MPolyfi*PolyB!31.5xA14+7xA12+19.2GxAll+G9.