多項式加法實驗報告

1、題 目： 多項式加法 8 / 10文檔可自由編輯打印多項式加法一、 課題概述線性表是一種最簡單、最基本，也是最常用的數(shù)據(jù)結(jié)構(gòu)，其用途十分廣泛，例如，用帶表頭結(jié)點的單鏈表求解一元整系數(shù)多項式加法和乘法運算?，F(xiàn)給兩個一元整系數(shù)多項式，請求解兩者之和。輸入兩組數(shù)據(jù)，每一組代表一個一元整系數(shù)多項式，有多行組成，其中每一行給出多項式每一項的系數(shù)和指數(shù)，這些行按指數(shù)遞減次序排序，每一組結(jié)束行為0 -1。輸出三組數(shù)據(jù)，前兩組為一元整系數(shù)多項式，最后一組為兩個多項式的和。一元整系數(shù)多項式輸出形式如下：（1）多項式項4x輸出為4X（2）多項式項4x2輸出為4X2（3）第一項系數(shù)為正數(shù)時，加號不要輸出（4）除常系

2、數(shù)項外，項系數(shù)為1不顯式輸出，-1輸出為-例如，4x3- x2+x-1正確輸出形式為4X3-X2+X-1，錯誤輸出形式為 +4X3-1X2+1X-1二、 設計與實現(xiàn)1、類的層次關系及核心算法分析：項節(jié)點類Trem中定義了三個私有變量，系數(shù)coef、指數(shù)exp和指向下一個項節(jié)點的指針域link。多項式類Polynominal被聲明成項節(jié)點類Trem類的友元類。公有函數(shù)InsertAfter構(gòu)造一個新的項節(jié)點，其系數(shù)為c指數(shù)為e,并將新節(jié)點插入在調(diào)用該函數(shù)的項節(jié)點及后繼節(jié)點之間。多項式類Polynominal中包含了3個公有成員函數(shù)：AddTerms，Output和 PolyAdd。Ad

3、dTerms函數(shù)通過輸入流in,輸入多項式的各項構(gòu)造一個多項式的單循環(huán)鏈表；Output函數(shù)將多項式按降冪方式送輸出流；PolyAdd函數(shù)實現(xiàn)將多項式r加到指針this指示的多項式上。AddTerms函數(shù)從輸入流in按降冪輸入各項（c,e）來構(gòu)造多項式的單循環(huán)鏈表，當輸入（0，-1）是構(gòu)造過程結(jié)束。Output函數(shù)遍歷單循環(huán)鏈表將多項式按降冪方式送輸出流，它調(diào)用項類Trem上重載的“<<”操作符實現(xiàn)按項輸出。多項式加法，設有多項式p(x)和q(x),分別用單循環(huán)鏈表表示。設p和q分別指向多項式p(x)和q(x)的當前正進行比較的項節(jié)點，初始時分別指向兩多項式中最高冪次的項節(jié)點。q

4、1指向q的前驅(qū)節(jié)點。對p(x)進行遍歷。直到處理完所有節(jié)點。當p->exp<q->exp，則q指示的項應該為多項式結(jié)果中的一項，所以q 1和 q 右移一項，指針p不動。當多項式指數(shù)相等時（p->exp=q->exp），系數(shù)相加，即q->coef=q->coef+p->coef。加完之后如果系數(shù)為0，則刪除節(jié)點，p右移一項，如果加完之后系數(shù)不為0，指針q 1和q均右移一個節(jié)點。當p->exp>q->exp，則復制p所指示的節(jié)點，并將其插入在q 1后；指針右移一個節(jié)點。2、關鍵函數(shù)流程圖：一元多項式創(chuàng)建成功按降冪依次輸入各項的系數(shù)和

