一元稀疏多項式計算器(數(shù)據(jù)結(jié)構(gòu))

./院系：計算機科學(xué)學(xué)院專業(yè)：軟件工程年級：2013級課程名稱：數(shù)據(jù)結(jié)構(gòu)姓名：韋宜〔4指導(dǎo)教師：宋2015年12月15日題目：設(shè)計一個一元稀疏多項式簡單計算器班級：軟件工程1301：韋宜學(xué)號：4完成日期：12月15日需求分析問題描述：設(shè)計一個一元多項式加法器基本要求：輸入并建立多項式；

<2>兩個多項式相加；

<3>輸出多項式：n,c1,e1,c2,e2,…cn,en,其中,n是多項式項數(shù),ci和ei分別是第i項的系數(shù)和指數(shù),序列按指數(shù)降序排列。

<4>計算多項式在x處的值；

<5>求多項式的導(dǎo)函數(shù)。軟件環(huán)境：Windows,UNIX,Linux等不同平臺下的VisualC++6.0硬件環(huán)境:512MB存,80Gb硬盤,Pentium4CPU,CRT顯示器。概要分析本程序有五個函數(shù)：PolyNode*Input<><輸入函數(shù)>；PolyNode*Deri<PolyNode*head>〔求導(dǎo)函數(shù)；PolyNode*Plus<PolyNode*A,PolyNode*B>〔求和函數(shù)；voidOutput<PolyNode*head>〔輸出函數(shù)；intmain<>〔主函數(shù)本程序可使用帶有附加頭結(jié)點的單鏈表來實現(xiàn)多項式的鏈表表示,每個鏈表結(jié)點表示多項式的一項,命名為node,它包括兩個數(shù)據(jù)成員：系數(shù)coef和指數(shù)exp,他們都是公共數(shù)據(jù)成員,*next為指針域,用鏈表來表示多項式。適用于不定的多項式,特別是對于項數(shù)再運算過程中動態(tài)增長的多項式,不存在存儲溢出的問題。其次,對于某些零系數(shù)項,在執(zhí)行加法運算后不再是零系數(shù)項,這就需要在結(jié)果多項式中增添新的項；對于某些非零系數(shù)項,在執(zhí)行加法運算后可能是零系數(shù)項,這就需要在結(jié)果多項式中刪去這些項,利用鏈表操作,可以簡單的修改結(jié)點的指針以完成這種插入和刪除運算〔不像在順序方式中那樣,可能移動大量數(shù)據(jù)項運行效率高。詳細設(shè)計〔1主函數(shù)：intmain<>{ PolyNode*head_a,*head_b; intchoice; head_a=newPolyNode;head_a->next=NULL; do { system<"cls">;//清屏函數(shù) Output<head_a>; cout<<"______________________________\n"; cout<<"|1.輸入公式|\n"; cout<<"|2.求導(dǎo)|\n"; cout<<"|3.兩式求和|\n"; cout<<"|4.退出程序|\n"; cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"; cin>>choice; if<choice==1>head_a=Input<>; elseif<choice==2>head_a=Deri<head_a>;//求導(dǎo) elseif<choice==3>{head_b=Input<>;head_a=Plus<head_a,head_b>;}//求和 elseif<choice==4>break; elsecout<<"輸入錯誤,重新輸入：\n"; } while<choice!=5>; return0;〔2由于此程序是二人合作完成,我在此程序中主要是完成求和和求導(dǎo)函數(shù)的設(shè)計。所以下面著重介紹下求和函數(shù)和求導(dǎo)函數(shù)。PolyNode*Deri<PolyNode*head>〔求導(dǎo)函數(shù)：流程圖如下：NNNYstart建立以head1為頭指針的空鏈表,A指向后一接點建立以head2為頭指針的空鏈表,p=head2q=B的第一個接點返回指針head1調(diào)用求和函數(shù)head1=head1+head2A指向后一接點q指向的接點與A指向的接點相乘,結(jié)果保存到head2后面,q指向后一接點A!=NULLq!=NULLYENDPolyNode*Mul<PolyNode*A,PolyNode*B>求導(dǎo)函數(shù)部分代碼：PolyNode*Deri<PolyNode*head>//求導(dǎo){ PolyNode*p=head; while<p->next!=NULL> { if<p->next->exp==0>p->next=NULL;//指數(shù)為零返回 else { p->next->coef*=p->next->exp;//系數(shù)乘以指數(shù) p->next->exp--;//指數(shù)減一 p=p->next; } }returnhead;用于對輸入的多項式進行求導(dǎo),求導(dǎo)在鏈表進行計算,即運算完成鏈表的值改變,返回頭指針。PolyNode*Plus<PolyNode*A,PolyNode*B>〔求和函數(shù)：流程圖如下：startstartNYNYNYYNNYNYNY建立鏈表head,p=head,兩頭指針A、B均指向各自的nextA、B為空A的指數(shù)大于B的指數(shù)A、B的系數(shù)互為倒數(shù)AB指數(shù)相等B為空A為空p->next=NULL將A的當(dāng)前接點接到新鏈表后面,A后指A、B均后指將B接到p后面合并相同系數(shù)相同項,連接到新鏈表后面將A接到p后面將B的當(dāng)前接點接到新鏈表后面,B后指如果AB都為空返回頭指針ENDPolyNode*Plus<PolyNode*A,PolyNode*B>本函數(shù)用于對多項式進行加法計算,需要運用存有兩個多項式的頭指針,前一頭指針可是前一計算的計算結(jié)果,也可是調(diào)用輸入函數(shù),后一頭指針是調(diào)用輸入函數(shù)輸入的多項式的頭接點。經(jīng)過計算得到一個新的鏈表,函數(shù)返回鏈表的頭指針。求和函數(shù)部分代碼PolyNode*Plus<PolyNode*A,PolyNode*B>//相加{ PolyNode*head,*p; head=newPolyNode; p=head; A=A->next; B=B->next;while<A!=NULL||B!=NULL> { if<A==NULL>{p->next=B;break;}//如果A空,把B后面的所有接點接到p之后 if<B==NULL>{p->next=A;break;}//如果B空,把A后面的所有接點接到p之后if<A->exp==B->exp>//如果兩指數(shù)數(shù)相等,相加 { if<A->coef+B->coef!=0> {p->next=newPolyNode; p=p->next; p->exp=A->exp; p->coef=A->coef+B->coef; } A=A->next; B=B->next;continue;//如果兩系數(shù)互為倒數(shù),不保存,后指,繼續(xù)循環(huán) } if<A->exp>B->exp>//A的指數(shù)大于B的指數(shù) { p->next=newPolyNode; p=p->next; p->exp=A->exp; p->coef=A->coef; A=A->next;continue;//將A的當(dāng)前接點接到新鏈表后面,A后指 } p->next=newPolyNode; p=p->next; p->exp=B->exp; p->coef=B->coef; B=B->next;//將B的當(dāng)前接點接到新鏈表后面,B后指 } if<A==NULL&&B==NULL>//如果AB都為空 p->next=NULL; returnhead;//返回頭指針}〔3其他函數(shù)〔同組的成員設(shè)計#include<iostream>#include<process.h>usingnamespacestd;typedefstructnode{floatcoef;//系數(shù)intexp;//指數(shù)structnode*next;//指針域指向下一個系數(shù)不為0的子項}PolyNode;PolyNode*Input<>//輸入函數(shù){ floatc;//系數(shù)域 inte;//指數(shù)域 PolyNode*p,*q,*r,*head; cout<<"請輸入多項式:\n"; cout<<"形式：系數(shù)1指數(shù)1系數(shù)2指數(shù)2系數(shù)3指數(shù)300：\n"; head=newPolyNode;//建立頭接點 p=head;p->next=NULL; for<;;> { cin>>c>>e; if<c==0&&e==0>break;//結(jié)束輸入 if<c==0>continue;//從新輸入,不保存 if<head->next==NULL>//輸入第一個接點 { p->next=newPolyNode; p=p->next; p->coef=c,p->exp=e; p->next=NULL; continue; } p=head; while<p->next!=NULL&&e<=p->next->exp>p=p->next; //如果輸入的指數(shù)小于p的下一個接點,p向后指 if<e==p->exp>{p->coef+=c;continue;} //如果相等,直接加上去,繼續(xù)循環(huán) q=newPolyNode; q->coef=c,q->exp=e; if<p->next!=NULL&&e>p->next->exp> //如果p的后繼接點的指數(shù)小于輸入的指數(shù),插入到p的當(dāng)前接點之后 { r=p->next; p->next=q; q->next=r; continue; } p->next=q; //如果輸入的值小于所有接點,接在最后一個接點之后 p=p->next;p->next=NULL; } returnhead;}輸出函數(shù)voidOutput<PolyNode*head>//輸出{ PolyNode*p; p=head->next; if<p==NULL>{cout<<"當(dāng)前沒有公式或計算結(jié)果為0,請選1輸入?。?！\n";return;} if<p!=NULL> { cout<<"計算結(jié)果：\n"; cout<<p->coef<<"X~"<<p->exp;p=p->next; } while<p!=NULL> { cout<<"+"<<p->coef<<"X~"<<p->exp; p=p->next; } cout<<endl; cout<<"如果想重新輸入公式,請選1輸入?。?！\n\n";}調(diào)試分析與操作說明〔1當(dāng)程序運行時,進入主界面。如圖：此時輸入1-4選擇操作〔2輸入1后按回車出現(xiàn)：輸入12345600后按回車之后會出現(xiàn)界面：〔3求導(dǎo)：輸入2求導(dǎo)后按回車會出現(xiàn)結(jié)果：結(jié)果正確?！?求和：如果進入圖4.3后輸入3后按回車會出現(xiàn)界面：圖4.5求和界面輸入22446600后結(jié)果會出來：