数据结构链表应用技术一元多项式运算

1、数据结构链表应用一元多项式运算院系：信息工程学院组号：2组员：田志泽、孙伟伟、程蜜蜜张剑、贾明、王忠愿班级：10计科3班B组日期：20120322计算机科学与技术一元多项式运算功能具体实现部分#include应用数据结构SimpleLinkList.h需将线性链表SimpleLinkList包含在内structPolyDatadoublecoef;intexpn;PolyData()coef=0;expn=0;PolyData(doublec,inte)coef=c;expn=e;/一元多项式的数据部分结构定义/系数/指数classPolynomialprotected:SimpleLinkL

2、istPoly;定义一元多项式类将一元多项式定义为线性链表结构public:Polynomial();voidvoidvoidvoidvoidvoidvoidADD(Polynomial&p.Polynomial&q);SUB(Polynomial&p.Polynomial&q);MUL(Polynomial&p,Polynomial&q);operator=(Polynomial&cp)Poly=cp.Poly;Sort();Unit();Show();实现一元多项式的加法运算实现一元多项式的减法运算实现一元多项式的乘法运算实现一元多项式的复制运算将一元多项式按指数由小到大排列friendv

3、oidCinhelp();/以Sort()为基础合并多项式中指数相同的项并清除系数为0的项实现多项式的输出显示辅助输入;将当前多项式的链表请空将得链表直接添加到当前链表中对当前链表进行并项去零操作将当前多项式的链表请空将得链表直接添加到当前链表中对当前链表进行并项去零操作voidPolynomial:ADD(Polynomial&p,Polynomial&q)Poly.Clear();Poly.ADD(p.Poly,q.Poly);Sort();voidPolynomial:SUB(Polynomial&p.Polynomial&q)PolyDatae;Polynomialtmp;while(

4、tmp.Poly.length()q.Poly.length()q.Poly.GetElem(tmp.Poly.length()+1,e);e.coef=-e.coef;tmp.Poly.SetElem(e);ADD(p,tmp);依次取岀q中的每一个元素对取得的元素取相反数依次写入到tmp中，完成后得-q调用ADD实现p-q功能voidPolynomial:MUL(Polynomial&p.Polynomial&q)Poly.Clear();inti=1,j;PolyDatae,ei,ej;while(i=p.Poly.length()p.Poly.GetElem(i,ei);j=1;i+;

5、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+;voidPolynomial:Sort()inti=1,j;PolyDataei,ej;while(i=Poly.length()-1)Poly.GetElem(i,ei);j=i+1;while(jej.expn)将当前多项式的链表请空取岀p中的每一个元素取岀q中的每一个元素产生的新项的系数为pq两项系数相乘产生的新项的指数为pq两项指数相加将产生的新项存入当前多项式的链表中将

6、当前多项式的链表请空取岀p中的每一个元素取岀q中的每一个元素产生的新项的系数为pq两项系数相乘产生的新项的指数为pq两项指数相加将产生的新项存入当前多项式的链表中取出当前多项式链表中的每一个元素/与当前元素之后的每一个元素今次那个比较若当前元素的指数大于其后的某一个元素时/交换两个元素Poly.ReSetElem(i,ej);Poly.ReSetElem(j,ei);ei=ej;/对应的两项交换后，将i项当前值更新j+;i+;voidPolynomial:Unit()inti=1;/获取第一项的数据部分PolyDataei,ej;Poly.GetElem(i,ei);while(i=Poly.

7、length()-1)Poly.GetElem(i+1,ej);if(ei.coef=0)Poly.DelElem(i);ei=ej;/获取后一项的数据部分当第i个元素的系数为0时将该项清除当第i+1个元素的系数为0时将该项清除/判断相邻两项的指数部分是否相同两部分系数之和为0,则将这两项删除elseif(ej.coef=0)Poly.DelElem(i+1);elseif(ei.expn=ej.expn)if(ei.coef+ej.coef=0)Poly.DelElem(i+1);Poly.DelElem(i);Poly.GetElem(i,ei);else/系数之和不是ei.coef+=e

8、j.coef;Poly.ReSetElem(i,ei);Poly.DelElem(i+1);elsei+;ei=ej;/两个元素都删除后对ei赋新值0,两项合并到i将第i+1项删除将指数相同的两项合并到第i项中重置第i项删除第i+1项/当指数不相同时转至下一个元素/比较下一项为ei依次装入后继元素voidPolynomial:Show()inti=1;PolyDataelem;Poly.GetElem(i,elem);if(elem.coef=0);elseif(elem.expn=0)while(i0)coutelem.coef;elsecout-0)if(elem.coef!=1)cout

9、elem.coef;couta;elsecout-;if(elem.coef!=-1)cout-elem.coef;cout0)if(elem.coef=1)coutaA;elsecoutvelem.coefvvavvA;if(elem.expnO)coutv(velem.expn);当指数小于0时加一个括号elsecoutelem.expn;else系数小于0且指数不为0时if(elem.coef=-1)cout-aA;elsecout-elem.coefaA；if(elem.expn0)coutv(velem.expn);elsecoutelem.expn;if(i+10)cout+;i+

