題目1_一元多項式的加法、減法、乘法的實現(xiàn)_報告

1、西華大學(xué)理學(xué)院課程設(shè)計說明書理學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐 課 程 代 碼: 6015059 題 目 一:一元多項式加法、減法、乘法 年級/專業(yè)/班: 2013/信科/2班 學(xué) 生 姓 名: 馮金慧 學(xué) 號: 3120130902209 開 始 時 間: 2015 年 12 月 28 日完 成 時 間: 2016 年 01 月 10 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐任務(wù)書學(xué)院名稱： 理學(xué)院 課程代碼：_6015059_專業(yè)： 信科

2、 年級： 2012 一、 設(shè)計題目 一元多項式的加法、減法、乘法的實現(xiàn)（限最多1人完成）二、 主要內(nèi)容 完成一無多項式的基本運算功能。三、具體要求及提交的材料設(shè)有一元多項式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 請實現(xiàn)求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 要求： 1) 首先判定多項式是否稀疏2) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；3) 結(jié)果M(x)中無重復(fù)階項和無零系數(shù)項；要求輸出結(jié)果的升冪和降冪兩種排列

3、情況測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；必須上機調(diào)試通過l按數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大綱中的要求完成課程設(shè)計報告格式。設(shè)計結(jié)束后，每個學(xué)生必須上交的材料有：1 課程設(shè)計報告打印稿一份 2課程設(shè)計的源代碼電子文檔一份四、主要技術(shù)路線提示稀疏的多項式最好采用鏈?zhǔn)酱鎯Y(jié)構(gòu)；兩式相減與相加的算法是一致的，只是減式的數(shù)據(jù)項反號；兩式相乘是兩式相加的變形。五、進度安排共計兩周時間，建議進度安排如下：1 選題，應(yīng)該在上機實驗之前完成 2. 需求分析、概要設(shè)計可分配4學(xué)時完成2 詳細(xì)設(shè)計可分配4學(xué)時 4. 調(diào)試和分析可分配10學(xué)時。2學(xué)時的機動，可提前安排部分提前結(jié)束任務(wù)的學(xué)生答辯六、 推薦參考資料1. 馮博琴

4、等編著，軟件技術(shù)基礎(chǔ)（修改版），西安交通大學(xué)出版社，19972. 嚴(yán)蔚敏 等著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，20033. 李蕓芳 等著，軟件技術(shù)基礎(chǔ)（第二版），清華大學(xué)出版社，20004. 徐孝凱 等著，數(shù)據(jù)結(jié)構(gòu)（C語言描述），清華大學(xué)出版社，2004指導(dǎo)教師 簽名日期 年 月 日系 主 任 審核日期 年 月 日目 錄摘 要11問題的背景分析21.1問題的提出21.2任務(wù)與分析22 系統(tǒng)分析32.1功能需求32.2總體要求72.3數(shù)據(jù)需求73、詳細(xì)設(shè)計與實現(xiàn)73.1設(shè)計思路73.2詳細(xì)編碼94系統(tǒng)測試和結(jié)果分析234.1設(shè)計測試數(shù)據(jù)234.2調(diào)試的詳細(xì)過程23總 結(jié)30致 謝31 一元多項式的加

5、法、減法、乘法摘 要一元多項式計算是用C語言設(shè)計一個一元多項式簡單計算機，它能夠?qū)崿F(xiàn)按指數(shù)降冪排列或者按指數(shù)升冪排列建立并輸出多項式，并且能夠完一元多項式的四則運算，并將其運算結(jié)果輸出的功能。一元多項式的存儲方式分為靜態(tài)數(shù)組存儲和動態(tài)鏈表存儲兩種方式，兩種方式的特點各不相同，順序存儲簡單明了，但是缺乏靈活性，當(dāng)多項式為稀疏多項式時，順序存儲則會浪費許多存儲空間，鏈?zhǔn)酱鎯討B(tài)分配內(nèi)存，但操作起來比順序存儲稍微復(fù)雜一些，所以具體內(nèi)容具體分析，該選擇哪一種方式進行存儲還需進一步分析；通過一元多項式鏈?zhǔn)酱鎯晚樞虼鎯Φ谋容^與體會，可以體會到對一元多項式鏈?zhǔn)酱鎯晚樞虼鎯Ω髯缘牡膬?yōu)缺點和適用性。一元多項

