一元多項(xiàng)式運(yùn)算課程設(shè)計(jì)報(bào)告

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　2011 ～2012 學(xué)年第 1 學(xué)期</p><p>　　學(xué)生姓名： 專業(yè)班級(jí)： 10級(jí)計(jì)科1班 </p><p>　　指導(dǎo)教師：

2、 工作部門： 計(jì)算機(jī)學(xué)院 </p><p><b>　　一、課程設(shè)計(jì)題目</b></p><p><b>　　一元多項(xiàng)式的運(yùn)算</b></p><p><b>　　二、課程設(shè)計(jì)內(nèi)容</b></p><p>　　1．一元多項(xiàng)式的存儲(chǔ)</

3、p><p>　　2．一元多項(xiàng)式的加法與減法</p><p>　　3．一元多項(xiàng)式的乘法</p><p><b>　　三、進(jìn)度安排</b></p><p>　　1、2011年12月19日，設(shè)計(jì)動(dòng)員，布置任務(wù)</p><p>　　2、2011年12月20日到21日，查閱資料，分析、討論與設(shè)計(jì)</p&g

4、t;<p>　　3、2011年12月22日到27日，編寫程序，進(jìn)行調(diào)試</p><p>　　4、2011年12月28日到29日完成模塊聯(lián)調(diào)，進(jìn)行測(cè)試</p><p>　　5、2011年12月30日，成果驗(yàn)收，完成設(shè)計(jì)報(bào)告</p><p><b>　　四、基本要求</b></p><p>　　1．用C語(yǔ)言實(shí)現(xiàn)

5、一元多項(xiàng)式的運(yùn)算.</p><p>　　2．利用鏈表實(shí)現(xiàn)一元多項(xiàng)式運(yùn)算的存儲(chǔ).</p><p>　　3．該程序具有加法、減法、乘法基本運(yùn)算功能.</p><p>　　4. 程序的各個(gè)功能模塊要求用函數(shù)的形式實(shí)現(xiàn).</p><p>　　5. 完成設(shè)計(jì)任務(wù)并書寫課程設(shè)計(jì)報(bào)告。</p><p><b>　　目 錄

6、</b></p><p><b>　　一 概述3</b></p><p>　　二 總體方案設(shè)計(jì)4</p><p><b>　　三 詳細(xì)設(shè)計(jì)6</b></p><p>　　四 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明12</p><p>　　五 課程設(shè)計(jì)總結(jié)16</

7、p><p><b>　　參考文獻(xiàn)17</b></p><p>　　附錄：程序源代碼18</p><p><b>　　一 概述</b></p><p><b>　　課程設(shè)計(jì)的目的</b></p><p>　　1．理解和掌握該課程中的有關(guān)基本概念，程序設(shè)計(jì)思

8、想和方法。</p><p>　　2．培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)獨(dú)立完成課題的能力。</p><p>　　3．培養(yǎng)勇于探索、嚴(yán)謹(jǐn)推理、實(shí)事求是、有錯(cuò)必改，用實(shí)踐來(lái)檢驗(yàn)理論，全方位考慮問(wèn)題等科學(xué)技術(shù)人員應(yīng)具有的素質(zhì)。</p><p>　　4．掌握從資料文獻(xiàn)、科學(xué)實(shí)驗(yàn)中獲得知識(shí)的能力，提高學(xué)生從別人經(jīng)驗(yàn)中找到解決問(wèn)題的新途徑的悟性，初步培養(yǎng)工程意識(shí)和創(chuàng)新能力。</p>

9、;<p><b>　　課程設(shè)計(jì)的要求</b></p><p>　　1．用C語(yǔ)言實(shí)現(xiàn)一元多項(xiàng)式的運(yùn)算.</p><p>　　2．利用鏈表實(shí)現(xiàn)一元多項(xiàng)式運(yùn)算的存儲(chǔ).</p><p>　　3．該程序具有加法、減法、乘法基本運(yùn)算功能.</p><p>　　4. 程序的各個(gè)功能模塊要求用函數(shù)的形式實(shí)現(xiàn).</p&

10、gt;<p>　　5. 完成設(shè)計(jì)任務(wù)并書寫課程設(shè)計(jì)報(bào)告。</p><p><b>　　二 總體方案設(shè)計(jì)</b></p><p><b>　　1程序設(shè)計(jì)</b></p><p>　　對(duì)多項(xiàng)式存儲(chǔ)的解釋與說(shuō)明：多項(xiàng)式，顧名思義是含有多個(gè)單項(xiàng)式的，所以很容易讓程序員聯(lián)想到的是鏈?zhǔn)絾捂湵?，因?yàn)殒準(zhǔn)降膯捂湵肀软樞虻牟僮?/p>

11、靈活，鏈?zhǔn)降谋阌诓迦牒蛣h除。</p><p>　　我對(duì)多項(xiàng)式的存儲(chǔ)思考了很多常見(jiàn)的輸入錯(cuò)誤，必須要對(duì)輸入的每個(gè)單項(xiàng)式進(jìn)行校驗(yàn)，符合條件的就存入，反之就刪除并提示重新輸入，所以我的程序中也是選擇鏈?zhǔn)絾捂湵韥?lái)存儲(chǔ)多項(xiàng)式的，這樣就給我程序后期的算法設(shè)計(jì)帶來(lái)了很多的好處。</p><p><b>　　頭結(jié)點(diǎn)</b></p><p>　　如上頭結(jié)點(diǎn)，是采