5、指數(shù)創(chuàng)建鏈表類型的 項多項式創(chuàng)建流程圖： N輸入“0 -1”開始 Y 多項式加法流程圖： Output函數(shù)流程圖：開始開始遍歷單循環(huán)鏈表，統(tǒng)計統(tǒng)計單循環(huán)鏈表有幾項（k），統(tǒng)計單循環(huán)鏈表前幾項(i)為0。跳過系數(shù)大的項指數(shù)相等嗎？N如果只有一項，并且為系數(shù)為0，則輸出一個0。 Y系數(shù)相加如果全為0，則輸出一個0。系數(shù)為0 N再遍歷一次單循環(huán)鏈表，找到第一個不為0的節(jié)點，并把系數(shù)輸出，不管正負號。 Y刪除p,重置q指針。移動q1和q以p的系數(shù)和指數(shù)生成新節(jié)點，插入q1后.從第一個不為0的節(jié)點之后的節(jié)點開始遍歷單循環(huán)鏈表。系數(shù)>0指數(shù)大于等于0 Y 結(jié)束輸出該項輸出一個“+"out&

6、lt;<*m結(jié)束 N Y3、源代碼：#include<iostream>using namespace std;class Polynominal; /向前引用 ，因為后面定義的Trem類中用到Polynominal類 class Term /定義項節(jié)點類Trem public: Term(int c,int e); Term(int c,int e,Term *nxt); Term* InsertAfter(int c,int e); /在this指針指示的節(jié)點后插入新節(jié)點 private: int coef; /系數(shù) int exp; /指數(shù) Term *link; fr

7、iend ostream & operator<<(ostream &,const Term &); /重載”<<“，輸出多項式的一項 friend class Polynominal; /類Polynominal作為類Term的友元類 ;Term:Term(int c,int e):coef(c),exp(e) link=0;Term:Term(int c,int e,Term *nxt):coef(c),exp(e)link=nxt;Term* Term:InsertAfter(int c,int e)/為新項申請節(jié)點的存儲單元，并用Term

8、函數(shù)將c,e和this->link的值填入新節(jié)點的相應域 link=new Term(c,e,link); return link;ostream & operator<<(ostream & out,const Term & val)/重載”<<"，輸出多項式的一項，用coef Xexp表示多項式的每一項 if(val.coef=0) return out; /如果系數(shù)為0，直接跳出 if(val.coef=1) /如果系數(shù)為1 ，再判斷 switch (val.exp) case 0:out<<1;break; /

9、如果在系數(shù)為1的前提下，指數(shù)為0，則輸出“1" case 1:out<<"X" break; /如果在系數(shù)為1的前提下，指數(shù)為1，則輸出"X" default:out<<"X"<<val.exp; break; /如果在系數(shù)為1的前提下，不為0，也不為1，則輸先出“X" ,后面緊跟輸出指數(shù)的值 return out; if( val.coef=-1)/如果系數(shù)為-1 ，再判斷 switch (val.exp) case 0:out<<-1;break;/如果在系數(shù)為-

10、1的前提下，指數(shù)為0，則輸出“-1" case 1:out<<"-X" break;/如果在系數(shù)為-1的前提下，指數(shù)為1，則輸出“-" default:out<<"-X"<<val.exp; break; /如果在系數(shù)為-1的前提下，指數(shù)不為0，也不為1，則輸出“-X",后面緊跟輸出指數(shù)的值 return out; else /如果系數(shù)不滿足以上所有情況，則執(zhí)行else語句 out<<val.coef; /先輸出系數(shù)，對于整數(shù)前面的"+"，在 Output中

11、進行處理 switch (val.exp) case 0:break; /如果指數(shù)為0，則什么都不做，直接break case 1:out<<"X" break;/如果指數(shù)為1的話，輸出一個"X" default:out<<"X"<<val.exp; break;/如果指數(shù)不為0，也不為1，則輸出“-X",后面緊跟輸出指數(shù)的值 return out; class Polynominal /多項式類public: Polynominal(); /構(gòu)造函數(shù)的聲明 Polynominal();