6、式的運算，包含四個方面，多項式的加、減、乘、除，然而那，在具體計算中，我們需要考慮很多因素。首先，我們需要判斷多項式是否稀疏，其次，考慮對多項式的存儲方式（順序存儲或者鏈?zhǔn)酱鎯Γ?，并且，我們還需要保證在計算結(jié)果中，不能有重復(fù)階的出現(xiàn)和零項系數(shù)的出現(xiàn)，在輸出結(jié)果時，我們可以讓其升序或者降序輸出。 本程序用VS2010編寫，可以實現(xiàn)對多項式的加減乘的運算，采用順序存儲和鏈?zhǔn)酱鎯煞N方式分別可以進行多項式的加、減、乘的運算以及判斷該多項式是否稀疏，最后再將運算結(jié)果以升序或者降序排列情況輸出。關(guān)鍵詞：多項式，順序存儲，鏈?zhǔn)酱鎯?，升序降序?言1問題的背景分析 為了更好的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這一門理論和實踐性均

7、較強的基礎(chǔ)課程，熟練掌握理論知識的同時更需要加強上機的實踐。本課程就是要達到理論和實踐相互結(jié)合，培養(yǎng)學(xué)生的動手能力，在實踐中理解各種算法，在創(chuàng)作中提升，使我們能夠在數(shù)據(jù)結(jié)構(gòu)課程中，學(xué)會數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計解決問題的思想。1.1問題的提出 本課程設(shè)計主要是探究一元多項式的四則運算，而與此同時，首先，需要我掌握和理解的是對一元多項式的不同的存儲方式（鏈?zhǔn)酱鎯晚樞虼鎯Γ┲?，如何有效的對其進行加、減、乘的運算。其次，需要解決的問題就是給定一個一元多項式，要怎么去判斷多項式的稀疏和稠密性。再者，打印多項式時可如何進行升冪和降冪的打印出多項式。這些問題都需要我逐一解決。C語言C語言既有高級語言的特點，又具

8、有匯編語言的特點；既是一個成功的系統(tǒng)設(shè)計語言，有時一個使用的程序設(shè)計語言；既能用來編寫不依賴計算機硬件的應(yīng)用程序，又能用來編寫各種系統(tǒng)程序；是一種受歡迎、應(yīng)用廣泛的程序設(shè)計語言。C語言發(fā)展過程1973年，美國貝爾實驗室的D.M.RITCHIE在B語言的基礎(chǔ)上最終設(shè)計出了一種新的語言，他取了BCPL的第二個字母作為這種語言的名字，這就是C語言。1977年Dennis M.Ritchie 發(fā)表了不依賴于具體機器系統(tǒng)的C語言編譯文本可移植的C語言編譯程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，從

9、而使C語言成為目前世界上流行最廣泛的高級程序設(shè)計語言。1.2任務(wù)與分析任務(wù)是實現(xiàn)求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 4) 首先判定多項式是否稀疏5) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；6) 結(jié)果M(x)中無重復(fù)階項和無零系數(shù)項；要求輸出結(jié)果的升冪和降冪兩種排列情況分析：（1）用一維數(shù)組cp1n1和cp2n2存儲一元多項式Am(x)和Bn(x)的系數(shù)，用for循環(huán)來計算順序結(jié)構(gòu)中的加法、減法、乘法的結(jié)果。而順序存儲的加減乘運算則分為三個模塊函數(shù)來解決這三種運算。（2）用指針*d,*q來存儲一元多項式的內(nèi)容，再利用

10、指針計算動態(tài)鏈表下一元多項式的加法、減法、乘法的結(jié)果。（3）在用降冪升冪兩種排列輸出結(jié)果時，用expn和coef表示一元多項式的系數(shù)和指數(shù)，輸出兩種排列結(jié)果。而鏈?zhǔn)酱鎯Φ募訙p乘運算也是分為三個模塊函數(shù)來解決這三種運算2 系統(tǒng)分析2.1功能需求 此課題是主要任務(wù)是創(chuàng)建一元多項式，并可以選擇不同的存儲方式對一元多項式進行存儲并且可以進行多項式的加、減、乘基本運算，最后將結(jié)果可以按照升序或者降序排列。首先需要創(chuàng)建兩個一元多項式，才能繼續(xù)下一步的進行基本的多項式運算（加、減、乘）。然后將兩種不同的存儲方式各自分成一個子快，編寫出相應(yīng)的2個函數(shù)（順序存儲、鏈?zhǔn)酱鎯Γ?，然后在主程序里面提示各個選項對相應(yīng)的

