一元多项式_课程设计

1、数据结构课程设计题目： 一元多项式计算器 学生姓名： 刘胜寒 学号： 系别： 计算机科学与技术 专业： 计算机科学与技术 指导教师： 马竹根 讲师 起止日期： 2012.3.292012.4.5 2012年 4月 9 日目 录一元多项式操作的设计与开发I摘 要I关键词I1 前言12 需求分析22.1 范围22.1.1 标识22.1.2 系统概述22.2 需求概述32.2.1 系统目标32.2.2 运行环境32.2.3 实验环境3Windows 2000 以上，C-Free任意版本。32.2.4 用户的特点32.3功能需求33 概要设计43.1 范围43.1.1 标识43.1.2 系统概述43.

2、2 系统结构44 系统详细设计54.1 范围54.1.1 标识54.1.2 系统概述54.2 详细设计说明54.2.2 字符串处理算法64.2.2 提取多项式各个参数算法设计74.2.3 加减算法设计94.2.4 乘法算法设计104.2.5 化简算法设计115 测试说明125.1 范围125.1.1 标识125.1.2 系统概述125.2 测试计划及预期结果135.3 具体测试情况13总结14致 谢15附录16 一元多项式操作的设计与开发摘 要系统本次试验依据2012年怀化学院10级数据结构实验要求，较完善的对题目进行了分析，理解和编程，程序思路清晰，考虑全面。 对于此题，可以使用线性表和链式

3、表存储结构存储多项式信息。并根据C语言算法进行编程。同时本书在后面附带了一部分程序源码和对程序同步的解释。在用C语言编程的时候，要用到的语句主要有函数调用语句，判断语句，输出和输入语句。关键词一元多项式 线性表 系数 指数1 前言本次课程设计的的目的：是对数据结构所学的额内容进一步理解与巩固，是将计算机课程与实际问题联结起来的关键步骤。通过课程设计，能够提高分析问题，解决问题，从而运用所学知识解决实际问题的能力。系统的操作非常简单，输入两个多项式（注意：输入多项式中不能含有空格），会有不可预料的错误，而后就会得出两个多项式的相乘，相加，相减的结果。比如输入字符串2x+5x8-3.1x11 和7

4、-5x8+11x9就会得到其中字符串A，B化简后多项式是用来检错的，用来检测字符串处理是否正确并且按照升幂排序。当前系统只支持加减乘三种运算。本系统主要为进行繁杂的多项式加减乘运算的学生和教学工作者使用，节省工作时间，提高工作效率。系统支持任意的多项式，比如-1.3x0.3+x+2.03x(-0.12)+x，x+x(-1.3)+x。此系统是基于数组（线性表）开发，这所以使用数组用来开发此软件主要就是排序方便，可以调用sort（）函数，用链表排序的话比较慢，代码也不是一两句就能写完的。感谢怀化学院计算机系给我了这样一次机会。2 需求分析2.1 范围2.1.1 标识文件状态：【 】草稿【】正式发布

5、【 】正在修改文件标识：一元多项式计算器需求分析报告当前版本：1.0作 者：刘胜寒完成日期：2012-4-12.1.2 系统概述软件名称：一元多项式计算器软件功能：为用户提供快速计算两个任意一元多项式的计算器（只包括加法，减法，乘法）。用户：中学生开发者：刘胜寒2.2 需求概述2.2.1 系统目标系统的开发目标是对于用户给定的任意两个一元多项式实现其之间的加法，减法，乘法，三种功能，并且按照升幂的方式输出运算结果。2.2.2 运行环境配置一般的PC机就行，运行环境为win7/xp（此系统在win7环境下开发，调试，测试）。2.2.3 实验环境 Windows 2000 以上，C-Free任意版

