数据结构程序设计作业——《一元多项式的四则运算》.doc

《数据结构程序设计作业——《一元多项式的四则运算》.doc》由会员分享，可在线阅读，更多相关《数据结构程序设计作业——《一元多项式的四则运算》.doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构程序设计作业一元多项式的四则运算.精品文档.教学单位 学生学号 数据结构 课程设计报告书题目一元多项式四则运算学生姓名 专业名称 指导教师 目 录1 问题描述- 2 -2 功能描述- 2 -2.1 课题要求- 2 -2.2 软件格式规定- 2 -3 设计- 2 -3.1 相关函数介绍说明- 2 -3.2 主程序的流程基函数调用说明- 3 -4 程序设计- 5 -4.1 多项式存储的实现- 5 -4.2 加减乘除算法- 5 -4.2.1加法运算的实现-5 -4.2.2减法运算的实现- 6 -4.2.3乘法运算的实现- 7 -4.2.4除

2、法运算的实现- 7 -4.3 函数调用关系图- 8-5 运行测试- 9-6 设计小结- 12-参考文献- 12-谢 辞- 13-附录：程序清单- 14-1 问题描述1.1首先是确定结构化程序设计的流程图，利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。最后，编写main主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。总而言之，就是先用自顶向下、逐步细化的设计

3、方法来分析并画出程序设计流程图；然后用自下而上、逐步积累的设计方法来写出程序。2 功能描述2.1 课题要求 A. 支持一元多项式的运算器B. 能够正确输入并显示输入多项式的每一项C. 要求将输入的多项式F（X），G(X)可进行加，减，乘，除运算，并显示结果2.2 软件格式规定A输入的形式 :按程序菜单的数字选择输入，并按提示输入多项式。按照（系数 指数）的格式进行输入并以输入（0 0）作为结束输入的控制。 B. 程序所能达到的功能 :能够进行多项式的输入，显示，加，减，乘，除运算。C.输出的形式:按照多项式的数学表达式的形式输出，形如：F(x)=X2+2X3-2X4-3X3-X1+103 设计

4、3.1 相关函数介绍说明 （1）程序定义的数据结构类型为线性表的链式存储结构类型变量： typedef struct linknode（2）程序定义的其它函数：linnode *Sort(linnode *S);/多项式按指数从大到小排序linnode *CreateList(); /创建多项式Void ShowList(linnode *head) ; /显示多项式linnode *Copy(linnode *copy); /拷贝多项式（因为做减法运算时会破坏原来输入的多项式）linnode *SearchList(linnode *head,int x);/查找函数Linnode *Mul

5、r(linnode *s,linnode *p)/用一个节点去乘与一个多项式（辅助除法运算）Linnode *AddSame(linnode *head);/和并多项式的同类项linnode *Add(linnode *head1,linnode *head2); / 加法linnode *Mul(linnode *head1,linnode *head2); / 乘法linnode *Sub(linnode *head1,linnode *head2); / 减法Void Div(linnode *head1,linnode *head2)/除法int main( )/主函数3.2 主程序的

6、流程基函数调用说明（1）主程序的简要流程图选择界面菜单对应操作的数字结束执行完选择的功能后返回结果并回到程序主界面调用功能对应的函数main()图1 主程序流程图（2）各程序模块之间的层次（调用）关系 输入模块“CreateList（）”，首先按提示逐项输入多项式的每一项，当接收到“0 0”时终止输入，此时调用“Sort（）”进行按指数降序排列后直接返回多项式的链表头指针。 加法运算模块“Add（）”，首先将两个多项式连接成一个多项式，再调用“AddSame（）”函数进行合并连接后的多项式的同类项并返回头指针。减法运算程序模块“Sub( )”，首先判断多项式1是否为空，不为空时调用“Searc

7、hList（）”进行查找操作，查找到的结果与多项式1作减法后删除多项式2中查找到的对应项。多项式2中剩余的项取反后连接到多项式1的尾部，再调用“AddSame（）”进行合并同类项操作并返回头指针。 乘法运算程序模块“Mul( )”， 首先判断输入的多项式两个不为空时进行多项式相乘运算，并将结构存储在新创建的多项式中。再调用“AddSame（）”进行合并同类项后返回头指针。除法运算模块“Div”，首先判断第一个多项式的最高次数大于或等于第二多项式的最高次数，然后再用第一个多项式的第一项去除于第二个多项式的第一项，所得的商的第一项，然后调用“Mulr（）”用商的第一项去乘第二个多项式，用第一个多项

