數據結構實系數一元多項式運算實驗報告解讀

1、實系數一元多項式問題實驗報告2010級計算機科學與技術(非師范)100704033魯靜2011年10月14日星期五1、需求分析實現實系數一元多項式的創(chuàng)建，打印以及兩個一元多項式的加、減、乘運算。(1)程序所能達到的功能：a.實現一元多項式的輸入；.實現一元多項式的輸出；.計算兩個一元多項式的和并輸出結果；d.計算兩個一元多項式的差并輸出結果；e.計算兩個一元多項式的積并輸出結果；(2)輸入的形式和輸入值的范圍：輸入要求：分行輸入，每行輸入一項，先輸入多項式的指數，再輸入多項式的系數，以00為結束標志，結束一個多項式的輸入。輸入形式：-12-21-33-1-1輸入值的范圍：系數為int型,輸出的

2、形式：第一行輸出多項式第二行輸出多項式第三行輸出多項式第四行輸出多項式第五行輸出多項式注：多項式的每一項形如:指數為float型。1;2;1與多項式2相加的結果多項式；1與多項式2相減的結果多項式；1與多項式2相乘的結果多項式2. Ox “3,注意指數應保留一位小數多項式按照升幕次序排列；系數為1的非零次項應略去系數，系數為0的項不能出現在結果中；指數為0的項應只輸出系數；多項式的第一項系數符號為正時，不要輸出“+”，其他項要輸出“+”，“-”符號。輸出形式: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、概要設計抽象數據類型一元多項式的定義如下：ADTPolynomial數據對象：D=aiaiTermSet,i=l,2,m,m>0a-中的指數值V a中的對多項式進行排序輸 出多項式判斷系數為 零的情況合并指數相 同的項創(chuàng)建多項式多項式相加/多項式相減/多項式相乘TermSet中的每個元素包含一個表示系數的實數和表示指數的整數數據關系：R1=<ai-l,ai>|ai-i,aiD,且指數值，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結點類型系數指數多項式的抽象數據類型的定義：typedefstructPolynomial/(floatcoef;/intexp;/structPolynomial*next;PolyNode,*Polyn;判斷h1,h2系數是否為0調川print()函數，輸出,合并過并排好序的hi,h2調用addPoly(h1,h2),合并并輸出調用sub

5、Poly(h1,h2),合并并輸出謝川multPoly(h1,h2),合并并輸出結束3、詳細設計偽碼算法：主函數:intmain()t (hl);prin t (h2);add Poly (hl,h2);sub Poly (hl, h2); multPoly (hl, h2); return 0;創(chuàng)建多項式1 創(chuàng)建多項式2 輸出多項式1 輸出多項式2實現多項式1和2的相加，并輸出實現多項式1和2的相減，并輸出實現多項式1和2的相乘,并輸出分支函數:voidsort(Polyn&h);voidpri/t(Polynh);voiddelZeroCoef(Polyn&h);/排序輸出

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

7、roCoef函數來解決問題。b.算法的時空分析(包括基本操作和其他算法的時間復雜度和空間復雜度的分析)和改進設想:時間復雜度和空間復雜度：設兩個多項式分別用m,n示空間復雜度，那么：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()表示時間復雜度，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改進設想：可以在原來的基礎上改進程序，或者設計一些新的算法，盡量減小時間復雜度和空間復雜度。C.經驗和體會：L這次用鏈表來解決問題讓我的收獲很大，對鏈表的構建更加熟練，對鏈表的向前推進把握的更加準確，在調試代碼，檢驗的時候，曾遇到很大的阻礙，但解決問題后，自己也收獲了很多。2. 通過本次實驗，我發(fā)現自己分析問題不是很全面，容易

9、忽略一些細節(jié)，以后分析問題時要仔細考慮認真分析，避免細節(jié)上的錯誤。3. 在設計該算法時，由于過于依賴書本上的例子，導致很多不必要的麻煩，例如在建立鏈表時頭指針的設立導致了之后運用到相關的指針時沒能很好的移動指針出現了數據重復輸出或是輸出系統缺省值，不能實現算法。5、測試數據與測試結果第一組數據：輸入：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第二組數據：輸入：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第三組數據：輸入：-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第四組數據：輸入：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-