軟 件 學 院課程設計報告書課程名稱 數據結構課程設計 設計題目 一元稀疏多項式計算器 專業班級 學 號 姓 名 指導教師 2010 年 12 月目錄1 設計時間22 設計目的23設計任務24 設計內容24.1需求分析24.2總體設計24.3詳細設計54.4測試與分析64.4.1測試64.4.2分析84.5 附錄95、 總結與展望11參考文獻13成績評定131 設計時間2010年12月27日2 設計目的實現一元多項式的相加，相減，輸出結果。3設計任務設計一個一元稀疏多項式簡單計算器。4 設計內容 4.1需求分析 1、程序所能達到的功能；(1)輸入并建立多項式creatpolyn()；(2)輸出多項式，輸出形式為整數序列：n,c1,e1,c2,e2,cn,en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數升序排列 printpolyn()；(3)多項式a和b相加，建立多項式a+b，輸出相加的多項式addpolyn()；(4)多項式a和b相減，建立多項式a-b，輸出相減的多項式subpolyn()。2、輸入的形式和輸入值的范圍；輸入形式：多項式輸入值范圍：實數3、輸出的形式：輸出多項式，輸出形式為整數序列：n,c1,e1,c2,e2,cn,en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數升序排列 printpolyn()4、測試數據：輸入：a=2X+3X2; b=2X3+7X4輸出：a+b=2X+3X2+ 2X3+7X4a-b=2X+3X2-2X3-7X44.2總體設計內容包括：1、說明本程序中用到的所有抽象數據類型的定義； typedef struct Polynomial float coef; int expn; struct Polynomial *next; *Polyn,Polynomial;void Insert(Polyn p,Polyn h)Polyn CreatePolyn(Polyn head,int m)void PrintPolyn(Polyn P)Int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn Derivative(Polyn head)2、主程序的流程；開始運行選擇輸入求和求差建立兩個多項式多項式相加減輸出求和結果輸出求差結果3、說明各程序模塊之間的層次（調用）關系。Main()InsertCreatePolynPrintPolynAddPolynSubtractPolyncompareDerivative4.3詳細設計內容包括：函數CreatePolyn建立一個頭指針為head、項數為m的一元多項式，然后調運函數Insert向生成鏈表中保存多項式項數及每項的指數、系數。函數CreatePolyn生成多項式a和多項式b。通過函數compare和函數PrintPolyn對多項式a和多項式b指數、系數進行分析。當多項式a指數指數大于多項式b指數時，鏈表保存多項式a系數；當多項式b指數指數大于多項式a指數時，鏈表保存多項式b系數；當多項式b指數指數等于多項式a指數時，對多項式a和多項式b系數進行加減運算，之后將系數保存在鏈表中。函數Polyn AddPolyn對多項式a和多項式b進行加運算，調運函數compare、函數PrintPolyn、函數CreatePolyn。函數SubtractPolyn對多項式a和多項式b進行減運算，其對多項式b中各系數正負取反，然后調用函數Polyn AddPolyn進行a+(-b)。主函數運行分別輸入多項式和多項式的項數、系數和指數，然后選擇對多項式操作A：a+b或 B：a-b，從而實現對多項式的加減運算。，3、函數的調用關系圖。Main()InsertCreatePolyn你PrintPolynAddPolynSubtractPolyncompareDerivative4.4測試與分析4.4.1測試：輸入：a=2X+3X2; b=2X3+7X4輸出：a+b=2X+3X2+ 2X3+7X4a-b=2X+3X2-2X3-7X44.4.2分析：1、調試過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析；認真觀察自己的算法，看錯誤來自哪里，找出錯誤，并加以修改。2、算法的時間復雜度和空間復雜度的分析，改進設想。Insert的時間復雜度O(1)空間復雜度O(1)； Derivativ的時間復雜度O(1)空間復雜度O(1)；CreatePolyn的時間復雜度O(n)空間復雜度O(1)；compare的時間復雜度O(1)空間復雜度O(1)；PrintPolyn的時間復雜度O(1)空間復雜度O(1)；AddPolyn 的時間復雜度O(n)空間復雜度O(1)；SubtractPolyn的時間復雜度O(n)空間復雜度O(1)；Main()的時間復雜度O(n)空間復雜度O(1)。4.5 附錄定義多項式的項typedef struct Polynomial float coef; int expn; struct Polynomial *next; *Polyn,Polynomial;void Insert(Polyn p,Polyn h)向鏈表中插入多項式的項數、系數、指數。Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數為m的一元多項式。調運函數Insert生成多項式a和多項式b。void PrintPolyn(Polyn P)當多項式指數為“1”時，對多項式a和多項式b系數進行加減。Polyn AddPolyn(Polyn pa,Polyn pb)求解并建立多項式a+b，返回其頭指針。調運函數compare對多項式a和多項式b進行降冪輸出。Polyn SubtractPolyn(Polyn pa,Polyn pb)求解并建立多項式a-b，返回其頭指針。對多項式b中各項系數正負取反，然后調運函數Polyn AddPolyn，對多項式a和多項式b進行a+(-b)降冪輸出。Polyn Derivative(Polyn head)求解并建立導函數多項式，并返回其頭指針。void main()/主函數 int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; printf( 歡迎使用多項式操作程序nn); printf(請輸入a的項數:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多項式a printf(請輸入b的項數:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多項式b /輸出菜單printf( *n);printf( * 多項式操作程序 *n);printf( * A:輸出a+b B:輸出a-b *n);printf( * *n);printf( *n);while(a) printf(n請選擇操作：); scanf( %c,&flag);/空格符號一定要注意 switch(flag) caseA: casea: pc=AddPolyn(pa,pb); printf(n a+b=); PrintPolyn(pc); break; caseB: caseb: pc=SubtractPolyn(pa,pb); printf(n a-b=); PrintPolyn(pc); break; default:printf(n 您的選擇錯誤，請重新選擇!n); 5 總結與展望在編程過程中很容易發現程序中的錯誤，要盡快找出這些錯誤，使程序能正確運行。平時缺乏鍛煉即使在明確的出錯提示下也往往找不出錯誤，不知道該怎么辦，而求救于別人。但更重要的是通過自己的直接實踐來累積。因此，在實驗時千萬不要在程序通過后就認為萬事大吉、完成任務了，而應當在已通過的程序基礎上作一些改動，再進行編譯、連接和運行。我覺得我們對于數據結構的學習不僅包括理論部分的學習，還要讓我們勤動手，多實踐。剛開始學的時候確實有很多地方我很不理解，每次上課時老師都會給我們出不同的設計題目，對于我們來說，無疑是一個具大的挑戰，撞了幾次壁之后，我決定靜下心來，仔細去寫程序。老師會給我們需要編程的內容一些講解，順著老師的思路，來完成自己的設計，我們可以開始運行自己的程序，可是好多處的錯誤，還看不出到底是哪里出現了錯誤，但是程序還是得繼續下去，我多次和同學討論研究，逐漸能自己找出錯誤，并加以改正。此次的程序設計能夠成功，是我和我的同學共同努力作用的結果。在這一段努力學習的過程中，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費了好多心血，覺得它很難