一元多项式加减乘除运算程序.doc

1、韶关学院计算机科学学院数据结构课程设计题 目：一元多项式运算学生姓名：XXX学 号：XXXXXXXXXX专 业：计算机科学与技术班 级：XXXXXXX 指导教师姓名及职称：XXX 讲师 起止时间： 2012 年 2 月 2012 年 4 月1 需求分析1.1 课题背景及意义随着计算机时代的到来与快速发展，计算机的处理运算能力远远超出了人们日常的运算能力。它以运行速度之快在人们的日常生活中大大地节约了人们的时间，并且准确度高。因此当人们面对多项式计算这类较复杂的计算问题时，计算机无疑是我们的好帮手。对此我们设计出多项式运算程序具有其意义。数据结构课程设计是一门实践性的计算机课程，为了学好这门课程

2、，必须在掌握理论知识的同时，加强上机实践。通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.2 课题要求 A. 支持一元多项式的运算器B. 能够正确输入并显示输入多项式的每一项C. 要求将输入的多项式F（X），G(X)可进行加，减，乘运算，并显示结果D. 选做内容：除法和实现多项式的取反并实现取反之后的加减乘除运算1.3 软件格式规定A输入的形式 :按程序菜单的数字选择输入，并按提示输入多项式。按照（系数 指数）的

3、格式进行输入并以输入（0 0）作为结束输入的控制。 B. 程序所能达到的功能 :能够进行多项式的输入，显示，加，减，乘，除，取反运算。C.输出的形式:按照多项式的数学表达式的形式输出，形如：F(x)=8X6+4X5-2X4-123X3-X1+10 D.测试的数据：1)、正确的输入：以下是进行测试所要输入的多项式：f(x)=8x6+4x5-2x4-123x3-x+10g(x)=2x3-5x2+x正确的运算结果：相加：f(x)+g(x)=8x6+4x5-2x4-121x3-5x2+10相减：f(x)-g(x)=8x6+4x5-2x4-125x3+5x2-2x+10相乘：=16x9-32x8-16x

4、7-232x6+613x5-125x4+25x3-51x2+10x相除：f(x)g(x)=4x3+12x2+27x 余数=-27x2-x+101.4 设计目标A. 软件名称：一元多项式运算器B. 软件组成：XXXXXXX.exe（dos系统应用程序） C. 制作平台及相关调试工具：Win32 ； Microsoft Visual Studio 2010D. 运行环境：dos/winxp/win7E. 性能特点：（1）运算器由一个可执行文件组成，具有以下特点:XXXXXXX.exe为dos系统应用程序，体积小，高效快捷，适用范围广，兼容性好。（2）输入的多项式各项的系数为浮点型，指数为整型。（3

5、）XXXXXXX.exe（dos系统应用程序）的输入和输出形式：菜单数字选择按回车键按要求输入多项式选择菜单对应运算法则的数字显示运算结果或下级菜单（5）运行时间较短，精确度高，输出形式整齐好看。（6）个别其他功能可进行再扩展。2 概要设计2.1问题解决的思路概述首先是确定结构化程序设计的流程图，利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除，取反运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块、实现多项式取反的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。最后，编写main

6、主函数以实现对多项式输入输出以及加、减、乘、除、取反操作，调试程序并将不足的地方加以修改。总而言之，就是先用自顶向下、逐步细化的设计方法来分析并画出程序设计流程图；然后用自下而上、逐步积累的设计方法来写出程序。2.2 相关函数介绍说明 （1）程序定义的数据结构类型为线性表的链式存储结构类型变量： typedef struct linknode（2）程序定义的其它函数：linnode *Sort(linnode *S);/多项式按指数从大到小排序linnode *Negate(linnode *head);/取反操作linnode *CreateList(); /创建多项式Void ShowLi

7、st(linnode *head) ; /显示多项式linnode *Copy(linnode *copy); /拷贝多项式（因为做减法运算时会破坏原来输入的多项式）linnode *SearchList(linnode *head,int x);/查找函数Linnode *Mulr(linnode *s,linnode *p)/用一个节点去乘与一个多项式（辅助除法运算）Linnode *AddSame(linnode *head);/和并多项式的同类项linnode *Add(linnode *head1,linnode *head2); / 加法linnode *Mul(linnode *

8、head1,linnode *head2); / 乘法linnode *Sub(linnode *head1,linnode *head2); / 减法Void Div(linnode *head1,linnode *head2)/除法int main( )/主函数2.3 主程序的流程基函数调用说明（1）主程序的简要流程图选择界面菜单对应操作的数字结束执行完选择的功能后返回结果并回到程序主界面调用功能对应的函数main()图1 主程序流程图（2）各程序模块之间的层次（调用）关系 输入模块“CreateList（）”，首先按提示逐项输入多项式的每一项，当接收到“0 0”时终止输入，此时调用“So