12、用的結(jié)構(gòu)體形式，其中大的方面分為兩個(gè)域，分別為data域和next域，其中data域又是一個(gè)嵌套的結(jié)構(gòu)體，里面又分為coef 和expn兩個(gè)域，而next域是指向下一個(gè)結(jié)點(diǎn)的指針域。初始化頭結(jié)點(diǎn)時(shí)，我將coef 和expn賦初值為 0 和 -1，因?yàn)轭^結(jié)點(diǎn)在整個(gè)算法中都沒(méi)有參與計(jì)算，只是起到一個(gè)連接的作用，而其指數(shù)域expn為 -1 是起標(biāo)志性的作用。</p><p>　　整體設(shè)計(jì)思路：模仿DOS界面，用命令行來(lái)

13、操控整個(gè)程序的運(yùn)行；</p><p>　　算法的整體思路：先寫命令行函數(shù)，然后將一元多項(xiàng)式運(yùn)算的函數(shù)插入到命令行函數(shù)中，以達(dá)到函數(shù)調(diào)用的目的；</p><p>　　主要特點(diǎn)：可以實(shí)現(xiàn)一元多項(xiàng)式的DOS界面命令操控；</p><p>　　具體功能：用命令調(diào)用函數(shù)，以實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)、相加、相減、相乘的功能，還有顯示、銷毀、清屏、幫助、退出等命令。</p>

14、;<p><b>　　2.主要問(wèn)題解決</b></p><p>　　我所承擔(dān)的設(shè)計(jì)工作是實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)、相加、相減、相乘的功能，而我就想到了模仿DOS界面命令形式，采用命令操作來(lái)實(shí)現(xiàn)本次課程設(shè)計(jì)的要求，其中還加入了一些另外的功能，比如DOS界面的幫助、清屏、退出等命令。</p><p><b>　　3.程序的主要模塊</b>&

15、lt;/p><p>　　如上1、2所提到的，我采用的是模仿DOS命令界面來(lái)實(shí)現(xiàn)多項(xiàng)式的存儲(chǔ)以及其相加、相減、相乘等功能。所以我設(shè)計(jì)的程序模塊主要有兩大模塊，其分別為命令行調(diào)用模塊和一元多項(xiàng)式的存儲(chǔ)、運(yùn)算模塊。</p><p>　　3.1命令行調(diào)用模塊</p><p>　　在此模塊中，我也使用了結(jié)構(gòu)體來(lái)存儲(chǔ)相關(guān)命令，但這里采用的是順序的鏈表，因?yàn)樵谑褂妹钚泻瘮?shù)的時(shí)候會(huì)有

16、指針偏移尋找相關(guān)命令的函數(shù)指針，所以用順序有利益控制循環(huán)使用。</p><p>　　命令行的節(jié)點(diǎn)形式，pCmdName為命令名，pCmdInfo為命令的功能說(shuō)明，pFun是自定義的一個(gè)函數(shù)指針內(nèi)型，也就是存儲(chǔ)相關(guān)命令的函數(shù)指針。</p><p>　　然后就寫了一個(gè)命令行輸入函數(shù)CmdProc，在此函數(shù)里面用while循環(huán)來(lái)輸入相關(guān)的命令，用庫(kù)函數(shù)strcmp來(lái)核對(duì)輸入的命令，以達(dá)到調(diào)用相關(guān)

17、命令函數(shù)的效果。而相關(guān)命令函數(shù)里面就調(diào)用下面模塊中的相關(guān)函數(shù)。</p><p>　　3.2一元多項(xiàng)式的存儲(chǔ)、運(yùn)算模塊</p><p>　　在此模塊中，我使用的鏈?zhǔn)絾捂湵韥?lái)存儲(chǔ)多項(xiàng)式的，相關(guān)的介紹看上面的 1.程序設(shè)計(jì) 中的詳細(xì)說(shuō)明。 </p><p>　　此模塊主要的幾大功能函數(shù)為createLink創(chuàng)建鏈表，printList輸出鏈表，addPolyn相加函數(shù)，s

18、ubstractPolyn相減函數(shù)，mulPolyn相乘函數(shù)。</p><p>　　還有相關(guān)的輔助函數(shù)copyLink復(fù)制多項(xiàng)式函數(shù)，locateLink核對(duì)單項(xiàng)式函數(shù)，destroyLink銷毀結(jié)點(diǎn)函數(shù)。</p><p>　　相關(guān)的主要函數(shù)和輔助函數(shù)之間的聯(lián)系如上所示。</p><p><b>　　三 詳細(xì)設(shè)計(jì)</b></p>

19、<p>　　1.一元多項(xiàng)式運(yùn)算函數(shù)設(shè)計(jì)</p><p>　　1.1創(chuàng)建多項(xiàng)式的過(guò)程</p><p>　　編寫此過(guò)程中，我采用了鏈?zhǔn)絾捂湵淼男问剑倘蛔詈笠粋€(gè)區(qū)域是指針next域，其中多項(xiàng)式結(jié)點(diǎn)中data域里又嵌套了一個(gè)結(jié)構(gòu)體，即將data域劃分為系數(shù)coef和指數(shù)expn兩個(gè)區(qū)域。</p><p><b>　　頭結(jié)點(diǎn)</b></

20、p><p>　　這是創(chuàng)建多項(xiàng)式的過(guò)程，此多項(xiàng)式為15*x^2+23x^23+17x^8 ，當(dāng)然了在創(chuàng)建多項(xiàng)式的過(guò)程中還有更為細(xì)密的校驗(yàn)，如：（在輸入的過(guò)程中）</p><p><b>　　1.指數(shù)為負(fù)校驗(yàn)：</b></p><p>　　2.系數(shù)為 0 的校驗(yàn)：</p><p>　　3.輸入指數(shù)相同的校驗(yàn)：</p>

