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

1、實(shí)系數(shù)一元多項(xiàng)式問題實(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)式的輸入；.實(shí)現(xiàn)一元多項(xiàng)式的輸出；.計(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-1輸入值的范圍：系數(shù)為int型,輸出的

2、形式：第一行輸出多項(xiàng)式第二行輸出多項(xiàng)式第三行輸出多項(xiàng)式第四行輸出多項(xiàng)式第五行輸出多項(xiàng)式注：多項(xiàng)式的每一項(xiàng)形如:指數(shù)為float型。1;2;1與多項(xiàng)式2相加的結(jié)果多項(xiàng)式；1與多項(xiàng)式2相減的結(jié)果多項(xiàng)式；1與多項(xiàng)式2相乘的結(jié)果多項(xiàng)式2. Ox “3,注意指數(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-XWl-2.Ox-3.Ox八3-XWl+3.0-2.OX-XXA-1+3.0+2.Ox+5.Ox八3-3.OXWl

3、-6.Ox-2.Ox2-9.OX3-4.OX八46.0X八62、概要設(shè)計(jì)抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTPolynomial數(shù)據(jù)對(duì)象：D=aiaiTermSet,i=l,2,m,m>0a-中的指數(shù)值V a中的對(duì)多項(xiàng)式進(jìn)行排序輸 出多項(xiàng)式判斷系數(shù)為 零的情況合并指數(shù)相 同的項(xiàng)創(chuàng)建多項(xiàng)式多項(xiàng)式相加/多項(xiàng)式相減/多項(xiàng)式相乘TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：R1=<ai-l,ai>|ai-i,aiD,且指數(shù)值，i=2,n基本操作：sort(Polyn&h);/pnnt(Polynh);/delZeroCoef(Polyn&

4、;h);/merge(Polyn&h);/createListO;/addPoly(Polynhl,Polynh2);subPoly(Polynhl,Polynh2);multPoly(Polynhl,Polynh2);/ADTPolynomial結(jié)點(diǎn)類型系數(shù)指數(shù)多項(xiàng)式的抽象數(shù)據(jù)類型的定義：typedefstructPolynomial/(floatcoef;/intexp;/structPolynomial*next;PolyNode,*Polyn;判斷h1,h2系數(shù)是否為0調(diào)川print()函數(shù)，輸出,合并過并排好序的hi,h2調(diào)用addPoly(h1,h2),合并并輸出調(diào)用sub

5、Poly(h1,h2),合并并輸出謝川multPoly(h1,h2),合并并輸出結(jié)束3、詳細(xì)設(shè)計(jì)偽碼算法：主函數(shù):intmain()t (hl);prin t (h2);add Poly (hl,h2);sub Poly (hl, h2); multPoly (hl, h2); return 0;創(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的相乘,并輸出分支函數(shù):voidsort(Polyn&h);voidpri/t(Polynh);voiddelZeroCoef(Polyn&h);/排序輸出

6、多項(xiàng)式判斷處理系數(shù)為0的情況Po ly n h2);/voidmerge(Polyn&h);/PolyncreateListO;/voidaddPoly(Polynhl,Polynh2);/voidsubPoly(Polynhl,Polynh2);/voidmultPoly(Polynhl,合并多項(xiàng)式創(chuàng)建多項(xiàng)式兩個(gè)多項(xiàng)式相加并輸出兩個(gè)多項(xiàng)式相減并輸出兩個(gè)多項(xiàng)式相乘并輸出函數(shù)的調(diào)用關(guān)系:4、調(diào)試分析a.調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析：在輸入諸如“0,3”，“2,0”時(shí)，程序無(wú)法正常運(yùn)行或總是出解決：對(duì)指數(shù)或系數(shù)為0的情況應(yīng)單獨(dú)討論。為此，建立了delZe

7、roCoef函數(shù)來解決問題。b.算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想:時(shí)間復(fù)雜度和空間復(fù)雜度：設(shè)兩個(gè)多項(xiàng)式分別用m,n示空間復(fù)雜度，那么：sort(Polyn&h)pnnt(Polynh)delZeroCoef(Polyn&h)merge(Polyn&h):T(m*m),T(n*n)createList()：T(m),T(n)addPoly(Polynhl,Polynh2)subPoly(Polynhl,Polynh2)multPoly(Polynhl,Polynh2)來表示，T()表示時(shí)間復(fù)雜度，0()表：T(m*m),T(

8、n*n);0(m),0(n)。：T(m),T(n);0(l),0(l)o：T(m),T(n);0(1),0(1)o；0(1),0(l)o;0(1),0(l)o：T(m),T(n);0，0(1)。：T(m),T(n);0，0(1)。：T(m),T(n);0(1),0(1)o改進(jìn)設(shè)想：可以在原來的基礎(chǔ)上改進(jìn)程序，或者設(shè)計(jì)一些新的算法，盡量減小時(shí)間復(fù)雜度和空間復(fù)雜度。C.經(jīng)驗(yàn)和體會(huì)：L這次用鏈表來解決問題讓我的收獲很大，對(duì)鏈表的構(gòu)建更加熟練，對(duì)鏈表的向前推進(jìn)把握的更加準(zhǔn)確，在調(diào)試代碼，檢驗(yàn)的時(shí)候，曾遇到很大的阻礙，但解決問題后，自己也收獲了很多。2. 通過本次實(shí)驗(yàn)，我發(fā)現(xiàn)自己分析問題不是很全面，容易

9、忽略一些細(xì)節(jié)，以后分析問題時(shí)要仔細(xì)考慮認(rèn)真分析，避免細(xì)節(jié)上的錯(cuò)誤。3. 在設(shè)計(jì)該算法時(shí)，由于過于依賴書本上的例子，導(dǎo)致很多不必要的麻煩，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。5、測(cè)試數(shù)據(jù)與測(cè)試結(jié)果第一組數(shù)據(jù)：輸入：2 43 21 52 3005 36 3# 57 68 44800輸出：3.0xA2+2.0xA3+2.0xM+xA57.0xA3+7.OxM+6.0xA5+3.0xA6+4.0xA83.Ox2+9.Ox3+9.Ox4+7.0x*5+3.Ox6+4.Ox83.Ox2-5.Ox3-5.Ox4-5.O

10、x*5-3.Ox6-4.Ox821.Ox-5+35.0x*6+46.0x7+42.OxK+25.Ox-9+24.0x*10+11.Ox"11+8.Ox*12+4.0x-13Pressanykeytocontinue第二組數(shù)據(jù)：輸入：4604335241002 03 54 65 700輸出：4.Ox+5.Ox2+3.Ox3+4.Ox62.0+3.Ox*5+3.Ox6+4.Ox72.0+4.Ox+5.Ox2+3.Ox3+3.Ox5+7.Ox6+4.Ox7-2.0+4.Ox+5.Ox2+3.Ox3-3.0x5+x6-4.Ox78.0x+10.Ox2+6.Ox3+20.Ox6+27.Ox7+

11、40.Ox8+29.Ox9+12.Ox10+12.Ox11+12.0x12+16.0x13Pressanykeytocontinue第三組數(shù)據(jù)：輸入：-212 -33 0957-400-65085-6-349000輸出：7.OxA-4+2.OxA-3+3.0-2.Ox+9.0xA55.OxA-6+9.0-3.0xA4-6.0xA55.OxA-6+7.OxA-4+2.OxA-3+12.0-2.Ox-3.OxM+3.0xA5一5OxA-6+7.OxA-4+2.OxA-3-6.0-2.Ox+3.OxM+15.0xA535.0xA-10+10.OxA-9+15.0xA-6-10.OxA-5+63.OxA-4+18.OxA-3+45.OxA-1+6.0-66.Ox-12.0xA2-9.OxM+69.0xA5+12.0xA6-27.0xA9-54.OxAlOPressanykeytocontinue第四組數(shù)據(jù)：輸入：3-9-78-2-47803-10002-3-43100-5輸出：3.OxA-9-2.OxA-4T.02. Ox-3+1.0-4.Ox33. Ox-9-2.Ox-4+2.Ox-3-4.Ox34. Ox-