9、rt（）”进行按指数降序排列后直接返回多项式的链表头指针。 加法运算模块“Add（）”，首先将两个多项式连接成一个多项式，再调用“AddSame（）”函数进行合并连接后的多项式的同类项并返回头指针。减法运算程序模块“Sub( )”，首先判断多项式1是否为空，不为空时调用“SearchList（）”进行查找操作，查找到的结果与多项式1作减法后删除多项式2中查找到的对应项。多项式2中剩余的项取反后连接到多项式1的尾部，再调用“AddSame（）”进行合并同类项操作并返回头指针。 乘法运算程序模块“Mul( )”， 首先判断输入的多项式两个不为空时进行多项式相乘运算，并将结构存储在新创建的多项式中。

10、再调用“AddSame（）”进行合并同类项后返回头指针。除法运算模块“Div”，首先判断第一个多项式的最高次数大于或等于第二多项式的最高次数，然后再用第一个多项式的第一项去除于第二个多项式的第一项，所得的商的第一项，然后调用“Mulr（）”用商的第一项去乘第二个多项式，用第一个多项式减去乘得的多项式，所得的差多项式再与第二个多项式的最高指数项判断。直到第二多项式的最高次数项大于与之判断的多项式时结束运算，并调用“ShowList（）”输出相应的结果。 显示函数“ShowList（）”，首先调用“Sort（）”进行排序，再按格式输出多项式的每一项。3 详细设计3.1 多项式存储的实现 多项式是由

11、若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。根据所学数据结构，采用线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为：typedef struct linknode /链表节点的结构体float coe; /系数int index; /指数struct linknode *next; linnode; 3.2 加减乘除算法 在多项式运算的程序设计中，每一部分都会调用一些其它函数来辅助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清

12、单。3.2.1加法运算的实现开始 加法计算还是比较容易实现的，将两个传递过来的多项式链表进行复制操作（加法运算会破坏原来两个链表的结构），再将复制出来的两链表进行连接操作，即将第一个多项式链表的尾指针next指向第二个链表的第一个节点，最后进行合并同类项操作。 复制两个多项式连接两个多项式合并连接好的多项式的同类项返回合并同类项后的多项式头指针结束图2 加法运算原理图对于加法运算我们并不用考虑多项式是否为空的情况，为空时连接后合并同类项处理后仍然返回空的多项式。3.2.2减法运算的实现 多项式的减法与加法类似，先将传递进来的两个多项式进行判断是否为空，若被减数为空时，减数按逐项系数取反操作。不

13、为空时，被减数的每一项的指数去查找减数中与之对应的项，找到后并同类项相减，把值赋给被减数与之对应的同类项，再在减数中删除查找到的那个项（节点）。彻底查找后，将减数剩余的节点取反后再连接到被减数的末尾，在进行合并同类项操作并返回头指针。开始被减数是否为空 是被减数每一项查找减数与之对应的项 否 没找到找到加法操作，并将值赋给被减数 被减数与减数取反后连接 合并同类项 结束 图3 减法运算原理图3.2.3乘法运算的实现开始 多项式的乘法运算，首先是判断多项式都不为空，为空时直接输出结过为0。否则将其中一个多项式的每一项去乘于另外个多项式的每一项，将乘得每一项的结果连接成一个完整的多项式，然后在对其

14、进行合并同类项操作。最后返回结果头指针。判断两个多项式是否都为空多项式两两相乘 否 合并同类项 结束 是图4 乘法运算原理图3.2.4除法运算的实现 首先将相除的两个多项式降序排列，两个多项式为非空时。判断被除数的最高次幂大于或等于除数的最高次幂，然后用被除数的第一项去除于除数的第一项所得商的第一项，在用所得商的这一项去乘除数的所有项所得的多项式与被减数作差，在用所得差作为被减数。循环上述步骤，当被减数最高次幂小于减数最高次幂是终止循环，输出相应的结果。开始判断两个多项式是否都为空 判断最高次幂被减数=减数 否相除得商的第一项 是 乘与被除数被除数减去所得多项式得到的结果作为被除数输出商和余数

15、否 结束 是图5 除法运算原理图在程序设计时应注意: 由于在输入多项式的时候就调用了Sort（）函数进行降序排序，因此在除法运算时并不需要从新排序。3.3 函数调用关系图此函数调用关系图主要描述了四则运算的实现、取反及实现各运算所要调用的函数，详情还请看程序清单。Sort()排序ShowList()显示输出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索节点AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()Div除法运算Copy()备份Sub()减法运算AddSame()合并Sort

