任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算

1、西安文理學(xué)院軟件學(xué)院課程設(shè)計(jì)報(bào)告設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目： 任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算學(xué)生學(xué)號(hào)： 1402120433 專業(yè)班級(jí)： 軟件工程12級(jí)4班 學(xué)生姓名： 學(xué)生成績(jī)： 指導(dǎo)教師（職稱）： 課題工作時(shí)間： 2014.6.16 至 2014.6.27 說明：1、報(bào)告中的任務(wù)書、進(jìn)度表由指導(dǎo)教師在課程設(shè)計(jì)開始前填寫并發(fā)給每個(gè)學(xué)生。2、學(xué)生成績(jī)由指導(dǎo)教師根據(jù)學(xué)生的設(shè)計(jì)情況給出各項(xiàng)分值及總評(píng)成績(jī)。3、所有學(xué)生必須參加課程設(shè)計(jì)的答辯環(huán)節(jié)，凡不參加答辯者，其成績(jī)一律按不及格處理。答辯由指導(dǎo)教師實(shí)施。4、報(bào)告正文字?jǐn)?shù)一般應(yīng)不少于3000字，也可由指導(dǎo)教師根據(jù)本門綜合設(shè)計(jì)的情況另行

2、規(guī)定。5、平時(shí)表現(xiàn)成績(jī)低于6分的學(xué)生，取消答辯資格，其本項(xiàng)綜合設(shè)計(jì)成績(jī)按不及格處理。軟件學(xué)院課程設(shè)計(jì)任務(wù)書學(xué)生姓名學(xué)號(hào)專業(yè)班級(jí)設(shè)計(jì)題目任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算內(nèi)容概要： 用c+語言及數(shù)據(jù)結(jié)構(gòu)的思想解決任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算。數(shù)據(jù)輸入方面可以根據(jù)一元高次多項(xiàng)式的特征，從左到右開始，按每一項(xiàng)指數(shù)、系數(shù)的順序輸入。運(yùn)用單鏈表、動(dòng)態(tài)鏈表等關(guān)鍵技術(shù)，實(shí)現(xiàn)所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間、程序的運(yùn)行時(shí)間應(yīng)盡可能的少的功能。開發(fā)環(huán)境：Visual C+ 6.0讓同學(xué)深入了解C+，掌握C+的功能和數(shù)據(jù)結(jié)構(gòu)的功能。文獻(xiàn)資料：1 韓利凱，李軍. 數(shù)據(jù)結(jié)構(gòu)M. 浙江：浙江大學(xué)出版社,201

3、3.2 蘇仕華. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M. 北京：機(jī)械工業(yè)出版社 ,2009.3 耿國(guó)華. 數(shù)據(jù)結(jié)構(gòu)-用C語言描述M. 北京：高等教育出版社,2011.4 嚴(yán)蔚敏,陳文博. 數(shù)據(jù)結(jié)構(gòu)及算法教程M. 北京: 清華大學(xué)出版社,2010.設(shè)計(jì)要求： 設(shè)計(jì)程序以實(shí)現(xiàn)任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算。 （1）所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間。 （2）程序的運(yùn)行時(shí)間應(yīng)盡可能的少。工作期限：設(shè)計(jì)工作自2014年6月16日至2014年6月27日止。指導(dǎo)教師： 院長(zhǎng)： 日 期：2014年6月16日軟件學(xué)院課程設(shè)計(jì)進(jìn)度安排表學(xué)生姓名： 學(xué)號(hào)： 專業(yè)： 軟件工程 班級(jí)： 2012級(jí)4班 起止日期內(nèi) 容備注6月16

4、日 6月 17日下任務(wù)書；收集、閱讀、整理相關(guān)參考文獻(xiàn)，并進(jìn)行歸納和概括總結(jié)，完成項(xiàng)目/任務(wù)背景介紹部分文字內(nèi)容。6月18日11月20日系統(tǒng)功能設(shè)計(jì)和模塊設(shè)計(jì)、系統(tǒng)體系結(jié)構(gòu)構(gòu)建。6月21日6月24日各功能模塊編碼實(shí)現(xiàn)，系統(tǒng)各功能模塊調(diào)試與維護(hù)。6月25日6月26日系統(tǒng)功能集成、系統(tǒng)調(diào)試與測(cè)試，按照模板要求撰寫課程設(shè)計(jì)/項(xiàng)目設(shè)計(jì)報(bào)告。6月27日課程設(shè)計(jì)/項(xiàng)目設(shè)計(jì)分組答辯，提交課程設(shè)計(jì)/項(xiàng)目設(shè)計(jì)報(bào)告以及相關(guān)文檔，進(jìn)行成績(jī)?cè)u(píng)定。指導(dǎo)教師簽名： 2014年6月16日成績(jī)?cè)u(píng)定表學(xué)生姓名： 學(xué)號(hào)： 專業(yè)： 軟件工程 班級(jí)： 2012級(jí)4班 類別合計(jì)分值各項(xiàng)分值評(píng)分標(biāo)準(zhǔn)實(shí)際得分合計(jì)得分平時(shí)表現(xiàn)1010按時(shí)參