10、;当后一个元素的系数为正数时输岀一个+号coutendl;voidCinhelp()PolynomialA,B,C;intchoice=1,pos;doubleelemd;intelemi;while(choice)coutendl请选择一元多项式相关操作:endlendl1.输入两个一元多项式2两多项式相加3两多项式相减4两多项式相乘endlendlchoice;switch(choice)case1:coutendl当前第一个多项式中有A.Poly.length()pos;choice=A.Poly.length();coutendl请依次输入多项式的vvposvv个项，系数和指数交替输入

11、空格间隔Enter确认:elemdelemi;PolyDataelem(elemd,elemi);Poly.SetElem(elem);coutendl第一个多项式为：endl;Show();coutendl当前第二个多项式中有B.Poly.length()pos;choice=B.Poly.length();coutendl请依次输入多项式的vvposvv个项，系数和指数交替输入空格间隔Enter确认:endl;while(B.Poly.length()elemdelemi;PolyDataelem(elemd,elemi);Poly.SetElem(elem);coutendlvv第二个多

12、项式为：endl;Show();break;case2:case2:Sort();A.Unit();coutendl第一个多项式规格化后为：endl;A.Show();Sort();B.Unit();coutendl第二个多项式规格化后为：endl;B.Show();coutendl两多项式相加endl;ADD(A,B);cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()当有项消去时输岀该部分cout=;C.Show();coutendl当前多项式中有C.Poly.length()个元

13、素项;coutendl;break;case3:case3:Sort();A.Unit();coutendl第一个多项式规格化后为：endl;Show();Sort();B.Unit();coutendl第二个多项式规格化后为：endl;Show();coutendl多项式一减多项式二endl;SUB(A,B);cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()当有项消去时输岀该部分cout=;C.Show();coutendl当前多项式中有C.Poly.length()个元素项;co

14、utendl;case4:break;Sort();A.Unit();coutendl第一个多项式规格化后为：endl;Show();Sort();B.Unit();coutendl第二个多项式规格化后为：endl;Show();coutendl两多项式乘endl;MUL(A,B);cout=;C.Show();coutendl;Sort();cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()/当有项消去时输岀该部分coutvv=;C.ShowO;coutendlvv当前多项式中有C.

15、Poly.length()个元素项;coutendl;break;coutendlchoice;coutendlendlendl;voidmain()主函数调用部分Cinhelp();一元多项式运算功能输入截图：请选择一元多项式相关操作：二输入两个一元多项式2两多项式相加勺”两多项式相减4两多项式相乘请依次输入多项式的4个项，系数和指数交替输入空格间隔Entor确认：12453220第一个多项式为：十2*5笃*2*2请依次输入多项式的3个项.系数和指数交替输入空格间隔Enter确认二15315264第二个多项式为：比廿*3歌*与盘几2第一个多项式规格化后为2+4宀+4aS第二个多项式规格化后为

16、；3a+5aA2+战5一元多项式运算功能结果输出截图:旨多项式相加=2+3a+4*2+5日7+4aA5+5=2+3a+9aA2+5aA5当前多项式中有4个元素项多项式一减多项式二=2-3a+4aA2-5aA2+4a5-2-3a-a2+3aA5两多项式乘=6a+10aA2+2aA5+12aA3+20aA4+4aA7+12aA6+20a+4al0=6a*10aA2+12a3+20aA4+2aA5+12a%+4aA7+20aA?+4al0=6a*102+12a3+2Ba4+2*5+126+24aA7+4sia10当前多项式中有8个元素项/以部分为头文件SimpleLinkList.h部分，用该部分替

17、换顶部的SimpleLinkList.h可实现一元多项式功能#include/结点类模板templatevclassETstructnodeETdata;点的数据部分node*next;个节点的位置node()next=NULL;给定参数时结点的初始化node(ETdat,node*link)data=dat;next=link;数结点构造函数，构造给定数据和指针的结点;/简单线性链表类Pag52templatevclassETclassSimpleLinkListprotected:intcount;素个数，即表长node*head;置指针应用数据结构结点数据域，存储该结结点指针域，指示下一

18、无参数结点构造函数，用于未给定参用于计数表元顺序表起始位public:SimpleLinkList()count=O;head=newnode;/简单线性链表构造函数SimpleLinkList()Clear();deletehead;简单线性链表析构函数简单线性链表相关操作0有元素boolEmpty()returncount=0;/voidClear();voidShow();表是否为空表清空，置元素个数为输出现实表中现有的所node*GetPtr(intpostion);获取指向第pos个位置节点的指针数加一voidSetElem(ET&e);/向表中末位写入元素e，元素总voidReSe

19、tElem(intpos,ET&e);重置表中第pos个位置元素的数据部分为e,元素总数不变voidInsert(intpos,ET&e);素，元素总数加一向表中第pos个位置插入新的结点元voidGetElem(intpos,ET&e);从表中获取第pos元素，写入e中，由e输岀voidDelElem(intpos);删除表中第pos个位置的元素.元素减一voidoperator=(SimpleLinkList&cop);/赋值符重载函数，实现简单线性链表的复制功能voidSUB(SimpleLinkList&A,SimpleLinkList&B);/实现表相减，将仅存在于A中的元素写入当前

20、链表voidADD(SimpleLinkList&A,SimpleLinkList&B);/实现链表相加，将表A表B中的元素依次写入当前链表voidSeprate();奇偶分离函数，使得所有奇数均排列在偶数前voidSort();对链表中的元素进行排序voidReserve();对线性链表逆序voidResHelp(int&tmp);线性链表逆序辅助函数voidCinHelp();提示输入函数，用于实现键盘输入交互式操作;templatevclassETvoidSimpleLinkList:Clear()while(count)DelElem(1);当表中有元素时templatevclassE

21、TvoidSimpleLinkList:Show()intcot=count;ETtmp;node*shw=head;指向头指针的第一个后继coutendl当前表中共有count个元素,endl0)shw=shw-next;tmp=shw-data;coutvvtmpvv;输岀cot-;减一coutendl;当表中有元素时每输岀一位向后移动一位将后继的数据部分逐一计数元素总数templatevclassETnode*SimpleLinkList:GetPtr(intpostion)intpos=postion;node*ElemPtr;if(pos=0)returnhead;elseif(po

22、scount+1)coutendl操作无效！请确保输入元素位置小于count+2大于等于0next;while(pos1)ElemPtr=ElemPtr-next;pos-;/不断指向下一个结点，头指针所在位置为零returnElemPtr;templatevclassETvoidSimpleLinkList:SetElem(ET&e)node*prt=GetPtr(count);prt-next=newnode;的结点count+;在的元素，元素总数加一prt-next-data=e;获取指向最后一个结点的指针将最后一个节点的后继指向新置入表中不存将e写入后继结点的数据部分templatev

