數(shù)據(jù)結(jié)構(gòu)實系數(shù)一元多項式運(yùn)算實驗報告解讀

實系數(shù)一元多項式問題實驗報告2010級計算機(jī)科學(xué)與技術(shù)（非師范）100704033魯靜2011年10月14日星期五1、需求分析實現(xiàn)實系數(shù)一元多項式的創(chuàng)建，打印以及兩個一元多項式的加、減、乘運(yùn)算。1）程序所能達(dá)到的功能：a．實現(xiàn)一元多項式的輸入；b．實現(xiàn)一元多項式的輸出；c．計算兩個一元多項式的和并輸出結(jié)果；d．計算兩個一元多項式的差并輸出結(jié)果；e．計算兩個一元多項式的積并輸出結(jié)果；a．實現(xiàn)一元多項式的輸入；b．實現(xiàn)一元多項式的輸出；c．計算兩個一元多項式的和并輸出結(jié)果；d．計算兩個一元多項式的差并輸出結(jié)果；e．計算兩個一元多項式的積并輸出結(jié)果；2）輸入的形式和輸入值的范圍：輸入要求：分行輸入，每行輸入一項，先輸入多項式的指數(shù)，再輸入多項式的系數(shù)，以00為結(jié)束標(biāo)志，結(jié)束一個多項式的輸入。輸入形式：-12-21-33-1-100輸入值的范圍：系數(shù)為int型，指數(shù)為float型。（3）輸出的形式：要求：第一行輸出多項式1；第二行輸出多項式2；第三行輸出多項式1與多項式2相加的結(jié)果多項式；第四行輸出多項式1與多項式2相減的結(jié)果多項式；第五行輸出多項式1與多項式2相乘的結(jié)果多項式注：多項式的每一項形如：2.0x"，注意指數(shù)應(yīng)保留一位小數(shù);多項式按照升冪次序排列；系數(shù)為1的非零次項應(yīng)略去系數(shù)，系數(shù)為0的項不能出現(xiàn)在結(jié)果中；指數(shù)為0的項應(yīng)只輸出系數(shù)；多項式的第一項系數(shù)符號為正時，不要輸出“+”，其他項要輸出“+”，“-”符號。輸出形式：3.0+2.0X八3-x-1-2.0x-3.0x3

_xT+3.0-2.0x-x3x八T+3.0+2.0x+5.0x八3-3.0x八T-6.0x-2.0x八2-9.0X八3-4.0X八4-6.0X八62、概要設(shè)計抽象數(shù)據(jù)類型一元多項式的定義如下：ADTPolynomial｛數(shù)據(jù)對象：D二｛a|aGTermSet,i=l,2,…，TermSet"中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)｝數(shù)據(jù)關(guān)系：R1={<a,a>|數(shù)據(jù)關(guān)系：R1={<a,a>|a,i-1i i-1指數(shù)值，i=2,…,n}基本操作：sort(Polyn&h);print(Polynh);aGD,且a中的指數(shù)值Va中的i i-1 i//對多項式進(jìn)行排序//輸出多項式delZeroCoef(Polyn&delZeroCoef(Polyn&h);//判斷系數(shù)為零的情況merge(Polyn&merge(Polyn&h);//合并指數(shù)相同的項createList();//創(chuàng)建多項式createList();//創(chuàng)建多項式//多項式相加//多項式相減//多項式相加//多項式相減//多項式相乘subPoly(Polynh1,Polynh2);multPoly(Polynh1,Polynh2);}ADTPolynomial多項式的抽象數(shù)據(jù)類型的定義：主程序的流程圖主程序的流程圖typedefstructPolynomial{floatcoef;intexp;structPolynomial*next;}PolyNode,*Polyn;//結(jié)點類型//系數(shù)//指數(shù)輸入兩個多項式hl,h2判斷h1,h2系數(shù)是否為0