5、加設(shè)計(jì)指導(dǎo)，無違反紀(jì)律情況。完成情況3020按設(shè)計(jì)任務(wù)書的要求完成了全部任務(wù)，能完整演示其設(shè)計(jì)內(nèi)容，符合要求。10能對(duì)其設(shè)計(jì)內(nèi)容進(jìn)行詳細(xì)、完整的介紹，并能就指導(dǎo)教師提出的問題進(jìn)行正確的回答。報(bào)告質(zhì)量3510報(bào)告文字通順，內(nèi)容翔實(shí)，論述充分、完整，立論正確，結(jié)構(gòu)嚴(yán)謹(jǐn)合理；報(bào)告字?jǐn)?shù)符合相關(guān)要求，工整規(guī)范，整齊劃一。5課題背景介紹清楚，綜述分析充分。5設(shè)計(jì)方案合理、可行，論證嚴(yán)謹(jǐn)，邏輯性強(qiáng)，具有說服力。5符號(hào)統(tǒng)一；圖表完備、符合規(guī)范要求。5能對(duì)整個(gè)設(shè)計(jì)過程進(jìn)行全面的總結(jié)，得出有價(jià)值的結(jié)論或結(jié)果。5參考文獻(xiàn)數(shù)量在2篇以上，格式符合要求，在正文中正確引用。答辯情況2510在規(guī)定時(shí)間內(nèi)能就所設(shè)計(jì)的內(nèi)容進(jìn)行

6、闡述，言簡(jiǎn)意明，重點(diǎn)突出，論點(diǎn)正確，條理清晰。15在規(guī)定時(shí)間內(nèi)能準(zhǔn)確、完整、流利地回答教師所提出的問題?？傇u(píng)成績(jī)： 分 指導(dǎo)教師： （簽字） 日期：2014 年6月 27 日摘 要摘要：任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算。所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間，程序的運(yùn)行時(shí)間應(yīng)盡可能少。在數(shù)據(jù)輸入方面可以根據(jù)一元高次多項(xiàng)式的特征，從左到右開始，按每一項(xiàng)指數(shù)、系數(shù)的順序輸入。但是相乘的多項(xiàng)式項(xiàng)數(shù)是未知的，所以選擇什么樣的存儲(chǔ)方式在本課程設(shè)計(jì)中尤為重要。程序通過調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)，并且經(jīng)過適當(dāng)完善后，將可以應(yīng)用在商業(yè)中解決實(shí)際問題。關(guān)鍵詞：高次多項(xiàng)式; 加法; 乘法; 存儲(chǔ)方式西安文理學(xué)院

7、軟件學(xué)院 課程設(shè)計(jì)報(bào)告目 錄摘 要VI第一章 課題背景11.1 需求分析11.2 程序的目的11.3 要解決的問題11.4 設(shè)計(jì)思路11.5 程序運(yùn)行平臺(tái)11.6 性能要求2第二章 設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述32.1設(shè)計(jì)簡(jiǎn)介32.2 數(shù)據(jù)結(jié)構(gòu)的選擇32.3解決方案32.4 各程序模塊之間的層次（調(diào)用）關(guān)系42.5 用戶使用說明4第三章 詳細(xì)設(shè)計(jì)53.1 算法思想53.2 下面是針對(duì)本程序?qū)ｉT定義的數(shù)據(jù)結(jié)構(gòu)類型53.3 結(jié)構(gòu)圖63.4 算法描述6第四章 設(shè)計(jì)結(jié)果及分析114.1 程序調(diào)試114.2 時(shí)間空間復(fù)雜度的計(jì)算124.3 錯(cuò)誤分析134.4 存在的不足與對(duì)策、編程體會(huì)13總結(jié)14參考文獻(xiàn)15