8、式减去乘得的多项式，所得的差多项式再与第二个多项式的最高指数项判断。直到第二多项式的最高次数项大于与之判断的多项式时结束运算，并调用“ShowList（）”输出相应的结果。 显示函数“ShowList（）”，首先调用“Sort（）”进行排序，再按格式输出多项式的每一项。4 程序设计4.1 多项式存储的实现 多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。根据所学数据结构，采用线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为：typedef struct linknode /链表节点的结构体float coe;

9、 /系数int index; /指数struct linknode *next; linnode; 4.2 加减乘除算法 在多项式运算的程序设计中，每一部分都会调用一些其它函数来辅助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘除运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。4.2.1加法运算的实现开始 加法计算还是比较容易实现的，将两个传递过来的多项式链表进行复制操作（加法运算会破坏原来两个链表的结构），再将复制出来的两链表进行连接操作，即将第一个多项式链表的尾指针next指向第二个链表的第一个节点，最后进行合并同类项操作。 复制两个多项式连接

10、两个多项式合并连接好的多项式的同类项返回合并同类项后的多项式头指针结束图2 加法运算原理图对于加法运算我们并不用考虑多项式是否为空的情况，为空时连接后合并同类项处理后仍然返回空的多项式。4.2.2减法运算的实现多项式的减法与加法类似，先将传递进来的两个多项式进行判断是否为空，若被减数为空时，减数按逐项系数取反操作。不为空时，被减数的每一项的指数去查找减数中与之对应的项，找到后并同类项相减，把值赋给被减数与之对应的同类项，再在减数中删除查找到的那个项（节点）。彻底查找后，将减数剩余的节点取反后再连接到被减数的末尾，在进行合并同类项操作并返回头指针。开始被减数是否为空 是被减数每一项查找减数与之对

11、应的项 否 找到未找到加法操作，并将值赋给被减数被减数与减数取反后连接 合并同类项 结束 图3 减法运算原理图4.2.3乘法运算的实现开始 多项式的乘法运算，首先是判断多项式都不为空，为空时直接输出结过为0。否则将其中一个多项式的每一项去乘于另外个多项式的每一项，将乘得每一项的结果连接成一个完整的多项式，然后在对其进行合并同类项操作。最后返回结果头指针。判断两个多项式是否都为空多项式两两相乘 否 合并同类项 结束 是图4 乘法运算原理图4.2.4除法运算的实现 首先将相除的两个多项式降序排列，两个多项式为非空时。判断被除数的最高次幂大于或等于除数的最高次幂，然后用被除数的第一项去除于除数的第一

12、项所得商的第一项，在用所得商的这一项去乘除数的所有项所得的多项式与被减数作差，在用所得差作为被减数。循环上述步骤，当被减数最高次幂小于减数最高次幂是终止循环，输出相应的结果。开始判断两个多项式是否都为空 判断最高次幂被减数=减数 否相除得商的第一项 是 乘与被除数被除数减去所得多项式得到的结果作为被除数输出商和余数否 结束 是图5 除法运算原理图在程序设计时应注意: 由于在输入多项式的时候就调用了Sort（）函数进行降序排序，因此在除法运算时并不需要从新排序。4.3 函数调用关系图此函数调用关系图主要描述了四则运算的实现、取反及实现各运算所要调用的函数，详情还请看程序清单。Sort()排序Sh

13、owList()显示输出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索节点AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()Div除法运算Copy()备份Sub()减法运算AddSame()合并Sort()排序Copy()备份Mul()乘法运算Add()加法运算CreateList()创建main（）选择菜单图6函数调用关系图5 运行测试图7 主界面效果图 图8 按1输入多项式 图9 输入测试数据图10 显示输入的测试多项式图11 多项式相加图12 多项式相减图13 多项式相乘图1

14、4 多项式相除6 设计小结数据结构课程设计是一门实践性的计算机课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。参考文献1 严蔚敏吴伟民数据结构（C语言版）北京：清华大学出版社2002 2 谭浩强 C语言程序设计(第三版) 谢 辞感谢李志敏老师的殷切辅导，给予我帮助。帮我答疑解惑，从未知的迷茫道路上，渐渐走向光明的成功之路。附录：程序清单#include

15、stdlib.h#include iostreamtypedef 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

16、=x-next-coe; x-next-coe=S-next-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 *CreateList() /创建线性表int n=0,z=1;linnode *p,*s,*head;float coe;int index;head=new linnode;head-next=NULL;p=head;while(z) printf(ntt请输入：); scanf(%f,&coe); s