23、classETvoidSimpleLinkList:ReSetElem(intpos,ET&e)if(poscount)coutendl操作无效！请确保输入元素位置小于count+1大于0data=e;重置表中元素，元素总数不变templatevoidSimpleLinkList:lnsert(intpos,ET&e)在第pos个位置插入一个新结点if(poscount+1)coutendl操作无效！请确保输入元素位置小于count+2大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=newnode;的结点count

24、+;在的元素，元素总数加一prt-next-data=e;prt-next-next=pNext;的结点大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=newnode;的结点count+;在的元素，元素总数加一prt-next-data=e;prt-next-next=pNext;的结点获取指向第pos-1个结点的指针获取指向第pos个结点的指针将第pos-1个结点的后继指向新置入表中不存将e写入新结点的数据部分将新结点的后继指向原来第pos个位置templatevoidSimpleLinkList:GetElem

25、(intpos,ET&e)if(poscount)coutendl操作无效！请确保输入元素位置小于count+1大于0data;获取指向第pos个结点的数据部分templatevoidSimpleLinkList:DelElem(intpos)删除在第pos个位置的结点if(poscount)coutendl操作无效！请确保输入元素位置小于count+1大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=pNext-next;结点的后继deletepNext;count-;template获取指向第pos-1个结点的指