8、附錄：程序源代碼16第一章 課題背景1.1 需求分析我們?nèi)粘Ｉ畹拈_支，大額數(shù)字或者多倍小數(shù)的計(jì)算都需要計(jì)算器的幫助。小學(xué)時(shí)，你可能拿的是簡(jiǎn)單的計(jì)算器，而高中，這簡(jiǎn)單的計(jì)算器已經(jīng)滿足不了你的需求。雖然現(xiàn)在的計(jì)算器價(jià)格比較便宜，各種功能不同，操作不便。有時(shí)你需要的那種功能計(jì)算器還不能實(shí)現(xiàn)，所以能夠通過自己的手設(shè)計(jì)開發(fā)出你所需要的計(jì)算程序是非常有意義的。為方便讓你算出任意兩個(gè)高次多項(xiàng)式的加法和乘法，特編寫此程序。使用該程序之后，所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間，程序的運(yùn)行時(shí)間應(yīng)盡可能少。 1.2 程序的目的設(shè)計(jì)程序以實(shí)現(xiàn)任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算。所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間，

9、程序的運(yùn)行時(shí)間應(yīng)盡可能少。 1.3 要解決的問題1. 怎樣實(shí)現(xiàn)兩個(gè)多項(xiàng)式的乘法？2. 相乘后若有指數(shù)相同的項(xiàng)用什么方法合并？3. 使用什么數(shù)據(jù)結(jié)構(gòu)來滿足盡可能節(jié)省存儲(chǔ)空間的要求？4. 用什么方法來輸出表達(dá)式？1.4 設(shè)計(jì)思路從題目看出所設(shè)計(jì)的程序應(yīng)能達(dá)到的功能，設(shè)計(jì)好的程序要滿足以上兩點(diǎn)。在數(shù)據(jù)輸入方面可以根據(jù)一元高次多項(xiàng)式的特征，從左到右開始，按每一項(xiàng)指數(shù)、系數(shù)的順序輸入。這里要留意一個(gè)問題，因?yàn)橐喑说亩囗?xiàng)式項(xiàng)數(shù)是未知的，所以選擇什么樣的存儲(chǔ)方式在 課程設(shè)計(jì)中尤為重要，這也是本程序好壞的一個(gè)評(píng)定。1.5 程序運(yùn)行平臺(tái)該程序是用Visual C+6.0制做的，使用Visual C+ 6.0運(yùn)

10、行該程序，具體操作是：打開Visual C+ 6.0，菜單欄里點(diǎn)文件打開工作區(qū)找到“cpp1.dsw”這個(gè)文件打開，或者在資源管理器中雙擊該文件，此時(shí)，VC+6.0會(huì)自動(dòng)打開，并載入該系統(tǒng)相關(guān)資源。 1.6 性能要求1.系統(tǒng)易操作性所開發(fā)的系統(tǒng)應(yīng)操作簡(jiǎn)單，使學(xué)生不受電腦水平的限制。2.系統(tǒng)具有可維護(hù)性由于系統(tǒng)設(shè)計(jì)的范圍較廣，數(shù)據(jù)庫中的信息需定期修改，為了使系統(tǒng)運(yùn)作的更好，可以對(duì)系統(tǒng)數(shù)據(jù)及簡(jiǎn)單的功能進(jìn)行簡(jiǎn)單的維護(hù)及調(diào)整。3.該系統(tǒng)能夠在開發(fā)的硬件系統(tǒng)中運(yùn)行不會(huì)因外部系統(tǒng)的不同面做不同的修改。第二章 設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述2.1設(shè)計(jì)簡(jiǎn)介設(shè)計(jì)題目: 設(shè)計(jì)程序以實(shí)現(xiàn)任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算

11、目的：要求熟練掌握C+語言的基本知識(shí)和編輯技能；基本掌握結(jié)構(gòu)化程序設(shè)計(jì)的基本思路和方法；以及數(shù)據(jù)結(jié)構(gòu)的使用。 要求：1.所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間。2.程序的運(yùn)行時(shí)間應(yīng)盡可能少。2.2 數(shù)據(jù)結(jié)構(gòu)的選擇本程序選擇的數(shù)據(jù)結(jié)構(gòu)是單鏈表，原因如下：鏈表的定義：（1） 鏈表是有限個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合，D=ai/i=1,2,，n;ai為數(shù)據(jù)元素。（2） 數(shù)據(jù)元素之間的關(guān)系R=/ai,ai+1D。（3） 數(shù)據(jù)元素ai 在存儲(chǔ)器中占用任意的、連續(xù)或不連續(xù)的物理存儲(chǔ)區(qū)域。動(dòng)態(tài)鏈表：當(dāng)需要插入數(shù)據(jù)元素時(shí)，臨時(shí)動(dòng)態(tài)地為其申請(qǐng)一個(gè)存儲(chǔ)空間，而不是將結(jié)點(diǎn)放在一個(gè)定義的數(shù)組中，刪除數(shù)據(jù)元素時(shí)，可以

