设计程序以实现任意两个高次多项式的加法和乘法运算

1、设计程序以实现任意两个高次多项式的加法和乘法运算学生姓名：王帆 指导老师：张建明摘 要 本课程设计主要解决任意两个高次多项式的乘法运算。所设计的数据结构 应尽可能节省存储空间，程序的运行时间应尽可能少。从题目看出所设计的程序应 能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次 多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个 问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设 计中尤为重要，这也是本程序好坏的一个评定。程序通过调试运行，初步实现了设 计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词 高次多项

2、式；加法；乘法；时间复杂度；空间复杂度1 问题分析和任务定义1.1 任务定义设计程序以实现任意两个高次多项式的乘法运算。要求：（ 1）所设计的数据结构应尽可能节省存储空间。 （2）程序的运行时间应尽可能 少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右幵始，按每一项指数、系 数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选 择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。设计算法（程序）测试用例:4x5+6x4xs+7x23-5xs图1-1图1-2图1-1为正确的输出结果，图1

3、-2为错误的输出结果1.2要解决的问题（1）怎样实现两个多项式的乘法？（2）相乘后若有指数相同的项用什么方法合并？（3）使用什么数据结构来满足尽可能节省存储空间的要求?（4）用什么方法来输出表达式？2概要设计和数据结构的选择2.1数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：（1） 链表是有限个具有相同数据类型的数据元素的集合，D=n/i=1,2, 为数据元素。（2） 数据元素之间的关系R=<ai,ai+1>/ai,ai+1 D。（3）数据元素ai在存储器中占用任意的、连续或不连续的物理存储区域。动态链表：当需要插入数据元素时，临时动态地为其申请一个存储空间，而

4、不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个 结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类 型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而且 相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就 没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间

5、。2.2 结构图输入枉意商个高次多 项式的系数、指数侑将输入值分别存储在两个动态链表中输出曲个要柑乘的芈项v式相乘需结果存入C链表将存放相乘的多项式各J项系数、指数的链衣置空若有指数相同的项合并输岀结果图2-1图2-1即为本程序的结构图2.3下面是针对本程序专门定义的数据结构类型结点的数据类型如下：typedef struct Pno deint coef;/系数指针int exp;/指数指针struct Pno de* next;polyno de;数据结构的设计思想：链表中的每一个结点存放多项式的一个系数非0项。它包含三个域，分别存放放该项的系数、指数以与指向下个多项式结点的指针。如图2-

6、2所示为多项式链表结点的结构。系数指数 指针coofxpnext图2-2例如2-3所示，多项式的单链表表示如下图2-32.4流程图毎兒>ohTi<de SlIhH A K C科i 式衣诂式 的常咬指Jft值週用feth z b两今券 Hl 式（谐甲 ouiptii说川社I耻函敷将A. B两爭坨试相桑.并郴 结果右诸业匸醴我屮图2-4图2-4为主函数的流程图定义一蛾雜型变世阳来存指敢.農数谀“ e申诜 牛空軽我用来海攜独入的 数据H £辙入缶珑式第以的播数tfl /河於宀系数爼賦缶c/申请肃时劫崙空间sS'<pdlyMKk*XiullM(ii2fiottjwl

7、ynodt);斟输丄的系数捋裁曲打住此空冊内乩叱xF冲亡；将£伯故入R罹农屮Tvlurii 111图2-5图2-5为plcreate 多项式链表生成函数的流程图开齡,r童文phjyiuKk屯荷制m氐亡1h' M IT久蚪点删f陕从城肯放b指针的（W 戎忡I帛问tn红总捋|指钊和宿阿上 :岩一点芯IneJil城片指 甸的縮点地址賦 劭指针伽:图2-6图2-6为置空函数流程图i开结.1I定义m井专其指向娃我的首络点忆鳶° id", lb > at!n姑点茶數屋出 %dnA%*rth->门卜*5h h-»cKth! Mb IXN揃向下一培走