21、<p>　　黑體函數(shù)locateLink是一個(gè)判斷指數(shù)是否與多項(xiàng)式中已存在的某項(xiàng)相同。</p><p><b>　　補(bǔ)充：</b></p><p>　　在校驗(yàn)3之前必須將每次輸入的單項(xiàng)式按從小到大的順序排列，這也為locateLink和下面的相加、相減函數(shù)做了簡(jiǎn)單的鋪墊。我采用的遍歷發(fā)找到每次輸入的單項(xiàng)式應(yīng)在的位置，然后插入。</p>&l

22、t;p>　　1.2 多項(xiàng)式輸出實(shí)現(xiàn)過(guò)程</p><p>　　在輸出之前必須對(duì)傳入?yún)?shù)指針進(jìn)行校驗(yàn)：</p><p>　　本來(lái)一開始我想的是從多項(xiàng)式的第一個(gè)結(jié)點(diǎn)一次輸出，這樣很簡(jiǎn)單啊，可是我發(fā)現(xiàn)這樣的通用性很差，所以我就想到了先將第一個(gè)結(jié)點(diǎn)分開輸出，然后再依次用循環(huán)輸出其它結(jié)點(diǎn)，這樣就大大地提高了此函數(shù)的通用效果。同時(shí)在輸出各結(jié)點(diǎn)時(shí)，我還對(duì)系數(shù)、指數(shù)進(jìn)行了討論，（系數(shù)不可能為0）以多項(xiàng)

23、式的第一項(xiàng)系數(shù)大于0的情況輸出為例，如下：</p><p>　　如果指數(shù)為0時(shí)，只輸出系數(shù)</p><p>　　如果系數(shù)和指數(shù)都為1時(shí)就不用輸出1，只輸出x</p><p>　　如果系數(shù)或指數(shù)其中一個(gè)為1的時(shí)候，也不用輸出1，其它的照原樣輸出：</p><p>　　1.3多項(xiàng)式相加過(guò)程</p><p>　　在兩個(gè)多項(xiàng)式

24、相加對(duì)其進(jìn)行了保護(hù)，將兩個(gè)多項(xiàng)式分別復(fù)制給了另外兩個(gè)多項(xiàng)式中。</p><p>　　同樣也對(duì)兩個(gè)多項(xiàng)式進(jìn)行了校驗(yàn)：</p><p>　　如果校驗(yàn)正確，則進(jìn)行相加，如下：</p><p>　　兩個(gè)多項(xiàng)式?jīng)]有指數(shù)相同時(shí)，算法中結(jié)點(diǎn)的變化如下：</p><p>　　（“蛇形連接”的尾是“和”的next域，而頭就從在“加數(shù)”和“被加數(shù)”中尋找指數(shù)小的

25、項(xiàng)，然后通過(guò)指針偏移連接。）</p><p>　　兩個(gè)多項(xiàng)式中如果有指數(shù)相同的的項(xiàng)，則先相加存到其中一個(gè)多項(xiàng)式， 然后再用上面1的“蛇形連接”的方法連接，不過(guò)唯一要注意的就是要將指數(shù)相同的項(xiàng)中未被累加存儲(chǔ)的那項(xiàng)給跳過(guò)，不用連接。</p><p>　　3. 但是在指數(shù)相同的項(xiàng)相加時(shí)還要注意一點(diǎn)，那就核對(duì)相加的結(jié)果，即對(duì)存到其中一個(gè)多項(xiàng)式中的項(xiàng)的系數(shù)，必須進(jìn)行非0 的校驗(yàn)。因?yàn)閮煞N情況

26、的結(jié)點(diǎn)連接方式不同：</p><p>　　當(dāng)然了如果校驗(yàn)不正確，則有：</p><p>　　1.4多項(xiàng)式相減過(guò)程</p><p>　　相減函數(shù)就很簡(jiǎn)單了，就是想將第二個(gè)多項(xiàng)式的所有項(xiàng)的系數(shù)化為負(fù)號(hào)，然后再與第一個(gè)多項(xiàng)式相加，同樣在函數(shù)之前使用了“復(fù)制copyLink”多項(xiàng)式結(jié)點(diǎn)的操作：</p><p><b>　　補(bǔ)充：</b

27、></p><p>　　黑體函數(shù)destroyLink是銷毀單鏈表的函數(shù)，是為了釋放內(nèi)存空間的：</p><p>　　具體的函數(shù)代碼如下：</p><p>　　同時(shí)destroyLink函數(shù)也是命令行DesPolyn調(diào)用的主要函數(shù)。</p><p>　　1.5多項(xiàng)式相乘過(guò)程</p><p>　　由于相乘過(guò)程中只需

28、用其中一個(gè)多項(xiàng)式的每一項(xiàng)依次去乘另一個(gè)多項(xiàng)式的每一項(xiàng)，依次形成多項(xiàng)式，并累加到同一個(gè)多項(xiàng)式中，這樣最后得到了所要的結(jié)果了，并及時(shí)銷毀臨時(shí)的多項(xiàng)式：</p><p>　　2.模仿DOS命令行設(shè)計(jì)</p><p>　　命令行函數(shù)中定義的是順序單鏈表，第一個(gè)域?yàn)樽址羔槪蠲?，?lt;/p><p>　　二個(gè)域也是字符串指針域（命令功能），第三個(gè)域?yàn)楹瘮?shù)指針域（命令函數(shù)

29、）。</p><p>　　然后分別寫了以上9個(gè)函數(shù)，并用函數(shù)指針執(zhí)行了對(duì)應(yīng)的函數(shù)，隨后寫了個(gè)調(diào)用命令的函數(shù)CmdProc，在這里面進(jìn)行循環(huán)輸入命令字符串，然后用strcmp比較輸入的字符串與命令名，如果相同則調(diào)用相應(yīng)函數(shù)指針?biāo)赶虻暮瘮?shù)。</p><p>　　四 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明</p><p>　　1.程序的源代碼：（見(jiàn)附錄）</p><