12、釋放該數(shù)據(jù)元素所占用的空間，即可以根據(jù)表的實(shí)際需要臨時(shí)動(dòng)態(tài)的分配存儲(chǔ)空間以存儲(chǔ)表中的數(shù)據(jù)元素。單鏈表是有限個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素組成的鏈表且該鏈表的每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域。帶頭結(jié)點(diǎn)的單鏈表是在單鏈表的第一個(gè)結(jié)點(diǎn)之前加一個(gè)同類型的結(jié)點(diǎn)，目的是為了使鏈表有一致的描述。本程序解決的是兩多項(xiàng)式相加和相乘的問題，多項(xiàng)式的項(xiàng)數(shù)本身就是不確定的，而且相乘后的多項(xiàng)式可能含有指數(shù)相同的問題，這時(shí)就需要合并，合并后其中的一項(xiàng)就沒有用了需要?jiǎng)h除，不然就浪費(fèi)內(nèi)存空間?；谝陨蠋c(diǎn)所以采用了鏈表。鏈表具有動(dòng)態(tài)生成，靈活添加或刪除結(jié)點(diǎn)的特點(diǎn)，盡可能節(jié)省存儲(chǔ)空間。2.3解決方案 1、首先進(jìn)行需求分析，搞清楚系統(tǒng)功能

13、和任務(wù)；2、然后在總體設(shè)計(jì)中確定模塊結(jié)構(gòu)、劃分功能模塊，將軟件功能需求分配給所劃分的最單元模塊。確定模塊間的聯(lián)系，確定數(shù)據(jù)結(jié)構(gòu)、文件結(jié)構(gòu)、數(shù)據(jù)庫模式，確定測(cè)試方法與策略；3、在詳細(xì)設(shè)計(jì)中，為每個(gè)模塊確定采用的算法，選擇適當(dāng)?shù)墓ぞ弑磉_(dá)算法的過程（流程圖）來描述模塊的詳細(xì)過程。確定每一模塊采用的數(shù)據(jù)結(jié)構(gòu)和模塊接口的細(xì)節(jié)，對(duì)系統(tǒng)內(nèi)部其他模塊的接口 4、根據(jù)分析編寫C+語言代碼。 2.4 各程序模塊之間的層次（調(diào)用）關(guān)系在執(zhí)行主函數(shù)時(shí)先調(diào)用creat 生成要相乘的多項(xiàng)式，存儲(chǔ)在兩個(gè)動(dòng)態(tài)鏈表中，然后調(diào)用print 函數(shù)輸出兩個(gè)多項(xiàng)式，繼續(xù)執(zhí)行相乘函數(shù)，相乘后調(diào)用置空函數(shù)將相乘的鏈表刪除。然后，檢驗(yàn)是否有

14、指數(shù)相同的項(xiàng)，如果沒有則調(diào)用print函數(shù)輸出結(jié)果，否則調(diào)執(zhí)行合并函數(shù)將指數(shù)項(xiàng)相同的合并，調(diào)用print函數(shù)輸出結(jié)果。2.5 用戶使用說明（1）給出任意兩個(gè)高次多項(xiàng)式，只需按照多項(xiàng)式從左到右依次輸入系數(shù)值、指數(shù)值，當(dāng)輸入指數(shù)值為-1 時(shí)結(jié)束。（由于程序設(shè)計(jì)的缺陷系數(shù)指數(shù)都要輸入所以結(jié)束之前系數(shù)值可隨便輸入不影響運(yùn)算結(jié)果。）（2）程序中指數(shù)、系數(shù)定義的是整型，所以表達(dá)式中系數(shù)值、指數(shù)值不能超出整型范圍。（3）輸入是正數(shù)直接輸入，負(fù)數(shù)要加負(fù)號(hào)。指數(shù)不能選擇-1。第三章 詳細(xì)設(shè)計(jì)3.1 算法思想算法思想如下：（1）：首先將兩個(gè)已知的多項(xiàng)式的指數(shù)和系數(shù)存放在指定鏈表中在執(zhí)行乘法運(yùn)算。乘法運(yùn)算的過程是將

15、f（x）式中的第一項(xiàng)與g（x）式的每一項(xiàng)相乘，在將f（x）式的第二項(xiàng)與g（x） 式的每一項(xiàng)相乘，依次下去直到f（x）式的所有項(xiàng)與g（x） 式乘完為止。將相乘后所得的指數(shù)、系數(shù)存在剛開始建好的F(x)鏈表中。（2）：F（x） 鏈表中如果有指數(shù)相同的項(xiàng)就需要合并，合并時(shí)將結(jié)果放在前一個(gè)項(xiàng)中，將后一項(xiàng)刪除。這里需要將F（x） 鏈表中的每一項(xiàng)都要對(duì)比一遍，這里就要發(fā)揮指針的作用了。首先定義3個(gè)指針，x、y、z，x、y 指向首元素結(jié)點(diǎn)z 指向第二個(gè)結(jié)點(diǎn)，用z 結(jié)點(diǎn)中指數(shù)項(xiàng)與x 結(jié)點(diǎn)的指數(shù)項(xiàng)比較，如果不同指針z 向后移，若相同則將z 結(jié)點(diǎn)的系數(shù)加到x 上去然后將z 所在結(jié)點(diǎn)空間釋放，并且指針z 后移。直到