8、 h li-' ne *i1*,h:叱 5W = -h->coct>Q 帝敎大丁 Q"：| odx A0 od创；h 0p,是）1r/输出Lp!-NULLq' MILL中图2-7图2-7为output输出多项式函数的流程图开晞I '¥定文昭严显型指针.宦袞曼量也y指针P小分别術向九B T7元匝州点 m是 c的指针帯针F向后移 播针1脂向首 节虑 k ipolyttikk' Itiikllod hijetj：! pdkikHJe”用来脇时疗脇数SCy K*exp+q->exp;k->wei'm-i'heu

9、t k； k;i图2-8图2-8为多项式相乘函数流程图幵皓定义ploynode总捕對u丄tk飢 i. d Om%性d牯I可 芥吒若我沽.岛出 NULLLi ck e-u.->ntxLe 1&向 u 的下-牛射点i垦iC所指歸魚钳社耳L1F1 指站点指迪是否栢同e!-NVLL 指叶 足杵如空将相冋项申的石 域捋钊理賦上-l-. e： _-' Lix.' I 石负亲數与耐顷祭 數相hlu->iwM e- nc?ii；y ftfStf-eff# 皿指针指向e的后一坡e ZneU frw( rr，-,郸"r皓点丫闸d d*-ill： XL*e?u 分别抬向

10、图2-9图2-9为合并指数相同项函数的流程图2.5 各程序模块之间的层次（调用）关系在执行主函数时先调用 plcreate 生成要相乘的多项式，存储在两个动态链表中， 然后调用 output 函数输出两个多项式，继续执行相乘函数，相乘后调用置空函数 将相乘的链表删除。然后，检验是否有指数相同的项，如果没有则调用 output 函 数输出结果，否则调执行合并函数将指数项相同的合并，调用 output 函数输出结 果。3 详细设计和编码3.1 算法思想先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。乘法 运算的过程是将 A 式中的第一项与 B 式的每一项相乘，在将 A 式的第二项与

11、 B 式 的每一项相乘， 依次下去直到 A 式的所有项与 B 式乘完为止。 将相乘后所得的指数、 系数存在预先建好的 C 链表中。C 链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将 后一项删除。这里需要将 c 链表中的每一项都要对比一遍，这里就要发挥指针的作 用了。首先定义 3个指针， x、y、 z，x、y 指向首元素结点 z 指向第二个结点，用 z 结点中指数项与 x 结点的指数项比较，如果不同指针 z 向后移，若相同则将 z 结点 的系数加到 x 上去然后将 z 所在结点空间释放，并且指针 z 后移。直到指针 z 指向 空后，将指针 x 后移一项，并令 z 指向 x 的