11、功能，用戶輸入相應(yīng)的操作數(shù)，分別調(diào)用不同的函數(shù)，打印出相應(yīng)的排列結(jié)果（升冪排列或者降冪排列）。因此，實際需要設(shè)計的任務(wù)就是創(chuàng)建一元多項式，以及不同存儲方法的函數(shù)編寫，還有不同存儲模式下各自的加減乘的函數(shù)編寫，為了直觀和方便，畫出流程圖如下圖：一元多項式的計算主流程圖1.1：為動態(tài)鏈表結(jié)構(gòu)為順序結(jié)構(gòu)開始輸入兩個多項式各項的系數(shù)選擇實現(xiàn)結(jié)構(gòu)順序結(jié)構(gòu)？YN選擇打印輸出結(jié)果的方式升冪？YN升冪輸出結(jié)果降冪輸出結(jié)果打印輸出處理后的結(jié)果結(jié)束圖1.1一元多項式的計算主流程圖（2）順序存儲結(jié)構(gòu)流程圖如圖1.2所示減法？開始采用順序存儲結(jié)構(gòu)調(diào)用加法函數(shù)YN加法？調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)YN調(diào)用減法函數(shù)調(diào)

12、用乘法函數(shù)選擇打印輸出結(jié)果的順序升冪？YN打印輸出處理后的結(jié)果結(jié)束圖1.2順序存儲結(jié)構(gòu)流程圖（3）動態(tài)鏈表結(jié)構(gòu)流程圖如圖1.3所示減法？開始采用動態(tài)鏈表存儲結(jié)構(gòu)調(diào)用加法函數(shù)YN加法？調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)YN調(diào)用減法函數(shù)調(diào)用乘法函數(shù)選擇打印輸出結(jié)果的順序升冪？YN打印輸出處理后的結(jié)果結(jié)束圖1.3動態(tài)鏈表結(jié)構(gòu)流程圖流程圖很直觀的描述了整個程序服務(wù)過程。 2.2總體要求首先主函數(shù)中必須成功創(chuàng)建兩個一元多項式，然后查閱資料知道多項式的存儲方法，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程，我選擇了比較熟悉的順序存儲和鏈?zhǔn)酱鎯?，用戶想要對兩個多項式進行不同的運算，首先就必須按照先序成功創(chuàng)建一元多項式。用戶要對多項式進行

13、運算，那就需要知道他想怎么運算（加減乘）。這需要用戶手動輸入選擇序號。通過用戶輸入的信息，計算機就可以進行相關(guān)的操作，根據(jù)用戶輸入的信息調(diào)用對應(yīng)的函數(shù)進行加減乘的運算，最后再按照用戶輸入的選擇升序或者降序輸出結(jié)果供用戶瀏覽了；我就要用相應(yīng)的程序去實現(xiàn)這個過程,這才是我最后的目的。2.3數(shù)據(jù)需求 輸入一元多項式的項數(shù)，系數(shù)和對應(yīng)的次數(shù)3、詳細(xì)設(shè)計與實現(xiàn) 3.1設(shè)計思路 要完成一元多項式順序存儲和鏈?zhǔn)酱鎯Φ募印p、乘這幾個基本的運算，有很多種方法可以實現(xiàn)。但結(jié)合數(shù)據(jù)結(jié)構(gòu)課程，我選擇了比較適合自己的算法，其他的算法還有很多，只是都不是很熟悉，我的思想大多都來源于書上，對一元多項式的順序存儲和鏈?zhǔn)酱鎯?/p>

14、的算法做了分析，下一步自然就是完成它的程序了，不能用程序描述出來那在好也沒有用的。詳細(xì)設(shè)計如下：/定義順序存儲結(jié)構(gòu)類型int n1,n2;int cp1n1; intcp2n2/定義動態(tài)鏈表結(jié)構(gòu)類型#define INFEX 10000#define INFCO 10000double coef;int expn;p_pol *next;/順序存儲結(jié)構(gòu)的抽象數(shù)據(jù)類型定義int n1,n2;利用一維數(shù)組cp1n1和cp2n2存儲多項式的系數(shù)/基本操作：void creatpoly1(double *a,int pt)操作結(jié)果：建立順序結(jié)構(gòu)void addpoly(double *a,double

