數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 一元稀疏多項式計算器.doc

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