30、;p>　　2. 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明：</p><p><b>　　運(yùn)行結(jié)果圖片一：</b></p><p>　　說(shuō)明：第一次輸入的命令有誤，所以緊接著就是提示語(yǔ)句。在使用Help之后就 </p><p>　　顯示了該模擬DOS界面內(nèi)的命令與其功能，而后如果之前沒(méi)有創(chuàng)建多項(xiàng)式，則你輸入的其它要用到多項(xiàng)式的命令都會(huì)無(wú)效，而且還會(huì)給予相應(yīng)

31、的提示，要我們先創(chuàng)建多項(xiàng)式。隨后我創(chuàng)建了兩個(gè)相同的多項(xiàng)式（1+x），然后把兩個(gè)多項(xiàng)式顯示出來(lái)。</p><p><b>　　運(yùn)行結(jié)果圖片二：</b></p><p>　　說(shuō)明：由于界面內(nèi)容太多，所以我就輸入了Clear命令。按下回車后結(jié)果如上圖。</p><p><b>　　運(yùn)行結(jié)果圖片三：</b></p>

32、<p>　　說(shuō)明：雖然上面的采用了Clear清屏操作，但是其不影響原有多項(xiàng)式的內(nèi)容，所以我有一次顯示了原來(lái)輸入的兩個(gè)多項(xiàng)式，隨后操作了相加、相減、相乘的命令，最后銷毀了多項(xiàng)式。如果在銷毀多項(xiàng)式之后還想進(jìn)行操作，就應(yīng)該再次創(chuàng)建多項(xiàng)式，不然系統(tǒng)會(huì)再次提醒你未創(chuàng)建多項(xiàng)式。</p><p><b>　　運(yùn)行結(jié)果圖片四：</b></p><p>　　說(shuō)明：這是未創(chuàng)建多

33、項(xiàng)式之前的錯(cuò)誤命令操作，以及退出命令Exit。</p><p><b>　　運(yùn)行結(jié)果圖片五：</b></p><p>　　說(shuō)明：第二次操作，創(chuàng)建了不同的兩個(gè)多項(xiàng)式，已經(jīng)其相關(guān)命令操作。</p><p>　　3.算法的改進(jìn)設(shè)想：</p><p>　　最開始想到的創(chuàng)建多項(xiàng)式方法很簡(jiǎn)單，并沒(méi)有對(duì)多項(xiàng)式進(jìn)行指數(shù)由小到大的排列，最

34、后到多項(xiàng)式相加的時(shí)候才發(fā)現(xiàn)有點(diǎn)麻煩了，每次都要用兩個(gè)指針?lè)謩e從兩個(gè)多項(xiàng)式的鏈表的頭遍歷到尾，找其有沒(méi)有指數(shù)相同的兩項(xiàng)，然后對(duì)其系數(shù)相加。這樣就很消耗時(shí)間，而且還改變了原有的兩個(gè)多項(xiàng)式。所以我又寫了個(gè)“復(fù)制函數(shù)”，就是將一個(gè)多項(xiàng)式復(fù)制到另一個(gè)里面，已達(dá)到保護(hù)原有的多項(xiàng)式的作用。而且一早將多項(xiàng)式進(jìn)行了排序，在相加時(shí)將兩個(gè)原多項(xiàng)式進(jìn)行“保護(hù)”，隨后只需要判斷兩個(gè)復(fù)制過(guò)來(lái)的多項(xiàng)式最前面的指數(shù)是不是相等，采用“蛇形連接”的方式將兩個(gè)復(fù)制多項(xiàng)式中的

35、結(jié)點(diǎn)連接到另一個(gè)多項(xiàng)式中。</p><p>　　對(duì)于相減函數(shù)就簡(jiǎn)單多了，只需將第二個(gè)多項(xiàng)式的系數(shù)全部變?yōu)樨?fù)數(shù)，然后再將其與第一個(gè)多項(xiàng)式進(jìn)行相加。</p><p>　　對(duì)于相乘的函數(shù)，就是采用一般的算法，用其中一個(gè)多項(xiàng)式中每一項(xiàng)依次去乘另一個(gè)多項(xiàng)式，然后將其都相加起來(lái)。</p><p>　　對(duì)于命令行的函數(shù)，由于這個(gè)這需要定義一個(gè)屬于命令行的結(jié)構(gòu)體，里面含有三個(gè)內(nèi)容：

36、1.命令名稱；2.命令功能；3.命令名對(duì)應(yīng)的函數(shù)指針。再寫一個(gè)輸入命令的函數(shù)進(jìn)行調(diào)用相關(guān)的命令函數(shù)。</p><p>　　4.時(shí)間復(fù)雜度分析：</p><p>　　在createPolyn創(chuàng)建多項(xiàng)式的函數(shù)中，用了個(gè)while對(duì)多項(xiàng)式進(jìn)行指數(shù)由小到大的排序，是為后面的相加函數(shù)做鋪墊。時(shí)間復(fù)雜度為O(n) 。</p><p>　　由于addPolyn函數(shù)中采用的是“蛇形

37、連接”，所以其時(shí)間復(fù)雜度為O(m+n)。</p><p>　　由于mulPolyn函數(shù)中采用的是用其中一個(gè)多項(xiàng)式中每一項(xiàng)依次去乘另一個(gè)多項(xiàng)式，所以時(shí)間復(fù)雜度為O(n*m)。</p><p>　　其它的輔助函數(shù)，如：輸出多項(xiàng)式函數(shù)printList、復(fù)制多項(xiàng)式函數(shù)copyLink</p><p>　　、校驗(yàn)輸入單項(xiàng)式有沒(méi)有指數(shù)相同的函數(shù)locateLink 的時(shí)間復(fù)雜

