《设计程序以实现任意两个高次多项式的加法和乘法运算.doc》由会员分享，可在线阅读，更多相关《设计程序以实现任意两个高次多项式的加法和乘法运算.doc（34页珍藏版）》请在三一办公上搜索。
1、设计程序以实现任意两个高次多项式的加法和乘法运算 学生姓名：王帆 指导老师：张建明 摘 要 本课程设计主要解决任意两个高次多项式的乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。 关键词 高次多项式；加
2、法；乘法；时间复杂度；空间复杂度 1 问题分析和任务定义1.1 任务定义 设计程序以实现任意两个高次多项式的乘法运算。要求： （1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。 从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。 设计算法（程序）测试用例： 图1-1 图1-2 图1-1 为正确的输出结果，图1-2 为错误的输出结果1.2 要解
3、决的问题（1） 怎样实现两个多项式的乘法？（2） 相乘后若有指数相同的项用什么方法合并？（3） 使用什么数据结构来满足尽可能节省存储空间的要求？（4） 用什么方法来输出表达式？2概要设计和数据结构的选择2.1 数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：（1） 链表是有限个具有相同数据类型的数据元素的集合，D=ai/i=1,2,，n;ai为数据元素。（2） 数据元素之间的关系R=/ai,ai+1D。（3） 数据元素ai 在存储器中占用任意的、连续或不连续的物理存储区域。动态链表： 当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除
4、数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。2.2 结构图图2-1图2-1 即为本程序
5、的结构图2.3 下面是针对本程序专门定义的数据结构类型 结点的数据类型如下：typedef struct Pnodeint coef; /系数指针int exp; /指数指针struct Pnode*next;polynode;数据结构的设计思想：链表中的每一个结点存放多项式的一个系数非0 项。它包含三个域,分别存放放该项的系数、指数以及指向下一个多项式结点的指针。 如图2-2 所示为多项式链表结点的结构。系数 指数 指针图2-2例如2-3 所示，多项式的单链表表示如下 图2-32.4 流程图 图2-4图2-4为主函数的流程图 图2-5 图2-5为plcreate 多项式链表生成函数的流程图图
6、2-6图2-6为置空函数流程图图2-7图2-7为output 输出多项式函数的流程图图2-8图2-8 为多项式相乘函数流程图图2-9图2-9 为合并指数相同项函数的流程图2.5 各程序模块之间的层次（调用）关系 在执行主函数时先调用plcreate 生成要相乘的多项式，存储在两个动态链表中，然后调用output 函数输出两个多项式，继续执行相乘函数，相乘后调用置空函数将相乘的链表删除。然后，检验是否有指数相同的项，如果没有则调用output 函数输出结果，否则调执行合并函数将指数项相同的合并，调用output 函数输出结果。3 详细设计和编码3.1 算法思想 先将两个已知的多项式的指数和系数存
7、放在指定链表中在执行乘法运算。乘法运算的过程是将A 式中的第一项与B 式的每一项相乘，在将A 式的第二项与B 式的每一项相乘，依次下去直到A 式的所有项与B 式乘完为止。将相乘后所得的指数、系数存在预先建好的C 链表中。 C 链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。这里需要将c 链表中的每一项都要对比一遍，这里就要发挥指针的作用了。首先定义3个指针，x、y、z，x、y 指向首元素结点z 指向第二个结点，用z 结点中指数项与x 结点的指数项比较，如果不同指针z 向后移，若相同则将z 结点的系数加到x 上去然后将z 所在结点空间释放，并且指针z 后移。直到指针
8、z 指向空后，将指针x 后移一项，并令z 指向x 的下一项，然后按上述步骤依次执行，直到x 指向空结束。这里指针y 是z 的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。本程序核心部分全部是运用while 循环语句实现的。3.2 算法描述例分别用单链表表示，并描述相乘过程。AB 图3-1图3-1 为A、B 两多项式的链表表示A qB 图3-2如图3-2 所示，P=A-next; q=B-next;指针p，q 分别指向多项式的首元素节点，A B C 图3-3 依次执行 x=p-coef*q-coef;y=p-exp+q-expk=(polynode*)malloc(si
9、zeof(polynode);k为暂存相乘结果的动态链表k-coef=x;k-exp=y; k-next=NULL; m-next=k; m=k;m 是c 链表的指针,继续执行q=q-next; 图3-3 所示C 图3-4 图3-4 为多项式执行到q-next=NULL 时的结果 PA B 图3-5当执行到q-next=NULL 时，指针p 后移，指针q 指向B 链表的首元素结点，继续以上循环。如图3-5 所示 图3-6当q 指向空时，多项式相乘结束所有数据存入c 链表如图3-6 所示。这样就完成了乘法运算，相乘后的C 链表还可能出现指数相同的项，这时就需要合并。例图3-7 所示，A、B 两式
10、相乘结果如下图3-7用u、d 指向头结点，e 指向第二个结点，图3-7 所示图3-8u 指针跟随e 指针，当d-exp=e-exp 时，将e 指针所指项的系数加到d 指针所指项上去。并将e 当前所指项删除。图3-8 所示。 r=e; /将相同项的后一项e赋予*r d-coef+=e-coef; /后项系数与前项系数相加 u-next=e-next; /将指针e所前一项指针指向e的后一项 e=e-next; free(r); /释*r结点空间图3-9这样就完成了一次合并。C 链表变为图3-10 图3-10 继续按上述方法直到将链表中所有同类项合并完为止。 d图3-11 当d-next=NULL
11、时结束。如3-11 所示。 （1）设指针p、q 分别为指向A、B 的首元素结点，用p-coef 乘q-coef,p-exp+q-exp,并令指针p 后移。 （2）当q-next 为空时，指针p 向后移一位，指针q 继续从B 链表的第一项开始，执行p-coef 乘q-coef,p-exp 加q-exp.每执行一次指针p 后移。 （3）重复（1）、（2）步，直到p-next 为空后，结束。将乘出结果存入C 链表。合并时用两个指针指向C 链表，一个指针跟随另一个当作后一个指针前驱指针，这样合并后释放就容易将前后结点链接上。综合以上分析，两个高次多项式相乘的算法如下： polynode *p,*q,*
12、m,*k,*d,*e,*r,*u;int x,y; /m,d,e,r,u指向C链表的指针 p=A-next; q=B-next; /p,q分别指向A和B多想失恋表中的第一个结点 C=（polynode*）malloc(sizeof(polynode); C-next=NULL; /建立空多项式单链表用来储存多项式相乘结果 m=C; while(p!=NULL) /当A链表不为空时 while(q!=NULL) /当B链表不为空时 k=(polynode*)malloc(sizeof(polynode); /k为暂存相乘结果的动态链表 x=p-coef*q-coef;/系数相乘 y=p-exp+
13、q-exp;/指数相加 k-coef=x;k-exp=y; k-next=NULL; /建立空链表 m-next=k; m=k; /将结果放入C链表中 q=q-next; q=B-next; p=p-next; printf(n未合并前多项式为:n); output(C); /输出未合并前多项式 合并同类项 d=C-next; /d指向C链表的头结点 while(d!=NULL) /当C链表不为空时 u=d; e=u-next; /u指向*e的前驱结点 while(e!=NULL) /当e结点不为空时，执行 if(d-exp=e-exp) /后面的项与前面的项指数相同时 r=e; /将相同项中
14、的后一项指针e赋予*r d-coef+=e-coef; /后项系数与前项系数相加 u-next=e-next; /将指针e所有前一项指针指向e的后一端 e=e-next; free(r); /释*r结点空间 i=1; else e=e-next; u=u-next; /*e，*u分别指向下一项 d=d-next; if(i!=1) printf(n没有指数相同的项。n); else Printf(n合并后n); output(C); Printf(n) getch() 用尾插法生成多项式链表的算法如下： polynode *plcreate() polynote *H,*R,*S; int c
15、, e; H=(polynote*)malloc(sizeof(polynote); H-exp=-1; H-next=HULL; R=H; scanf(%d%d,&c,&e); while(e!=-1) S=(polynode*)malloc(sizeof(polynode); S-coef=c; S-exp=e; S-next=NULL; R=S; scanf(%d%d,%c,%e); return H; 这个算法是按照课本上介绍的尾插法建链表算法加以修改而成。将没用的链表删除以防浪费存储空间。算法如下： polynode *setnull(polynode *L) polynode *a
16、,*b,*c; a=L; b=L-next; while(b!=NULL) c=b; L-next=b-next; b=b-next; free(c); return L; Output 输出函数。 void output (polynode *h) /输出多项式函数 h=h-nxt; if(h!=NULL) /当多项式不为空时输出 if(h-coef!=0) /输出多项式的第一项 if(h-exp!=0) /指数不为零时 printf(%dx%d,h-coef,h-exp); else printf(%d,h-coef); /指数为零时 else printf(0); h=h-next; /
17、第二项以后 while(h!=HULL) /当多项式不为空时，执行此循环 if(h-coef0) /系数大于零时 if(h-exp!=0) printf(+%dx%d,h-coef,h-exp); else printf(+%d,h-coef); if(h-coefexp!=0) printf(%dx%d,h-coef,h-exp); else printf(%d,h-coef); if(h-coef=0) printf(); /系数等于零时 h=h-next以上就是按照题目功能要求和数据结构要求，编写算法和各程序模块代码。4 上机调试4.1 调试中遇到的问题和解决方法图4-1 1 在开始设计
18、output 函数时，当输入数据系数为负数是就出现了图4-1 所示+、- 号同时出现在表达式中。当时output 函数如下 void output(polynode *h) h=h-next; while(h!=HULL) if(h-next!=HULL) if(h-exp!=0) printf(%d%d+,h-coef,h-exp); else printf(%d+,h-coef); else if(h-exp!=0) printf(%d%d,h-coef,h-exp); else printf(%d,h-coef); h=h-next; 当时我没想到判断系数正负问题，所以才出现以上情况 ，
19、在程序中曾加一个if 语句判别h-coef 大于0、小于0、还是等于0，判别之后在进行输出改后为：while (n!=NULL) if(h-coef0) /系数大于零时 if(h-exp!=0) printf(+%dx%d,h-coef,h-exp); else printf(+%d,h-coef); if(h-coefexp1=0) printf(%dx%d,h-coef,h-exp); else printf(%d,h-coef); if(h-coef=0) printf(); /系数等于零时 h=h-next;图4-2 图4-2 修改后输出结果 2 当程序执行到合并指数相同项时就出现了错
20、误。调试后发现执行完第一次while 循环后指向c 链表的指针e 不在存储空间中，导致无法判断while 循环，仔细检查后，发现合并时将e 指针所指结点释放后，没有给他指定新的结点。把指针e 后移一位，这样就解决了问题。4.2 时间空间复杂度的计算若多项式A 有n 项,多项式B 有m 项，则两多项式相乘时为m*n ,接下来检验是否有同类项检查方法是每一项都要对比所以为(m*n)!,时间复杂度为O（m*n+(m*n）!)由于各个算法是基于动态链表而建成的，所以各算法的空间性能均较好。4.3 设计体会 这个题目不是很难，但是一开始自己却觉的非常的吃力，不知从那里入手,下面是我这次课程设计的一些感想
21、：（1）通过本设计实验又将数据结构中的链表的知识重新温习了一遍，并且自己能够独立设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。（2）在课程设计中遇到了很多的问题，都是以前没有发现的，这些问题涉及的方面很多，有的是c 语言基础的，也有最近学习的数据结构的知识。通过本次课程设计，让我发现了自己的不足。自己在学习知识上面的漏洞。希望通过弥补这些发现的漏洞，提高自己的专业知识水平。（3）设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网络等等。（4）实验过程中也走了很多的弯路，由于
22、在开始设计的时候思路不是很清晰，对于一些问题不能很好的提出解决问题的方法，在设计过程中，代码总是重复的修改，在很多问题上，代码并不时最优的。相信在以后的学习中，随着知识的增多，问题会逐渐得到解决。总之，我付出了许多时间，换来的是用任何东西都不能比的财富，别人抢不走，因为他是知识。因为自己知识有限所以程序不是很好，但它是我自己一步一步编写出来。只有好好学习，自己将来才有出路。5 测试结果及其分析图5-1图5-1 两多项式相乘后没有指数相同项输出的结果图5-2 两多项式相乘后有指数相同项合并后输出的结果图5-2 6 用户使用说明（1）给出任意两个高次多项式，只需按照多项式从左到右依次输入系数值、指
23、数值，当输入指数值为-1 时结束。（由于程序设计的缺陷系数指数都要输入所以结束之前系数值可随便输入不影响运算结果。（2）程序中指数、系数定义的是整型，所以表达式中系数值、指数值不能超出整型范围。（3）输入是正数直接输入，负数要加负号。指数不能选择-1。参考文献1王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007.2苏仕华等编著. 数据结构课程设计. 北京：机械工业出版社 ,2005.3苏仕华编著. 数据结构与算法解析. 合肥:中国科学技术大学出版社,2004.4郭嵩山等著. 国际大学生程序设计竞赛例题解. 北京:电子工业出版社,2008.5刘大有,唐海鹰等编著. 数据结构.
24、 北京:高等教育出版社,2001.6徐孝凯编著.数据结构实用教程. 北京: 清华大学出版社,1999.7严蔚敏,陈文博编著. 数据结构及算法教程. 北京: 清华大学出版社,2001.8刘振安,刘燕君等编著. C 程序设计课程设计. 北京: 机械出版社,2004.9胡学钢. 数据结构与算法设计指导. 北京: 清华大学出版社, 1999.附录：程序源代码/ 程序名称：GCDXS.CPP / 程序功能：实现任意两个高次多项式的加法和乘法运算/ 程序作者：王帆/* 多项式加法和乘法示例 */ #include #include #include using namespace std; /定义多项式的
25、项类 class term public: int coef; /多项式系数 int exp; /多项式指数 /初始化项的系数和指数 term( int c=0,int e=0):coef(c),exp(e) ; /定义多项式类 class PolyArith private: list m_poly_list_first; /存储第一个多项式 list m_poly_list_second; /存储第二个多项式 list m_poly_list_result; /用以存储运算结果 /多项式私有成员函数,用以乘法时的调用 list Poly_add(list&poly_list_first,
26、list&poly_list_second) list poly_list_result; / /用以存储运算结果 list:iterator iter_first = poly_list_first.begin(); list:iterator iter_second = poly_list_second.begin(); /该while循环针对两个链表迭代器都没有指到结尾的情形 while(iter_first != poly_list_first.end()& iter_second != poly_list_second.end() term t_temp; term t_first
27、= (term)*iter_first; term t_second = (term)*iter_second; if(t_first.expt_second.exp) poly_list_result.push_back(t_first); iter_first+; else if(t_second.expt_first.exp) poly_list_result.push_back(t_second); iter_second+; else t_temp.coef=t_first.coef+t_second.coef; t_temp.exp=t_first.coef; poly_list_
28、result.push_back(t_temp); iter_first+; iter_second+; /该for循环针对第一个多项式的迭代器没有指到结尾 /第二个指到结尾的情形 for(;iter_first != poly_list_first.end();iter_first+) poly_list_result.push_back(*iter_first); /该for循环针对第二个多项式的迭代器没有指到结尾 /第一个指到结尾的情形 for(;iter_second!=poly_list_second.end();iter_second+) poly_list_result.push
29、_back(*iter_second); return poly_list_result; public: /输入函数，用以输入多项式 void Poly_input() int n; cout请输入第一个多项式的项数：n; cout按降幂输入第一个多项式的每一项的系数和指数：; coutendl; for(int i=1;i=n;i+) term t_temp; cout请输入第i 项系数和指数,以enter为界：; coutt_temp.coef; cint_temp.exp; m_poly_list_first.push_back(t_temp); n = 0; cout请输入第二个多项
30、式的项数：n; cout按降幂输入第二个多项式的每一项的系数和指数：; coutendl; for(int j=1;j=n;j+) term t_temp; cout请输入第j 项系数和指数，以enter为界：; coutt_temp.coef; cint_temp.exp; m_poly_list_second.push_back(t_temp); /输出函数，用以输出多项式 void Poly_output() /用以指向输出多项式的第一个元素 list:iterator iter = m_poly_list_result.begin(); /输出多项式的每一项 for(;iter!=m_
31、poly_list_result.end();) term t_temp=*iter; coutt_temp.coefxt_temp.exp; if(+iter!=m_poly_list_result.end() cout+; coutendl; /加法函数，其基本思想同上边的私有成员函数Poly_add() /此处不带参数，多项式运算对象为私有数据成员 void Poly_add() list:iterator iter_first = m_poly_list_first.begin(); list:iterator iter_second = m_poly_list_second.begi
32、n(); while(iter_first != m_poly_list_first.end()& iter_second != m_poly_list_second.end() term t_temp; term t_first=(term)*iter_first; term t_second = (term)*iter_second; if(t_first.expt_second.exp) m_poly_list_result.push_back(t_first); iter_first+; else if(t_second.expt_first.exp) m_poly_list_resu
33、lt.push_back(t_second); iter_second+; else t_temp.coef=t_first.coef+t_second.coef; t_temp.exp=t_first.exp; m_poly_list_result.push_back(t_temp); iter_first+; iter_second+; for(;iter_first != m_poly_list_first.end();iter_first+) m_poly_list_result.push_back(*iter_first); for(;iter_second != m_poly_li
34、st_second.end();iter_second+) m_poly_list_result.push_back(*iter_second); /乘法函数，用以作多项式乘法 void Poly_multi() list poly_list_result; list:iterator iter_first = m_poly_list_first.begin(); for(;iter_first!=m_poly_list_first.end();iter_first+) list poly_list_temp; /用以存储多项式的中间运算结果 list:iterator iter_second
35、 = m_poly_list_second.begin(); for(;iter_second!=m_poly_list_second.end(); iter_second+) term t_temp; /用以存储项的中间运算结果 term t_first = (term)*iter_first; term t_second = (term)*iter_second; /此处实现多项式项的相乘 t_temp.coef = t_first.coef*t_second.coef; /系数相乘 t_temp.exp = t_first.exp + t_second.exp; /指数相加 poly_list_temp.push_back(t_temp); /此处调用私有成员函数Poly_add（） poly_list_result = Poly_add(poly_list_temp,poly_list_result);