6、本。2.2.4 用户的特点经常进行一元多项式操作的工作者。2.3功能需求用户要求输入两个字符串（任意一元多项式）然后进行加减乘操作，并且按照升幂输出结果。此系统可以直接输入两个任意一元多项式的字符串，支持同类项合并（输入的多项式可以有相同的指数），去掉系数为的项。网上关于一多项式的操作代码大多是分别输入多项式的有几项然后依次输入各项的系数、指数，有的不支持同类项合并，有的连小数都不支持，还要人工进行拆分系数，指数合并同类项，增加许多麻烦，这与系统原来的意愿背道而驰。此系统缺点就是没有菜单，只有输入输出。操作界面蹩脚，不能给用户一个友好的操作界面。优点就是操作简单，只需用户输入一元多项式即可，一

7、元多项式的格式不限，注意：输入一个完整的多项式时中间不能有空格，因为此系统是用cin读入。3 概要设计3.1 范围3.1.1 标识文件状态：【 】草稿【】正式发布【 】正在修改文件标识：概要设计报告当前版本：1.0作 者：刘胜寒完成日期：2012-3-313.1.2 系统概述软件名称：一元多项式计算器。软件功能：为学生用户提供快速计算两个一元多项式的计算器（只包括加法，减法，乘法）。用户：初中生。开发者：刘胜寒3.2 系统结构该系统直接面向用户。用户可以直接运行此软甲，进行一元多项式的操作。该系统只是进行简单的一元多项式的计算，没有设计什么菜单，用户类型，用户权限。这只是一个工具。4 系统详细

8、设计4.1 范围4.1.1 标识文件状态：【 】草稿【】正式发布【 】正在修改文件标识：详细设计报告当前版本：1.0作 者：刘胜寒完成日期：2011-4-104.1.2 系统概述软件名称：一元多项式简单计算器软件功能：节约学生计算一元多项式的时间，提高效率。用户：初中生开发者：刘胜寒。4.2 详细设计说明 此软件按照分治思想来进行编写的。分别进行，字符串处理算法设计，提取多项式各个系数和指数算法设计，加、减、乘算法设计，化简算法设计，输出算法设计。这设计每个算法时，定义每个函数的参数，所要实现那些功能。int cmp(Node A,Node B) 比较指数int huajian(Node AB

9、,int n) 合并同类项int zhuanhuan(char A,string AB) 分解一元多项式int Tiqu(string A,Node AB,int S) 提取单项式的系数和指数int Multi(Node AB1,int n,Node AB2,int m,Node AB3) 多项式相乘int add_sub(Node tmp1,int n,Node tmp2,int m,Node AB3,int N)多项式相加或者相减void output(Node A,int n) 输出计算结果4.2.2 字符串处理算法这个函数的主要功能就是分解一元多项式的项数，把一元多项式变成一个个单项式

10、。例如2x+5x8-3.1x11，会被分解为2x，+5x8，-3.1x11。也是整个系统的第一个函数，待操作的一元多项式都会经过这个函数进行处理。参数分别为待处理的一元多项式A，和用来保存单项式的数组AB。int zhuanhuan(char A,string AB) / A 输入的一元多项式 AB 分解后的一元多项式 string B=; int s=0;for(int i=0;istrlen(A);i+) if(Ai=+|Ai=-)&(Ai-1=)|Ai-1=x )&i!=0) /判断是否为多项式 ABs+=B; B=; if(Ai=+|Ai=-)& (Ai-1=0 ) ) /判断是否为多