16、指針z 指向空后，將指針x 后移一項(xiàng)，并令z 指向x 的下一項(xiàng)，然后按上述步驟依次執(zhí)行，直到x 指向空結(jié)束。這里指針y 是z 的前驅(qū)結(jié)點(diǎn)他的作用是合并后結(jié)點(diǎn)空間釋放結(jié)點(diǎn)空間將此結(jié)點(diǎn)的前后兩項(xiàng)鏈接起來。本程序核心部分全部是運(yùn)用while 循環(huán)語句實(shí)現(xiàn)的。界面通過switch、case等語句來控制的。3.2 下面是針對(duì)本程序?qū)ｉT定義的數(shù)據(jù)結(jié)構(gòu)類型結(jié)點(diǎn)的數(shù)據(jù)類型如下：typedef struct node /定義節(jié)點(diǎn)類型 float coef; int expn; struct node * next; PLOY; 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思想：鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非0 項(xiàng)。它包含三個(gè)域,分

17、別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式結(jié)點(diǎn)的指針。多項(xiàng)式鏈表結(jié)點(diǎn)的結(jié)構(gòu)如下圖3-1所示：系數(shù) 指數(shù) 指針coefexpnnext圖 3-1 鏈表結(jié)點(diǎn)例如：多項(xiàng)式4x8+7x23-5x的單鏈表表示如下圖3-2所示: 圖3-2 單鏈表表示3.3 結(jié)構(gòu)圖整體的結(jié)構(gòu)圖如下圖3-3所示：輸入任意兩個(gè)高次多項(xiàng)式的系數(shù)、指數(shù)值將輸入值分別存儲(chǔ)在兩個(gè)動(dòng)態(tài)鏈表中輸出兩個(gè)要相乘的多項(xiàng)式相乘將結(jié)果存入F(x)鏈表將存放相乘的多項(xiàng)式各項(xiàng)系數(shù)、指數(shù)的鏈表置空若有指數(shù)相同的項(xiàng)合并輸出結(jié)果 圖 3-3 整體結(jié)構(gòu)圖3.4 算法描述（1） 設(shè)指針p、q 分別為指向A、B 的首元素結(jié)點(diǎn)，用p-coef 乘q-coef,p-e

18、xp+q-exp,并令指針p 后移。（2）當(dāng)q-next 為空時(shí)，指針p 向后移一位，指針q 繼續(xù)從B 鏈表的第一項(xiàng)開始，執(zhí)行p-coef 乘q-coef,p-exp 加q-exp.每執(zhí)行一次指針p 后移。（3）重復(fù)（1）、（2）步，直到p-next 為空后，結(jié)束。將乘出結(jié)果存入C 鏈表。合并時(shí)用兩個(gè)指針指向C 鏈表，一個(gè)指針跟隨另一個(gè)當(dāng)作后一個(gè)指針前驅(qū)指針，這樣合并后釋放就容易將前后結(jié)點(diǎn)鏈接上。綜合以上分析，兩個(gè)高次多項(xiàng)式相乘的算法如下：PLOY *byPLOY(PLOY *head1,PLOY *head2) /多項(xiàng)式相乘 PLOY *inpt,*res,*pre; int flag=0;

