数据结构课程报告

数据结构课程报告姓名周涛学号201313040322#includeiostream#include stdlib.h#include math.husing namespacestd;typedef struct Polynomialint coe;int exp;structPolynomial*next;}*Polyn,Polynomial;〃在多项式信息输入时按照指数降序排列建立链表，实现同类项时合并void lnsertPolyn p,Polyn hifp-coe==0delete p;else{Polyn ql,q2;ql=h;q2=h-next;whileq2p-expq2-expql=q2;q2=q2-next;ifq2p-exp==q2-expq2-coe+=p-coe;delete p;if!q2-coe ql-next=q2-next;delete q2;elsep-next=q2;ql-next=p;链表头结点的创建Polyn CreatePolynPolyn headjnt m//int i;Polyn p;p=head=new Polynomial;head-next=NULL;fori=0;im;i++{p=new Polynomial;;请输入第,,项的系数:；cout”cin»p-coe;指数:；cout«cin»p-exp;lnsertp,head;return head;链表的销毁void DestroyPolynPolyn p//Polyn t;whilep!=NULL t=P；p=p-next;delete t;链表数据的多项式输出void PrintPolynPolynP//Polyn q=P-next;int flag=l;if⑹cout«0;cout«endl;return;while qifq-coe0flag!=l cout«+;ifq-coe!=lq-coe!=-l cout«q-coe;ifq-exp==l cout«Xn;else ifq-exp cout«XA«q-exp;elseifq-coe==lif!q-exp cout«l;else ifq-exp==l cout«X；else cout«nXA，,«q-exp;ifq-coe==-l if!q-exp cout«-l;else ifq-exp==l cout«-X;else cout«H-XA«q-exp;q=q-next;flag++;cout«endl;〃两个多项式的指数，项数进行比较int comparePolyna,Polyn bifabif!b||a-expb-exp return1;else if!a||a-expb-exp return-1;else return0;else if!ab return-1;else return1;〃两个多项式的加法Polyn AddPolynPolyn pa,Polyn pbPolyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=new Polynomial;hc-next=NULL;headc=hc;whileqa||qbqc=new Polynomial;switchcompareqa,qbcase1:qc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;case0:qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;case-1:qc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break;ifqc-coe!=0qc-next=hc-next;hc-next=qc;hc=qc;else delete qc;return headc;〃两个多项式的减法Polyn SubtractPolynPolyn pa,Polyn pbPolyn h=pb;Polynp=pb-next;Polyn pd;whilepp-coe*=-l;p=p-next;pd=AddPolynpa,h;forp=h-next;p;p=p-next p-coe*=-l;return pd;void desktopsystemCcls;cout«COUt**********************************************611611,cout«**

1.输出多项式a和b**«endl;cout«**

2.建立多项式a+b**«endl;cout«**

3.建立多项式a-b**«endl;cout«H**