12、下一项，然后按上述步骤依次执行，直到x指向空结束。这里指针y是Z的前驱结点他的作用是合并后结点空间释放结点 空间将此结点的前后两项链接起来。本程序核心部分全部是运用while循环语句实现的。3.2算法描述例J R二仏分别用单链表表示，并描述相乘过程AB图3-1图3-1为A、B两多项式的链表表示图3-2如图3-2所示，P=A->next; q=B->next;指针p，q分别指向多项式的首元素节点,A图3-3依次执行x=p->coef*q->coef;y=p->exp+q->expk=(po lyno de*)malloc(sizeof(po lynode);k

13、 为暂存相乘结果的动态链表 k->coef=x;k->exp=y; k->next二NULL;m->next二k; m=k;m是c链表的指针，继续执行q=q->next;图3-3 所示图3-4图3-4为多项式执行到q->next二NULL时的结果Pq图3-5当执行到q->next二NULL时，指针p后移，指针q指向B链表的首元素结点,继续以上循环。如图3-5所示图3-6当q指向空时，多项式相乘结束所有数据存入 c链表如图3-6所示。这样就完成了乘法运算，相乘后的C链表还可能出现指数相同的项，这时就需要合并。例图3-7所示，A、B两式相乘结果如下图3-7

14、用u、d指向头结点，e指向第二个结点，图3-7所示图3-8u 指针跟随e 指针，当d->exp=e->exp所指项上去。并将e当前所指项删除。图r=e;d->coef+二e->coef;u->n ext=e->n ext;项时，将e指针所指项的系数加到d指针3-8所示。/将相同项的后一项e赋予*r/后项系数与前项系数相加/将指针e所前一项指针指向e的后一一e=e->n ext;free(r);/释*r结点空间d图3-9这样就完成了一次合并。C链表变为图3-10图 3-10继续按上述方法直到将链表中所有同类项合并完为止图 3-11当d->next二

15、NULL 时结束。如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链表，一个指针跟随另一个当作后一个指针前驱指针，这样合并后释放就容易将前后结点链接上。

16、m,d,e,r,u指向C链表的指针综合以上分析，两个高次多项式相乘的算法如下：polynode *p,*q,*m,*k,*d,*e,*r,*u;int x,y;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=(poly no de*)malloc(sizeof(poly no de); k为

17、暂存相乘结果的动态链表x=p->coef*q->coef;/系数相乘y=p->exp+q->exp;/指数相加/ 建立空链表k->coef=x;k->exp=y;k->next=NULL;m->next=k;m=k;/将结果放入C链表中r=e;/将相冋项中的后项指针e赋予*rd->coef+=e->coef;/ 后项系数与前项系数相加/将指针e所有前一项指针指向e的后一一u->next=e->next;q=q->next;q=B->next;p=p->next;printf("n 未合并前多项式

18、为 :n"); output(C);合并同类项d=C->next;while(d!=NULL)u=d;e=u->next;while(e!=NULL) if(d->exp=e->exp)/ 输出未合并前多项式d指向C链表的头结点/当C链表不为空时u指向*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)没有指数相同的项。 n");el

19、se Printf("n 合并后 n");output(C);getch()'用尾插法生成多项式链表的算法如下：polynode *plcreate()polynote *H,*R,*S;int c, 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

20、->next=NULL;R=S; scanf("%d%d",%c,%e);return H;这个算法是按照课本上介绍的尾插法建链表算法加以修改而成。将没用的链表删 除以防浪费存储空间。算法如下：polynode *setnull(polynode *L)polynode *a,*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 (polyno

21、de *h) h=h->nxt; if(h!=NULL)if(h->coef!=0)/ 输出多项式的第一项if(h->exp!=0)/ 指数不为零时prin tf("%dxA%d",h->coef,h->exp);else printf("%d",h->coef); / 指数为零时else/ 第二项以后/ 当多项式不为空时，执行此循/ 系数大于零时h=h->next;while(h!=HULL)环if(h->coef>0)if(h->exp!=0)pri ntf("+%dxA%d&qu

22、ot;,h->coef,h->exp);else printf("+%d",h->coef);if(h->coef<0) / 系数小于零时if(h->exp!=0)prin tf("%dxA%d",h->coef,h->exp);else printf("%d",h->coef);if(h->coef=0) printf("");/ 系数等于零时h=h->next以上就是按照题目功能要求和数据结构要求，编写算法和各程序模块代码。4 上机调试4.1 调

23、试中遇到的问题和解决方法贰"H:S2Debugds. exe*BEI输入A式系数和指数值3坪3x>+-5x"65 6 M -1输入B式系数和指数值3 4-1-6 23 -113x>+-Sx*23Press ang key to continue.图4-11在幵始设计output函数时，当输入数据系数为负数是就出现了图4-1所示+、-号同时出现在表达式中。当时 output函数如下void output(po lynode *h)h=h->n ext;while(h!二HULL)if(h->n ext!=HULL)if(h->exp!=0)pri

24、n tf("%dA%d+",h->coef,h->exp);else pri ntf("%d+",h->coef);else if(h->exp!=0) else prin tf("%d",h->coef);h=h->next;当时我没想到判断系数正负问题， 所以才出现以上情况 ，在程序中曾加一个 if 语句判别 h->coef 大于 0、小于 0、还是等于 0，判别之后在进行输出改后为：while (n!=NULL) if(h->coef>0)if(h->exp!=0)pr

25、in tf("+%dxA%d",h->coef,h->exp);else printf("+%d",h->coef);/ 系数大于零时if(h->coef<0) if(h->exp1=0)prin tf("%dxA%d",h->coef,h->exp);else printf("%d",h->coef);if(h->coef=0) printf("");/ 系数小于零时/ 系数等于零时h=h->next;图4-2图4-2修改后输出

26、结果2当程序执行到合并指数相同项时就出现了错误。调试后发现执行完第一次while循环后指向c链表的指针e不在存储空间中，导致无法判断 while循环，仔细检查后，发现合并时将e指针所指结点释放后，没有给他指定新的结点。把指针e后移一位，这样就解决了问题。4.2时间空间复杂度的计算若多项式A有n项,多项式B有m项，则两多项式相乘时为 m*n ，接下来检验是否有同类项检查方法是每一项都要对比所以为(m* n)!,时间复杂度为0(m*n+(m*n )!)由于各个算法是基于动态链表而建成的，所以各算法的空间性能均较好。4.3设计体会这个题目不是很难，但是一幵始自己却觉的非常的吃力，不知从那里入手，下面

27、是我这次课程设计的一些感想：(1) 通过本设计实验又将数据结构中的链表的知识重新温习了一遍，并且自己能 够独立设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的 解决这些问题。（2）在课程设计中遇到了很多的问题，都是以前没有发现的，这些问题涉与的方 面很多，有的是 c 语言基础的，也有最近学习的数据结构的知识。通过本次课程设 计，让我发现了自己的不足。自己在学习知识上面的漏洞。希望通过弥补这些发现 的漏洞，提高自己的专业知识水平。（3）设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才 不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网（4

28、）实验过程中也走了很多的弯路，由于在开始设计的时候思路不是很清晰，对 于一些问题不能很好的提出解决问题的方法， 在设计过程中， 代码总是重复的修改， 在很多问题上，代码并不时最优的。相信在以后的学习中，随着知识的增多，问题 会逐渐得到解决。总之， 我付出了许多时间， 换来的是用任何东西都不能比的财富， 别人抢不走， 因为他是知识。因为自己知识有限所以程序不是很好，但它是我自己一步一步编写 出来。只有好好学习，自己将来才有出路。5 测试结果与其分析c、 H八鬲级參项式乘法冋题XD ebuc*输入A式系数和指数值斗5 6 8 2-1 斗耳”5+6耳八8输入B式系数和指数值4 12 3 21 2 -

29、14x'12+3xa21未合并前多项式为：16x"1T+12xrt26*24x"20+l8x"29没有扌旨数相同的项口图5-1图5-1两多项式相乘后没有指数相同项输出的结果s*鬲级峯瑕式乘法简蟲AD宕bugAdw.亡霍巳_ X输入口式系数和指数值4 5 G 8 2 -1>ix'5+6x"8输入B式系数和指数值4 8 7 23 -5 5 2 -18+7x"235x'5未合并前多项式为：16x1 3+28xa28-20xa10+24xa16+H2xa31-30xa13合异后:HMx'l 3+28x'2&

30、amp;-20x"1 0+24x'l 6+42x"31| 4k图5-2两多项式相乘后有指数相同项合并后输出的结果图5-26用户使用说明（ 1）给出任意两个高次多项式，只需按照多项式从左到右依次输入系数值、指数 值，当输入指数值为 -1 时结束。（由于程序设计的缺陷系数指数都要输入所以结束之前系数 值可随便输入不影响运算结果。（2）程序中指数、系数定义的是整型，所以表达式中系数值、指数值不能超出整 型范围。（3）输入是正数直接输入，负数要加负号。指数不能选择-1 。参考文献1王昆仑 ,李红等编著 . 数据结构与算法 . 北京 :中国铁道出版社 ,2007. 2苏仕华等

31、编著 . 数据结构课程设计 . 北京：机械工业出版社 ,2005.3苏仕华编著 . 数据结构与算法解析 . 合肥 :中国科学技术大学出版社 ,2004.4 郭嵩山等著 . 国际大学生程序设计竞赛例题解 . 北京 :电子工业出版社 ,2008.5 刘大有 ,唐海鹰等编著 . 数据结构 . 北京 :高等教育出版社 ,2001.6 徐孝凯编著 .数据结构实用教程 . 北京 : 清华大学出版社 ,1999.7 严蔚敏 ,陈文博编著 . 数据结构与算法教程 . 北京 : 清华大学出版社 ,2001.8 刘振安 ,刘燕君等编著 . C 程序设计课程设计 . 北京: 机械出版社 ,2004.9 胡学钢 .

32、数据结构与算法设计指导 . 北京: 清华大学出版社 , 1999.附录：程序源代码/ 程序名称： GCDXS.CPP/ 程序功能：实现任意两个高次多项式的加法和乘法运算/ 程序作者：王帆/* 多项式加法和乘法示例 */#include <list>#include <iostream>#include <cassert>/ 定义多项式的项类/ 多项式系数/ 多项式指数/ 初始化项的系数和指数using namespace std;class term public:int coef;int exp;term( int c=0,int e=0):coef(c)

33、,exp(e);/ 定义多项式类class PolyArith private: list<term> m_poly_list_first; list<term> m_poly_list_second; list<term> m_poly_list_result; 员函数 ,用以乘法时的调用/ 存储第一个多项式/ 存储第二个多项式/ 用以存储运算结果/ 多项式私有成list<term> Poly_add(list<term>&poly_list_first, list<term>&poly_list_sec

34、ond)list<term> poly_list_result; / 用以存储运算结果list<term>:iterator iter_first = poly_list_first.begin(); list<term>:iterator iter_second = poly_list_second.begin(); / 对两个链表迭代器都没有指到结尾的情形该 while 循环针while(iter_first != poly_list_first.end()&&iter_second != poly_list_second.end() t

35、erm t_temp;term t_first = (term)*iter_first;term t_second = (term)*iter_second;if(t_first.exp>t_second.exp)poly_list_result.push_back(t_first); iter_first+;else if(t_second.exp>t_first.exp) poly_list_result.push_back(t_second); iter_second+;else t_temp.coef=t_first.coef+t_second.coef; t_temp.e

36、xp=t_first.coef;poly_list_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_secon

37、d+) poly_list_result.push_back(*iter_second);return poly_list_result;public: / 输入函数，用以输入多项式void Poly_input()int n; cout<<" 请输入第一个多项式的项数： "<<endl;cin>>n; cout<<" 按降幂输入第一个多项式的每一项的系数和指数： " cout<<endl; for(int i=1;i<=n;i+)term t_temp; cout<<&quo

38、t;请输入第 "<<i <<" 项系数和指数 ,以 'enter' 为界： "cout<<endl;cin>>t_temp.coef;cin>>t_temp.exp; m_poly_list_first.push_back(t_temp);n = 0;cout<<" 请输入第二个多项式的项数： "<<endl;cin>>n;cout<<" 按降幂输入第二个多项式的每一项的系数和指数： "cout<

39、<endl;for(int j=1;j<=n;j+)term t_temp;cout<<" 请输入第 "<<j <<" 项系数和指数，以 'enter' 为界 cout<<endl;cin>>t_temp.coef;cin>>t_temp.exp;m_poly_list_second.push_back(t_temp);/ 输出函数，用以输出多项式void Poly_output()/ 输出多项式的每一项/ 用以指向输出多项式的第一个元素list<term&g

40、t;:iterator iter = m_poly_list_result.begin();for(;iter!=m_poly_list_result.end();)term t_temp=*iter;cout<vt_temp.coefvv"xA"v<t_temp.exp;if(+iter!=m_poly_list_result.end() cout<<"+"cout<<endl;/ 加法函数，其基本思想同上边的私有成员函数 Poly_add()/ 此处不带参数，多项式运算对象为私有数据成员 void Poly_add

41、()list<term>:iterator iter_first = m_poly_list_first.begin();list<term>:iterator iter_second = m_poly_list_second.begin(); 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.exp>t_second.exp) m_poly_list_result.push_back(t_first);iter_first+; else if(t_second.exp>t_first.exp)m_poly_list_result.push_back(t_second);iter_second+;elset_temp.c