15、 *b,double *c)初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相加void subpoly(double *a,double *b,double *c)初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相減 void mulpoly(double *a,double *b,double *c) 初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相乘void ansprint(double *a,int n) 初始條件: 一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：選用升冪或降冪排列打印出結(jié)果/動態(tài)鏈表結(jié)構(gòu)的抽象數(shù)據(jù)類型定義typede

16、f struct p_pol double coef; int expn; p_pol *next；MPP；基本操作：MPP * creatlink(MPP *p,int n,int pt)初始條件：動態(tài)鏈表已定義操作結(jié)果：構(gòu)造動態(tài)鏈表結(jié)構(gòu)void addlink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相加void sublink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相減void mullink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相乘

17、void printlink(MPP * p)初始條件：動態(tài)鏈表已定義操作結(jié)果：選用升冪或降冪排列打印結(jié)果void deletelink(MPP *p)初始條件：動態(tài)鏈表已定義操作結(jié)果：刪除結(jié)點釋放內(nèi)存3.2詳細(xì)編碼/包含頭文件#include "stdafx.h"#include <stdio.h> #include<math.h>#include <malloc.h> #include <stdlib.h> #include <queue> #include <stack> #include <

18、;iostream> using namespace std;/自定義函數(shù)原型說明void creatpoly1(double *a, int pt) /建立順序結(jié)構(gòu)void ansprint(double *a, int n) /打印出結(jié)果void addpoly(double *a, double *b, double *c,int m,int n) /順序結(jié)構(gòu)相加void subpoly(double *a, double *b, double *c) /順序結(jié)構(gòu)相減void mulpoly(double *a, double *b, double *c) /順序結(jié)構(gòu)相乘MPP *

19、 creatlink(MPP *p, int n, int pt) /構(gòu)造動態(tài)鏈表結(jié)構(gòu)void printlink1(MPP * p) /打印結(jié)果Am(x)void printlink2(MPP * p) /打印結(jié)果Bn(x)void printlink(MPP * p) /打印結(jié)果M(x)void addlink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相加void sublink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相減void mullink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相乘void deleteli

