庞贝贝-1104040216-课设报告2-一元多项式计算.doc

试验报告二课题名称：一元多项式计算班级：信管112 姓名：庞贝贝 学号：1104040216日期：2013/7/11一、需求分析1、任务1）能够按照指数降序排列建立并输出多项式；2）能够完成两个多项式的相加、相减，并将结果输入。2、功能：1）建立多项式；2）按照指数降序排列输出多项式；3）完成多项式相加并输出；4）完成多项式相减并输出。3、程序执行的命令1）分别输入两个多项式的系数和指数2）输出多项式3）完成多项式相加并输出4）完成多项式相减并输出二、概要设计1、存储结构对应于线性表的两种存储结构，一元多项式也可以有两种存储表示方法。在实际应用程序中取用哪种，要视多项式做何种运算而定。若只对多项式“求值”而不改变多项式的系数和指数的运算，而且则采用类似于顺序表的存储结构即可，否则应采用链式存储表示，本算法采用链式存储表示。2、抽象数据类型的一元多项式定义ADT Polynomial数据对象：D=|TermSet,i=1,2,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1=|,D,且中的指数值中的指数值,i=1,2n基本操作：CreatPolyn(&p,m)操作结果：输入m项的系数和指数，建立一元多项式。DestroyPolyn(&p)初始条件：一元多项式P已经存在。操作结果：销毁一元多项式P。PrintPolyn(P)初始条件：一元多项式P已经存在。操作结果：打印输出一元多项式P。PolynLength(p)初始条件：一元多项式P已经存在。操作结果：返回一元多项式P中的项数。AddPoloy(&Pa,&Pb)初始条件：一元多项式Pa和Pb已经存在。操作结果：完成多项式相加运算，即Pa=Pa+Pb,并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已经存在。操作结果：完成多项式相减运算，即Pa=Pa-Pb,并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已经存在。操作结果：完成多项式相乘运算，即Pa=PaPb,并销毁一元多项式Pb。ADT Polynomial3、为实现程序需要使用线性表typedef struct LNode ElemType *elemInt lengthInt listsize;LNode,*linklist;A5 17 9 83 17 0 -1 4、多项式相加的基本过程的算法思路B-9 8 22 78 1 -1 如图，分别为多项式和多项式的单链表存储结构。实现两个多项式相加的算法思路如下：1、 设qa,qb分别指向两个链表的第一个元素；申请一个新的头结点C，并置头指针为空2、 比较所指元素的指数项1）若qa所指结点的指数值qb所指结点的指数值，则申请一个新结点s，放入当前qb所指结点的系数值与指数值,并将s链接到C之后, qb指针加一；3) 若qa所指结点的指数值=qb所指结点的指数值，判断qa所指结点的系数值与qb所指结点的指数值之和是否为0，若不为0，则申请一个新结点s，放入当前qa指针和qb指针所指结点的系数值之和，以及它们的指数值,并将s链接到C之后, qa指针和qb指针都加一，若为0，则qa指针和qb指针都加一；3、最后C指针所指的链表即为多项式相加后得到的和的链表表示。5、本程序分为4个模块1)主程序模块void main()While(标志1)switch(标志2)case 标志2:输入多项式;break;case 标志2:输出多项式;break;case 标志2:多项式求和并输出;break;case 标志2:多项式求差并输出;break;case 标志2：退出;break;default 输出提示语：您输入的选择序号有误;2)建立多项式，并降序输出多项式Polypn CreatPolyn()申请头结点;for()申请新结点，输入多项式的每一项，每一项包括系数值和指数值;按照指数值得大小插入到链表中return p;3）打印降序输出一元多项式Pvoid PrintPolyn(Polyn P)l=A-next;输出命令；l=l-next;4)多项式求和并输出void AddPoloy(Polyn Pa, Polyn Pb)申请头结点，头指针C指向头结点pa=A-next; pb=B-next;while(pa&pb)if(比较指数域)执行命令；5)多项式求差并输出void SubtractPolyn(Polyn Pa, Polyn Pb)申请头结点，头指针C指向头结点pa=A-next; pb=B-next;while(pa&pb)if(比较指数域)执行命令；各模块之间的关系如下主程序模块momokuai建立多项式模块多项式求和模块多项式求差模块三、详细设计#include#includetypedef struct LNodefloat coef; /每一项的系数int expn; /每一项的指数struct LNode *next;LNode,*Polyn;1、建立多项式Polyn CreatPolyn()int n,i,b;float a;Polyn p,q,s,r;p=new LNode;p-coef=NULL;p-expn=-1;p-next=NULL;cout请问需要建立的多项式一共有几项n;for(i=0;in;i+)q=p;s=new LNode;cout请输入第i+1项的系数值和指数值:ab;s-coef=a;s-expn=b;if(q-next=NULL) s-next=q-next;q-next=s;else q=p-next;r=p;while(q-next!=NULL&(q-expn)(s-expn)q=q-next;if(q-expn)(s-expn)s-next=q-next;q-next=s;if(q-expn)expn)s-next=q;r-next=s;if(q-expn=s-expn)if(q-coef+s-coef)q-coef=q-coef+s-coef;elser-next=q-next;return p;2、降序输出多项式void PrintPolyn(Polyn p)Polyn l;l=p-next;for(;l;)cout(coefxexpnnext)coutnext;coutcoef=NULL;pc-expn=-1;pc-next=NULL;r=pc;p=pa-next;q=pb-next;while(p&q)s=new LNode;if(p-expn)(q-expn) s-expn=p-expn;s-coef=p-coef;s-next=r-next;r-next=s;r=s;p=p-next;else if(p-expn)expn) s-expn=q-expn;s-coef=q-coef;s-next=r-next;r-next=s;r=s;q=q-next;else if(p-coef)+(q-coef)!=NULL)s-expn=p-expn;s-coef=(p-coef)+(q-coef);s-next=r-next;r-next=s;r=s;p=p-next;q=q-next;if(p)r-next=p;if(q)r-next=q;return pc;4、多项式求差Polyn SubtractPolyn(Polyn pa, Polyn pb)Polyn p,q,s,r,pc;float c;pc=new LNode;pc-coef=NULL;pc-expn=-1;pc-next=NULL;r=pc;p=pa-next;q=pb-next;while(p&q)s=new LNode;if(p-expn)(q-expn) s-expn=p-expn;s-coef=p-coef;s-next=r-next;r-next=s;r=s;p=p-next;else if(p-expn)expn) s-expn=q-expn;s-coef=q-coef;s-next=r-next;r-next=s;r=s;q=q-next;else c=(p-coef)-(q-coef);if(c)s-expn=p-expn;s-coef=c;s-next=r-next;r-next=s;r=s;p=p-next;q=q-next;if(p)r-next=p;if(q)r-next=q;return pc;5、主函数void main()int flag=1,a;Polyn pa,pb,pc,pd;while(flag)cout请选择要执行的任务:endl;cout1.输入一个一元多项式pa; 2.输入一个一元多项式pb;endl;cout3.打印输出一元多项式pa; 4.打印输出一元多项式pb;endl;cout5.一元多项式pa和pb求和并输出; 6.多项式pa和pb求差并输出.endl;cout7.退出a;switch(a)case 1:system(cls);pa=CreatPolyn();break;case 2:system(cls);pb=CreatPolyn();break;case 3:system(cls);coutpa=;PrintPolyn(pa);break;case 4:system(cls);coutpb=;PrintPolyn(pb);break;case 5:system(cls);pc=AddPoloy(pa,pb),PrintPolyn(pc);break;case 6:system(cls);pd=SubtractPolyn(pa,pb),PrintPolyn(pd);break;case 7:system(cls);cout谢谢使用endl;break;default:cout您输入的选择序号有误,请重新输入:;6、函数调用关系四、调试分析1、本程序采用结构体的形式定义，且采用链式存储结构，方便插入，删除，在技术上，本程序可以对多项式进行合并同类项，大大减少存储空间。2、本程序的模块的划分也十分的合理，根据题目的要求，将模块十分情绪的分成四个大的模块，由于数据对象并比较少，所以都是采用最简便最有效的方式。然后通过主函数直接调用这些函数已达到完成所需要的命令。3、算法时空分析，本算法基本上采用fo