一元稀疏多项式计算器

实 习 报 告题目：编制一个一元稀疏多项式基本运算的程序班级：计算机02（8） 姓名：陈 堪 学号：04 完成日期：2004.7.6一、需求分析1 在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。由稀疏多项式的特点，故采用链式存储结构，可以不会带来浪费存储空间。2 程序中单链表存储，根据链表的指数域，对链表进行升序排序，可给运算带来方便。3 输出形式为类数学表达式，例如多项式: 2x+5x8-3.1x11; 指数升序排列。4 测试数据(附后) 。 5 程序设计是在VC6.0环境下设计的的。6 程序执行的命令为：1)一多项式求值; 2)一元多项式加法; 3)一元多项式减法;4)一元多项式乘法; 5) 一元多项式求导; 6)退出二、概要设计1. 抽象数据类型一元多项式的定义如下：ADT Polynpial 数据对象：D=ai|aiTermSet,i=1,2,n,n0数据关系：R1=|ai-1D,i=2,n基本操作：InitPolyn( polynomail &P) 操作结果：构造一个多项式,创建头结点.MakeNode( polynomail &pp,float Ncoef,int Nexpn) 初始条件：一元多项式P已存在.操作结果：创建一个结点.CreatPolyn( polynomail &P,int m)初始条件：一元多项式P已存在操作结果：输入m项的系数和指数，建立表示一元多项式的有序链表P ClearPolyn( polynomail &P)初始条件：一元多项式P已存在操作结果：将单链表清空，并释放原链表的结点空间 DestroyPolyn( polynomail &P)初始条件：一元多项式P已存在.操作结果：销毁一元多项式P PrintPolyn( polynomail P)初始条件：一元多项式P已存在.操作结果：打印输出一元多项式P PolynLength( polynomail P)初始条件：一元多项式P已存在.操作结果：返回一元多项式P中的项数 MergePolynCoef(polynomail &Pn)初始条件：一元多项式Pn已存在.操作结果：在序链表中,合并同类项 SortPolyn(polynomail &Pn)初始条件：一元多项式Pn已存在.操作结果：根据链表的expn指数域，对链表进行升序排序 DelZeroNode(polynomail &Pn)初始条件：一元多项式Pn已存在.操作结果：释放无用结点,即系数为0项 AddPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)初始条件：一元多项式Pa,Pb和Pc已存在.操作结果：完成多项式相加运算，即：Pc=Pa+Pb SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)初始条件：一元多项式Pa,Pb和Pc已存在.操作结果：完成多项式相减运算，即：Pc=Pa-Pb MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)初始条件：一元多项式Pa,Pb和Pc已存在.操作结果：完成多项式相乘运算，即：Pc=PaPb void Difference( polynomail &pa)初始条件：一元多项式pa已存在.操作结果：求多项式的导函数 Evaluate(polynomail pn, float x)初始条件：一元多项式pn已存在.操作结果：求多项式的值ADT Polynpial2. 主程序：void main( )初始化；do 接受命令；选择处理命令； while(命令！=“退出”)3.本程序只有两三个模块,调用关系简单.主程序模块 多项式模块三、详细设计1. 元素类型、结点类型和指针类型 typedef int status;typedef struct NodeType float coef; /系数 int expn; /指数 struct NodeType *next; NodeType, *LinkType; /结点类型，指针类型 typedef LinkType polynomail; /用带头结点的有序链表表示多项式 2基本操作的函数 有序链表的基本操作设置如下：void InitPolyn( polynomail &P); /构造一个多项式status MakeNode( polynomail &pp,float Ncoef,int Nexpn); /创建一个结点void CreatPolyn( polynomail &P,int m); /输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid ClearPolyn( polynomail &P); /将单链表清空，并释放原链表的结点空间void DestroyPolyn( polynomail &P); /销毁一元多项式Pvoid PrintPolyn( polynomail P); /打印输出一元多项式Pint PolynLength( polynomail P); /返回一元多项式P中的项数void MergePolynCoef(polynomail &Pn); /在序链表中,合并同类项void SortPolyn(polynomail &Pn); /根据链表的expn指数域，对链表进行升序排序void DelZeroNode(polynomail &Pn); /释放无用结点,即系数为0项void AddPolyn( polynomail Pa,polynomail Pb,polynomail &Pc); /完成多项式相加运算，即：Pc=Pa+Pbvoid SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc); /完成多项式相减运算，即：Pc=Pa-Pbvoid MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc); /完成多项式相乘运算，即：Pc=PaPbvoid Difference( polynomail &pa); /求多项式的导函数float Evaluate(polynomail pn, float x); /求多项式的值其中部分操作的算法如下void InitPolyn( polynomail &P)/构造一个多项式 P=(NodeType *)malloc(sizeof(NodeType); P-coef=0;P-expn=0;P-next=NULL; /初始化带头结点的单链表 / InitPolynvoid ClearPolyn( polynomail &P)/将单链表清空，并释放原链表的结点空间 LinkType q; q=P-next; while(q!=NULL) /释放原链表的结点空间 P-next=q-next;free(q);q=P-next;/ ClearPolynvoid DestroyPolyn( polynomail &P) /销毁一元多项式PLinkType q=P; while(q!=NULL) q=P-next;free(P);/释放所有结点空间/ DestroyPolynvoid SortPolyn(polynomail &Pn)/根据链表的expn指数域，对链表进行升序排序 MergePolynCoef(Pn);/先合并同类项 LinkType p,q,r; q=Pn-next;Pn-next=NULL; while(q!=NULL) /插入法排序 p=Pn; while(p-next!=NULL&p-next-expnexpn) p=p-next; r=q-next; q-next=p-next; p-next=q; q=r; / SortPolynvoid MergePolynCoef(polynomail &Pn)/在序链表中,合并同类项 LinkType p,p1,p2; p=Pn-next; while(p!=NULL) p1=p;p2=p-next; while(p2!=NULL) /合并指数相同项 if(p-expn=p2-expn)p-coef+=p2-coef; p1-next=p2-next; free(p2); p2=p1-next; else p1=p2;p2=p1-next; p=p-next; DelZeroNode(Pn);/删除合并后系数为0的结点/MergePolynstatus MakeNode( polynomail &pp,float Ncoef,int Nexpn)/创建一个结点 if (!(pp=(LinkType)malloc(sizeof(NodeType) coutError, the memory is overflow!coef=Ncoef; pp-expn=Nexpn; pp-next=NULL； return TRUE;/ MakeNodevoid CreatPolyn( polynomail &P,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表P float fcoef; int fexpn; NodeType *s,*q; q=P; /if(m=0)cout空表!; for(int i=1;i=m;i+) cout第i项式endl; coutfcoeffexpn; s=(NodeType *)malloc(sizeof(NodeType); s-coef=fcoef;s-expn=fexpn;s-next=NULL; q-next=s;q=s;q-next=NULL; MergePolynCoef(P); /合并指数相同项 DelZeroNode(P); /删除系数为0的结点 SortPolyn(P); /按指数域，对链表进行升序排序/ CreatPolynvoid Difference(polynomail &pa)/ 稀疏多项式pa 以链表作存储结构， / 将此链表修改成它的导函数，并释放无用结点 LinkType p,q; p=pa-next; q=pa; while(p!=NULL) if(p-expn=0) q-next=p-next;free(p);p=q-next; /常数项，导数为零，释放结点 else p-coef=p-coef*p-expn; /系数=原系数* 指数 (p-expn )-; q=q-next; p=p-next;/指数减1 / Differencefloat Evaluate(polynomail pn, float x)/求多项式的值 LinkType p; p=pn-next; float result=0; while(p!=NULL) result+=(p-coef)*(float)pow(x,p-expn); /pow函数求x的n次方 p=p-next;return result;/ Evaluatevoid AddPolyn(polynomail Pa,polynomail Pb,polynomail &Pc)/完成多项式相加运算，即：Pc=Pa+Pb float x; LinkType p,q,r; NodeType *s; p=Pa-next; q=Pb-next; r=Pc; while(p!=NULL&q!=NULL) if(p-expn=q-expn)/指数相同 x=p-coef+q-coef ; if(x!=0) /指数相同，若系数相加不等于0,插入表中s=(NodeType *)malloc(sizeof(NodeType); s-coef=x;s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; p=p-next;q=q-next; else if(q-expnexpn) /指数小的插入表中 s=(NodeType *)malloc(sizeof(NodeType);s-coef=q-coef;s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; q=q-next; else s=(NodeType *)malloc(sizeof(NodeType); s-coef=p-coef;s-expn=p-expn;s-next=NULL; r-next=s;r=r-next; p=p-next; /加入余下的多项式 while(p!=NULL) s=(NodeType *)malloc(sizeof(NodeType);s-coef=p-coef;s-expn=p-expn;s-next=NULL; r-next=s;r=r-next; p=p-next; while(q!=NULL) s=(NodeType *)malloc(sizeof(NodeType); s-coef=q-coef;s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; q=q-next;/ AddPolyvoid SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc) /完成多项式相减运算，即：Pc=Pa-Pb float x; LinkType p,q,r; NodeType *s; p=Pa-next; q=Pb-next; r=Pc; while(p!=NULL&q!=NULL) if(p-expn=q-expn)/指数相同 x=p-coef-q-coef; if(x!=0) /指数相同，若系数相减不等于0,插入表中s=(NodeType *)malloc(sizeof(NodeType); s-coef=x;s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; p=p-next;q=q-next; else if(q-expnexpn) /指数小的插入表中 s=(NodeType *)malloc(sizeof(NodeType); s-coef=-q-coef; /减数的系数变为相反数 s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; q=q-next; else s=(NodeType *)malloc(sizeof(NodeType);s-coef=p-coef;s-expn=p-expn;s-next=NULL; r-next=s;r=r-next; p=p-next; /加入余下的多项式，减数的系数变为相反数 while(p!=NULL) s=(NodeType *)malloc(sizeof(NodeType);s-coef=p-coef;s-expn=p-expn;s-next=NULL; r-next=s;r=r-next; p=p-next; while(q!=NULL) s=(NodeType *)malloc(sizeof(NodeType); s-coef=-q-coef;s-expn=q-expn;s-next=NULL; r-next=s;r=r-next; q=q-next;/ SubtractPolynvoid MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc) /完成多项式相乘运算，即：Pc=PaPb LinkType p,q,r; NodeType *s; p=Pa-next; r=Pc; while(p!=NULL) q=Pb-next; while(q!=NULL) s=(NodeType *)malloc(sizeof(NodeType); s-coef=p-coef*q-coef; s-expn=p-expn+q-expn; s-next=NULL； r-next=s;r=r-next; q=q-next; p=p-next; MergePolynCoef(Pc);/合并指数相同项 DelZeroNode(Pc); /删除系数为0的结点 SortPolyn(Pc); /按指数域，对链表进行升序排序/ MultiplyPolyn3.主函数void main()inp: while(1)system(cls); int choice; coutendlchoice; coutendl; switch(choice) case 1: cout求多项式A的值endl;Evaluate(pa, x); case 2: cout多项式加法C=A+Bendl; AddPolyn(pa,pb,pc); case 3: cout多项式减法C=A-Bendl;SubtractPolyn(pa,pb,pc); case 4: cout多项式乘法C=ABendl; MultiplyPolyn(pa,pb,pc); case 5: cout求多项式A的导数endl; Difference(pa); case 0:cout谢谢使用!再见!endlendl; return ; default:cout错误命令!endl; coutPress any key to continue!next域搞乱,造成死循环。3创建一元多项式链表时，可能不是按照指数域的大小输入，故增加了排序，按指数域，对链表进行升序排序。4在做多项式运算时，产生了零结的和指数相同项，在写程序过程中才增加合