数据结构-链表应用-一元多项式运算.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.Unit();if(choice!=C.Poly.length()当有项消去时输出该局部cout<<,'="C.Show();cout<<endl<<"当前多项式中有"C.Poly,length()<<"个元素项"；cout<<endl;break;case4:A.Sort();A.Unit();COUt<<endlv<"第一个多项式规格化后为："<<endl;A.Show();B.Sort();B.Unit();COUt<<endl<v"第二个多项式规格化后为："<<endl;B.Show();CoUt<vendl<<"两多项式乘"<<endl;C.MUL(A,B);cout<<"="C.Show();cout<<endl;C.Sort();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;CoUt<<endl<<"O.退出1.继续选择："；cin>>choice;cout<<endl<<endl<<end1;voidmain()主函数调用局部(CinhelpO;一元多项式运算功能输入截图:请选择一元多项式相关操作：1 .输入两个一元多项式2.两多项式相加3.两多项式相减4.两多项式相乘请依次输入多项式的4个项,系数和指数交替输入空格间隔Enter确认:12453220第一个多项式为：a2+4a5+3a2÷2情依次输入多项式的3个项，系数和指数交替输入空格间隔Entex确认:15315264.二个多项式为：1.人5+3a+5a人2第一个多项式规格化后为:2 ÷4a2+4a5第二个多项式规格化后为:3a5a)2a人5一元多项式运算功能结果输出截图:两多项式相加=2÷3a+4a人2+5a2+4a5+a人5=2+3a+9a2÷5a5当前多项式中有4个元素项多项式一减多项式二=2-3a+4a人2-5a人2+4a5-a5=2-3a-a2÷3a5当前多项式中有4个元素项两多项式乘=Ga÷10a2+2a5+12a3+20a4+4a7+12a6÷20a7+4a10=6a÷10a2÷12a3+20a4+2a人5+12a6+4a7+20a?+4a人10=Ga÷10a2+12a3÷20a4+2a5+12a6+24a7+4a人10当前多项式中有8个元素项以局部为头文件SimpleLinkList.h局部，用该局部替换顶部的#include"K:应用数据结构DataStructSimpleLinkList.h"可实现一元多项式功能#include<iostream.h>结点类模板template<classET>structnode结点数据域，存储该结点的数据局部结点指针域，指示下一个节点的位置ETdata;node<ET>*next;node()next=NULL;)无参数结点构造函数，用于未给定参数时结点的初始化node(ETdat,node<ET>*link)data=dat;next=link;给定参数结点构造函数，构造给定数据和指针的结protected:int count;node<ET>* head;简单线性链表类Pag52template<classET>classSimpleLinkList用于计数表元素个数,即表长顺序表起始位置指针public:SimpleLinkListOlcount=0;head=newnode<ET>)简单线性链表构造函数-SimpleLinkListOClear();deletehead;简单线性链表析构函数简单线性链表相关操作boolEmpty()returncount=0;)表是否为空voidClear();表清空，置元素个数为0void Show();输出现实表中现有的所有元素node<ET>*GetPtr(intpostion);获取指向第pos个位置节点的指针voidSetElem(ET&e);向表中末位写入元素e,元素总数加一voidReSetElem(intpos,ET&e);重置表中第pos个位置元素的数据局部为e,元素总数不变voidInsert(intpos,ET&e);向表中第pos个位置插入新的结点元素，元素总数加一voidGetElem(intpos,ET&e);从表中获取第pos元素，写入e中，由e输出voidDelElem(intpos);删除表中第pos个位置的元素.元素减-voidOPerator=(SinlPIeLinkLiStVET>&cop);赋值符重载函数，实现简单线性链表的复制功能voidSUB(SimpIeLinkList<ET>&A,SimpleLinkList<ET>&B);实现表相减，将仅存在于A中的元素写入当前链表voidADD(SimpleLinkList<ET>&A,SimpleLinkList<ET>&B);实现链表相加，将表A表B中的元素依次写入当前链表voidSeprate();voidSort();voidReserve();voidResHeIp(int&tmp);voidCinHeIpO;；template<classET>voidSimpIeLinkList<ET>:Clear()while(count)DeIElem(I);)template<classET>voidSimpleLinkList<ET>"Show()intcot=count;ETtmp;node<ET>*shw=head;COUt<<endl<<"当前表中共有"<<couwhile(cot>0)shw=shw->next;tmp=shw->data;cout<<tmp<<"cot;奇偶别离函数，使得所有奇数均排列在偶数前对链表中的元素进行排序对线性链表逆序线性链表逆序辅助函数提示输入函数，用于实现键盘输入交互式操作当表中有元素时指向头指针的第一个后继nt<v"个元素,"<<endlvv"依次为：当表中有元素时每输出一位向后移动一位将后继的数据局部逐输出计数元素总数减一cout<<endl;template<classET>node<ET>*SimPleLinkLiStVETGetPtr(intpostion)(intpos=postion;node<ET>*ElemPtr;if(pos=0)returnhead;elseif(pos<lpos>count+1)CoUt<<endl<<"操作无效！请确保输入元素位置小于"<<count+2<<"大于等于O"<<endl;elseElemPtr=head->next;while(pos>l)EIemPtr=ElemPtr->next;pos-;不断指向下一个结点，头指针所在位置为零returnEIemPtr;template<class ET>void SirnPIeLinkLiStVETSetEIem(ET &e) node<ET>* prt = GetPtr(count);prt->next = new node<ET>count+;prt->next->data = e;获取指向最后一个结点的指针将最后一个节点的后继指向新的结点置入表中不存在的元素，元素总数加一将e写入后继结点的数据局部template<classET>voidSimpleLinkList<ET>"ReSetElem(intpos,ET&e)if(pos<1Hpos>count)CoUt<<endl<<"操作无效！请确保输入元素位置小于"<<count+1<<"大于O"<<endl;elseGetPtr(pos)->data=e;重置表中元素，元素总数不变)template<classET>voidSimpleLinkList<ET>"Insert(intpos,ET&e)在第pos个位置插入一个新结点if(pos<lHpos>count+I)CoUt<<endl<<"操作无效！请确保输入元素位置小于"<<count+2<v"大于O"<<endl;elsenode<ET>*prt=GetPtr(pos-l);node<ET>*pNext=prt->next;prt->next=newnode<ET>count+;prt->next->data=e;prt->next->next=pNext;获取指向第pos-1个结点的指针获取指向第POS个结点的指针将第POSJ个结点的后继指向新的结点置入表中不存在的元素，元素总数加一将e写入新结点的数据局部将新结点的后继指向原来第pos个位置的结点template<classET>voidSimpIeLinkList<ET>:GetEIem(intpos,ET&e)(if(pos<lHpos>count)COUt<<endl<<"操作无效！请确保输入元素位置小于,'<<count+1<<"大于O"<<endl;elsee=GetPtr(pos)->data;获取指向第pos个结点的数据局部template<classET>voidSimpIeLinkList<ET>:DelEIem(intpos)删除在第pos个位置的结点if(pos<lHpos>count)COUt<<endl<<"操作无效！请确保输入元素位置小于,'<<count+1<<"大于O"<<endl;elsenode<ET>*prt=GetPtr(pos-l);node<ET>*pNext=prt->next;prt->next=pNext->next;deletepNext;count;获取指向第pos-1个结点的指针获取指向第POS个结点的指针将第pos-1个结点的后继指向第pos个结点的后继将第POS个结点删除表元素元素总数减一template<classET>voidSimPleLinkLiStVET>:oPeratOr=(SimPIeLinkLiSt<ET>&cop)赋值符“二”重载Clear();对当前链表先清空if(cop.count>0)intcot=cop.count;ETelem;node<ET>*opr=cop.head;复制COP的头指针while(cot>0)当表中还有元素时opr=opr->next;向后继结点移动一位elem=opr->data;SetElem(eIem);cot;取出后继结点中的数据生成新结点计数元素总数减一template<classET>voidSimPleLinkLiSt<ET>:SUB(SimPIeLinkLiSt<ET>&A,SimpleLinkList<ET>&B)Clear();intcountA=l,countB;ETelemA,elemB;node<ET>*posA=A.head,*posB;whiIe(countA<=A.count)(CountB=I;posB=B.head;posA=posA->next;elemA=posA->data;countA+;vhile(countB<=B.count)(posB=posB->next;elemB=posB->data;if(elemA=elemB)break;比拟，假设相同那么中断本次循环countB+;)if(countB>B.count)SetElem(elemA);对当前链表先清空当表A中还有元素时从B表表头开始比对依次获取A表中元素的数据局部当表B中还有元素时将A中的每一个元素分别与B中的每一个元素进行假设与B中所有元素均不相同时将该元素写入当前表中template<classET>voidSimPleLinkLiStVETADD(SimPleLinkLiSt<ET>&A,SimpleLinkList<ET>&B)Clear();intcountA=1,countB=1;对当前链表先清空while(countA<=A.count)当表A中还有元素时node<ET>*posA=A.head,*posB=B.head;SetEIem(posA->data);依次获取A表中元素的数据局部,写入当前链表posA=posA->next;countA+;posB=posB->next;SetEIem(posB->data);countB+;依次获取B表中元素的数据局部template<classET>voidSimpIeLinkList<ET>"Seprate()奇偶别离函数，使得所有奇数均排列在偶数前/count为链表中元素的总个数inti=O,jb=O,jc=O;int*B=newintcount,*C=newintcount;将链表中的元素按奇数、偶数分别存放到数组B、Cnode<ET>*pos=head;ETtmp;while(i<count)(pos=pos->next;tmp=pos->data;if(tmp%2=1)Bjb=tmp;jb+;)/jb用于计数奇数的个数elseCjc=tmp;jc+;)/jc用于计数偶数的个数i+；i=0;pos=head;while(i<jb)pos=pos->next;pos->data=Bi;i+；将奇数依次存回到链表中i=0;while(i<jc)pos=pos->next;pos->data=Ci;i+；将偶数依次存回到链表中奇数之后template<classET>voidSimpleLinkList<ET>"Sort()对链表中的元素进行排序inti=l,j;node<ET>*posi=head,*posj;ETtmp;while(i<=count-1)(j=i+hposi=posi->next;posj=posi;vhile(j<=count)(posj=posj->next;if(posi->data>posj->data)交换数据元素tmp=posi->data;posi->data=posj->data;posj->data=tmp;)j+；1i+；1)template<classET>voidSimpleLinkList<ET>:Reserve()inttmp=1;化到count-1ResHelp(tmp);为逆序的递归算法提供计数变量tmp,变量从1变并对其进行调用template<classET>voidSimpleLinkList<ET>:ResHelp(int&tmp)node<ET>*pos;if(tmp<count)(pos=head->next;指向线性链表的第一个元素head->next=pos->next;头结点的后继依次向下一个元素tmp+;ResHelp(tmp);用tmp进行计数，当到达元素总数时退出递归调用对下一个结点递归调用逆序函数pos->next->next=pos;个元素从第count-1个元素开始回溯，使其后继指向第count-1template<classET>voidSimpleLinkList<ET>:CinHeIp()intchoice=1,pos;ETelem;while(choice)(COUt<<endlv<"请选择链表相关操作:"<<endl<<endl<<"l.添加新元素2.插入表元素3.删除表元素4.修改元素5.清空"<<endl<<endl<<"选择并以Entel确认："；cin>>choice;switch(choice)(case 1:COUt<<endlv<"请输入要输入的表元素个数Enter确认:"；cin>>pos;choice=count;链表中原有的元素数不应在计数范围内COUt<<endlv<"请依次输入"<<pos<<"个表元素空格间隔Enter确认："v<endl;while(count<pos÷choice)cin>>elem;SetElem(elem);)Show();break;case 2: 插入表元素CoUt<<endlv<”请依次输入表元素和位置空格间隔Enter确认:cin>>elem>>pos;Insert(pos,elem);Show();break;case 3: 删除表元素COUt<<endlv<"请输入要删除第几个元素,Enter确认："；cin>>pos;if(pos<lHpos>count)CoUt<<endlv<"操作无效！请确保输入元素位置小于"<<count+l<<"大于O"<<endl;elseGetElem(pos,elem);获取该位置的数据存入elemDelElem(pos);COUt<<endl«"第"v<pos<<"个位置的元素"<<elem<<"已成功删除"<<endl;Show();break;case 4: 修改元素CoUt<<endk<”请依次输入表元素和要修改元素位置空格间隔Enter确认:cin>>elem>>pos;ReSetElem(pos,elem);Show();break;case 5: 清空Clear();Show();break;CoUtVVendlVV"0.退出1.继续选择:cin>>choice;cout<<endl<<endl<<endl;