數(shù)據(jù)結(jié)構(gòu)上機實驗-多項式加法

1、!-多項式加法班級:姓名:完成日期:2014-04-061. 需求分析本程序的任務(wù)是實現(xiàn)兩個多項式的加法其中多項式的系數(shù)為浮點型, 指數(shù)為整數(shù)，輸出的結(jié)果也為系數(shù)和指數(shù)。(1) 輸入的形式和輸入值的范圍:輸入多項式的系數(shù)a和未知數(shù)X的指數(shù)b,當a和b都為零時,輸入結(jié)束。輸入值的范圍：a為實數(shù)，b為整數(shù)。(2) 輸出形式:輸出多項式的系數(shù)和多項式未知數(shù) X的指數(shù)即(a,b)形式。(3) 程序所能達到的功能:實現(xiàn)兩個多項式的加法，并輸出最后的結(jié)果。(4) 測試數(shù)據(jù):輸入：7 0 3 1 9 8 5 17 0 08 1 22 7 -9 8 0 0輸出：(7,0)(11,1)(22,7)(5,17)2

2、. 概要設(shè)計(1) 抽象數(shù)據(jù)類型的定義如下:屬于 AtomSet;ADT Li nkList數(shù)據(jù)對象：D=Ei|i=1,2,3n;n> 0;EiAtomSet是某個數(shù)據(jù)對象基本操作:In itList_L(&L);操作結(jié)果：創(chuàng)建頭節(jié)點，并初始化該節(jié)點。ADT Li nkList(2) 主程序:Void mai n( )創(chuàng)建鏈表并用循環(huán)結(jié)構(gòu)將數(shù)據(jù)輸入到鏈表中;Add Poly n(L1,L2);輸出結(jié)果;(3) 程序模塊的調(diào)用關(guān)系3. 詳細設(shè)計(1) 節(jié)點類型typ edef struct Lnodefloat coef; /存儲項系數(shù)int expn;/存儲項指數(shù)struct L

3、node *n ext;Lno de,*L in kList;(2) 多項式的基本操作為:In itList_L(Li nkList &L);/初始化頭節(jié)點;void Add Polyn(polyno mial pa, polyno mial p b);/實現(xiàn)多項式加法，并返回多項式加法的最終結(jié)果/同時釋放節(jié)點Void mai n()/ 創(chuàng)建鏈表L1和L2,并使 p=L1,q=L2 ；In itList_L(Li nkList &L);for(;)cin>>a;cin>>b;if(a=0&&b=0)/跳出循環(huán)，結(jié)束輸入break;m=ne

4、w Lno de;/創(chuàng)建新節(jié)點m->coef=a;m->ex pn二b;q->n ext=m;q=m;q->n ext=n ull;/輸入第一個多項式的系數(shù)和X的指數(shù)for(;)cin>>a;cin>>b;if(a=0&&b=0)/跳出循環(huán)，結(jié)束輸入break;n=new Lno de;/倉U建新節(jié)點n->coef二a;n->ex pn二b;p->n ext 二n;P 二n;p->n ext=n ull;輸入第二個多項式的系數(shù)和 X的指數(shù)Add Poly n(L1,L2);while(L1-> nex

5、t)匸n ull)cout<<L1- >n ext->coef<<" "<<L1- >n ext->ex pn<<""L1=L1-> next; / 循環(huán)輸出結(jié)果(3) 函數(shù)的調(diào)用關(guān)系圖4. 調(diào)試分析(1) 調(diào)試過程中遇到的問題及解決方法:在向創(chuàng)建的鏈表里輸入數(shù)據(jù)時，因為忘記將創(chuàng)建的新節(jié)點的next指針置空(即q->next=null )，導(dǎo)致在輸出節(jié)點的數(shù)據(jù) 時出現(xiàn)錯誤。解決方法將 for循環(huán)輸入的最后一條語句改為 q->n ext=null ，正確的解決了這個問