19、 res=(PLOY *)malloc(sizeof(PLOY); /創(chuàng)建鏈表頭 res-next=NULL; head1=head1-next; pre=head2; while(flag=0) if(pre-next=NULL) pre=head2;/當(dāng)現(xiàn)在指向空時(shí)跳出循環(huán) head1=head1-next; continue; if(head1=NULL) flag=1;/當(dāng)現(xiàn)在指向空時(shí)跳出循環(huán) continue; pre=pre-next; inpt=(PLOY *)malloc(sizeof(PLOY);/創(chuàng)建新鏈節(jié) inpt-coef=pre-coef*head1-coef; in

20、pt-expn=pre-expn+head1-expn; inpt-next=NULL; insert(res,inpt);/把當(dāng)前g(x)的鏈節(jié)插入到y(tǒng)(x)中 return res; 用尾插法生成多項(xiàng)式鏈表的算法如下：PLOY *creat(char ch)/輸入多項(xiàng)式 PLOY *head,*inpt; float x; int y; head=(PLOY *)malloc(sizeof(PLOY); /創(chuàng)建鏈表頭 head-next=NULL; printf(請(qǐng)輸入多項(xiàng)式%c:(格式是：系數(shù) 指數(shù)；以0 0 結(jié)束！)n,ch); scanf(%f %d,&x,&y); while(x!

21、=0) inpt=(PLOY *)malloc(sizeof(PLOY); /創(chuàng)建新鏈節(jié) inpt-coef=x; inpt-expn=y; inpt-next=NULL; insert(head,inpt); /不然就查找位置并且插入新鏈節(jié) printf(請(qǐng)輸入多項(xiàng)式%c的下一項(xiàng):(以0 0 結(jié)束！)n,ch); scanf(%f %d,&x,&y); return head; 輸出函數(shù)：void print(PLOY *fun) /輸出多項(xiàng)式 PLOY *printing; int flag=0; printing=fun-next; /正在被打印的鏈節(jié) if(fun-next=NULL)

22、 /如果函數(shù)為空打印0 printf(0n); return; while(flag=0) if(printing-coef0&fun-next!=printing) printf(+); /為正數(shù)時(shí)打印+號(hào) if(printing-coef=1);/如果為1就不用打印系數(shù)了 else if(printing-coef=-1) printf(-); /如果為-1就打印-號(hào)就行了 else printf(%f,printing-coef);/其余情況都得打印 if(printing-expn!=0) printf(x%d,printing-expn);/如果指數(shù)為0不打印指數(shù)項(xiàng) else if(

23、printing-coef=1)|(printing-coef=-1) printf(1); if(printing-next=NULL) flag=1; /如果現(xiàn)在的鏈節(jié)沒有下一個(gè)就結(jié)束 else printing=printing-next; printf(n); 以上就是按照題目功能要求和數(shù)據(jù)結(jié)構(gòu)要求，編寫算法和各程序模塊代碼。第四章 設(shè)計(jì)結(jié)果及分析4.1 程序調(diào)試1. 在VC的環(huán)境下,調(diào)試程序,進(jìn)入界面，如下圖4-1所示： 圖4-1進(jìn)入界面2. 按降冪輸入第一個(gè)多項(xiàng)式數(shù)據(jù),如下圖4-2所示： 圖4-2按升降冪輸入數(shù)據(jù) 3. 按升冪輸入第二個(gè)多項(xiàng)式數(shù)據(jù)，如下圖4-3所示： 圖4-3按升降

24、冪輸入數(shù)據(jù)4. 運(yùn)行結(jié)果正確如下圖4-4所示：圖4-4 運(yùn)行結(jié)果4.2 時(shí)間空間復(fù)雜度的計(jì)算若多項(xiàng)式A 有n 項(xiàng),多項(xiàng)式B 有m 項(xiàng)，則兩多項(xiàng)式相乘時(shí)為m*n ,接下來檢驗(yàn)是否有同類項(xiàng)檢查方法是每一項(xiàng)都要對(duì)比所以為(m*n)!,時(shí)間復(fù)雜度為O（m*n+(m*n）!)由于各個(gè)算法是基于動(dòng)態(tài)鏈表而建成的，所以各算法的空間性能均較好。4.3 錯(cuò)誤分析（1） 語句后面漏分號(hào)，或者在不該加分號(hào)的地方加了分號(hào)，或者忘記后括號(hào)。通過編譯時(shí)的指出，改正了這些錯(cuò)誤。（2）當(dāng)程序執(zhí)行到合并指數(shù)相同項(xiàng)時(shí)出現(xiàn)了錯(cuò)誤。調(diào)試后發(fā)現(xiàn)執(zhí)行完第一次while 循環(huán)后指向c 鏈表的指針e 不在存儲(chǔ)空間中，導(dǎo)致無法判斷while

25、循環(huán)，仔細(xì)檢查后，發(fā)現(xiàn)合并時(shí)將e 指針?biāo)附Y(jié)點(diǎn)釋放后，沒有給他指定新的結(jié)點(diǎn)。把指針e 后移一位，這樣就解決了問題。（3）關(guān)于時(shí)間空間復(fù)雜度的計(jì)算不太會(huì)用，最后經(jīng)過問同學(xué)和在互聯(lián)網(wǎng)上查資料解決了這個(gè)問題。4.4 存在的不足與對(duì)策、編程體會(huì)因?yàn)檎莆盏闹R(shí)有限，所以程序編起來有點(diǎn)難。通過編寫這個(gè)系統(tǒng)，我體會(huì)到了一個(gè)系統(tǒng)應(yīng)該作為一個(gè)整體來看待，系統(tǒng)具有牽一發(fā)而動(dòng)全身的特性，某一個(gè)模塊的一個(gè)小小錯(cuò)誤都可能導(dǎo)致系統(tǒng)其他模塊功能的喪失甚至是崩潰，同時(shí)在編程時(shí)應(yīng)該按照模塊來編寫，一個(gè)模塊實(shí)現(xiàn)一個(gè)功能，這樣在調(diào)試的時(shí)候就方便檢查，還有一個(gè)程序?qū)懲炅?，不是真正的結(jié)束，還需要不斷地調(diào)試不斷地修改程序中的錯(cuò)誤。在編程

26、中出現(xiàn)了一個(gè)致命的錯(cuò)誤：我在程序中定義了幾個(gè)函數(shù)但是忘記了使用引用導(dǎo)致了最后編譯是出現(xiàn)了重大錯(cuò)誤，經(jīng)過好幾個(gè)小時(shí)的仔細(xì)排查終于找到了問題所在。所以此次編程我最大的一個(gè)收獲是：仔細(xì)研究每一個(gè)函數(shù)的定義，不要出現(xiàn)定義中形參缺少或者實(shí)參形參形式不符出現(xiàn)的錯(cuò)誤總結(jié)本系統(tǒng)實(shí)現(xiàn)了以任意兩個(gè)高次多項(xiàng)式的加法和乘法運(yùn)算。所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間，程序的運(yùn)行時(shí)間應(yīng)盡可能少。通過本設(shè)計(jì)實(shí)驗(yàn)又將數(shù)據(jù)結(jié)構(gòu)中的鏈表的知識(shí)重新溫習(xí)了一遍，并且自己能夠獨(dú)立設(shè)計(jì)一些東西，學(xué)會(huì)了在設(shè)計(jì)實(shí)驗(yàn)過程時(shí)的基本步驟?；旧夏軌蛴袟l理的解決這些問題。在課程設(shè)計(jì)中，我使用了數(shù)據(jù)結(jié)構(gòu)中學(xué)到的鏈表，因?yàn)殒湵砭哂袆?dòng)態(tài)生成，靈活添加或刪