11、项式 ABs+=B;B=; B=B+Ai; if(i=strlen(A)-1) /结束 ABs+=B;B=; return s;/一元多项式的个数 4.2.2 提取多项式各个参数算法设计个提取单项式的系数和指数，参数A代表单项式，AB用来存放单项式的系数和指数。S表示有多少个单项式，用来返回AB的有效个数。int Tiqu(string A,Node AB,int S) int l,BJ=-1,bj=-1,i,B2,s=0,Bj=-1; / BJ标记x的位置 bj标记系数有无括号 Bj表示指数是否含有- double x=0,y=0;/x 用来存放 系数 y用来存放指数 l=A.length(

12、); memset(B,-1,sizeof(B); / 用来标记 小数点的位置 B0标记系数 B1标记 指数 for(int i=0;i=BJ;i-) if(Ai=() bj=i; / 指数 括号的位置 if(Ai=.) B1=i; / 指数 小数点的 位置 if(Ai=-) Bj=i; / 指数 判断有无 - if(Ai=)break; if(BJ!=-1)/* /xn n!=0 for(int j=0;j=0&Aj=9) x=x*10+Aj-0; if(A0=+|A0=-)&A1=x)x=1; if(A0=x)x=1; if(A0=-)x=-x; if(B0!=-1) x=x*pow(0.

13、1,BJ-B0-1); if(BJ=-1)/ xn n=0 for(int j=0;j=0&Aj=9) x=x*10+Aj-0; if(A0=-)x=-x; if(B0!=-1) x=x*pow(0.1,l-B0-1); /*处理指数 if(BJ=-1)y=0;/没有指数 也就是指数为0 if(BJ!=-1) for(int j=BJ+1;j=0&Aj=9) y=y*10+Aj-0; if(BJ+1=l)y=1; if(B1!=-1) if(bj!=-1) /有括号 y=y*pow(0.1,l-2-B1); if(bj=-1) y=y*pow(0.1,l-B1-1); if(Bj!=-1)y=

14、-y; ABS.x=x; ABS.y=y; S+; coutx yendl; return S;4.2.3 加减算法设计进行加法或者减法计算，加法和减法只是后者取相反数，这个参数N为0时，tmp2的参数全部去相反数，就执行减法运算了。tmp1存储第一个多项式的系数和指数，n为个数。tmp2和tmp1一样，m为tmp2存储个数。N判断加法还是减法int add_sub(Node tmp1,int n,Node tmp2,int m,Node AB3,int N) /N=0 执行减法 N=1 执行加法 AB3 运行后的结果 Node AB1100, AB2100;for(int i=0;in;i+

15、)/复制AB1i=tmp1i;for(int i=0;im;i+)/复制AB2i=tmp2i;if(N=0)/ 判断是否执行减法AB2i.x*=-1;for(int i=0;in;i+)for(int j=0;jm;j+)if(AB1i.y=AB2j.y)AB1i.x+=AB2j.x;AB2j.x=0; / 标记 是否有同类项AB3i=AB1i;for(int j=0;jm;j+)/添加未被运算的多项式if(AB2j.x!=0)AB3n+=AB2j; for(int i=0;in;i+)/同类项合并 for(int j=i+1;jn;j+) if(AB3i.y=AB3j.y)AB3i.x+=A

16、B3j.x;AB3j.x=0; / 标记 是否有同类项 sort(AB3,AB3+n,cmp);/升幂排序return n;/ 执行 加法或者减法后的 不同项的个数4.2.4 乘法算法设计执行乘法AB3用来保存运算结果int Multi(Node AB1,int n,Node AB2,int m,Node AB3) int s=0;for(int i=0;in;i+)/for 循环for(int j=0;jm;j+) AB3s.x=AB1i.x*AB2j.x; AB3s.y=AB1i.y+AB2j.y; s+; for(int i=0;is;i+)/合并同类项 for(int j=i+1;js

17、;j+) if(AB3i.y=AB3j.y)AB3i.x+=AB3j.x;AB3j.x=0; / 标记 是否有同类项 /coutAB1i.x AB1i.yendl; sort(AB3,AB3+s,cmp);return s;4.2.5 化简算法设计int huajian(Node AB,int n) sort(AB,AB+n,cmp); int s=0; for(int i=0;in;i+) for(int j=i+1;jn;j+)if(ABi.y=ABj.y&ABi.x!=0)ABi.x+=ABj.x;ABj.x=0; / 标记 是否有同类项 for(int i=0;in;i+) if(AB

18、i.x!=0) ABs+=ABi;return s;4.2.6 输出算法设计void output(Node A,int n)double x,y;int BJ=0;/表示是否所有的多项式的因子全为0 即多项式为0for(int i=0;i0&i!=0)cout+; if(x0)cout-; if(y=0) coutfabs(x); else if(y=1) if(fabs(x)!=1) coutfabs(x)x; else coutx; else if(y0) if(fabs(x)!=1) coutfabs(x)x(y); else coutx(y); else if(fabs(x)!=1)

19、 coutfabs(x)xy; else coutxy; if(BJ=0)cout0;coutendl;5 测试说明5.1 范围5.1.1 标识文件状态：【 】草稿【】正式发布【 】正在修改文件标识：需求分析报告当前版本：1.0作 者：刘胜寒完成日期：2011-4-105.1.2 系统概述软件名称：一元多项式简单计算器软件功能：节约学生计算一元多项式的时间，提高效率。用户：初中生开发者：刘胜寒。5.2 测试计划及预期结果( 2x+5x8-3.1x11 )+(7-5x8+11x9) = 7+2x+11x9-3.1x11( 2x+5x8-3.1x11 )-(7-5x8+11x9) = 7+2x+1

20、1x9-3.1x11( 2x+5x8-3.1x11 )*(7-5x8+11x9) = 14x+35x8-10x9+22x10-21.7x11-25x16+55x17+15.5x19-34.1x20(6x(-3)-x+4.4x2-1.2x9)+(-6x(-3)+5.4x2-x2+7.8x15)= -x+8.8x2-1.2x9+7.8x15(6x(-3)-x+4.4x2-1.2x9)-(-6x(-3)+5.4x2-x2+7.8x15)= 12x(-3)-x-1.2x9-7.8x15(6x(-3)-x+4.4x2-1.2x9)*(-6x(-3)+5.4x2-x2+7.8x15)= -36x(-6)+

21、6x(-2)-4.4x3+19.36x4+7.2x6-5.28x11+46.8x12-7.8x16+34.32x17-9.36x24(x+x2)+(1+x+x2)= 1+2x+2x2(x+x2)-(1+x+x2)= -1(x+x2)*(1+x+x2)= x+2x2+2x3+x4 5.3 具体测试情况2x+5x8-3.1x11 7-5x8+11x96x(-3)-x+4.4x2-1.2x9 -6x(-3)+5.4x2-x2+7.8x15x+x2 1+x+x2总结 通过这次课程设计，有对数据结构加深一次认识，对C语言编程有了一定的提高。另外也提高了我分析问题，解决问题，从而运用所学知识解决实际问题的

22、能力。 一开始选这个课题的时候感觉应该很容易，因为只牵涉到一元多项式的加减乘。按照一班的写法就是把多项式的因子和指数分开读取，这样写的话，确实蛮简单，网上各种资料一大堆。基本不用修改什么就可以拿来用了。但这是不是我想要的，按照我的想法就是把一元多项式用字符串的方法读取。这样可以方便用户操作，大大节约用户的时间。 一个大的程序是有许许多多小的函数组成的。给定每个函数的接口，任务，功能。这样就能化难为简，化繁为简。 这次没有使用链表写，是因为对链表不是很感兴趣，换成链表写的话，就改一下排序就行了。因为用数组写的时后可以调用函数sort直接进行排序，如果用链表，要用比较暴利的循环在进行排序。其他地方

23、就不需要怎么大的修改就行可以实现用链表操作。 参考文献1 杨永斌. 数据结构理论与实践 M. 天津科学技术出版社, 2011.2 谭浩强，C程序语言设计（第三版）M. 清华大学出版社, 2007. 致 谢经过一个月的忙碌，课程设计顺利完成了。 在这里感谢我的数据结构老师高艳霞在以往的基础课学习中为我打下来良好的基础，是我这次课程设计能够顺利完成的前提。 感谢指导老师马竹根的悉心指导，没有他的帮助很多关键部分以己之力是很难完成，马老师的悉心知道是这次课程设计顺利完成的必要条件。 感谢学校能够给我们提供这么好的机房，是我方便上网查资料，有地方做这次的课程设计， 很感谢寝室的室友，请他们帮我调试，提

24、了不少宝贵的意见，是我的程序有了进一步的完善。附录#include#include#includeusing namespace std;struct Nodedouble x,y;int N=45,NN=43;int cmp(Node A,Node B)if(A.yB.y)return 0;else return 1;int huajian(Node AB,int n) sort(AB,AB+n,cmp); int s=0; for(int i=0;in;i+)/合并同类项 for(int j=i+1;jn;j+)if(ABi.y=ABj.y&ABi.x!=0)ABi.x+=ABj.x;AB

25、j.x=0; / 标记 是否有同类项 for(int i=0;in;i+) if(ABi.x!=0) ABs+=ABi; return s;int zhuanhuan(char A,string AB) string B=; int s=0;for(int i=0;istrlen(A);i+)if( (Ai=+|Ai=-) & ( Ai-1=)|Ai-1=x )&i!=0) ABs+=B; B=; if( (Ai=+|Ai=-) & ( Ai-1=0 ) ) ABs+=B; B=; B=B+Ai; if(i=strlen(A)-1) ABs+=B;B=; return s;int Tiqu(s

26、tring A,Node AB,int S) int l,BJ=-1,bj=-1,i,B2,s=0,Bj=-1; double x=0,y=0; l=A.length(); memset(B,-1,sizeof(B); for(int i=0;i=BJ;i-) if(Ai=() bj=i; / 括号的位置 if(Ai=.) B1=i; /指数 小数点的 位置 if(Ai=-) Bj=i; /判断有无 - if(Ai=)break; /*处理因子* if(BJ!=-1)/* /xn n!=0 for(int j=0;j=0&Aj=9) x=x*10+Aj-0; if(A0=+|A0=-)&A1=

27、x)x=1; if(A0=x)x=1; if(A0=-)x=-x; if(B0!=-1) x=x*pow(0.1,BJ-B0-1); /* if(BJ=-1)/ xn n=0 for(int j=0;j=0&Aj=9) x=x*10+Aj-0; if(A0=-)x=-x; if(B0!=-1) x=x*pow(0.1,l-B0-1); /*处理指数* if(BJ=-1)y=0;/没有指数 也就是指数为0 if(BJ!=-1) for(int j=BJ+1;j=0&Aj=9) y=y*10+Aj-0; if(BJ+1=l)y=1; if(B1!=-1) if(bj!=-1) /有括号 y=y*p

28、ow(0.1,l-2-B1); if(bj=-1) y=y*pow(0.1,l-B1-1); if(Bj!=-1)y=-y; ABS.x=x; ABS.y=y; S+;/* return S;int Multi(Node AB1,int n,Node AB2,int m,Node AB3) int s=0;for(int i=0;in;i+)for(int j=0;jm;j+)AB3s.x=AB1i.x*AB2j.x; AB3s.y=AB1i.y+AB2j.y; s+; for(int i=0;is;i+) for(int j=i+1;js;j+) if(AB3i.y=AB3j.y)AB3i.

29、x+=AB3j.x;AB3j.x=0; / 标记 是否有同类项 /coutAB1i.x AB1i.yendl; sort(AB3,AB3+s,cmp);return s;int add_sub(Node tmp1,int n,Node tmp2,int m,Node AB3,int N) / 0 - 1 + NM=0,MN=1;Node AB1100, AB2100;for(int i=0;in;i+)AB1i=tmp1i;for(int i=0;im;i+)AB2i=tmp2i;if(N=0)AB2i.x*=-1;for(int i=0;in;i+)for(int j=0;jm;j+)if(AB1i.y=AB2j.y)AB1i.x+=AB2j.x;AB2j.x=0; / 标记 是否有同类项AB3i=AB1i;for(int j=0;jm;j+)if(AB2j.x!=0)AB3n+=AB2j; for(int i=0;in;i+) for(int j=i+1;jn;j+) if(AB3i.y=AB3j.y)AB3i.x+=AB3j.x;AB3j.x=0; / 标记 是否有同类项 /coutAB1i.x AB1i.yendl; sort(AB3,AB3+n,cmp);ret