6、題。(2) 算法的時空分析整個程序運行期間實行動態(tài)創(chuàng)建節(jié)點， 一邊輸入數(shù)據(jù)，一邊 創(chuàng)建節(jié)點。當將全部數(shù)據(jù)輸入到單鏈表中后再調(diào)用多項式加法這 個函數(shù)，并一邊實現(xiàn)多項式的相加，一邊釋放節(jié)點，有效防止了 在程序反復(fù)運行過程中可能出現(xiàn)系統(tǒng)空間不夠分配的現(xiàn)象。(3) 經(jīng)驗和體會通過編寫多項加法這個程序， 我將自己所學到的創(chuàng)建鏈表，初始化鏈表和多項式加法算法都應(yīng)用了一次，這使我們不僅僅只 是理論化的學習書本上的知識， 而是將學習到的理論知識應(yīng)用到實際的操作中來增強我們的實際操作能力，這使我增加了實際操 作經(jīng)驗，也使我通過實際操作來認識到自己在程序編寫上的不足 從而增強了我的實際編寫程序的能力。5. 用戶使

7、用說明(1)本程序的運行環(huán)境為Microsoft Visual C+ 6.0。(2)進入程序后的界面為(3)輸入數(shù)據(jù)，當一組數(shù)據(jù)中的系數(shù)與指數(shù)都為零時，輸入結(jié)束，按回車鍵，同樣的方法再輸入第二組數(shù)據(jù)。最后按回車鍵就 會輸出結(jié)果。6. 測試結(jié)果輸入數(shù)據(jù)：7 0 3 1 9 8 5 17 0 08 1 22 7 -9 8 0 0輸出操作結(jié)果:(7,0) (11,1) (22,7) (5 ,17)輸入數(shù)據(jù)：3 1輸出操作結(jié)果:(5,1) (5,2) (4,3) (15,5) (9,8)輸入數(shù)據(jù)：2 0 3 2 5 4 6 7 0 03 0 4 3 8 4 5 7 0 0輸出操作結(jié)果：(5,0) (3

8、,2) (4,3) (13,4) (11,7)輸入數(shù)據(jù)：4 2 3 5 6 7 9 8 0 03 2 5 5 7 7 2 10 0 0輸出操作結(jié)果：(7,2) (8,5) (13,7) (9,8) (2,10)7. 附錄#in clude<iostream> using n ames pace std;typ edef int Status;#defi ne OVERFLOW -1#defi ne null 0typ edef struct Lnodefloat coef; II存儲項系數(shù)int expn;/ 存儲項指數(shù)struct Lnode *n ext;Lno de,*L i

9、n kList;初始化頭節(jié)點typ edef Lin kList polyno mial;Status In itList_L(Li nkList &L) /L=(L in kList)malloc(sizeof(L no de);if(!L)return(-1);L>n ext 二nu II;return 1;void Add Polyn(polyno mial pa, polyno mial p b)/實現(xiàn)兩個多項式相加的算法float x;polyno mial qa;polyno mial qb;polyno mial s;polyno mial u;qa二pa->

10、n ext; qb二pb->n ext; s二pa;while(qa&&qb)if(qa->ex pn< qb->ex pn)s=qa;qa=qa->n ext;else if(qa->ex pn二二qb->ex pn)x=qa->coef+qb->coef;if(x!=0)qa->coef=x;s=qa;qa=qa->n ext;u=qb;qb=qb->n ext;free(u);elses->n ext=qa->n ext;free(qa);qa=s->n ext;u=qb;qb=qb

11、->n ext;free(u);else if(qa->ex pn> qb->ex pn)u=qb->n ext;s->n ext=qb;s=qb;qb->n ext=qa;qb=u;if(qb)qa->n ext=qb;free( pb);void mai n()float a;int b;polyno mial L1;polyno mial L2;Lin kList q;Lin kList p;Lin kList m;Lin kList n;In itList_L(L1);q=L1;In itList_L(L2);P=L2;coutvv&qu

12、ot;請輸入數(shù)據(jù)："<<endl;for(；)cin>>a;cin>>b;if(a=0&&b=0)break;m=new Lnode;m->coef=a;m->ex pn二b;q->n ext=m;q=m;q->n ext=n ull;循環(huán)輸入第一個多項式的系數(shù)與指數(shù)for(;)cin>>a;cin>>b;if(a=O&&b=0)break;n=new Lnode;n->coef二a;n->ex pn二b;p->n ext 二n;P 二n;p->n ext=n ull;循環(huán)輸入第二個多項式的系數(shù)與指數(shù)Add Poly n( L1,L2);/調(diào)用多項式相加的算法w