16、()排序Negate()取反Copy()备份Mul()乘法运算Add()加法运算CreateList()创建main（）选择菜单图6函数调用关系图4 调试分析表1 调试过程情况表序号时间出现问题解决方法12012-3-25做除法时由于没有考虑到当两个多项式最高次幂相等的情况，出现了输出结果错误的情况加入多项式最高次幂相等的判断情况22010-3-30乘法算法指针冲突将乘法没新建一个节点是next=NULL32010-4-5由于指针越界ShowList()算法错误加入next指针的约束条件42010-4-6部分未能相加调准节点的循环遍历条件5 用户使用说明（1）运行XXXXXXX.exe应用程序

17、后会出现主界面； （2）选择输入多项式，按下回车键；（3）按要求输入两个多项式，按下回车键；（4）选择所要做的运算或操作，按下回车。图7 主界面效果图 6 测试结果应用程序测试结果：图8 按1输入多项式 图9 输入测试数据图10 显示输入的测试多项式图11 多项式相加图12 多项式相减图13 多项式相乘图14 多项式相除图15 多项式取反操作菜单参考文献1陈元春，王中华等.实用数据结构M.北京：中国铁道出版社，2011.22 C语言程序设计(第三版)-谭浩强附录：程序清单本程序设计由101150130贺荣根.cpp组成#include stdlib.h#include iostreamtype

18、def struct linknode /定义节点的结构体float coe; int index;struct linknode *next; linnode; /定义节点类型linnkodelinnode *Sort(linnode *S) /多项式按降序排列linnode *z,*s;s=S;z=new linnode;z-next=NULL;while(S-next!=NULL)for(linnode *x=S-next;x-next!=NULL;x=x-next)if(S-next-indexnext-index) z-coe=x-next-coe; x-next-coe=S-nex

19、t-coe;S-next-coe=z-coe;z-index=x-next-index;x-next-index=S-next-index;S-next-index=z-index;S=S-next;return s;linnode *Negate(linnode *head) /多项式取反 linnode *p; p=head;while(head-next!=NULL)head-next-coe=-(head-next-coe);head=head-next;return p;linnode *CreateList() /创建线性表int n=0,z=1;linnode *p,*s,*he

20、ad;float coe;int index;head=new linnode;head-next=NULL;p=head;while(z) printf(ntt请输入：); scanf(%f,&coe); scanf(%d,&index); getchar(); if(coe!=0|index!=0) s=new linnode; s-coe=coe; s-index=index; p-next=s; s-next=NULL; p=s; else z=0;return Sort(head);void ShowList(linnode *head)/ 显示线性表linnode *P= Sort

21、(head);if(head-next=NULL)printf(多项式为空！ );else while(P-next!=NULL) if(P-next-coe)!=0)(P-next-coe)0?printf(+%5.2f ,P-next-coe):printf(%5.2f ,P-next-coe); (P-next-index)!=0?printf(X%d,P-next-index):printf(); P=P-next;linnode *Copy(linnode *copy) linnode *d,*head3,*a;d=new linnode;head3=d;if(copy-next!=

22、NULL)while(copy-next!=NULL)a=new linnode;a-coe=copy-next-coe;a-index=copy-next-index;d-next=a;a-next=NULL;d=a;copy=copy-next;return head3;elsereturn copy;linnode *SearchList(linnode *head,int x) /查找函数linnode *p;if(head!=NULL)p=head-next;while(p!=NULL&p-index!=x) p=p-next;if(p!=NULL)return p;elseretu

23、rn NULL;else return NULL;linnode *AddSame(linnode *head) /合并同类项linnode *heads,*s,*z;heads=head;while(head-next!=NULL)linnode *x=SearchList(head-next,head-next-index); /搜索相同节点if(x!=NULL)head-next-coe+=x-coe;for(s=head-next;(s-next-index)!=x-index;)s=s-next;s-next=x-next;delete x;else head=head-next;r

24、eturn heads;linnode *Sub(linnode *head1,linnode *head2) /多项式做减法函数,并向函数传递两个链表（即两个待相加的多项式）linnode *s,*p,*head3; /定义三个节点指针变量s=head1; head3=s; /用于存储第一个传进来的链表的头指针p=head2;while(s-next!=NULL) /当第一个链表不为空时依次循环获取每一个节点的index值linnode *z=SearchList(p,s-next-index); /用于搜索第一链表的每个节点的index值在第二链表中是否存在并返回其节点if(z!=NULL

25、) /条件为真是，即在第二链表中查找到与第一链表中相同index值的节点s-next-coe-=z-coe; while(p-next-index)!=z-index) /用于查找搜索到节点在第二链表中的位置p=p-next;p-next=z-next; delete z; /在第二链表中删除查找到的节点 s=s-next; /头指针向后移动for(s-next=head2-next;s-next!=NULL;s=s-next)s-next-coe=-(s-next-coe);return AddSame(head3); /返回第一链表的头指针linnode *Add(linnode *hea

26、d1,linnode *head2) /多项式加法函数linnode *s,*p,*d,*a,*head3;s=head1;p=head2;d=new linnode;head3=d;while(s-next!=NULL)a=new linnode;a-coe=s-next-coe;a-index=s-next-index;d-next=a;a-next=NULL;d=a;s=s-next;while (p-next!=NULL)a=new linnode;a-coe=p-next-coe;a-index=p-next-index;d-next=a;a-next=NULL;d=a;p=p-ne

