一元稀疏多项式计算器.doc

实 习 报 告题目：编制一个一元稀疏多项式基本运算的程序班级：计算机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在做多项式运算时，产生了零结的和指数相同项，在写程序过程中才增加合并同类项函数MergePolynCoe和清零函数DelZeroNode。5整个程序运行期间实行动态存储管理，释放无用空间；特别是通过清除函数ClearPolyn和销毁函数DestroyPolyn释放无用空间。有效地防止了在程序反复运行可能出现系统空间不够分配的现象。6主要算法的时空分析: 假设一元多项式Pa和Pb长度分别为m，n。 本题中四个主要算法：SortPolyn，AddPolyn ，SubtractPolyntk和MultiplyPolyn 其中排序SortPolyn，使用插入法排序；链表Pa的时间复杂度为O(m2)；其它的均为O(mn)。7 经验体会：经过多次测试和修改，程序得到一定的完善。五、用户手册1 本程序的运行环境为DOS操作系统，执行文件为：一元稀疏多项式计算器.exe。作者班级、姓名、学号2 进入演示程序后，即显示文本方式的用户界面：测试数据功能选项3 进入界面后可按用户需要选择功能选项，直接输入0-5其中一个数字。4 注意：按提示语句输入命令六、测试结果1.测式数据 (1) x=2; x+x2+x3=14_ (2) (2x+5x8-3.1x11)+(7-5x8+11x9)=7+2x+11x9-3.1x11 (3) (6x(-3)-x+4.4x2-1.2x9)-(-6x(-3)+5.4x2-x2+7.8x15) =-x+12x(-3)-1.2x9-7.8x15(4) (x+x2)(1+x+x2)=x+2x2+2x3+x4(5) （9+x+x4+2x6）=1+2x3+12x5 2按题目测试要求输入： 例如：求导数求导数功能结 果七、附录源程序文件清单：一元稀疏多项式计算器.cpp八、参考资料 数据结构（C语言版）清华大学出版社； 作者： 严蔚敏、吴伟民；数据结构题集（C语言版）清华大学出版社； 作者： 严蔚敏、吴伟民、米宁程序设计题典（C语言版）清华大学出版社； 作者： 李春葆1 输入并建立多项式2 输出多项式，输出形式外为整数序列：c1,e1;c2,e2;.cn,en;其中n为多项式的项数，ci和ei分别为第i项的系数和指数，序列按指数降序排列3 多项式a和b相加，建立多项式a+b4 多项式a和b相减，建立多项式a-b代码如下：#include#include#define MAX 20 /多项式最多项数typedef struct /定义存放多项式的数组类型 float coef; /系数 int exp; /指数PolyArrayMAX;typedef struct pnode /定义单链表结点类型 float coef; /系数 int exp; /指数 struct pnode *next;PolyNode; void DispPoly(PolyNode *L) /输出多项式PolyNode *p=L-next;while (p!=NULL) printf(%g,%d;,p-coef,p-exp); p=p-next;printf(n);void CreateListR(PolyNode * &L,PolyArray a,int n) /尾插入法建表PolyNode *s,*r;int i;L=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点L-next=NULL;/L-exp=n;/ printf(%dn,L-exp);r=L; /r始终指向终端结点，开始时指向头结点for(i=0;icoef=ai.coef; s-exp=ai.exp; r-next=s; /将*s插入*r之后 r=s;r-next=NULL; /将终端结点next域置为NULLvoid Sort(PolyNode * &head) /按exp域的值递减排序 PolyNode *p=head-next,*q,*r; if(p!=NULL) /当原单链表不为空时 r=p-next; /r保存*p结点后继结点的指针 p-next=NULL; /构造只含一个数据结点的有序表 p=r; while(p!=NULL) r=p-next; /r保存*p结点后继结点的指针 q=head; while(q-next!=NULL & q-next-expp-exp) q=q-next; /在有序表中找插入*p的前驱结点*q p-next=q-next; /将*p插入到*q之后 q-next=p; p=r; void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc)/求两个有序表的并 PolyNode *pa=ha-next,*pb=hb-next,*s,*tc; float c; hc=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点 tc=hc; while(pa!=NULL & pb!=NULL) if(pa-exppb-exp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点 s-exp=pa-exp;s-coef=pa-coef; tc-next=s;tc=s; pa=pa-next;else if(pa-expexp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点 s-exp=pb-exp;s-coef=pb-coef; tc-next=s;tc=s; pb=pb-next;else /pa-exp=pb-exp时c=pa-coef+pb-coef;if(c!=0) /系数之和不为0时创建新结点 s=(PolyNode *)malloc(sizeof(PolyNode); s-exp=pa-exp;s-coef=c; tc-next=s;tc=s;pa=pa-next;pb=pb-next; if(pb!=NULL) /复制余下结点 pa=pb; while(pa!=NULL) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; tc-next=NULL; void Subs(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /求两个有序表的差 PolyNode *pa=ha-next,*pb=hb-next,*s,*tc; float c; hc=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点 tc=hc; while(pa!=NULL & pb!=NULL) if(pa-exppb-exp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点 s-exp=pa-exp;s-coef=pa-coef; tc-next=s;tc=s; pa=pa-next;else if(pa-expexp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点 s-exp=pb-exp;s-coef=-pb-coef; /如果前个多项式中的指数小于后个多项式指数加上负号 tc-next=s;tc=s; pb=pb-next;else /pa-exp=pb-exp时c=pa-coef-pb-coef;if(c!=0) /系数之差不为0时创建新结点 s=(PolyNode *)malloc(sizeof(PolyNode); s-exp=pa-exp;s-coef=c; tc-next=s;tc=s;pa=pa-next;pb=pb-next; if(pb!=NULL) /复制余下结点 pa=pb; while(pa!=NULL) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; tc-next=NULL;void main() PolyNode *ha,*hb,*hc; /PolyArray a=1.2,0,2.5,1,3.2,3,-2.5,5; /PolyArray b=-1.2,0,2.5,1,3.2,3,2.5,5,5.4,10; int m=4,n=5; PolyArray a,b; for(int i=0;im;i+) printf(请输入A多项式中第%d项的系数和指数,i); scanf(%f%d,&ai.coef,&ai.exp); for(int j=0;jn;j+) printf(请输入B多项式中第%d项的系数和指数,j); scanf(%f%d,&bj.coef,&bj.exp); CreateListR(ha,a,4); CreateListR(hb,b,5); printf(原来A:n);DispPoly(ha); printf(原来B:n);DispPoly(hb); Sort(ha); Sort(hb); printf(排序后A:n);DispPoly(ha); printf(排序后B:n);DispPoly(hb); Add(ha,hb,hc); printf(相加后:n);DispPoly(hc); Subs(ha,hb,hc); printf(相减后:n);DispPoly(hc); 一元稀疏多项式计算器的课程设计(1) 输入并建立多项式(2) 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,.,Cn,en,其中n是多项式的相数,Ci和Ei分别是第i项的系数和指数,序列按指数降序排列(3) 两个多项式相加，建立并输出和多项式(4) 两个多项式相减，建立并输出差多项式(5) 两个多项式相乘, 建立乘积多项式(6) 计算多项式在x处的值实现提示:用带表头结点的单链表存储多项式#include#include#include/定义多项式的项typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if(p-coef=0) free(p);/系数为0的话释放结点 else Polyn q1,q2; q1=h; q2=h-next; while(q2&p-expnexpn) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系数为0的话释放结点 q1-next=q2-next; free(q2); else /指数为新时将结点插入 p-next=q2; q1-next=p; Polyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;void DestroyPolyn(Polyn p)/销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;void PrintPolyn(Polyn P)Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coe