27、除結(jié)點(diǎn)的特點(diǎn)，盡可能節(jié)省存儲(chǔ)空間。正好符合題目的要求，自己不僅靈活的使用了鏈表，而且弄清楚了很多關(guān)于鏈表的作用，受益非淺。在課程設(shè)計(jì)中遇到了很多的問題，都是以前沒有發(fā)現(xiàn)的，這些問題涉及的方面很多，有的是c 語言基礎(chǔ)的，也有最近學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的知識(shí)。在實(shí)習(xí)中，我們可以把這學(xué)期所學(xué)的理論知識(shí)和實(shí)踐聯(lián)系起來，在所要開發(fā)的項(xiàng)目中漸漸成長(zhǎng)。雖然我們對(duì)這些知識(shí)運(yùn)用得還不是很熟練，但是相信我們也在滴水穿石地成長(zhǎng)起來。發(fā)現(xiàn)問題，提出問題，解決問題，使我們從不足之處出發(fā)，尋找新的學(xué)習(xí)方向。通過本次課程設(shè)計(jì)，讓我發(fā)現(xiàn)了自己的不足。自己在學(xué)習(xí)知識(shí)上面的漏洞。希望通過彌補(bǔ)這些發(fā)現(xiàn)的漏洞，提高自己的專業(yè)知識(shí)水平。設(shè)計(jì)過

28、程中的解決問題的方法，讓我明白了如何學(xué)習(xí)會(huì)更有效。如何學(xué)習(xí)才不會(huì)耽誤太多的時(shí)間。也學(xué)會(huì)了解決問題的一般方法：向老師、同學(xué)請(qǐng)教，借助網(wǎng)絡(luò)等等。我要感謝學(xué)校給我提供的良好的環(huán)境，讓我們可以在機(jī)房好好的學(xué)習(xí)。同時(shí)感謝老師對(duì)我的指導(dǎo)和幫助，感謝高年級(jí)哥哥姐姐給我的鼓勵(lì)讓我逐漸有了信心，也感謝幫助我的同學(xué)們。是你們對(duì)我的幫助和耐心指導(dǎo)，讓我有信心完成這次作業(yè)，是你們給了我信心，也給了我無盡的希望。大家要互相幫助，共同進(jìn)步，才能更好的學(xué)習(xí)，讓自己的知識(shí)更加豐富，讓自己在編程生涯得到提升。參考文獻(xiàn)1 韓利凱，李軍. 數(shù)據(jù)結(jié)構(gòu)M. 浙江：浙江大學(xué)出版社,2013.2 蘇仕華. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M. 北京：機(jī)械

