数据结构-链表应用-一元多项式运算.docx

浜徽新华学经数据结构链表应用一元多项式运算院系：信息工程学院组号：_2组员：田志泽、孙伟伟、程蜜蜜一张剑、贾明、王忠愿一班级：10计科3班B组一日期：20120322计算机科学与技术一元多项式运算功能具体实现局部#include<iostream.h>#include"K:应用数据结构DataStructSimpleLinkList.h"需将线性链表SimpIeLinkList包含在内structPoIyData一元多项式的数据局部结构定义(doublecoef;系数intexpn;指数PoIyDataOcoef=();expn=();PolyData(doublec,inte)coef=c;expn=e;)；classPolynomial定义一元多项式类(protected:SimpleLinkList<PolyData>Poly;将一元多项式定义为线性链表结构public:PoIynomialOEvoidADD(Polynomial&p,Polynomial&q);实现元多项式的加法运算voidSUB(Polynomial&p,Polynomial&q);实现一元多项式的减法运算voidMUL(Polynomial&p,Polynomial&q);实现,元多项式的乘法运算voidoperator=(Polynomial&cp)Poly=cp.Poly;实现一元多项式的复制运算voidSort();将一元多项式按指数由小到大排列voidUnit();以SOrto为根底合并多项式中指数相同的项并去除系数为。的项voidShow();实现多项式的输出显示friendvoidCinheIpO;辅助输入voidPolynomial:ADD(Polynomial&p,Polynomial&q)(Poly.Clear();将当前多项式的链表请空Poly.ADD(p.Poly,q.Poly);将得链表直接添加到当前链表中Sort();对当前链表进行并项去零操作voidPolynomial:SUB(Polynomial&p,Polynomial&q)PolyDatae;Polynomialtmp;依次取出q中的每一个元素whi!e(tmp.Poly.length()<q.Poly.length()q.Poly.GetElem(tmp.Poly.length()+1,e);e.coef=-e.coef;对取得的元素取相反数tmp.Poly.SetElem(e);依次写入到tmp中，完成后得-q)ADD(p,tmp);调用ADD实现p-q功能voidPolynomial:MUL(Polynomial&p,Polynomial&q)Poly.Clear();int i=l,j;PolyData e, ei, ej;while(i <= p.Poly.length()(p.Poly.GetElem(i, ei);j=l；i+；while(j <= q.Poly.length()(q.Poly.GetElem(j, ej);e.coef = ei.coef * ej.coef;e.expn = ei.expn + ej.expn;Poly.SetElem(e);j+；将当前多项式的链表请空取出p中的每一个元素取出q中的每一个元素产生的新项的系数为Pq两项系数相乘 产生的新项的指数为pq两项指数相加 将产生的新项存入当前多项式的链表中void Polynomial:Sort()(int i=l,j;PolyData ei, ej;while(i <= Poly.length()-1)(Poly.GetElem(i, ei);j= i+1；while(j <= Poly.length()取出当前多项式链表中的每一个元素与当前元素之后的每个元素今次那个比拟Poly.GetElem(j, ej);if(ei.expn >ej.expn) 假设当前元素的指数大于其后的某一个元素时交换两个元素Poly.ReSetElem(i, ej);Poly.ReSetElem(j, ei);ei = ej;对应的两项交换后，将i项当前值更新j+;i+；voidPolynomiakiUnitO(inti=l;PolyDataei,ej;Poly.GetElem(i,ei);获取第一项的数据局部while(i<=Poly.length()-1)(Poly.GetElem(i+Lej);获取后一项的数据局部if(ei.coef=0)Poly.DelElem(i);ei=ej;当第i个元素的系数为0时将该项去除elseif(ej.coef=0)Poly.DelElem(i+l);当第i+1个元素的系数为0时将该项去除else if(ei.expn = ej.expn)(if(ei.coef + ej.coef = 0)(Poly.DelElem(i+l);Poly.DelElem(i);Poly.GetElem(i, ei);)else系数之和不是0,判断相邻两项的指数局部是否相同两局部系数之和为0,那么将这两项删除两个元素都删除后对ei赋新值两项合并到i将第i+1项删除ei.coef+=ej.coef;将指数相同的两项合并到第i项中Poly.ReSetElem(i,ei);重置第i项Poly.DelElem(i+l);删除第i+1项else当指数不相同时转至下一个元素i+；ei=ej;比拟下一项为ei依次装入后继元素voidPolynomiakzShowO(inti=l;PolyDataelem;while(i<=Poly.length()(Poly.GetElem(i,elem);当元素系数为。时，跳过该元素当元素指数为。时，仅输出系数局部if(elem.coef=0);elseif(elem.expn=0)if(elem.coef>O)cout<<elem.coef;elsecout<<,'",'<<-elem.coef;)elseif(elem.expn=1)当要输出的元素指数为1时，仅输出系数局部和字符a(if(elem.coef>0)if(elem.coef!=1)cout<<elem.coef;cout<<"a"elsecout<<'*-m;if(elem.coef!=-1)cout<<-elem.coef;cout<<"a",Jelseif(elem.coef>0)系数大于0且指数不为0时(if(elem.coef=l)cout«,ra"«'，A，'当系数为1时elseCOUt<<elem.coef<<"a"<v""if(elem.expn<O)CoUt<<"("<<elem.expn<<")"当指数小于0时加一个括号elsecout<<elem.expn;)else系数小于0且指数不为0时(if(elem.coef=-l)cout<<"-"<<,a"<<",'elsecout<<"->'«-elem.coef«",a"«"An;if(elem.expn<O)CoUt<<"("v<elem.expnv<")"elsecout<<elem.expn;Iif(i+1<=Poly.length()Poly.GetElem(i+l,elem);if(elem.coef>0)cout<<"+i+；当后一个元素的系数为正数时输出一个十号)cout<<endl;)voidCinhelpOPolynomialA,B,C;intchoice=1,pos;doubleelemd;intelemi;while(choice)(CoUt<vendlv<"请选择一元多项式相关操作:"<<endl<<endl<v"l.输入两个一元多项式2.两多项式相加3.两多项式相减4.两多项式相乘"<<endlv<endlvv"选择并以Enter确认：cin>>choice;switch(choice)(case1:COUt<<endl<<"当前第一个多项式中有"<<A.PolyJength()<<"个元素项"；CoUt<vendlvv"请输入第一个多项式要添加的项数Enter确认：cin>>pos;choice=A.Poly.length();CoUt<vendlvv"请依次输入多项式的“<vpos<<"个项，系数和指数交替输入空格间隔Enter确认：,<<endl;while(A.Poly.length()<pos+choice)(cin>>elemd>>elemi;PolyDataelem(elemd,elemi);A.Poly.SetElem(elem);)ColItVVendlVV”第一个多项式为:"<<endl;A.Show();COUt<<endl<<"当前第二个多项式中有"v<B.Poly.length()<v"个元素项”；CoUt<vendlvv"请输入第二个多项式添加的的项数Enter确认：cin>>pos;choice=B.Poly.length();COUt<vendl<<"请依次输入多项式的“<<posv<"个项，系数和指数交替输入空格间隔Enter确认：o<<endl;while(B.Poly.length()<pos+choice)cin>>elemd>>elemi;PolyDataelem(elemd,elemi);B.Poly.SetElem(elem);ICOUt<vendl<v"第二个多项式为：,'<<endl;B.Show();break;case2:A.Sort();A.Unit();COUt<<endl<<"第一个多项式规格化后为："<<endl;A.Show();B.Sort();B.Unit();CoUt<vendl<<"第二个多项式规格化后为："<<endl;B.Show();CoIItVVendlVV"两多项式相加"<<endl;C.ADD(A,B);cout<<,'="C.Show();cout<<endl;choice=C.Poly.length();C.Unit();if(choice!=C.Poly.length()当有项消去时输出该局部cout<<"="C.Show();COUt<<endl<<"当前多项式中有"<<C.Poly.length()<<"个元素项”；cout<<endl;break;case3:A.Sort();A.Unit();CoIn<vendl<<"第一个多项式规格化后为："<<endl;A.Show();B.Sort();B.Unit();CoUt<<endl<v”第二个多项式规格化后为："<<endl;B.Show();CoUt<<endl<<"多项式一减多项式二"<<endl;C.SUB(A,B);cout<<"="C.Show();cout<<endl;choice=C.Poly.length();C.Uni