12、/析構(gòu)函數(shù)則輸出“-X",后面緊跟輸出指數(shù) 的值 void AddTerms(istream& in); /輸入多項式的各項，構(gòu)造多項式鏈表 void Output(ostream& out)const;/將多項式送輸出流 void PolyAdd(Polynominal& r); /多項式相加 private:Term* theList; /單循環(huán)鏈表的表頭指針 friend ostream & operator <<(ostream &,const Polynominal&); friend istream &

13、operator >>(istream &,Polynominal &); friend Polynominal & operator +(Polynominal &, Polynominal &);Polynominal:Polynominal() /創(chuàng)建多項式的空的單循環(huán)鏈表 theList=new Term(0,-1); /分配表頭節(jié)點存儲單元 theList->link=theList; /構(gòu)成循環(huán)鏈表 Polynominal:Polynominal() /撤銷多項式的單循環(huán)鏈表 Term* p=theList->link

14、; while (p!=theList) theList->link=p->link; /刪除p節(jié)點 delete p; /釋放p之前的存儲空間 p=theList->link; /p指向下一個待刪除的節(jié)點 delete theList; /釋放表頭節(jié)點的存儲單元 void Polynominal:AddTerms(istream & in) /按指數(shù)遞減次序輸入各項，構(gòu)造單循環(huán)鏈表 int count=0; /定義一個變量，用作計數(shù) Term *q=theList; /定義一個指針，指向表頭節(jié)點 int c,e; /coef.exp for (;) cin>&

15、gt;c>>e; if (c=0&&e=-1) /當輸入”0，-1“的時候，構(gòu)造過程結(jié)束 break; else q=q->InsertAfter(c,e);/將c,e插入表尾節(jié)點之后 count+; /統(tǒng)計輸入項的個數(shù) if(count=0) q=q->InsertAfter(0,0);cout<<0;/如果計數(shù)器為0，即剛開始就輸入了”0，-1“，則輸出”0“ void Polynominal:Output(ostream& out)const int j,k=0,i=0; Term *m=theList->link; fo

16、r(;m!=theList&&m->coef=0;m=m->link)i+; /統(tǒng)計單循環(huán)鏈表前幾項為0 m=theList->link; for(;m!=theList;m=m->link)k+; /統(tǒng)計單循環(huán)鏈表有幾項 m=theList->link; if(k=1&&(m->coef=0) cout<<0<<endl; return; /如果只有一項，并且為系數(shù)為0，則輸出一個0 if(i=k) cout<<0<<endl; return; /如果全為0，則輸出一個0 fo

17、r(j=0;j<i;j+) /找到第一個不為0的項，并輸出 m=m->link; out<<*m; m=m->link; for(;m!=theList;m=m->link) /再遍歷第一個不為0的節(jié)點之后的節(jié)點 if(m->coef>0) /如果系數(shù)大于o out<<"+" /輸出一個“+" out<<*m; /然后輸出該項 else if(m->coef<0) /如果系數(shù)小于0 out<<*m; /直接輸出該項 cout<<endl; /換行 void

18、Polynominal:PolyAdd(Polynominal &r) /將多項式r加到多項式this上 Term *q,*q1=theList,*p; /q1指向表頭節(jié)點 p=r.theList->link; /p指向第一個要處理的節(jié)點 q=q1->link; /q1是q的前驅(qū)，p和Q就是指向當前要進行比較的項 while(p->exp>=0) / 對r的單循環(huán)鏈表進行遍歷， 直到全部節(jié)點處理完畢 while(p->exp<q->exp) / 跳過q->exp的項 q1=q; q=q->link; if(p->exp=q-&

19、gt;exp) /當指數(shù)相等時相加 q->coef=q->coef+p->coef; if (q->coef=0) /若相加后系數(shù)為0，則刪除p q1->link=q->link; delete (q); q=q1->link; / 重置q指針 else q1=q; q=q->link; /若相加后系數(shù)不為0，則移動q1和q else q1=q1->InsertAfter(p->coef,p->exp); /p->exp>1->exp的情況 p=p->link; / 以p的系數(shù)和指數(shù)生成新節(jié)點，插入q1后 ostream & operator <