一元多項式計算程序報告

/XX學(xué)院課程設(shè)計題目：〔一元多項式計算問題一元多項式計算。要求：能夠按照指數(shù)降序排列建立并輸出一元多項式；能夠完成兩個一元多項式的相加、相減.并將結(jié)果輸入。1、問題分析和任務(wù)定義<1>.任務(wù)定義：此程序需要完成如下的要求：將多項式按照指數(shù)降序排列建立并輸出.將兩個一元多項式進行相加、相減操作.并將結(jié)果輸入。a：輸入并建立多項式；

b：輸出多項式.輸出形式為表達式的形式.并且多項式的指數(shù)為降序；c：多項式a和b相加.建立多項式a+b；

d：多項式a和b相減.建立多項式a-b。

e：多項式的輸出形式為類數(shù)學(xué)表達式。<2>.問題分析：本程序的關(guān)鍵點在于如何將輸入的一元多項式按指數(shù)的降序進行排列.而難點就是將輸入的兩個一元多項式進行相加、相減操作。實現(xiàn)本程序需要解決以下幾個問題：1、如何將輸入的一元多項式按指數(shù)的降序進行排列；2、如何確定要輸入的多項式的項數(shù)；3、如何將輸入的兩個一元多項式進行顯示出來；4、如何將輸入的兩個一元多項式進行相加操作；5、如何將輸入的兩個一元多項式進行相減操作。次程序是鏈表的應(yīng)用.通過鏈表實現(xiàn)一元多項式的相加相減操作。要對一元多項式進行表示：一元多項式的表示在計算機內(nèi)可以用鏈表來表示為了節(jié)省存儲空間.我們只存儲多項式中系數(shù)非0的項。鏈表中的每一個節(jié)點存放多項式的一個系數(shù)非0項.它包含三個域.分別存放該項的系數(shù)、指數(shù)以及指向下一多項式項節(jié)點的指針。下圖1所示為該結(jié)點的結(jié)構(gòu)：圖1結(jié)點的結(jié)構(gòu)創(chuàng)建一元多項式鏈表.對一元多項式的運算中會出現(xiàn)各種可能情況進行分析.實現(xiàn)一元多項式的相加、相減操作。2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計本題設(shè)計要求能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加.相減.并將結(jié)果輸入。數(shù)據(jù)結(jié)構(gòu)的選用A:基于鏈表中的節(jié)點可以動態(tài)生成的特點.以及鏈表可以靈活的添加或刪除節(jié)點的數(shù)據(jù)結(jié)構(gòu).為了實現(xiàn)任意多項式的加法.減法.因此選擇單鏈表的結(jié)構(gòu)體.它有一個系數(shù).指數(shù).下一個指針3個元屬；例如.圖2中的兩個線性鏈表分別表示一元多項式和一元多項式。從圖中可見.每個結(jié)點表示多項式中的一項。圖2多項式表的單鏈存儲結(jié)構(gòu)B：本設(shè)計使用了以下數(shù)據(jù)結(jié)構(gòu)：structNode{//結(jié)點類型floatcoef;//系數(shù)intexp;//指數(shù)};C：設(shè)計本程序需用到九個模塊.用到以下九個子函數(shù)如下：1、CreateLink<Link&L,intn>;//創(chuàng)建含有n個鏈表類型結(jié)點的項.即創(chuàng)建一個n項多項式2、PrintList<LinkL>;//輸出鏈表3、PolyAdd<Link&pc,Linkpa,Linkpb>;//將兩個一元多項式相加4、PolySubstract<Link&pc,Linkpa,Linkpb>;//將兩個一元多項式相減5、CopyLink<Link&pc,Linkpa>;//把一個鏈表的內(nèi)容復(fù)制給另一個鏈表6、JudgeIfExpSame<Linkpa,Linke>;/*判斷指數(shù)是否與多項式中已存在的某項相同*/7、DestroyLink<Link&L>;8、Menu<>//菜單函數(shù)9、main<>//主程序模塊調(diào)用鏈一元多項式的各種基本操作模塊?！?多項式的輸入采用尾插法的方式.輸入多項式中一個項的系數(shù)和指數(shù).就產(chǎn)生一個新的節(jié)點.建立起它的右指針.并用頭節(jié)點指向它；為了判斷一個多項式是否輸入結(jié)束.在輸入前先確定要輸入的項數(shù)?！?兩個多項式的加法"和多項式"鏈表中的結(jié)點無需另生成.而應(yīng)該從兩個多項式的鏈表中摘取。其運算規(guī)則如下：假設(shè)指針qa和qb分別指向多項式A和多項式B中當(dāng)前進行比較的某個結(jié)點.則比較兩個結(jié)點中的指數(shù)項.有下列3種情況：①指針qa所指結(jié)點的指數(shù)值<指針qb所指結(jié)點的指數(shù)值.則應(yīng)摘取qa指針?biāo)附Y(jié)點插入到"和多項式"鏈表中去；②指針qa所指結(jié)點的指數(shù)值>指針qb所指結(jié)點的指數(shù)值.則應(yīng)摘取指針qb所指結(jié)點插入到"和多項式"鏈表中去；③指針qa所指結(jié)點的指數(shù)值=指針qb所指結(jié)點的指數(shù)值.則將兩個結(jié)點中的系數(shù)相加.若和數(shù)不為零.則修改qa所指結(jié)點的系數(shù)值.同時釋放qb所指結(jié)點；反之.從多項式A的鏈表中刪除相應(yīng)結(jié)點.并釋放指針qa和qb所指結(jié)點。例如.由圖2中的兩個鏈表表示的多項式相加得到的"和多項式"鏈表如圖3所示.圖中的長方框表示已被釋放的結(jié)點。圖3相加得到的和多項式上述多項式的相加過程歸并兩個有序表的過程極其類似.不同之處僅在于.后者在比較數(shù)據(jù)元素時只出現(xiàn)兩種情況。因此.多項式相加的過程也完全可以利用線性鏈表的基本操作來完成。〔4兩個多項式的減法兩個多項式的減法實現(xiàn).是從2個多項式的尾部開始.2個多項式的某一項都不為空時.如果指數(shù)相等的話.系數(shù)就應(yīng)該相減；相減的和不為0的話.用尾插法建立一個新的節(jié)點。p的系數(shù)小于q的系數(shù)的話.就應(yīng)該復(fù)制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話.就應(yīng)該復(fù)制p接點到多項式中.并且建立的接點的系數(shù)為原來的相反數(shù)；當(dāng)?shù)?個多項式空.第1個數(shù)不為空時.將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生。當(dāng)?shù)?個多項式空.第1個數(shù)不為空時.將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生.并且建立的接點的系數(shù)為原來的相反數(shù)。〔5程序流程圖:一元多項式相減流程圖如圖4：銷毀鏈表銷毀鏈表否P!=NULLP=pt把pb復(fù)制到pt系數(shù)變反P=p->next調(diào)用加法函數(shù)是圖4多項式相減流程圖一元多項式相加流程圖如圖5：pc=newLNodepc=newLNode、pc->next=NULLp1=p1->next、p2=p2->next復(fù)制兩個多項式分別到p1、p2p1!=NULLp2!=NULLp1->data.exp<p2->data.exp將p1加到pc上p1->data.exp>p2->data.exp將p2加到pc上P1系數(shù)加p2系數(shù)將p2加到pc上p1系數(shù)cofe！=0P1、p2后移刪除p1p1!=NULLp2!=NULLp->next=p1p->next=p2調(diào)用排序函數(shù)paixu<>對pc進行排序是否是否否是是否是是否否圖5相加流程圖3、詳細(xì)設(shè)計和編碼<1>、算法思想〔1輸入并建立多項式——CreateLink<>

〔2輸出多項式.輸出形式為整數(shù)序列.序列按指數(shù)降序排列——PrintList<>

〔3多項式a和b相加.建立多項式a+b.輸出相加的多項式——PolyAdd<>

〔4多項式a和b相減.建立多項式a-b.輸出相減的多項式——PolySubstract<>用帶表頭結(jié)點的單鏈表存儲多項式。此程序需要完成如下的要求：將多項式按照指數(shù)降序排列建立并輸出.將兩個一元多項式進行相加、相減操作.并將結(jié)果輸入。<2>、算法描述1、定義結(jié)點類型用floatcofe表示一元多項式的系數(shù).intexp表示一元多項式的指數(shù)創(chuàng)建鏈表的結(jié)點類型。structNode{floatcoef;//結(jié)點類型intexp;};2、定義鏈表的類型structLNode{polynomialdata;//鏈表類型LNode*next;};3、創(chuàng)建含有n個鏈表類型結(jié)點的項.即創(chuàng)建一個n項多項式.用函數(shù)voidCreateLink<Link&L,intn>表示.創(chuàng)建頭結(jié)點<L->data>.exp=-1;創(chuàng)建多項式?jīng)]有成功.遞歸調(diào)用重新創(chuàng)建CreateLink<L,n>;4、用函數(shù)intJudgeIfExpSame<LinkL,Linke>判斷指數(shù)是否與多項式中已存在的某項相同.如果輸入的一元多項式有重復(fù)的指數(shù)需重新輸入。5輸出鏈表用函數(shù)voidPrintList<LinkL>表示.這個部分根據(jù)項系數(shù)的不同分為項的系數(shù)大于0的5種情況和項的系數(shù)小于0的5種情況。6、鏈表內(nèi)容的復(fù)制：把一個鏈表的內(nèi)容復(fù)制給另一個鏈表用函數(shù)voidCopyLink<Link&pc,Linkpa>表示。8、將多項式按照指數(shù)降序排列建立并輸出.本程序用冒泡排序的方法將多項式的指數(shù)從大到小的順序進行排列voidpaixu<Linkhead1>對鏈表進行排序過程中用循環(huán)來確定鏈表的長度while<head1!=NULL>{n++;head1=head1->next;}將鏈表中的元素按照從大到小的順序排列if<<p->data>.exp<<q->data>.exp>{<m->data>.coef=<p->data>.coef;<m->data>.exp=<p->data>.exp;<p->data>.coef=<q->data>.coef;<p->data>.exp=<q->data>.exp;<q->data>.coef=<m->data>.coef;<q->data>.exp=<m->data>.exp;}9、將兩個一元多項式相加用函數(shù)voidPolyAdd<Link&pc,Linkpa,Linkpb>表示"和多項式"鏈表中的結(jié)點無需另生成.而應(yīng)該從兩個多項式的鏈表中摘取。其運算規(guī)則如下：假設(shè)指針qa和qb分別指向多項式A和多項式B中當(dāng)前進行比較的某個結(jié)點.則比較兩個結(jié)點中的指數(shù)項.有下列3種情況：①指針qa所指結(jié)點的指數(shù)值<指針qb所指結(jié)點的指數(shù)值.則應(yīng)摘取qa指針?biāo)附Y(jié)點插入到"和多項式"鏈表中去；②指針qa所指結(jié)點的指數(shù)值>指針qb所指結(jié)點的指數(shù)值.則應(yīng)摘取指針qb所指結(jié)點插入到"和多項式"鏈表中去；③指針qa所指結(jié)點的指數(shù)值=指針qb所指結(jié)點的指數(shù)值.則將兩個結(jié)點中的系數(shù)相加.若和數(shù)不為零.則修改qa所指結(jié)點的系數(shù)值.同時釋放qb所指結(jié)點；反之.從多項式A的鏈表中刪除相應(yīng)結(jié)點.并釋放指針qa和qb所指結(jié)點。10、將兩個多項式相減10、將兩個一元多項式相減用函數(shù)voidPolySubstract<Link&pc,Linkpa,Linkpb>表示.兩個多項式的減法實現(xiàn).是從2個多項式的尾部開始.2個多項式的某一項都不為空時.如果指數(shù)相等的話.系數(shù)就應(yīng)該相減；相減的和不為0的話.用尾插法建立一個新的節(jié)點。p的系數(shù)小于q的系數(shù)的話.就應(yīng)該復(fù)制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話.就應(yīng)該復(fù)制p接點到多項式中.并且建立的接點的系數(shù)為原來的相反數(shù)；當(dāng)?shù)?個多項式空.第1個數(shù)不為空時.將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生。當(dāng)?shù)?個多項式空.第1個數(shù)不為空時.將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生.并且建立的接點的系數(shù)為原來的相反數(shù)。4、上機調(diào)試1、語法錯誤及修改：編譯中出現(xiàn)的語法問題主要在于子函數(shù)和變量的定義.括號的配對.關(guān)鍵字和函數(shù)名稱的書寫.以及一些庫函數(shù)的規(guī)范使用。這些問題均可以根據(jù)編譯器的警告提示.對應(yīng)的將其解決。2、邏輯問題修改和調(diào)整：由于一元多項式的計算中.在輸入多項式的系數(shù)和一元多項式的指數(shù)是會有多種情況.所以設(shè)計過程中經(jīng)常出現(xiàn)各種沒有考慮到的情況.通過查找課本和資料最終比較全面的囊括了一元多項式會出現(xiàn)的各種情況。3、經(jīng)驗體會：在開始看到程序題目的時候會以為一元多項式的加減會很簡單.可是在課程設(shè)計的過程中發(fā)現(xiàn)程序的編寫并不是開始想象的那么簡單.在這過程也中遇到了難題.比如題目的要求中要對一元多項式的指數(shù)進行排序?qū)崿F(xiàn)從大到小的循序進行輸入.所以在對指數(shù)的排序中運行經(jīng)常出錯.最終用冒泡排序的方法解決了這個問題。5、測試結(jié)果及其分析菜單界面如圖6：圖6菜單界面創(chuàng)建要運算的兩個一元多項式如圖7：圖7創(chuàng)建要運算的兩個一元多項式顯示輸入的兩個多項式如圖8:圖8顯示輸入的兩個多項式將兩個一元多項式相加如圖9：圖9將兩個一元多項式相加將兩個一元多項式相減如圖10：圖10多項式相減銷毀創(chuàng)建的兩個多項式如圖11：圖11銷毀創(chuàng)建的兩個多項式6、用戶使用說明本程序運行后出現(xiàn)菜單界面.根據(jù)菜單提示進行操作。在創(chuàng)建多項式多項式的時候根據(jù)提示先確定要輸入的多項式的項數(shù).再依次輸入各項的系數(shù)和指數(shù).值得注意的時候在輸入指數(shù)的時候輸入的指數(shù)一定不能小于0.當(dāng)指數(shù)小于0的時候會提示出"你輸入有誤.指數(shù)不允許為負(fù)！"重新輸入；在輸入的項數(shù)中如果出現(xiàn)前面已經(jīng)輸入過的系數(shù)時會出現(xiàn)提示重新輸入。7、參考文獻[1]鄭莉.董淵.張瑞豐C++語言程序設(shè)計<第3版>清華大學(xué)出版社[2]王昆侖.李紅數(shù)據(jù)結(jié)構(gòu)與算法中國鐵道出版社8、附錄〔源程序#include<iostream>usingnamespacestd;structNode{floatcoef;//結(jié)點類型intexp;};typedefNodepolynomial;structLNode{polynomialdata;//鏈表類型LNode*next;};typedefLNode*Link;voidCreateLink<Link&L,intn>;voidPrintList<LinkL>;voidPolyAdd<Link&pc,Linkpa,Linkpb>;voidPolySubstract<Link&pc,Linkpa,Linkpb>;voidCopyLink<Link&pc,Linkpa>;intJudgeIfExpSame<Linkpa,Linke>;voidDestroyLink<Link&L>;intCompareIfNum<inti>;voidDestroyLink<Link&L>{Linkp;p=L->next;while<p>{L->next=p->next;deletep;p=L->next;}deleteL;L=NULL;}//創(chuàng)建含有n個鏈表類型結(jié)點的項.即創(chuàng)建一個n項多項式voidCreateLink<Link&L,intn>{if<L!=NULL>{DestroyLink<L>;}Linkp,q,newp;L=newLNode;L->next=NULL;<L->data>.exp=-1;//創(chuàng)建頭結(jié)點p=L;for<inti=1;i<=n;i++>{newp=newLNode;cout<<"請輸入第"<<i<<"項的系數(shù)和指數(shù):"<<endl;cout<<"系數(shù):";cin>><newp->data>.coef;cout<<"指數(shù):";cin>><newp->data>.exp;if<newp->data.exp<0>{cout<<"您輸入有誤.指數(shù)不允許為負(fù)值!"<<endl;deletenewp;i--;continue;}newp->next=NULL;p=L;if<newp->data.coef==0>{cout<<"系數(shù)為零.重新輸入!"<<endl;deletenewp;i--;continue;}while<<p->next!=NULL>&&<<p->next->data>.exp><newp->data>.exp>>{p=p->next;//p指向指數(shù)最小的那一個}q=p->next;if<!JudgeIfExpSame<L,newp>>{p->next=newp;newp->next=q;}else{cout<<"輸入的該項指數(shù)與多項式中已存在的某項相同,請重新創(chuàng)建一個正確的多項"<<endl;deletenewp;DestroyLink<L>;CreateLink<L,n>;//創(chuàng)建多項式?jīng)]有成功.遞歸調(diào)用重新創(chuàng)建break;}}}/*判斷指數(shù)是否與多項式中已存在的某項相同*/intJudgeIfExpSame<LinkL,Linke>{Linkp;p=L->next;while<p!=NULL&&<e->data.exp!=p->data.exp>>p=p->next;if<p==NULL>return0;elsereturn1;}/*輸出鏈表*/voidPrintList<LinkL>{Linkp;if<L==NULL||L->next==NULL>cout<<"該一元多項式為空！"<<endl;else{p=L->next;//項的系數(shù)大于0的5種情況if<<p->data>.coef>0>{if<<p->data>.exp==0>cout<<<p->data>.coef;elseif<<p->data>.coef==1&&<p->data>.exp==1>cout<<"x";elseif<<p->data>.coef==1&&<p->data>.exp!=1>cout<<"x^"<<<p->data>.exp;elseif<<p->data>.exp==1&&<p->data>.coef!=1>cout<<<p->data>.coef<<"x";elsecout<<<p->data>.coef<<"x^"<<<p->data>.exp;}//項的系數(shù)小于0的5種情況if<<p->data>.coef<0>{if<<p->data>.exp==0>cout<<<p->data>.coef;elseif<p->data.coef==-1&&p->data.exp==1>cout<<"-x";elseif<p->data.coef==-1&&p->data.exp!=1>cout<<"-x^"<<p->data.exp;elseif<p->data.exp==1>cout<<p->data.coef<<"x";elsecout<<<p->data>.coef<<"x^"<<<p->data>.exp;}p=p->next;while<p!=NULL>{if<<p->data>.coef>0>{if<<p->data>.exp==0>cout<<"+"<<<p->data>.coef;elseif<<p->data>.exp==1&&<p->data>.coef!=1>cout<<"+"<<<p->data>.coef<<"x";elseif<<p->data>.exp==1&&<p->data>.coef==1>cout<<"+"<<"x";elseif<<p->data>.coef==1&&<p->data>.exp!=1>cout<<"+"<<"x^"<<<p->data>.exp;elsecout<<"+"<<<p->data>.coef<<"x^"<<<p->data>.exp;}if<<p->data>.coef<0>{if<<p->data>.exp==0>cout<<<p->data>.coef;elseif<p->data.coef==-1&&p->data.exp==1>cout<<"-x";elseif<p->data.coef==-1&&p->data.exp!=1>cout<<"-x^"<<p->data.exp;elseif<p->data.exp==1>cout<<p->data.coef<<"x";elsecout<<<p->data>.coef<<"x^"<<<p->data>.exp;}p=p->next;}}cout<<endl;}/*把一個鏈表的內(nèi)容復(fù)制給另一個鏈表*/voidCopyLink<Link&pc,Linkpa>{Linkp,q,r;pc=newLNode;pc->next=NULL;r=pc;p=pa;while<p->next!=NULL>{q=newLNode;q->data.coef=p->next->data.coef;q->data.exp=p->next->data.exp;r->next=q;q->next=NULL;r=q;p=p->next;}}//對鏈表進行排序voidpaixu<Linkhead1>{Linkm,p1,p,q;m=newLNode;intn,i,j;p1=head1;while<head1!=NULL>{//用循環(huán)來確定鏈表的長度n++;head1=head1->next;}head1=p1;head1=head1->next;for<p=head1;p!=NULL;p=p->next>//冒泡排序for<q=p->next;q!=NULL;q=q->next>if<<p->data>.exp<<q->data>.exp>{//將鏈表中的元素按照從大到小的順序排列<m->data>.coef=<p->data>.coef;<m->data>.exp=<p->data>.exp;<p->data>.coef=<q->data>.coef;<p->data>.exp=<q->data>.exp;<q->data>.coef=<m->data>.coef;<q->data>.exp=<m->data>.exp;}head1=p1;}/*將兩個一元多項式相加*/voidPolyAdd<Link&pc,Linkpa,Linkpb>{Linkp1,p2,p,pd;CopyLink<p1,pa>;CopyLink<p2,pb>;pc=newLNode;pc->next=NULL;p=pc;p1=p1->next;p2=p2->next;while<p1!=NULL&&p2!=NULL>{if<p1->data.exp<p2->data.exp>{p->next=p1;p=p->next;p1=p1->next;}elseif<p1->data.exp>p2->data.exp>{p->next=p2;p=p->next;p2=p2->next;}else{p1->data.coef=p1->data.coef+p2->data.coef;if<p1->data.coef!=0>{p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else{pd=p1;p1=p1->next;p2=p2->next;deletepd;}}}if<p1!=NULL>{p->next=p1;}if<p2!=NULL>{p->next=p2;}paixu<pc>;}/*將兩個多項式相減*/voidPolySubstract<Link&pc,Linkpa,Linkpb>{Linkp,pt;CopyLink<pt,pb>;p=pt;while<p!=NULL>{<p->data>.coef=<-<p->data>.coef>;p=p->next;}PolyAdd<pc,pa,pt>;DestroyLink<pt>;}//清屏函數(shù)voidClear<>{system<"pause">;system<"cls">;}//菜單函數(shù)voidMenu<>{cout<<"\t*\t\t*"<<endl;cout<<endl;cout<<"\t*******************一元多項式的簡單運算*********************"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t*\t\t1創(chuàng)建要運算的兩個一元多項式\t\t*"<<endl;cout<<"\t*\t\t2將兩個一元多項式相加\t\t\t*"<<endl;cout<<"\t*\t\t3將兩個一元多項式相減\t\t\t*"<<endl;cout<<"\t*\t\t4顯示兩個一元多項式\t\t\t*"<<endl;cout<<"\t*\t\t5銷毀所創(chuàng)建的二個多項式\t\t*"<<endl;cout<<"\t*\t\t6退出\t\t\t\t\t*"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t*******************一元多項式的簡單運算*********************"<<endl;cout<<endl;cout<<"\t*\t\t請輸入你要進行的操作〔1-6\t\t*"<<endl;}//判斷輸入的整數(shù)是不是為1到6的數(shù)字intCompareIfNum<inti>{if<i>0&&i<8>return0;elsereturn1;}voidmain<>{intn;LinkL,La=NULL,Lb=NULL;//La,Lb分別為創(chuàng)建的兩個多項式intchoose;while<1>{Menu<>;//調(diào)用菜單函數(shù)cin>>choose;switch<choose>{case1:cout<<"請輸入你要運算的第一個一元多項式的項數(shù):"<<endl;cin>>n;if<CompareIfNum<n>==1>{cout<<"您的輸入有誤.請重新輸入……"<<endl;Clear<>;break;}CreateLink<La,n>;cout<<"請輸入你要運算的第二個一元多項式的項