4.返回重新输入参数**«endl;cout**********************************************”endl，执行操作:,；coutint mainintm,n;float x,result;char key;Polynpa,pb,pc,pd,pf;rl:“欢迎cout”endl;请输入多项式的项数:;cout Acin»m;pa=CreatePolynpa,m;cout«endl;请输入多项式的项数:;cout”Bcin»n;pb=CreatePolynpb,n;systemCpause;systemcls;whilekeydesktop;cin»key;switch keycasel:cout”多项式a”；PrintPolynpa;cout”多项式bPrintPolynpb;break;case2:pc=AddPolynpa,pb;cout”多项式aPrintPolynpa;cout多项式bPrintPolynpb;cout多项式a+bPrintPolynpc;DestroyPolynpc;break;case3:pd=SubtractPolynpa,pb;cout多项式aPrintPolynpa;cout多项式bPrintPolynpb;cout多项式a-bPrintPolynpd;DestroyPolynpd;break;case4:DestroyPolynpa;DestroyPolynpb;systemcls;goto rl;break;default:cout«Error!!!H«endl;cout«endl«endl;systempause;问题描述与功能设计本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减的运算数据结构与算法多项式的逻辑结构视为线性表px=3xl4-8x8+6x2+2数据元素coef,exp表示多项式项coef-Xexp,coef是该项的系数，exp是变元X的指数coe exp*next算法多项式的输入与建立调用函数建立链表，将多项式每一项的系数与指数作为链表一个结点的数据，按照指示CreatePolyn输入每一项的系数与指数时，将调用函数，将输入的结点信息按指数降序排列的方式插入到之前Insert建立的链表中，并合并同类项依次输入、建立一元多项式和如下图pa pb空多项式刊十卜|斗川行精+爱px=3/-8+2I3|14|8|86|2|4|2|0|b非空多项式带表头结点的单循环链表表示多项式多项式的输出调用PrintPolyn函数将多项式链表中的结点数据按照一元多项式的格式如6xA5+3xA3+7x+3输出到屏幕上两个多项式的加法调用函数直接对两个多项式的链表的结点成员的系数与指数按照数学中多项式相加的原则进AddPolyn行操作其中要调用函数对两个多项式的指数或是项数进行比较相加所得的多项式存放到新compare建的第三个多项式中再对第三个多项式输出即可「式斗±]o4d|-1|+0112|10I48I I0I与•卜0*4^*4^13|14|8|8|6|2I21climID3x14+2X10-4Ks+2一乂5-8一a元3整•系数8多3+项6式相ilb2x10+4x8-6xz两个多项式的减法调用函数对两个多项式减法运算首先对要减的多项式的系数求反，接着调用SubtractPolynAddPolyn函数对处理后的多项式相加即两个多项式的相减所得的多项式存放到新建的第三个多项式中，再对第三个多项式输出即可函数定义为了程序功能的顺利实现，在本程序中定义了如下函数:函数名功能Insert CreatePolyn链表结点数据的插入与排序DestroyPolyn链表头结点的创建PrintPolyn链表的销毁Compare链表数据的多项式形象化输出AddPolyn两个多项式的指数或是项数进行比较SubtractPolyn两个多项式的加法desktop两个多项式的减法程序界面的实现编码链表建立的函数,该函数在多项式信息输入时按照指数降序排列建立链表，并在出现同类项时合并void lnsertPolynp,Polynh〃当前结点的成员等于的时候删除当前结点ifp-coe==0delete p;coe0else{Polyn ql,q2;ql=h;q2=h-next;〃查找插入位置whileq2p-expq2-expql=q2;q2=q2-next;〃将指数相同相合并ifq2p-exp==q2-expq2-coe+=p-coe;delete p;if!q2-coeql-next=q2-next;deleteq2;〃指数为新时将结点插入elsep-next=q2;ql-next=p;链表信息按照多项式形式输出void PnntPolynPolynP{Polynq=P-next;〃项数计数器int flag=l;if!q{〃若多项式为空，输出0cout«0;cout«endl;return;}while q〃系数大于且不是第一项时就输出+〃ifq-coe0flag!=l cout+;0ifq-coe!=lq-coe!=-l系数非或的普通情况1-1cout«q-coe;ifq-exp==l cout”X;〃当前结点exp为1时else ifq-exp cout«XA«q-exp;else系数为的特殊情况ifq-coe==l1〃指数不存在if!q-exp cout«”l”;else ifq-exp==l cout“X;/指数等于一else cout«XA«q-exp;}系数为的特殊情况情况ifq-coe==-l-1〃指数不存在if!q-expelse ifq-exp==l cout・X”;〃指数等于一else cout«-XA«q-exp;〃当前指针指向下一结点q=q-next;〃项序数自力口flag++;1}cout«endl;两个多项式的加法〃对两个多项式的系数或项数进行比较int comparePolyna,Polyn b{〃两个多项式都存在ifab当多项式不存在或者多项式的指数大于的的时候，返回if!b||a-expb-exp return1;b a b1当多项式不存在或者多项式的指数大于的的时候，返回else if!a||a-expb-exp return-1;a ba-1〃其他情况返回else return0;0多项式已空,但多项式非空else if!ab return-1;//a b多项式已空,但多项式非空else return1;//b aPolynAddPolynPolyn pa,Polyn pbPolyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;〃建立一个新的结点hc=new Polynomial;hc-next=NULL;headc=hc;whileqa||qb{新建——个结点qc=new Polynomial;//{〃调用函数对两个多项式进行比较多项式的指数大于switchcompareqa,qb comparecase1://a的bqc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;〃有同类项则合并case0:qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;多项式的指数小于的case-1:a bqc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break;{〃当相加系数不为时ifqc-coe!=00qc-next=hc-next;hc-next=qc;hc=qc;〃当相加系数为时,释放该结点else deleteqc;0return headc;两个多项式的减法两个多项式的减法是建立在加法的的基础上，对要减的多项式的系数求反，接着调用函数对处理后的多项式相加即两个多项式的相减AddPolyn PolynSubtractPolynPolynpa,Polyn pbPolynh=pb;〃新建一个结点作为的后继结点Polynp=pb-next;pbPolyn pd;〃当结点存在时，对所有数据求反whilep coep-coe*=-l;p=p-next;二〃调用加法函数pd AddPolynpa,h;〃恢复的系数forp=h-next;p;p=p-next pbp-coe*=-l;return pd;测试及结果测试的数据•C:\Users\LCD\Desktop\Debug\l iechechepiao.exe需迎翦央青青4块输请的项工IE项1请输入第项的某款=请输24入第项的茎数:指数3-6:

2.%-A8=4B:r02269-13^:!=!SSBB⑴A+B A=3xl4-8x8+6x2+2B=2X10+4X8+-6X2*C:\Users\LCD\Desktop\Debug\liechechepiao.exe,1一元多项式的计算.地串多项式和1a bMM■MM

2.建立多项式a+b**.建立多项式3a-b版行摄作2多项4a3X^14-8X^9+6X^2*2多工页式人人人b2X10・4X8-6X2方项式a+b3X^14+2X^10-8X^9+4X^8+2⑵A-B A=11X14+3X10+2X8+10X6+5B=2X14+3X8+5X6+7•C:\User5\LCD\Desktop\Debug\liechechBpidoexe一元多项式的计算嘴出多项式和**1ab**•建立多项式**2a*b**.建立多项式**3a-b**执行操作3多项ga3X^14-8X^9+6X^2+2项式人人2b2XT0-4X8-6X2项式人人人人2a-b3X14-2X10-8X9-4X8+12X^2+2请按任意键继续...田聿心毛通过这个一元多项市的设计，熟悉了数据结构中数据之间的存储，自己的程序还有一些一些数据的限制还不够完善，对于乘法的设计也没有bug,完成，，，在程序做完一组数据后，若要重新输入多项市的参数，只能退出后在进入，返回没有实现，本来想有一个的，没搞好got返回搞好了，但是测试图没有重新弄还有就是数据测试的事例还太少，一些边际的数据还没测试下次努力更好附录源代码。