17、canf(%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(head);if(head-next=NULL)printf(多项式为空！ );else while(P-next!=NULL) if(P-next-coe)!=0)(P-next-coe)0?printf(

18、+%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!=NULL)while(copy-next!=NULL)a=new linnode;a-coe=copy-next-coe;a-index=copy-next-index;d-next=a;a-next=NULL;

19、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;elsereturn NULL;else return NULL;linnode *AddSame(linnode *head) /合并同类项linnode *heads,*s,*z;heads=head;while(head-n

20、ext!=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;return heads;linnode *Sub(linnode *head1,linnode *head2) /多项式做减法函数,并向函数传递两个链表（即两个待相加的多项式）linnode *s,*p,*head

21、3; /定义三个节点指针变量s=head1; head3=s; /用于存储第一个传进来的链表的头指针p=head2;while(s-next!=NULL) /当第一个链表不为空时依次循环获取每一个节点的index值linnode *z=SearchList(p,s-next-index); /用于搜索第一链表的每个节点的index值在第二链表中是否存在并返回其节点if(z!=NULL) /条件为真是，即在第二链表中查找到与第一链表中相同index值的节点s-next-coe-=z-coe; while(p-next-index)!=z-index) /用于查找搜索到节点在第二链表中的位置p=p

22、-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 *head1,linnode *head2) /多项式加法函数linnode *s,*p,*d,*a,*head3;s=head1;p=head2;d=new linnode;head3=d;while(s-next!=N

23、ULL)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-next;return AddSame(head3); /合并同类项后返回linnode *Mul(linnode *s,linnode *p) /多项式作乘法运算函数，两个参数用于传进两个待相乘的多项式链表linno

24、de *head1,*head2,*head3,*n,*head4; /定义链表指针用于存储多项式的节点指针head1=s; /将第一个用于存储多项式的链表的头指针赋值给head1head2=p; /将第二个用于存储多项式的链表的头指针赋值给head2head4=new linnode;/创建一个头节点head4-next=NULL;head3=head4; /用于存储新创建的链表的头指针if(head1-next!=NULL&head2-next!=NULL) /两个多项式不为空时for(;head1-next!=NULL;head2=p,head1=head1-next) /此循环用于实现

25、多项式中的乘法运算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); /指数相加head3-next=n;n-next=NULL;head3=n;return AddSame(head4);elsereturn head4;linnode *Mulr(linnode *s,lin

26、node *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-index+p-next-index;n-next=NULL;head2-next=n;head2=n;p=p-next;p=head1;return head;void Div(linnode *head1,linnode

27、 *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=head1-next-coe/head2-next-coe;z-index=head1-next-index-head2-next-index;temp1-next=z;z-next=NULL;temp1=z;head4

28、=Mulr(z,head2);linnode *head5=head1;while(head1-next!=NULL)head1=head1-next;head1-next=head4-next;head1=AddSame(head5); /合并while(head1-next!=NULL&head1-next-coe=0)head1=head1-next; printf(nF(X)/G(X);printf(n商：);ShowList(head3);printf(n余数：);ShowList(head1);int main()system(color 0F);int choice,j=1;li

29、nnode *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 linnode;head1-next=NULL; head2-next=NULL;head1-index=NULL; head2-index=NULL;add-next=NULL;sub-next=NULL;mul-next=NULL;copy1-next=NULL;copy

30、2-next=NULL;while(j)system(Color E0);printf(n);printf(ntt 一 元 多 项 式 的 四 则 运 算 );printf(n);printf(ntt 1-输入多项式 );printf(ntt 2-显示多项式 );printf(ntt 3-相 加 );printf(ntt 4-相 减 );printf(ntt 5-相 乘 );printf(ntt 6-相 除 );printf(ntt 0-退 出 ); printf(n);printf(ntt 请选择菜单号（0-6）进行操作:);scanf(%d,&choice);getchar();if(ch

31、oice=1)head1-next=NULL; head2-next=NULL;printf(ntt请逐个输入第1个多项式的结点，以“0 0”作为结束标记! n); head1=CreateList();printf(ntt请逐个输入第2个多项式的结点，以“0 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(he

32、ad2);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) copy1=Copy(head1); copy2=Copy(head2); sub=Sub(copy1,copy2); printf(n多项式：F(X)-G(X)=); ShowList(sub);else printf(请输入多项式！);elseif(choice=5)system(cls);if(head1-next!=NULL&head2-next!=NULL) mul=Mul(head1,head2); printf(n多项式：F(X)*G(X)=);ShowList(mul);else if(head1-next=NULL|head1-next=NULL)printf(n多项式：F(X)*G(X)=0);elseprintf(请输入多项式！);return 0;