27、xt;return AddSame(head3); /合并同类项后返回linnode *Mul(linnode *s,linnode *p) /多项式作乘法运算函数，两个参数用于传进两个待相乘的多项式链表linnode *head1,*head2,*head3,*n,*head4; /定义链表指针用于存储多项式的节点指针head1=s; /将第一个用于存储多项式的链表的头指针赋值给head1head2=p; /将第二个用于存储多项式的链表的头指针赋值给head2head4=new linnode;/创建一个头节点head4-next=NULL;head3=head4; /用于存储新创建的链表的

28、头指针if(head1-next!=NULL&head2-next!=NULL) /两个多项式不为空时for(;head1-next!=NULL;head2=p,head1=head1-next) /此循环用于实现多项式中的乘法运算for(;head2-next!=NULL;head2=head2-next) /此循环用于实现多项式中的乘法运算 n=new linnode; /新建一个节点用于存储多项式相乘之后每一项的结果n-coe=(head1-next-coe*head2-next-coe); /系数相乘n-index=(head1-next-index+head2-next-index)

29、; /指数相加head3-next=n;n-next=NULL;head3=n; return AddSame(head4);elsereturn head4;linnode *Mulr(linnode *s,linnode *p) /一个节点乘与整个多项式（辅助除法运算）linnode *head2,*n,*head1,*head;head2=new linnode;head2-next=NULL;head=head2;head1=p;while(p-next!=NULL&s-coe!=0)n=new linnode;n-coe=s-coe*p-next-coe;n-index=s-inde

30、x+p-next-index;n-next=NULL;head2-next=n;head2=n;p=p-next;p=head1;return head;void Div(linnode *head1,linnode *head2) /除法linnode *temp1,*head3,*head4,*z;temp1=new linnode;temp1-next=NULL;head3=temp1; /商while(head1!=NULL&head1-next!=NULL&head1-next-index=head2-next-index) /判断指数大小z=new linnode;z-coe=he

31、ad1-next-coe/head2-next-coe;z-index=head1-next-index-head2-next-index;temp1-next=z;z-next=NULL;temp1=z;head4=Mulr(z,head2);linnode *head5=head1;while(head1-next!=NULL)head1=head1-next;head4=Negate(head4); /取反head1-next=head4-next;head1=AddSame(head5); /合并while(head1-next!=NULL&head1-next-coe=0)head1

32、=head1-next; printf(nF(X)/G(X);printf(n商：);ShowList(head3);printf(n余数：);ShowList(head1);int main() system(color 0B);int choice,j=1;linnode *head1,*head2,*add,*sub,*mul,*copy1,*copy2;add=new linnode;sub=new linnode;mul=new linnode;head1=new linnode; head2=new linnode;copy1=new linnode;copy2=new linno

33、de;head1-next=NULL; head2-next=NULL;head1-index=NULL; head2-index=NULL;add-next=NULL;sub-next=NULL;mul-next=NULL;copy1-next=NULL;copy2-next=NULL;while(j)printf(n);printf(ntt 多项式运算 );printf(ntt*); printf(ntt*);printf(ntt* 1-输入多项式 *);printf(ntt* 2-显 示 *);printf(ntt* 3-相 加 *);printf(ntt* 4-相 减 *);print

34、f(ntt* 5-相 乘 *);printf(ntt* 6-相 除 *);printf(ntt* 7-多项式取反 *);printf(ntt* 0-退 出 *);printf(ntt*); printf(ntt*);printf(ntt 请选择菜单号（0-6）进行操作:);scanf(%d,&choice);getchar();if(choice=1)head1-next=NULL; head2-next=NULL;printf(ntt请逐个输入第1个多项式的结点，以“0 0”作为结束标记! n); head1=CreateList();printf(ntt请逐个输入第2个多项式的结点，以“0

35、 0”作为结束标记! n); head2=CreateList(); system(cls); printf(n多项式成功输入，请选择计算方式！);elseif(choice=2) system(cls);printf(n多项式1：F(X)=);ShowList(head1);printf(n多项式2：G(X)=);ShowList(head2);elseif(choice=3) system(cls); if(head1-next!=NULL|head1-next!=NULL) add=Add(head1,head2); printf(n多项式：F(X)+G(X)=); ShowList(add); else printf(请输入多项式！);elseif(choice=4) system(cls); if(head1-next!=NULL|head1-next!=NULL