26、针获取指向第pos个结点的指针将第pos-1个结点的后继指向第pos个将第pos个结点删除表元素元素总数减一voidSimpleLinkList:operator=(SimpleLinkListvET&cop)/赋值符“=”重载Clear();/对当前链表先清空if(cop.count0)intcot=cop.count;ETelem;复制cop的头指针复制cop的头指针node*opr=cop.head;while(cot0)opr=opr-next;elem=opr-data;SetElem(elem);cot-;减一当表中还有元素时/向后继结点移动一位取出后继结点中的数据生成新结点计数元

27、素总数对当前链表先清空当表A中还有元素时从B表表头开始比对依次获取A表中元素的当表B中还有元素时将A中的每一个元素分别与B若与B中所有元素均不相同时将该元素templatevoidSimpleLinkList:SUB(SimpleLinkList&A,SimpleLinkList&B)Clear();intcountA=1,countB;ETelemA,elemB;node*posA=A.head,*posB;while(countAnext;elemA=posA-data;数据部分countA+;while(countBnext;elemB=posB-data;if(elemA=elemB)

28、break;中的每一个元素进行比较，若相同则中断本次循环countB+;if(countBB.count)SetElem(elemA);写入当前表中templatevoidSimpleLinkList:ADD(SimpleLinkList&A,SimpleLinkList&B)Clear();对当前链表先清空intcountA=1,countB=1;node*posA=A.head,*posB=B.head;while(countAnext;SetElem(posA-data);分,写入当前链表countA+;while(countBnext;SetElem(posB-data);分count

29、B+;templatevoidSimpleLinkList:Seprate()偶数前为链表中元素的总个数inti=0,jb=O,jc=0;int*B=newintcount,*C=newintcount;中的元素按奇数、偶数分别存放到数组B、C中node*pos=head;ETtmp;while(inext;tmp=pos-data;if(tmp%2=1)Bjb=tmp;jb+;elseCjc=tmp;jc+;i+;当表A中还有元素时依次获取A表中元素的数据部当表B中还有元素时依次获取B表中元素的数据部奇偶分离函数，使得所有奇数均排列在/count/将链表jb用于计数奇数的个数/jc用于计数偶数的个数当表A中还有元素时依次获取A表中元素的数据部当表B中还有元素时依次获取B表中元素的数据部奇偶分离函数，使得所有奇数均排列在/count/将链表jb用于计数奇数的个数/jc用于计数偶数的个数i=0;pos=head;while(inext;pos-data=Bi;i+;i=0;while(inext;pos-data=Ci;i+;templatevclassETvoidSimpleL