实验一-一元多项式运算

1、实验一 - 一元多项式运算实验一 一元多项式的运算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

2、/第一项的系数和指数3 3/第二项的系数和指数-2 2/第三项的系数和指数6 0/第四项的系数和指数5/第二个多项式的项数-3 5/第一项的系数和指数2 2/第二项的系数和指数-6 0/第三项的系数和指数-1 -1/第四项的系数和指数1.2 -2/第五项的系数和指数2. 概要设计2.1 抽象数据类型需要定义一个多项式类型的数据类型，里面包含一个 int 型的指数 和一个 float 型的系数，再定义一个多项式节点，里面包含一个多项式 类型的数据， 和一个指向下一个节点的指针。 通过对多项式节点的操作， 实现对输入数据的运算。开始1加法运算3乘法运算结束输出运算后 的多项式 PrintPolyn

3、()2.2 主程序流程及各模块之间的调用关系输出第一个 多项式PrintPolyn()输入第一个 多项式的项 数创建多项式CreatPolyn()输出第一个 多项式PrintPolyn()创建多项式CreatPolyn()输入第二个 多项式的项 数Menu()2减法运算选择操作加法运算AddPolyn()减法运算SubtractPolyn()乘法运算MultiplyPolyn()3. 详细设计3.1 存储结构实现多项式结构体： typedef struct float coef; int expn;Poly;typedef struct LNodePoly data; struct LNode

4、* 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

5、的系数 *hb 的系数； ha 的指数 *hb 的指数；开辟一个新节点 E，将数据存入，并把 E 连到 c 后Sort(c);/ 对 c 中多项式排序 ha=ha-next;/ha 指向下一个项 while(ha!=NULL)/将 a 中第二项与 b 中所有项相乘，存入 d，然后将c 和 d相加得到新的 c，再以此对 a中其余各项做相同操作，最终得到乘法 运算后的 chb=b-next;/hb为 b 的第一项d=(polynomial)malloc(sizeof(LNode);/ 开辟一个 d 储存 相乘结果d-next=NULL;for(； hb 不空；下一项 )/ 将 a 中第一项与 b

6、中所有项相乘ha的系数 *hb 的系数 ;ha的指数 *hb 的指数 ;开辟一个新节点 E，将数据存入，并把 E连到 d 后;Sort(d);/ 对 d 中多项式排序ha=ha-next;/ha指向下一项AddPolyn(c,d);/将 c ， d 相加得到新的 ct=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(polynomi

7、al& 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)为一元多项式

8、，则有：M x A x B xA x b1xe1 b2xe1 L bnxennbi A x xeii1其中，每一项都是一个一元多项式。（2）销毁多项式销毁多项式只需要判断多项式中的项是否为空，不为空就将指针后移， 然后释放刚才的储存空间，当为空时结束循环。（3）对多项式各项进行排序 通过冒泡排序实现多现实各项的指数的排序，冒泡排序的实现过程为： 多项式中有多少项就进行多少次的排序， 第一次排序遍历一遍所有项， 进行 比较大小，将最大的项调整到链表最前端，然后依次遍历，排完所有项。4.2 算法的时空分析（1）多项式相乘假设多项式 a 长度为 m，多项式 b长度为 n，因为需要对两个表中的所 有元

9、素进行操作，所以时间复杂度为 O mn ， 需要建立两个临时表 c，d 来存储运算数据，因此空间复杂度为 O n 。（2）销毁多项式时间复杂度为 O n ， 空间复杂度为 O 1 。（3）冒泡排序时间复杂度为 O n2 ， 空间复杂度为 O 1 。4.3 算法的改进设想对于多项式中项的排序， 可以采用更高效的排序算法来实现， 因为输入 多项式中不含有指数相同的项（指数相同的项在运算中会被合并） ，因此可 以采用时间性能更好的快速排序来实现。4.4 经验和体会在算法设计中，有很多问题是可以相互转化的，例如对于乘法运算 的算法设计，因为乘法源自于加法，所以可以将求乘法的问题转化为求 一系列加法的问

10、题，从而使问题得到简化，更有利于解决。因此，在编 程过程中，应当多注意事物之间的内在联系，从而抽丝剥茧，简化问题， 有利于问题的求解。5. 使用说明按照屏幕提示，通过键盘输入数据，数据与数据之间用空格隔开，一组数 据输入完毕后，回车结束。6. 测试结果（截屏）（1） 多项式相乘2) 多项式排序(冒泡排序)7. 附录7.1 个人负责模块的程序代码int MultiplyPolyn(polynomial& a,polynomial& b)/ 多项式相乘/ 将 a 的每项分别和 b 所有项相乘，再将它们 相加void Sort(polynomial& L);/ 函数声明 void DestroyPo

11、lyn(polynomial& ); polynomial ha=NULL,hb=NULL,c=NULL; Poly e;if(a-next=NULL|b-next=NULL)return0;/ 若多项式中无项，则返回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-

12、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);/ 序处理ha=ha-next;/ while(ha!=NULL)/ 别与 b 中各项相乘 hb=b-next; polynomial d;对 c 中项的指数进行排指向下一项将 a 中其余各项分d=(polynomial)malloc(sizeof(LNode);d-next=NULL;for(;hb!=

13、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 两项相加，得到合并后的 cpolynomial t=a

14、;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-da

15、 ta.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 structfloat coef;int expn;Poly; typedef struct LNodePoly data;struct LNode* next;LNode,*LinkList;typed

16、ef LinkList polynomial;int main()/ 主函数/ 函数声明void CreatPolyn(polynomial& ,int );void DestroyPolyn(polynomial& );void const PrintPolyn(polynomial );intAddPloyn(polynomial& ,polynomial& );intSubtractPloyn(polynomial& ,polynomial&);intMultiplyPloyn(polynomial& ,polynomial& );voidMenu(polynomial& ,polyno

17、mial& );/ 定义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.c

18、oef,&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);intSubtractPolyn(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; els

19、e while(hb-next!=NULL) if(ha-next-data.expnnext-data.e xpn)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;

20、 free(p);elseha=ha-next;if(ha-next=NULL)hb-next-data.coef=0-hb-next-data.co ef;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.

21、 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; else while(hb-next!=NULL)if(ha-next-data.expnnext-data.e xpn)polynomial p,q;p=hb-next;q=p-next;p-next=ha-next;ha-next=p;hb-next=q;ha=ha-next;els

22、e 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);elseha=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

23、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.