38、度都為O(n)。</p><p><b>　　五 課程設(shè)計(jì)總結(jié)</b></p><p><b>　　1.程序總結(jié)：</b></p><p>　　通過(guò)這個(gè)的課程設(shè)計(jì)，我進(jìn)一步的鞏固了鏈?zhǔn)絾捂湵淼氖褂?，以及寫命令行的大致步驟。而且我已掌握一元多項(xiàng)式所要求的基本算法。</p><p>　　我的程序代碼完全

39、符合這次的課程要求，我通過(guò)模仿DOS命令行的形式來(lái)實(shí)現(xiàn)一元多項(xiàng)式的具體功能，其中的命令基本上很完善，初步的展現(xiàn)了我對(duì)命令行的理解與使用。在一元多項(xiàng)式的算法實(shí)現(xiàn)中，也幾乎是盡善盡美的，由于整個(gè)過(guò)程是采用的鏈?zhǔn)絾捂湵?，所以全部輸入和輸出的過(guò)程都有指針或者是數(shù)據(jù)的校驗(yàn)內(nèi)容，這樣就更加增強(qiáng)了代碼的可行性。</p><p>　　2.程序進(jìn)一步設(shè)想：</p><p>　　我的程序代碼滿足了這次課程設(shè)計(jì)

40、的要求，但我想我還沒(méi)有做到最完美的，因?yàn)樵谝辉囗?xiàng)式的運(yùn)算中應(yīng)該是有除法的，所以這樣就有問(wèn)題了，那我的程序里面還應(yīng)該加上指數(shù)為負(fù)數(shù)的操作，也就是除法的間接性實(shí)現(xiàn)的步驟。</p><p>　　對(duì)于一元多項(xiàng)式的除法以及指數(shù)為負(fù)的運(yùn)算提出假設(shè)：我想應(yīng)該可以寫個(gè)一元多項(xiàng)式相除的函數(shù)，是乘法函數(shù)的逆過(guò)程，只不過(guò)要在相除之前先確定兩者之間的關(guān)系是能夠除得盡的，不然這樣就很麻煩了。</p><p>　　

41、對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程的思考：</p><p>　　通過(guò)這次課程，我更深入的了解到《數(shù)據(jù)結(jié)構(gòu)》這門課程對(duì)于程序員來(lái)說(shuō)很重要，因?yàn)槌绦虻膬纱蠼M成成員之一就是數(shù)據(jù)結(jié)構(gòu)。程序的核心是算法，同時(shí)程序的實(shí)現(xiàn)也要靠數(shù)據(jù)結(jié)構(gòu)，所以數(shù)據(jù)結(jié)構(gòu)也是程序的主要成員，所以說(shuō)學(xué)好數(shù)據(jù)結(jié)構(gòu)是必須的。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 譚

42、浩強(qiáng)，C程序設(shè)計(jì)題解與上機(jī)指導(dǎo)（第二版），北京，清華大學(xué)出版社，2000年9月。</p><p>　　[2] 嚴(yán)蔚敏 吳偉民 ，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），北京，清華大學(xué)出版社，2007年</p><p>　　[3] [美] James P.Cohoon ，Jack W.Davidson 著，劉瑞挺 韓毅剛 盛素英 劉海嘉 等譯 ， C++ 程序設(shè)計(jì)（第三版），北京，電子工業(yè)出版社，2002年1

43、月</p><p>　　[4] 繆淮扣 顧訓(xùn)穰 沈俊 ，數(shù)據(jù)結(jié)構(gòu)(C++實(shí)現(xiàn)) ，北京，科學(xué)出版社，2001年</p><p><b>　　附錄：程序源代碼</b></p><p>　　#include <iostream></p><p>　　using namespace std;</p>

44、<p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　#include "stdio.h"</p><p>　　typedef struct</p><p><b>　　{ </b><

45、;/p><p>　　float coef;//結(jié)點(diǎn)類型</p><p><b>　　int expn;</b></p><p>　　}polynomial;</p><p>　　typedef struct LNode</p><p><b>　　{ </b></p>

46、<p>　　polynomial data;//鏈表類型</p><p>　　struct LNode *next;</p><p>　　}LNode,*Link;</p><p>　　typedef int (*PFUN)();</p><p>　　struct CMDINFO</p><p><

47、b>　　{</b></p><p>　　const char *pCmdName;</p><p>　　const char *pCmdInfo;</p><p>　　PFUN pFun;</p><p><b>　　};</b></p><p><b>　　/*調(diào)用的

48、函數(shù)*/</b></p><p>　　void createLink(Link &L,int n);</p><p>　　void printList(Link L);</p><p>　　void addPolyn(Link &pc,Link pa,Link pb);</p><p>　　void substra

49、ctPolyn(Link &pc,Link pa,Link pb);</p><p>　　void mulPolyn(Link &pc,Link pa,Link pb);</p><p>　　void copyLink(Link &pc,Link pa);</p><p>　　int locateLink(Link pa,Link e);&l

50、t;/p><p>　　void destroyLink(Link &L);</p><p><b>　　/*命令行函數(shù)*/</b></p><p>　　void CmdProc(const char *pTitle);</p><p>　　int CreatePolyn();</p><p>

51、　　int ShowPolyn();</p><p>　　int AddPolyn();</p><p>　　int SubPolyn();</p><p>　　int MulPolyn();</p><p>　　int DesPolyn();</p><p>　　int Clear();</p><

