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

實(shí)系數(shù)一元多項(xiàng)式問(wèn)題實(shí)驗(yàn)報(bào)告2010級(jí)計(jì)算機(jī)科學(xué)與技術(shù)（非師范）100704033魯靜2011年10月14日星期五1、需求分析實(shí)現(xiàn)實(shí)系數(shù)一元多項(xiàng)式的創(chuàng)建，打印以及兩個(gè)一元多項(xiàng)式的加、減、乘運(yùn)算。1）程序所能達(dá)到的功能：a．實(shí)現(xiàn)一元多項(xiàng)式的輸入；b．實(shí)現(xiàn)一元多項(xiàng)式的輸出；c．計(jì)算兩個(gè)一元多項(xiàng)式的和并輸出結(jié)果；d．計(jì)算兩個(gè)一元多項(xiàng)式的差并輸出結(jié)果；e．計(jì)算兩個(gè)一元多項(xiàng)式的積并輸出結(jié)果；a．實(shí)現(xiàn)一元多項(xiàng)式的輸入；b．實(shí)現(xiàn)一元多項(xiàng)式的輸出；c．計(jì)算兩個(gè)一元多項(xiàng)式的和并輸出結(jié)果；d．計(jì)算兩個(gè)一元多項(xiàng)式的差并輸出結(jié)果；e．計(jì)算兩個(gè)一元多項(xiàng)式的積并輸出結(jié)果；2）輸入的形式和輸入值的范圍：輸入要求：分行輸入，每行輸入一項(xiàng)，先輸入多項(xiàng)式的指數(shù)，再輸入多項(xiàng)式的系數(shù)，以00為結(jié)束標(biāo)志，結(jié)束一個(gè)多項(xiàng)式的輸入。輸入形式：-12-21-33-1-100輸入值的范圍：系數(shù)為int型，指數(shù)為float型。（3）輸出的形式：要求：第一行輸出多項(xiàng)式1；第二行輸出多項(xiàng)式2；第三行輸出多項(xiàng)式1與多項(xiàng)式2相加的結(jié)果多項(xiàng)式；第四行輸出多項(xiàng)式1與多項(xiàng)式2相減的結(jié)果多項(xiàng)式；第五行輸出多項(xiàng)式1與多項(xiàng)式2相乘的結(jié)果多項(xiàng)式注：多項(xiàng)式的每一項(xiàng)形如：2.0x"，注意指數(shù)應(yīng)保留一位小數(shù);多項(xiàng)式按照升冪次序排列；系數(shù)為1的非零次項(xiàng)應(yīng)略去系數(shù)，系數(shù)為0的項(xiàng)不能出現(xiàn)在結(jié)果中；指數(shù)為0的項(xiàng)應(yīng)只輸出系數(shù)；多項(xiàng)式的第一項(xiàng)系數(shù)符號(hào)為正時(shí)，不要輸出“+”，其他項(xiàng)要輸出“+”，“-”符號(hào)。輸出形式：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è)計(jì)抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTPolynomial｛數(shù)據(jù)對(duì)象：D二｛a|aGTermSet,i=l,2,…，TermSet"中的每個(gè)元素包含一個(gè)表示系數(shù)的實(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//對(duì)多項(xiàng)式進(jìn)行排序//輸出多項(xiàng)式delZeroCoef(Polyn&delZeroCoef(Polyn&h);//判斷系數(shù)為零的情況merge(Polyn&merge(Polyn&h);//合并指數(shù)相同的項(xiàng)createList();//創(chuàng)建多項(xiàng)式createList();//創(chuàng)建多項(xiàng)式//多項(xiàng)式相加//多項(xiàng)式相減//多項(xiàng)式相加//多項(xiàng)式相減//多項(xiàng)式相乘subPoly(Polynh1,Polynh2);multPoly(Polynh1,Polynh2);}ADTPolynomial多項(xiàng)式的抽象數(shù)據(jù)類型的定義：主程序的流程圖主程序的流程圖typedefstructPolynomial{floatcoef;intexp;structPolynomial*next;}PolyNode,*Polyn;//結(jié)點(diǎn)類型//系數(shù)//指數(shù)輸入兩個(gè)多項(xiàng)式hl,h2判斷h1,h2系數(shù)是否為0

3、詳細(xì)設(shè)計(jì)偽碼算法：主函數(shù)：intmain(){;//創(chuàng)建多項(xiàng)式1;//創(chuàng)建多項(xiàng)式1;//創(chuàng)建多項(xiàng)式2//輸出多項(xiàng)式1//輸出多項(xiàng)式2//實(shí)現(xiàn)多項(xiàng)式1和2的相加，并輸出//實(shí)現(xiàn)多項(xiàng)式1和2的相減，并輸出//實(shí)現(xiàn)多項(xiàng)式1和2的相乘，并輸出Polynh2=createList()print(h1);print(h2);addPoly(h1,h2);subPoly(h1,h2);multPoly(h1,h2);return0;}分支函數(shù)：voidsort(Polyn&h); //排序voidprint(Polynh); //輸出多項(xiàng)式voiddelZeroCoef(Polyn&h);//判斷處理系數(shù)為0的情況voidmerge(Polyn&h); //合并多項(xiàng)式PolyncreateList(); //創(chuàng)建多項(xiàng)式voidaddPoly(Polynhl,Polynh2);//兩個(gè)多項(xiàng)式相加并輸出voidsubPoly(Polynhl,Polynh2);//兩個(gè)多項(xiàng)式相減并輸出voidmultPoly(Polynh1,Polynh2);//兩個(gè)多項(xiàng)式相乘并輸出函數(shù)的調(diào)用關(guān)系：4、調(diào)試分析a.調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析:在輸入諸如“0,3”，“2,0”時(shí)，程序無(wú)法正常運(yùn)行或總是出錯(cuò).解決：對(duì)指數(shù)或系數(shù)為0的情況應(yīng)單獨(dú)討論。為此，建立了delZeroCoef函數(shù)來(lái)解決問(wèn)題。b?算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想:時(shí)間復(fù)雜度和空間復(fù)雜度：設(shè)兩個(gè)多項(xiàng)式分別用m,n來(lái)表示，T()表示時(shí)間復(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è)想：可以在原來(lái)的基礎(chǔ)上改進(jìn)程序，或者設(shè)計(jì)一些新的算法，盡量減小時(shí)間復(fù)雜度和空間復(fù)雜度。c?經(jīng)驗(yàn)和體會(huì)：這次用鏈表來(lái)解決問(wèn)題讓我的收獲很大，對(duì)鏈表的構(gòu)建更加熟練，對(duì)鏈表的向前推進(jìn)把握的更加準(zhǔn)確，在調(diào)試代碼，檢驗(yàn)的時(shí)候，曾遇到很大的阻礙，但解決問(wèn)題后，自己也收獲了很多。通過(guò)本次實(shí)驗(yàn)，我發(fā)現(xiàn)自己分析問(wèn)題不是很全面，容易忽略一些細(xì)節(jié)，以后分析問(wèn)題時(shí)要仔細(xì)考慮認(rèn)真分析，避免細(xì)節(jié)上的錯(cuò)誤。在設(shè)計(jì)該算法時(shí)，由于過(guò)于依賴書本上的例子，導(dǎo)致很多不必要的麻煩，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒(méi)能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。5、測(cè)試數(shù)據(jù)與測(cè)試結(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.