实验一 一元多项式运算.doc

实验一 一元多项式的运算1. 问题定义及需求分析1.1课题目的和任务问题描述：设计一个一元多项式简单计算器。实验要求：1)采用顺序表或链表等数据结构。2)输入并建立多项式。3)输出运算结果的多项式。1.2数据形式输入数据形式：通过键盘输入。输入值的范围：多项式的项数和指数的输入数据为int型，输入值范围为-32768至32767；多项式系数的输入值范围为float型，范围为1.2e-38至3.4e+38。输出数据形式：输出到显示器。1.3程序功能实现两个一元多项式之间的加法、减法和乘法运算。1.4测试数据4 /第一个多项式的项数1 4 /第一项的系数和指数3 3 /第二项的系数和指数-2 2 /第三项的系数和指数6 0 /第四项的系数和指数5 /第二个多项式的项数-3 5 /第一项的系数和指数2 2 /第二项的系数和指数-6 0 /第三项的系数和指数-1 -1 /第四项的系数和指数1.2 -2 /第五项的系数和指数2. 概要设计2.1抽象数据类型需要定义一个多项式类型的数据类型，里面包含一个int型的指数和一个float型的系数，再定义一个多项式节点，里面包含一个多项式类型的数据，和一个指向下一个节点的指针。通过对多项式节点的操作，实现对输入数据的运算。2.2主程序流程及各模块之间的调用关系3. 详细设计3.1存储结构实现多项式结构体：typedef struct float coef; int expn;Poly;typedef struct LNode Poly data; struct LNode* next;LNode,*LinkList;多项式类型的定义：typedef LinkList polynomial;3.2负责模块的伪码算法（1）int MultiplyPolyn(polynomial& a,polynomial& b)/多项式相乘 if(a,b中均没有项)return 0; c=(polynomial)malloc(sizeof(LNode);/开辟一个c储存相乘结果 c-next=NULL; ha=a-next;/ha为a中的项 hb=b-next;/hb为b中的项 for(；hb不空；下一项)/将a中第一项与b中所有项相乘 ha的系数*hb的系数； ha的指数*hb的指数； 开辟一个新节点E，将数据存入，并把E连到c后 Sort(c);/对c中多项式排序 ha=ha-next;/ha指向下一个项 while(ha!=NULL)/将a中第二项与b中所有项相乘，存入d，然后将c和d相加得到新的c，再以此对a中其余各项做相同操作，最终得到乘法运算后的c hb=b-next;/hb为b的第一项 d=(polynomial)malloc(sizeof(LNode);/开辟一个d储存相乘结果 d-next=NULL; for(；hb不空；下一项)/将a中第一项与b中所有项相乘 ha的系数*hb的系数; ha的指数*hb的指数; 开辟一个新节点E，将数据存入，并把E连到d后; Sort(d);/对d中多项式排序 ha=ha-next;/ha指向下一项 AddPolyn(c,d);/将c，d相加得到新的c t=a; a=c;/a指向运算结果 DestroyPolyn(b);/销毁初始的两个多项式 DestroyPolyn(t);（2）void DestroyPolyn(polynomial& L)/销毁多项式 while(L!=NULL) p=L; L=L-next;/指向后一项 free(p); （3）void Sort(polynomial& L)/对多项式的指数进行冒泡排序 for(多项式长度) for(j=L;j-next-next!=NULL;j=j-next) if(j-next指数 next-next指数)/将大的冒到前面 p=j-next; q=j-next-next; p-next=q-next; q-next=p; j-next=q; 4. 调试分析4.1问题分析与解决方法（1）多项式相乘对于多项式相乘，考虑到两个一元多项式的相乘，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算，所以只需循环执行加法运算，就可以完成多项式的相乘。例如A（x）和B（x）为一元多项式，则有：其中，每一项都是一个一元多项式。（2）销毁多项式销毁多项式只需要判断多项式中的项是否为空，不为空就将指针后移，然后释放刚才的储存空间，当为空时结束循环。（3）对多项式各项进行排序通过冒泡排序实现多现实各项的指数的排序，冒泡排序的实现过程为：多项式中有多少项就进行多少次的排序，第一次排序遍历一遍所有项，进行比较大小，将最大的项调整到链表最前端，然后依次遍历，排完所有项。4.2算法的时空分析（1）多项式相乘假设多项式a长度为m，多项式b长度为n，因为需要对两个表中的所有元素进行操作，所以时间复杂度为，需要建立两个临时表c，d来存储运算数据，因此空间复杂度为。（2）销毁多项式 时间复杂度为，空间复杂度为。（3）冒泡排序时间复杂度为，空间复杂度为。4.3算法的改进设想对于多项式中项的排序，可以采用更高效的排序算法来实现，因为输入多项式中不含有指数相同的项（指数相同的项在运算中会被合并），因此可以采用时间性能更好的快速排序来实现。4.4经验和体会在算法设计中，有很多问题是可以相互转化的，例如对于乘法运算的算法设计，因为乘法源自于加法，所以可以将求乘法的问题转化为求一系列加法的问题，从而使问题得到简化，更有利于解决。因此，在编程过程中，应当多注意事物之间的内在联系，从而抽丝剥茧，简化问题，有利于问题的求解。5. 使用说明按照屏幕提示，通过键盘输入数据，数据与数据之间用空格隔开，一组数据输入完毕后，回车结束。6. 测试结果（截屏）（1） 多项式相乘（2） 多项式排序（冒泡排序）7. 附录7.1个人负责模块的程序代码int MultiplyPolyn(polynomial& a,polynomial& b)/多项式相乘/将a的每项分别和b所有项相乘，再将它们相加 void Sort(polynomial& L);/函数声明 void DestroyPolyn(polynomial& ); polynomial ha=NULL,hb=NULL,c=NULL; Poly e; if(a-next=NULL|b-next=NULL)return 0;/若多项式中无项，则返回 c=(polynomial)malloc(sizeof(LNode);/开辟c，存储第一次运算结果 c-next=NULL; ha=a-next; hb=b-next; for(;hb!=NULL;hb=hb-next)/将b中每项都与a的第一项相乘 e.coef=(ha-data.coef)*(hb-data.coef); e.expn=(ha-data.expn)+(hb-data.expn); polynomial E=NULL; E=(polynomial)malloc(sizeof(LNode); E-data.coef=e.coef; E-data.expn=e.expn; E-next=c-next; c-next=E;/将每项结果保存在c中 Sort(c);/对c中项的指数进行排序处理 ha=ha-next;/指向下一项 while(ha!=NULL)/将a中其余各项分别与b中各项相乘 hb=b-next; polynomial d; d=(polynomial)malloc(sizeof(LNode); d-next=NULL; for(;hb!=NULL;hb=hb-next)/用d储存a中后一项和b中所有项的乘积 e.coef=(ha-data.coef)*(hb-data.coef); e.expn=(ha-data.expn)+(hb-data.expn); polynomial E=NULL; E=(polynomial)malloc(sizeof(LNode); E-data.coef=e.coef; E-data.expn=e.expn; E-next=d-next; d-next=E; Sort(d); ha=ha-next; AddPolyn(c,d);/将c，d两项相加，得到合并后的c polynomial t=a; a=c; DestroyPolyn(b);/销毁临时存储空间 DestroyPolyn(t); return 1;void DestroyPolyn(polynomial& L)/销毁线性表 while(L!=NULL) polynomial p; p=L; L=L-next; free(p); void Sort(polynomial& L)/冒泡排序 polynomial i,j; for(i=L;i-next!=NULL;i=i-next)/总次数 for(j=L;j-next-next!=NULL;j=j-next)/第一趟 if(j-next-data.expnnext-next-data.expn)/比较大小，将大的冒到前面 polynomial p,q; p=j-next; q=j-next-next; p-next=q-next; q-next=p; j-next=q; 7.2程序全部代码#include#include#include#define TRUE 1;#define FALSE 0;using namespace std;typedef struct float coef; int expn;Poly;typedef struct LNode Poly data; struct LNode* next;LNode,*LinkList;typedef LinkList polynomial;int main()/主函数 /函数声明 void CreatPolyn(polynomial& ,int ); void DestroyPolyn(polynomial& ); void const PrintPolyn(polynomial ); int AddPloyn(polynomial& ,polynomial& ); int SubtractPloyn(polynomial& ,polynomial& ); int MultiplyPloyn(polynomial& ,polynomial& ); void Menu(polynomial& ,polynomial& ); /定义 int n=1; while(n=0) polynomial a; polynomial b; system(cls); printf(请输入第一个多项式的项数(输入负数退出）：); scanf(%d,&n); if(n0)exit(0); CreatPolyn(a,n); PrintPolyn(a); printf(请输入第二个多项式的项数（输入负数退出）：); scanf(%d,&n); if(nnext=NULL; Poly e; int i=1; for(;n0;n-,i+) printf(请输入第%d,i); printf(项的系数和指数:); scanf(%f%d,&e.coef,&e.expn); polynomial E=NULL; E=(polynomial)malloc(sizeof(LNode); E-data.coef=e.coef; E-data.expn=e.expn; E-next=L-next; L-next=E; Sort(L);int SubtractPolyn(polynomial &Pa,polynomial &Pb)/多项式减法：Pa=Pa-Pbpolynomial ha=NULL,hb=NULL,p=NULL; ha=Pa; hb=Pb;if(ha-next=NULL) Pa=Pb; free(ha); return 0; elsewhile(hb-next!=NULL) if(ha-next-data.expnnext-data.expn) polynomial p,q; p=hb-next; q=p-next; p-data.coef=0-p-data.coef; p-next=ha-next; ha-next=p; hb-next=q; ha=ha-next; else if(ha-next-data.expn=hb-next-data.expn) ha-next-data.coef=ha-next-data.coef-hb-next-data.coef; p=hb-next; hb-next=hb-next-next;free(p);else ha=ha-next; if(ha-next=NULL) hb-next-data.coef=0-hb-next-data.coef; ha-next=hb-next; hb-next=NULL; free(hb); return 0;void const PrintPolyn(polynomial P)/输出多项式 polynomial a;a=P-next;/开始输出while(a-next)printf(%gx%d +,a-data.coef,a-data.expn);a=a-next;/输出最后一个 printf(%gx%dn,a-data.coef,a-data.expn);int AddPolyn(polynomial &Pa,polynomial &Pb)/多项式加法：Pa=Pa+Pbpolynomial ha=NULL,hb=NULL,p=NULL; ha=Pa; hb=Pb;if(ha-next=NULL) Pa=Pb; free(ha); return 0; elsewhile(hb-next!=NULL) if(ha-next-data.expnnext-data.expn) polynomial p,q; p=hb-next; q=p-next; p-next=ha-next; ha-next=p; hb-next=q; ha=ha-next; else if(ha-next-data.expn=hb-next-data.expn) ha-next-data.coef=ha-next-data.coef+hb-next-data.coef; p=hb-next; hb-next=hb-next-next;free(p);else ha=ha-next; if(ha-next=NULL) ha-next=hb-next; hb-next=NULL; free(hb); return 0;int MultiplyPolyn(polynomial& a,polynomial& b)/多项式相乘 void Sort(polynomial& L); void DestroyPolyn(polynomial& ); polynomial ha=NULL,hb=NULL,c=NULL; Poly e; if(a-next=NULL|b-next=NULL)return 0; c=(polynomial)malloc(sizeof(LNode); c-next=NULL; ha=a-next; hb=b-next; for(;hb!=NULL;hb=hb-next) e.coef=(ha-data.coef)*(hb-data.coef); e.expn=(ha-data.expn)+(hb-data.expn); polynomial E=NULL; E=(polynomial)malloc(sizeof(LNode); E-data.coef=e.coef; E-data.expn=e.expn; E-next=c-next; c-next=E; Sort(c); ha=ha-ne