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

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