52、;p>　　int Help();</p><p>　　int Exit();</p><p>　　CMDINFO g_CmdInfo[] = { "CreatePolyn", "創(chuàng)建多項(xiàng)式", CreatePolyn,</p><p>　　"ShowPolyn", "顯示

53、多項(xiàng)式", ShowPolyn,</p><p>　　"AddPolyn", "多項(xiàng)式相加", AddPolyn,</p><p>　　"SubPolyn", "多項(xiàng)式相減", SubPolyn,</p><p>　　"M

54、ulPolyn", "多項(xiàng)式相乘", MulPolyn,</p><p>　　"DesPolyn", "銷毀多項(xiàng)式", DesPolyn,</p><p>　　"Clear", "清屏操作", Clear,<

55、;/p><p>　　"Help", "幫助信息", Help,</p><p>　　"Exit", "退出", Exit};</p><p>　　int g_nCmdSize = sizeof(g_CmdInfo)/sizeof(CMDIN

56、FO);</p><p>　　Link La = NULL,Lb = NULL;</p><p>　　void main()</p><p><b>　　{</b></p><p>　　CmdProc("多項(xiàng)式");</p><p><b>　　}</b>

57、</p><p>　　void CmdProc(const char *pTitle) //Dos界面命令行函數(shù)</p><p><b>　　{</b></p><p>　　char szCmdBuf[50] = "";</p><p>　　int i = 0;</p><p

58、>　　if(NULL == pTitle)</p><p><b>　　{</b></p><p>　　cout<<"xxx空系統(tǒng) v 2.0"<<endl;</p><p><b>　　}</b></p><p><b>　　else&l

59、t;/b></p><p><b>　　{</b></p><p>　　cout<<pTitle<<"系統(tǒng) v 2.0"<<endl;</p><p><b>　　}</b></p><p>　　while(true)</p>