29、工業(yè)出版社 ,2009.3 耿國(guó)華. 數(shù)據(jù)結(jié)構(gòu)-用C語言描述M. 北京：高等教育出版社,2011.4 嚴(yán)蔚敏,陳文博. 數(shù)據(jù)結(jié)構(gòu)及算法教程M. 北京: 清華大學(xué)出版社,2010.附錄：程序源代碼#include #include typedef struct node /定義節(jié)點(diǎn)類型 float coef; int expn; struct node * next; PLOY; void start()/用戶選擇界面 printf(*n); printf( 任意兩個(gè)高次多項(xiàng)式的相加/相乘:n); printf(*n); printf(請(qǐng)選擇操作:n); printf(1.兩個(gè)高次多項(xiàng)式相加n)

30、; printf(2.兩個(gè)高次多項(xiàng)式相乘n); printf(0.退出n); void insert(PLOY *head,PLOY *inpt) /查找位置插入新鏈節(jié)程序 PLOY *pre,*now; int signal=0; pre=head; /pre定義為現(xiàn)在的前一個(gè)鏈節(jié) if(pre-next=NULL) pre-next=inpt; else now=pre-next; while(signal=0) if(inpt-expnexpn) /當(dāng)新鏈節(jié)小于現(xiàn)在的連接時(shí)向后移一個(gè)鏈節(jié) if(now-next=NULL) now-next=inpt; signal=1; else pr

31、e=now; now=pre-next; else if(inpt-expnnow-expn) /如果發(fā)現(xiàn)比現(xiàn)在的鏈節(jié)大了就插入到這個(gè)連接的前面 inpt-next=now; pre-next=inpt; signal=1; else now-coef=now-coef+inpt-coef; signal=1; free(inpt); /與當(dāng)前鏈節(jié)相等指數(shù) if(now-coef=0) pre-next=now-next; free(now); PLOY *creat(char ch)/輸入多項(xiàng)式 PLOY *head,*inpt; float x; int y; head=(PLOY *)m

32、alloc(sizeof(PLOY); /創(chuàng)建鏈表頭 head-next=NULL; printf(請(qǐng)輸入高次多項(xiàng)式%c:(格式是：系數(shù) 指數(shù)；以0 0 結(jié)束！)n,ch); scanf(%f %d,&x,&y); while(x!=0) inpt=(PLOY *)malloc(sizeof(PLOY); /創(chuàng)建新鏈節(jié) inpt-coef=x; inpt-expn=y; inpt-next=NULL; insert(head,inpt); /不然就查找位置并且插入新鏈節(jié) printf(請(qǐng)輸入高次多項(xiàng)式%c的下一項(xiàng):(以0 0 結(jié)束！)n,ch); scanf(%f %d,&x,&y); ret

33、urn head; PLOY *addPLOY(PLOY *head,PLOY *pre)/多項(xiàng)式相加 PLOY *inpt; int flag=0; while(flag=0) if(pre-next=NULL) flag=1;/當(dāng)現(xiàn)在指向空時(shí)跳出循環(huán) else pre=pre-next; inpt=(PLOY *)malloc(sizeof(PLOY);/創(chuàng)建新鏈節(jié) inpt-coef=pre-coef; inpt-expn=pre-expn; inpt-next=NULL; insert(head,inpt); /否則把當(dāng)前g(x)的鏈節(jié)插入到y(tǒng)(x)中 return head; PLO

34、Y *byPLOY(PLOY *head1,PLOY *head2)/多項(xiàng)式相乘 PLOY *inpt,*res,*pre; int flag=0; res=(PLOY *)malloc(sizeof(PLOY);/創(chuàng)建鏈表頭 res-next=NULL; head1=head1-next; pre=head2; while(flag=0) if(pre-next=NULL) pre=head2;/當(dāng)現(xiàn)在指向空時(shí)跳出循環(huán) head1=head1-next; continue; if(head1=NULL) flag=1;/當(dāng)現(xiàn)在指向空時(shí)跳出循環(huán) continue; pre=pre-next; inpt=(PLOY *)malloc(sizeof(PLOY);/創(chuàng)建新鏈節(jié) inpt-coef=pre-coef*head1-coef; inpt-expn=pre-expn+head1-expn; inpt-next=NULL; insert(res,inpt);/把當(dāng)前g(x)的鏈節(jié)插入到y(tǒng)(x)中 return res; void print(PLOY *fun) /輸