20、nk(MPP *p) /刪除結(jié)點釋放內(nèi)存/建立順序結(jié)構(gòu) 順序存儲一元多項式則是通過下標(biāo)作為指數(shù)，系數(shù)存儲在數(shù)組對應(yīng)的位置，若系數(shù)為0，則在其指數(shù)對應(yīng)的數(shù)組位置存儲的數(shù)為0。void creatpoly1(double *a, int pt) /建立順序結(jié)構(gòu)int i;if (pt = 1)/第一個多項式for (i = 0; i <= cp1n1 - 1.expn; i+)/把小于等于最大指數(shù)的項系數(shù)賦值為0ai = 0;for (i = 0; i < n1; i+)/把指數(shù)大于0的項賦值輸入的系數(shù)acp1i.expn = cp1i.coef;else/第二個多項式for (i =

21、 0; i <= cp2n2 - 1.expn; i+)/把小于等于最大指數(shù)的項系數(shù)賦值為0ai = 0;for (i = 0; i < n2; i+)/把指數(shù)大于0的項賦值輸入的系數(shù)acp2i.expn = cp2i.coef;/順序結(jié)構(gòu)相加，對應(yīng)的數(shù)組下標(biāo)相同的系數(shù)相加void addpoly(double *a, double *b, double *c, int m, int n) /順序結(jié)構(gòu)相加int min = (cp1n1 - 1.expn > cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/兩個多項式的最大

22、指數(shù)（較小）int max = (cp1n1 - 1.expn < cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/兩個多項式的最大指數(shù)（較大）int i;for (i = 0; i <= min; i+)/在小于某個多項式的最大指數(shù)（較?。┑那闆r下，直接相加ci = ai + bi;for (; i <= max; i+)/加上剩余的項if (cp1n1 - 1.expn>cp2n2 - 1.expn)/如果較小的最大指數(shù)在b多項式ci = ai;else/如果較小的最大指數(shù)在a多項式ci = bi;puts(&q

23、uot;相加結(jié)果為：");ansprint(c, max);/輸出最后的相加結(jié)果/順序結(jié)構(gòu)相減，對應(yīng)的數(shù)組下標(biāo)相同的系數(shù)相加void subpoly(double *a, double *b, double *c) /順序結(jié)構(gòu)相減int min = (cp1n1 - 1.expn > cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/兩個多項式的最大指數(shù)（較?。﹊nt max = (cp1n1 - 1.expn<cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/兩個多項

24、式的最大指數(shù)（較大）int i;for (i = 0; i <= min; i+)/在小于某個多項式的最大指數(shù)（較小）的情況下，直接相減ci = ai - bi;for (; i <= max; i+)/處理剩余的項if (cp1n1 - 1.expn>cp2n2 - 1.expn)/如果被減數(shù)a的最大指數(shù)較大ci = ai;else/如果減數(shù)b的最大指數(shù)較大ci = -bi;puts("相減結(jié)果為：");ansprint(c, max);/輸出最后的相減結(jié)果/順序結(jié)構(gòu)相乘void mulpoly(double *a, double *b, double

25、*c) /順序結(jié)構(gòu)相乘int max = cp1n1 - 1.expn + cp2n2 - 1.expn + 2;/計算乘積的項數(shù)int i, j;for (i = 0; i < max; i+)/如果小于max直接將新多項式的指數(shù)賦值為0ci = 0;for (i = 0; i <= cp1n1 - 1.expn; i+)/計算剩余的項for (j = 0; j <= cp2n2 - 1.expn; j+)ci + j += ai * bj;puts("相乘結(jié)果為：");/輸出計算的結(jié)果ansprint(c, max - 1);經(jīng)過用戶的輸入操作，很容易

26、就可以創(chuàng)建出用戶需要進行運算的一元多項式，找到對應(yīng)的存儲方式，并彈出菜單項，用戶就可以輸入選項進行下一步進行加減乘的操作；這樣，需要實現(xiàn)的第一個功能就很輕松的完成了。/動態(tài)鏈表的創(chuàng)建MPP * creatlink(MPP *p, int n, int pt) /利用動態(tài)鏈表結(jié)構(gòu)存儲多項式MPP *d, *q;int i;q = (MPP *)malloc(sizeof(MPP);if (q = NULL)exit(0);q->next = NULL;/初始化指針為NULLq->coef = INFCO;/初始化初始系數(shù)q->expn = -INFEX;/初始化初始指數(shù)p =

27、q;for (i = 0; i < n; i+)/建立多項式鏈表結(jié)構(gòu)d = (MPP *)malloc(sizeof(MPP);if (d = NULL)exit(0);d->next = NULL;if (pt = 1)/第一個多項式d->coef = cp1i.coef;/多項式系數(shù)d->expn = cp1i.expn;/多項式指數(shù)else/第二個多項式d->coef = cp2i.coef;/多項式系數(shù)d->expn = cp2i.expn;/多項式指數(shù)q->next = d;/繼續(xù)下一個結(jié)點q = d;return p;/打印結(jié)果，用戶可選擇

28、升冪或者降冪打印，如若用戶輸入的選項不正確，則系統(tǒng)默認(rèn)升冪打印出結(jié)果。void printlink(MPP * p) /打印結(jié)果M(x)int num = 0, i = 0, choose, count = 0;puts("請選擇輸出順序：1 升冪 2 降冪：");scanf_s("%d", &choose);/輸入打印格式選項MPP *tp = p;p = p->next;while (p != NULL)/計算結(jié)點個數(shù)num+;p = p->next;MPOL *d = new MPOLnum;/建立輸出數(shù)據(jù)結(jié)構(gòu)p = tp-&g

29、t;next;while (p != NULL)/對新建的數(shù)據(jù)結(jié)構(gòu)賦值di.coef = p->coef;di.expn = p->expn;i+;p = p->next;if (choose = 2) /降冪打印多項式count = 0;printf("M(X)=");for (i = num - 1; i >= 0; i-)if (di.coef>0)putchar('+');printf("%lfX%d", di.coef, di.expn);else /升冪打印多項式if (choose != 1)p

30、rintf("沒有%d選項，系統(tǒng)將默認(rèn)輸出升序：nM(X)=", choose);elseprintf("M(X)=");for (i = 0; i < num; i+)if (di.coef>0)putchar('+');printf("%lfX%d", di.coef, di.expn);putchar(10);/動態(tài)鏈表相加，即比較對應(yīng)的指數(shù)，如若相同，則系數(shù)相加void addlink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相加MPP * p, *head;p = (MPP

31、 *)malloc(sizeof(MPP);/建立動態(tài)鏈表if (p = NULL)exit(0);/初始化鏈表數(shù)據(jù)p->coef = INFCO;p->expn = -INFEX;p->next = NULL;head = p3 = p;p1 = p1->next;p2 = p2->next;while (p1 != NULL | p2 != NULL)/兩個鏈表相加，兩個鏈表到表尾時結(jié)束循環(huán)if (fabs(head->coef) > 1e-8)p = (MPP *)malloc(sizeof(MPP);/創(chuàng)建結(jié)點if (p = NULL)exit

32、(0);head->next = p;head = p;head->next = NULL;if (p1 = NULL)/將加數(shù)的值賦值給和的鏈表head->coef = p2->coef;head->expn = p2->expn;p2 = p2->next;continue;if (p2 = NULL)/將被加數(shù)的值賦值給和的鏈表head->coef = p1->coef;head->expn = p1->expn;p1 = p1->next;continue;if (p1->expn = p2->expn

33、)/兩個多項式指數(shù)相等，系數(shù)相加head->coef = p1->coef + p2->coef;head->expn = p1->expn;p1 = p1->next;p2 = p2->next;else if (p1->expn < p2->expn)/被加數(shù)小于加數(shù)，將被加數(shù)的值賦值給和head->coef = p1->coef;head->expn = p1->expn;p1 = p1->next;else/被加數(shù)大于加數(shù)，將加數(shù)的值賦值給和head->coef = p2->coef;

34、head->expn = p2->expn;p2 = p2->next;puts("相加結(jié)果為：");printlink(p3);/輸出最后相加的結(jié)果/動態(tài)鏈表相減，即比較對應(yīng)的指數(shù)，如若相同，則系數(shù)相減void sublink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相減MPP * p, *head;p = (MPP *)malloc(sizeof(MPP);/創(chuàng)建結(jié)點if (p = NULL)exit(0);/初始化鏈表p->coef = INFCO;p->expn = -INFEX;p->next = NUL

35、L;head = p3 = p;p1 = p1->next;p2 = p2->next;while (p1 != NULL | p2 != NULL) /兩個鏈表相減，兩個鏈表到表尾時結(jié)束循環(huán)if (fabs(head->coef) > 1e-8)p = (MPP *)malloc(sizeof(MPP);/創(chuàng)建結(jié)點if (p = NULL)exit(0);head->next = p;head = p;head->next = NULL;if (p1 = NULL)/被減多項式到表尾，將第二個多項式的值賦值給結(jié)果多項式/指數(shù)不變，系數(shù)取相反數(shù)head-&g

36、t;coef = -p2->coef;head->expn = p2->expn;p2 = p2->next;continue;if (p2 = NULL)/第二個多項式到表尾，將被減多項式的值賦值給結(jié)果多項式head->coef = p1->coef;head->expn = p1->expn;p1 = p1->next;continue;if (p1->expn = p2->expn)/兩個多項式的某項指數(shù)相等，將相減結(jié)果賦值給結(jié)果多項式head->coef = p1->coef - p2->coef;he

37、ad->expn = p1->expn;p1 = p1->next;p2 = p2->next;else if (p1->expn < p2->expn)/被減數(shù)指數(shù)小于減數(shù)，將被減數(shù)結(jié)果賦值給結(jié)果多項式head->coef = p1->coef;head->expn = p1->expn;p1 = p1->next;else/被減數(shù)大于減數(shù)，將減數(shù)的值賦值給結(jié)果多項式，系數(shù)去相反數(shù)head->coef = -p2->coef;head->expn = p2->expn;p2 = p2->ne

38、xt;puts("相減結(jié)果為：");printlink(p3);/輸出多項式相減的結(jié)果/動態(tài)鏈表相乘void mullink(MPP *p1, MPP *p2, MPP *p3) /動態(tài)鏈表相乘MPP *p, *head, *d, *tp;int i, j;p = (MPP *)malloc(sizeof(MPP);/創(chuàng)建結(jié)果鏈表if (p = NULL)exit(0);/初始化結(jié)果鏈表p->coef = INFCO;p->expn = -INFEX;p->next = NULL;tp = head = p3 = p;p = (MPP *)malloc(s

39、izeof(MPP);if (p = NULL)exit(0);p->coef = INFCO;p->expn = INFEX;p->next = NULL;tp->next = p;for (i = 0; i < n1; i+) /兩個多項式的相乘p1 = p1->next;d = p2;for (j = 0; j < n2; j+)d = d->next;p = (MPP *)malloc(sizeof(MPP);/創(chuàng)建結(jié)果鏈表結(jié)點if (p = NULL)exit(0);p->next = NULL;p->coef = p1-&

40、gt;coef*d->coef;/將兩個多項式系數(shù)相乘后賦值給結(jié)果鏈表p->expn = p1->expn + d->expn;/將兩個多項式指數(shù)相加后賦值給結(jié)果鏈表tp = p3;while (tp->next != NULL)if (tp->expn = p->expn)tp->coef += p->coef;free(p);/釋放結(jié)點break;if (tp->expn<p->expn&&tp->next->expn>p->expn)p->next = tp->ne

41、xt;tp->next = p;break;tp = tp->next;tp = p3;while (tp->next != NULL)if (tp->next->expn = INFEX)free(tp->next);tp->next = NULL;break;tp = tp->next;puts("相乘結(jié)果為：");printlink(p3);/輸出兩個多項式相乘結(jié)果/刪除結(jié)點釋放內(nèi)存void deletelink(MPP *p) /刪除結(jié)點釋放內(nèi)存MPP *d;while (p != NULL)d = p;p = p-&

42、gt;next;free(d);/釋放結(jié)點到此為止，所有功能已經(jīng)分別實現(xiàn)了，通過執(zhí)行各個函數(shù)，就可以完成相應(yīng)的功能?，F(xiàn)在唯一需要做的就是找個函數(shù)來將他們“集中起來”，用來組合在一起，才能讓它們互相配合，一起工作。這個任務(wù)當(dāng)然是由main()來完成了：int main()printf("n");printf("t功 能： 二 叉 樹 的 遍 歷nn");printf("t編 譯 環(huán) 境：V S 2 0 1 0nn");printf("t發(fā) 布 日 期：2 0 1 5 - 1 1 - 2 5nn");printf(&q

43、uot;n*程序開始！*n");/存儲結(jié)構(gòu)選擇菜單 d:printf("ttt存儲菜單n");printf("t*n");printf("ttt請選擇實現(xiàn)結(jié)構(gòu)：nttt1 順序結(jié)構(gòu) nttt2 動態(tài)鏈表結(jié)構(gòu) nttt3 主菜單nttt4 退出n");printf("t*nn");printf("請輸入選項：n");/四則運算選擇菜單p:printf("ntt四則運算菜單n");printf("t*n");printf("ttt選擇操作方

44、式：nttt1 相加 nttt2 相減 nttt3 相乘 nttt4 主菜單 nttt5 退出n");printf("t*n");scanf_s("%d", &choose2);在main（）里，對各個相應(yīng)的操作指定了選擇序號，使用戶簡單明了，形象直觀，首先必須成功按照先序創(chuàng)建一元多項式，現(xiàn)實中一樣。因為你需要運算的對象不明確，又如何能準(zhǔn)確的確定相應(yīng)的結(jié)果呢，然后通過一個友好的容易操作的界面面向用戶，這樣即使用戶對計算機一竅不通，也能夠輕松的使用這個系統(tǒng)進行一元多項式的加減乘運算了。為了使用戶能夠在進行了一項操作之后還能進行另外的操作，

45、例如：加法做了之后還可以繼續(xù)選擇減法等等。所以讓程序一直執(zhí)行，直到用戶輸入退出的信息后才中止程序，這樣做程序顯得更人性化些！到此，整個程序也就完成了。4系統(tǒng)測試和結(jié)果分析4.1設(shè)計測試數(shù)據(jù) 4.2調(diào)試的詳細(xì)過程對于所有執(zhí)行過程，通過圖片最好說明問題了，程序開始如下圖所示：1. 程序開始運行初始界面如圖1: 圖12.順序存儲升冪輸出加法運算結(jié)果的步驟如下圖2-3：圖2 圖 33.順序存儲進行加運算降冪輸出結(jié)果如下圖4所示：圖44順序存儲計算相減升冪打印計算結(jié)果的詳細(xì)步驟如圖5：圖55.順序存儲減運算降冪輸出結(jié)果如圖6：圖66. 順序存儲計算相乘升冪打印計算結(jié)果的詳細(xì)步驟如圖7：圖 77.順序存儲

46、相乘降冪輸出計算結(jié)果如圖8：圖88.鏈?zhǔn)酱鎯臃ㄟ\算并升冪輸出結(jié)果如圖9-10所示：圖9圖109.鏈?zhǔn)酱鎯臃ń祪巛敵鋈鐖D11：圖1110.鏈?zhǔn)酱鎯p法運算并升冪輸出結(jié)果如圖12所示：圖1211.鏈?zhǔn)酱鎯p法運算降冪輸出結(jié)果如圖13所示：圖1312.鏈?zhǔn)酱鎯Τ朔ㄟ\算并升冪輸出結(jié)果如圖14所示：圖1413.鏈?zhǔn)酱鎯Τ朔ㄟ\算并降冪輸出結(jié)果如圖15所示：圖1514.退出程序，如圖16：圖16整個對一元多項式的創(chuàng)建，順序存儲和鏈?zhǔn)酱鎯?，以及順序存儲和鏈?zhǔn)酱鎯ο碌募訙p乘的運算，升冪降冪輸出運算后的結(jié)果，判斷一元多項式的稀疏與稠密的操作過程就是這樣，很簡單，就這樣完成了總 結(jié)通過這次課程設(shè)計使我了解到編寫

47、的程序不但要拿來使用，還要讓人看得懂。所以，代碼編寫的風(fēng)格要盡量規(guī)范，清晰。變量要盡量少定義，結(jié)構(gòu)體采用簡單的。另外，對指針的使用要小心，盡量在定義的時候就進行初始化，避免出現(xiàn)沒有被定義的指針。該程序主要實現(xiàn)了順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法等運算功能。同時，也應(yīng)用了升冪和降冪的輸出方法，輸出程序的結(jié)果。雖然此次的程序不是很完備，但是總體還是一個比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識點的程序了，當(dāng)然只是相對于我這個初學(xué)者來說。這次設(shè)計中我發(fā)現(xiàn)了自己的許多不足，如對指針的機制掌握的還不是很透徹，有的時候會出現(xiàn)指針指向錯誤以及空指針的錯誤,還有不能很好地分析自己算法地復(fù)雜度以及不能很好地使用

48、控制機制使自己的程序流暢地運行。因此，在今后我會更加努力。致 謝在此我要非常感謝的是我的指導(dǎo)老師陳曉亮老師，感謝老師的細(xì)心認(rèn)真的輔導(dǎo)，讓我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更多的了解，也讓我對這門課程產(chǎn)生了濃厚的興趣。在這次課程設(shè)計中我又進一步地了解了數(shù)據(jù)結(jié)構(gòu)中算法的核心思想的重要性，懂得了一個程序地好壞關(guān)鍵在于算法是否優(yōu)秀，一個好的優(yōu)秀的算法可以使我們的程序更加完善，安全性更高以及有更高的效率。本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計讓我收獲很多，我從陳曉亮老師身上學(xué)到了很多東西。他認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我收益匪淺。無論在理論上還是在實踐中，都給與我很大的幫助，使我得到很大的提高，這對于我以

49、后的工作和學(xué)習(xí)都有一種巨大的幫助，在此感謝他耐心的輔導(dǎo)。在撰寫論文階段，老師審閱我們的論文，提出了許多寶貴意見，沒有他的指導(dǎo)，我就不能較好的完成課題設(shè)計的任務(wù)。 另外，我還要感謝在這幾周來對我悉心教導(dǎo)的各位老師，他們孜孜不倦的教誨不但讓我學(xué)到了很多知識，而且讓我掌握了學(xué)習(xí)的方法，更教會了我做人處事的道理，在此表示感謝。同時，在編程過程中還有我班同學(xué)也給了我不少幫助，這里一并表示感謝。參考文獻1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解M北京：中國電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大

50、學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國鐵道出版社，2003附 錄/ 期末數(shù)據(jù)結(jié)構(gòu)3一元多項式的加減乘.cpp : 定義控制臺應(yīng)用程序的入口點。/=二叉樹的遍歷=/=執(zhí)行軟件VS2010=/=發(fā)布日期：2015-11-28=#include "stdafx.h"#include <stdio.h> #include<math.h>#include <malloc.h> #include <stdlib.h> #include <queue> #include <stack> #include <iostream> /=頭文件部分= using namespace std;#define INFEX 10000/初始化頭結(jié)點#define INFCO