60、<p><b>　　{</b></p><p>　　cout<<">";</p><p>　　cin>>szCmdBuf;</p><p>　　for(i = 0; i < g_nCmdSize; i++)</p><p><b>　　{&l

61、t;/b></p><p>　　if(!strcmp(szCmdBuf, g_CmdInfo[i].pCmdName))</p><p><b>　　{</b></p><p>　　g_CmdInfo[i].pFun();</p><p><b>　　break;</b></p>

62、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(i == g_nCmdSize)</p><p><b>　　{</b></p><p>　　cout<<"您輸入的命令有誤，請(qǐng)用Help命令查詢

63、!"<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int CreatePolyn() //創(chuàng)建多項(xiàng)式</p><p>

64、<b>　　{</b></p><p>　　if(La != NULL && Lb != NULL) //多項(xiàng)式校驗(yàn)</p><p><b>　　{</b></p><p>　　cout<<"您已經(jīng)創(chuàng)建了多項(xiàng)式，請(qǐng)使用其它命令!"<<endl;<

65、;/p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　int n;</b></p><p>　　cout<<"請(qǐng)輸入你要運(yùn)算的第一個(gè)一元多項(xiàng)式的項(xiàng)數(shù): ";</p>

66、<p><b>　　cin>>n;</b></p><p>　　createLink(La,n);</p><p>　　cout<<"請(qǐng)輸入你要運(yùn)算的第二個(gè)一元多項(xiàng)式的項(xiàng)數(shù): ";</p><p><b>　　cin>>n;</b></p>&

67、lt;p>　　createLink(Lb,n);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int ShowPolyn() //顯示多項(xiàng)式</p><p><b>　　{</b><

68、;/p><p>　　if(La == NULL || Lb == NULL) //多項(xiàng)式校驗(yàn)</p><p><b>　　{</b></p><p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)建!"<<endl;</p><p><b>　　return 0;

69、</b></p><p><b>　　}</b></p><p>　　cout<<"第一個(gè)一元多項(xiàng)式為："<<endl;</p><p>　　printList(La);</p><p>　　cout<<"第二個(gè)一元多項(xiàng)式為："<

70、;<endl;</p><p>　　printList(Lb);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int AddPolyn() //多項(xiàng)式相加</p><p><b>

71、;　　{</b></p><p><b>　　Link L;</b></p><p>　　if(La == NULL || Lb == NULL) //多項(xiàng)式校驗(yàn)</p><p><b>　　{</b></p><p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)

72、建!"<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　addPolyn(L,La,Lb);</p><p>　　cout<<"兩個(gè)多項(xiàng)式相加后的結(jié)果為："<

73、<endl;</p><p>　　printList(L);</p><p>　　destroyLink(L);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int SubPolyn()

74、 //多項(xiàng)式相減</p><p><b>　　{</b></p><p><b>　　Link L;</b></p><p>　　if(La == NULL || Lb == NULL) //多項(xiàng)式校驗(yàn)</p><p><b>　　{</b></p><

75、;p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)建!"<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　substractPolyn(L,La,Lb);</p><p&g

76、t;　　cout<<"兩個(gè)多項(xiàng)式相減后的結(jié)果為："<<endl;</p><p>　　printList(L);</p><p>　　destroyLink(L);</p><p><b>　　return 0;</b></p><p><b>　　}</b&g

77、t;</p><p>　　int MulPolyn() //多項(xiàng)式相乘</p><p><b>　　{</b></p><p><b>　　Link L;</b></p><p>　　if(La == NULL || Lb == NULL) //多項(xiàng)式校驗(yàn)</p>

78、<p><b>　　{</b></p><p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)建!"<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>

79、　　mulPolyn(L,La,Lb);</p><p>　　cout<<"兩個(gè)多項(xiàng)式相乘后的結(jié)果為："<<endl;</p><p>　　printList(L);</p><p>　　destroyLink(L);</p><p><b>　　return 0;</b>&l

80、t;/p><p><b>　　}</b></p><p>　　int DesPolyn() //銷毀多項(xiàng)式</p><p><b>　　{</b></p><p>　　if(La == NULL || Lb == NULL) //多項(xiàng)式校驗(yàn)</p><p&g

81、t;<b>　　{</b></p><p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)建!"<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　if(La

82、 && Lb)</p><p><b>　　{</b></p><p>　　destroyLink(La);</p><p>　　destroyLink(Lb);</p><p>　　cout<<"銷毀成功！"<<endl;</p><p&g

83、t;<b>　　}</b></p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　cout<<"您還未創(chuàng)建多項(xiàng)式，請(qǐng)先創(chuàng)建!"<<endl;</p><p><b>　

84、　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int Clear() //清屏函數(shù)</p><p><b>　　{</b></p><p><

85、;b>　　char a;</b></p><p>　　a = getchar();</p><p>　　system("cls"); //system是DOS界面命令行操作函數(shù) cls是清屏命令 ，format d: /q 是格式化D盤命令</p><p>　　cout<<"多項(xiàng)式系統(tǒng) v 2.0"

86、;<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int Help() //幫助函數(shù)</p><p><b>　　{</b></p><p>　　i

87、nt i = 0;</p><p>　　int j = 0;</p><p>　　int nSize = 0;</p><p>　　cout<<"相關(guān)命令信息: "<<endl;</p><p>　　for(i = 0; i < g_nCmdSize; i++)</p><

88、p><b>　　{ </b></p><p>　　cout<<" "<<g_CmdInfo[i].pCmdName;</p><p>　　nSize = strlen(g_CmdInfo[i].pCmdName);</p><p>　　for(j = 0; j < 20 - nSi

89、ze; j++)</p><p><b>　　{</b></p><p>　　cout<<" ";</p><p><b>　　}</b></p><p>　　cout<<g_CmdInfo[i].pCmdInfo<<endl;</p&g

90、t;<p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int Exit() //退出函數(shù)</p><p><b>　　{</b>&

91、lt;/p><p><b>　　exit(0);</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void destroyLink(Link &L) //清空鏈表</p><p

92、><b>　　{</b></p><p><b>　　Link p;</b></p><p>　　p = L->next;</p><p><b>　　while(p)</b></p><p><b>　　{ </b></p>

93、<p>　　L->next = p->next;</p><p><b>　　delete p;</b></p><p>　　p = L->next;</p><p><b>　　}</b></p><p><b>　　delete L;</b>&l

94、t;/p><p><b>　　L = NULL;</b></p><p><b>　　}</b></p><p>　　/*判斷指數(shù)是否與多項(xiàng)式中已存在的某項(xiàng)相同*/</p><p>　　int locateLink(Link L,Link e)</p><p><b>

95、　　{</b></p><p><b>　　Link p;</b></p><p>　　p = L->next;</p><p>　　while(p != NULL && (e->data.expn != p->data.expn))</p><p><b>　　{

96、</b></p><p>　　p = p->next;</p><p><b>　　}</b></p><p>　　if(p == NULL)</p><p><b>　　{</b></p><p><b>　　return 0;</b>

97、;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　return 1;</b></p><p><b>　　}<

98、;/b></p><p><b>　　}</b></p><p>　　void createLink(Link &L,int n) //創(chuàng)建鏈表</p><p><b>　　{</b></p><p>　　Link p,newp;</p><p>　　L =

99、 new LNode;</p><p>　　L->next = NULL;</p><p>　　(L->data).expn = -1;//創(chuàng)建頭結(jié)點(diǎn)</p><p><b>　　p = L;</b></p><p>　　for(int i = 1; i <= n; i++)</p>&l

100、t;p><b>　　{</b></p><p>　　newp = new LNode;</p><p>　　cout<<"請(qǐng)輸入第"<<i<<"項(xiàng)的系數(shù)和指數(shù):"<<endl;</p><p>　　cout<<"系數(shù): "

101、;;</p><p>　　cin>>(newp->data).coef;</p><p>　　cout<<"指數(shù): ";</p><p>　　cin>>(newp->data).expn;</p><p>　　if(newp->data.expn < 0)

102、//指數(shù)校驗(yàn)</p><p><b>　　{</b></p><p>　　cout<<"您輸入有誤，指數(shù)不允許為負(fù)值!"<<endl;</p><p>　　delete newp;</p><p><b>　　i--;</b></p><

103、;p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　newp->next = NULL;</p><p><b>　　p = L;</b></p><p>　　if(newp->data.coef == 0

104、) //系數(shù)校驗(yàn)</p><p><b>　　{</b></p><p>　　cout<<"系數(shù)為零，重新輸入!"<<endl;</p><p>　　delete newp;</p><p><b>　　i--;</b></p><p

105、><b>　　continue;</b></p><p><b>　　}</b></p><p>　　while((p->next != NULL) && ((p->next->data).expn < (newp->data).expn)) </p><p>　　{

106、 //指數(shù)排序</p><p>　　p = p->next;</p><p><b>　　}</b></p><p>　　if(!locateLink( L, newp))</p><p><b>　　{</b></p><p&g

107、t;　　newp->next = p->next;</p><p>　　p->next = newp;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><

108、;p>　　cout<<"輸入的該項(xiàng)指數(shù)與多項(xiàng)式中已存在的某項(xiàng)相同,請(qǐng)重新創(chuàng)建一個(gè)正確的多項(xiàng)式"<<endl;</p><p>　　delete newp;</p><p>　　destroyLink(L);</p><p>　　createLink(L,n);</p><p><b>

109、;　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　/*輸出鏈表*/</b></p><p>　

110、　void printList(Link L)</p><p><b>　　{</b></p><p><b>　　Link p;</b></p><p>　　if(L == NULL || L->next == NULL) //校驗(yàn)</p><p><b>　　{</b&g

111、t;</p><p>　　cout<<"該一元多項(xiàng)式為空 !";</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　p = L

112、->next; //跳過(guò)頭結(jié)點(diǎn)</p><p>　　if((p->data).coef > 0 )</p><p><b>　　{ </b></p><p>　　if((p->data).expn == 0)</p><p><b>　　{</b></p>&

113、lt;p>　　cout<<(p->data).coef;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　if((p->data).coef ==

114、1 && (p->data).expn == 1)</p><p><b>　　{</b></p><p>　　cout<<"x";</p><p><b>　　}</b></p><p><b>　　else </b>&l

115、t;/p><p><b>　　{</b></p><p>　　if((p->data).coef == 1 && (p->data).expn != 1)</p><p><b>　　{</b></p><p>　　cout<<"x^"<

116、<(p->data).expn;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if((p->data).expn == 1 && (p->

117、;data).coef != 1)</p><p><b>　　{</b></p><p>　　cout<<(p->data).coef<<"x";</p><p><b>　　}</b></p><p><b>　　else </b

118、></p><p><b>　　{</b></p><p>　　cout<<(p->data).coef<<"x^"<<(p->data).expn;</p><p><b>　　}</b></p><p><b>

119、　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if((p->data).coef < 0)</p><p><b&

120、gt;　　{ </b></p><p>　　if((p->data).expn == 0)</p><p><b>　　{</b></p><p>　　cout<<(p->data).coef;</p><p><b>　　}</b></p>

121、<p><b>　　else </b></p><p><b>　　{ </b></p><p>　　if(p->data.coef == -1 && p->data.expn == 1)</p><p><b>　　{</b></p><p&

122、gt;　　cout<<"-x";</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　if(p->data.coef == -1 &&a

123、mp; p->data.expn != 1)</p><p><b>　　{</b></p><p>　　cout<<"-x^"<<p->data.expn;</p><p><b>　　}</b></p><p><b>　　els

124、e </b></p><p><b>　　{</b></p><p>　　if(p->data.expn == 1)</p><p><b>　　{ </b></p><p>　　cout<<p->data.coef<<"x";&l

125、t;/p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　cout<<(p->data).coef<<"x^"<<(p->

126、;data).expn;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}<

127、;/b></p><p>　　p = p->next;</p><p>　　while(p != NULL)</p><p><b>　　{</b></p><p>　　if((p->data).coef > 0)</p><p><b>　　{</b>

128、;</p><p>　　if((p->data).expn == 0) </p><p><b>　　{</b></p><p>　　cout<<"+"<<(p->data).coef;</p><p><b>　　}</b></p>

129、;<p><b>　　else </b></p><p><b>　　{</b></p><p>　　if((p->data).expn == 1 && (p->data).coef != 1) </p><p><b>　　{</b></p>

130、<p>　　cout<<"+"<<(p->data).coef<<"x";</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b><

131、/p><p>　　if((p->data).expn == 1 && (p->data).coef == 1)</p><p><b>　　{</b></p><p>　　cout<<"+x";</p><p><b>　　}</b></

132、p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　if((p->data).coef == 1 && (p->data).expn != 1)</p><p><b>　　{</b></p&g

133、t;<p>　　cout<<"+x^"<<(p->data).expn;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p&g

134、t;　　cout<<"+"<<(p->data).coef<<"x^"<<(p->data).expn;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　

135、}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if((p->data).coef < 0)</p><p><b>　　{ </b></p><p>　　if((p

136、->data).expn == 0)</p><p><b>　　{</b></p><p>　　cout<<(p->data).coef;</p><p><b>　　}</b></p><p><b>　　else </b></p>&

137、lt;p><b>　　{</b></p><p>　　if(p->data.coef == -1 && p->data.expn == 1)</p><p><b>　　{</b></p><p>　　cout<<"-x";</p><p

138、><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　if(p->data.coef == -1 && p->data.expn != 1)</p><p><

139、;b>　　{</b></p><p>　　cout<<"-x^"<<p->data.expn;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{<

140、/b></p><p>　　if(p->data.expn == 1)</p><p><b>　　{</b></p><p>　　cout<<p->data.coef<<"x";</p><p><b>　　}</b></p>

141、;<p><b>　　else </b></p><p><b>　　{</b></p><p>　　cout<<(p->data).coef<<"x^"<<(p->data).expn;</p><p><b>　　}</

142、b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　p=p->next;</p&

143、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　/*把一個(gè)鏈表的內(nèi)容復(fù)制給另一個(gè)鏈表*/</p><

144、;p>　　void copyLink(Link &pc,Link pa)</p><p><b>　　{</b></p><p>　　Link p,q,r;</p><p>　　pc = new LNode;</p><p>　　pc->next = NULL;</p><p>

145、;<b>　　r = pc;</b></p><p><b>　　p = pa;</b></p><p>　　while(p->next != NULL)</p><p><b>　　{</b></p><p>　　q = new LNode;</p>&l

146、t;p>　　q->data.coef = p->next->data.coef; //跳過(guò)頭結(jié)點(diǎn)</p><p>　　q->data.expn = p->next->data.expn;</p><p>　　r->next = q;</p><p>　　q->next = NULL;</p>

147、<p><b>　　r = q;</b></p><p>　　p = p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/*將兩個(gè)一元多項(xiàng)式相加*/</p><p>　　

148、void addPolyn(Link &pc,Link pa,Link pb)</p><p><b>　　{ </b></p><p>　　Link p1,p2,p,pd;</p><p>　　/*以下為保護(hù)原多項(xiàng)式操作 分別復(fù)制到 p1、p2里*/</p><p>　　copyLink(p1,pa);&l

149、t;/p><p>　　copyLink(p2,pb);</p><p>　　pc = new LNode;</p><p>　　pc->next = NULL;</p><p><b>　　p = pc;</b></p><p>　　p1 = p1->next; //跳過(guò)頭結(jié)點(diǎn)</