3、詳細(xì)設(shè)計偽碼算法：主函數(shù)：intmain(){;//創(chuàng)建多項式1;//創(chuàng)建多項式1;//創(chuàng)建多項式2//輸出多項式1//輸出多項式2//實現(xiàn)多項式1和2的相加，并輸出//實現(xiàn)多項式1和2的相減，并輸出//實現(xiàn)多項式1和2的相乘，并輸出Polynh2=createList()print(h1);print(h2);addPoly(h1,h2);subPoly(h1,h2);multPoly(h1,h2);return0;}分支函數(shù)：voidsort(Polyn&h); //排序voidprint(Polynh); //輸出多項式voiddelZeroCoef(Polyn&h);//判斷處理系數(shù)為0的情況voidmerge(Polyn&h); //合并多項式PolyncreateList(); //創(chuàng)建多項式voidaddPoly(Polynhl,Polynh2);//兩個多項式相加并輸出voidsubPoly(Polynhl,Polynh2);//兩個多項式相減并輸出voidmultPoly(Polynh1,Polynh2);//兩個多項式相乘并輸出函數(shù)的調(diào)用關(guān)系：4、調(diào)試分析a.調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析:在輸入諸如“0,3”，“2,0”時，程序無法正常運(yùn)行或總是出錯.解決：對指數(shù)或系數(shù)為0的情況應(yīng)單獨(dú)討論。為此，建立了delZeroCoef函數(shù)來解決問題。b?算法的時空分析(包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想:時間復(fù)雜度和空間復(fù)雜度：設(shè)兩個多項式分別用m,n來表示，T()表示時間復(fù)雜度，0()表示空間復(fù)雜度，那么：sort(Polyn&h)：T(m*m),T(n*n)；0(m),0(n)。print(Polynh)：T(m),T(n)；0(1),0(1)。delZeroCoef(Polyn&h)：T(m),T(n)；0(1),0(1)。merge(Polyn&h)：T(m*m),T(n*n)；0(1),0(1)。createList()：T(m),T(n)；0(1),0(1)。addPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。subPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。multPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。改進(jìn)設(shè)想：可以在原來的基礎(chǔ)上改進(jìn)程序，或者設(shè)計一些新的算法，盡量減小時間復(fù)雜度和空間復(fù)雜度。c?經(jīng)驗和體會：這次用鏈表來解決問題讓我的收獲很大，對鏈表的構(gòu)建更加熟練，對鏈表的向前推進(jìn)把握的更加準(zhǔn)確，在調(diào)試代碼，檢驗的時候，曾遇到很大的阻礙，但解決問題后，自己也收獲了很多。通過本次實驗，我發(fā)現(xiàn)自己分析問題不是很全面，容易忽略一些細(xì)節(jié)，以后分析問題時要仔細(xì)考慮認(rèn)真分析，避免細(xì)節(jié)上的錯誤。在設(shè)計該算法時，由于過于依賴書本上的例子，導(dǎo)致很多不必要的麻煩，例如在建立鏈表時頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時沒能很好的移動指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實現(xiàn)算法。5、測試數(shù)據(jù)與測試結(jié)果第一組數(shù)據(jù)：輸入：42530033564800輸出：3.0x“2+2.0x"3+2.0x“4+x“57.0x“3+7.0x"4+6.0x“5+3.0x飛+4.0x"83.0x“2+9.0x"3+9.0x“4+7.0x“5+3.0x飛+4.0x"83.0x“2—5.0x"3—5.0x“4—5.0x“5—3.0x飛—4.0x"821.0x“5+35.0x飛+46.0x“7+42.0x"8+25.0x"9+24.0x"10+11.0x"ll+8.0x"12+4.0x"13Pressanykeytocontinue第二組數(shù)據(jù)輸入：604321000536700輸出：4.0x+5.0x"2+3.0x“3+4.0x飛2.0+3.0x“5+3.0x飛+4.0x“72.0+4.0x+5.0x"2+3.0x“3+3.0x“5+7.0x飛+4.0x“7—2.0+4.0x+5.0x“2+3.0x“3—3.0x“5+x飛—4.0x“78.0x+10.0x“2+6.0x“3+20.0x飛+27.0x“7+40.0x"8+29.0x”9+12.0x"10+12.0x"ll+12.0x「2+16.0x「3Pressanykeytocontinue第三組數(shù)據(jù)：輸入：—21—30957—400—6508—6—349000輸出：7.0x-4+2.0x-3+3.0-2.0x+9.0x55.0x—6+9.0—3.0x4—6.0x55.0x—6+7.0x—4+2.0x—3+12.0—2.0x—3.0x4+3.0x5—5.0x—6+7.0x—4+2.0x—3—6.0—2.0x+3.0x4+15.0x535.0x—10+10.0x—9+15.0x—6—10.0x—5+63.0x—4+18.0x—3+45.0x—1+6.0—66.0xT2.0x2—9.0x4+69.0x5+12.0x6—27.0x9—54.0x10Pressanykeytocontinue第四組數(shù)據(jù)：輸入：3-9-78-2-47803-10002-3-43100-500輸出：3.0x"-9-2.0x"-4-1.02.0x-3+1.0-4.0x33.0x“-9-2.0x“-4+2.0x"-3-4.0x“33.0x-9-2.