一元多项式计算问题课程设计

长 沙 学 院课程设计说明书题目一元多项式计算问题系(部)计算机系专业(班级)10级软件D班姓名向栋良学号2010022D08指导教师邓旭东起止日期2011.9.4-2011.9.8课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：日期节次地点设计方式9月4日（周日）1-4科1408讲授内容9月4日（周日）5-8科1608答疑9月5日（周一）1-4科1408上机调试9月5日（周一）5-8科1608答疑9月6日（周二）1-4科1408上机调试9月6日（周二）5-8科1608答疑9月7日（周三）1-4科1408上机调试9月7日（周三）5-8科1608答疑9月8日（周四）1-4科1608答疑9月8日（周四）5-8科1408答辩指导教师签名：日期：教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表姓名徐皖宁学号2010022509专业软件工程班级软件五班设计题目课程设计安排指导教师杜红燕指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；摘 要 本文是关于一个一元稀疏多项式计算器的问题。一元稀疏多项式计算内容包括输入并建立多项式，多项式相加，多项式相减，以及其输出多项式。本程序运用面向对象的设计方法，使用C+语言，利用microsoft visual C+ 6.0开发工具，还有数据结构中学到的链式存储架构，存储一元多项式，从而实现程序的基本功能，在程序中定义了各种类型的运算模块，通过主程序的调用来完成它们之间的配合，从而使程序正确运行。关键词：数据结构；一元多项式；链表；C+语言目录摘 要第一章 需求分析11.1 输入的形式和输入值的范围：11.2 输出的形式11.3程序所能达到的功能12.1 设计思路1第三章 详细设计23.1、创建一个结点，表示多项式的一项23.2、链式存储多项式43.3 、多项式的计算53.4、释放结点9第四章 运行界面104.1、输入界面如图4-1：104.3、用户选择功能界面如图4-3104.4、各功能运行界面如图4-4：11参考文献12附录:13源代码;13 第一章 需求分析 1.1 输入的形式和输入值的范围： 输入是从键盘输入的，输入的内容为多项式的系数和指数，数为任意的整数，指数为大于等于0的整数 1.2 输出的形式 从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值。1.3程序所能达到的功能 a：输入并建立多项式； b：输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b； e：多项式的输出形式为类数学表达式。 系数值为1的非零项的输出形式中略去系数1。而-1x的输出形式为-x。 第二章 概要设计 2.1 设计思路 A：数据结构的选用 为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属； B：多项式的输入 采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入； C：2个多项式的加法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。 p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中。当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生 D：2个多项式的减法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。 p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。 第三章 详细设计3.1、创建一个结点，表示多项式的一项 pnode create(char *c,int i,int j) if(ji) return NULL; int a=0,b=0,flag=0;/a系数,b指数，flag指数正负记录。 if(!isnum(ci)a=1; else while(isnum(ci)&i=j) a=a*10+ci-0; i+; /跳过系数与指数间非数字字符。 while(!isnum(ci)&ij&flag=1) b=1; else if(ci-1=-&ci-2=) flag=2;/指数是负数情况记录。 while(isnum(ci)&ix=a; p-z=b; return p; /创建一个结点，表示多项式的一项。把12X3这样字符串转化成一个只有系数、指数、后继的结构体。3.2、链式存储多项式 pnode create_duo(char *c,int m) if(cm=0) return NULL; int i,j; pnode p,q,*t; i=m; if(ci=+|ci=-)i+; j=i; while(cj!=0&cj!=+&(cj!=-|cj-1=) j+; /移动到多项式字符串的从下标m起第一项末。if(ci!=0) p=create(c,i,j-1); if(i0&ci-1=-) p-x=-(p-x); q=create_duo(c,j);/处理下一项 if(q=NULL) p-next=q; else if(q&q-zz) p-next=q; else if(q) t=&q; while(*t!=NULL)t=&(*t)-next; *t=(pnode)malloc(sizeof(node); *t=p; (*t)-next=NULL; p=q; return p;else return create_duo(c,j); /系数为0项，不建立，跳过。/把一元多项式的字符串用链式存储。3.3 、多项式的计算pnode plus(pnode p,pnode q) pnode P,H,t,m,n; m=p; n=q; H=P=(pnode)malloc(sizeof(node); while(m!=NULL&n!=NULL) t=(pnode)malloc(sizeof(node); if(m-zn-z) t-x=m-x; t-z=m-z; m=m-next; else if(m-z=n-z) if(m-x=-(n-x) m=m-next; n=n-next; continue; /指数相同，系数相反，情况处理。 t-x=m-x+n-x; t-z=n-z; m=m-next; n=n-next; else t-x=n-x; t-z=n-z; n=n-next; P-next=t; P=P-next; while(m!=NULL) t=(pnode)malloc(sizeof(node); t-x=m-x; t-z=m-z; m=m-next; P-next=t; P=P-next; while(n!=NULL) t=(pnode)malloc(sizeof(node); t-x=n-x; t-z=n-z; n=n-next; P-next=t; P=P-next; P-next=NULL; P=H; H=H-next; free(P); return H;/两个一元多项式的相加。pnode minus(pnode p,pnode q) if(q=NULL) return p; pnode t,h,g,q1; t=q; h=(pnode)malloc(sizeof(node); h-x=-(t-x); h-z=t-z; t=t-next; q1=h; g=h; while(t!=NULL) h=(pnode)malloc(sizeof(node); h-x=-(t-x); h-z=t-z; g-next=h; g=g-next; t=t-next; g-next=NULL; if(p=NULL) return q1; return (plus(p,q1);/两个一元多项式的差3.4、释放结点void free_pnode(pnode p)pnode t;while(p!=NULL) t=p; p=p-next; free(t);第四章 运行界面4.1、输入界面如图4-1：图4-14.2、显示输出数据如图4-2：图4-24.3、用户选择功能界面如图4-3图4-34.4、各功能运行界面如图4-4：图4-4 第五章 总 结 C+语言功能强,使用灵活, 可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件通过这次课程设计我觉得我们学习数据结构的方法存在一定的弊端,数据结构的效果直接影响到我们对其它专业课的学习和今后业务的成长。我觉得我们对于数据结构的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。 最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利! 参考文献1 王挺C+程序设计 北京：清华大学出版社，2005.12 严蔚敏数据结构：C语言版 北京：清华大学出版社，2007附录:源代码;#include #include#include#define N 999 typedef struct node int x,z;/x系数，z指数 struct node *next;*pnode; int isnum(char c) if(c=0&c=9) return 1; else return 0;/判断用 pnode create(char *c,int i,int j) if(ji) return NULL; int a=0,b=0,flag=0;/a系数,b指数，flag指数正负记录。 if(!isnum(ci)a=1; else while(isnum(ci)&i=j) a=a*10+ci-0; i+; /跳过系数与指数间非数字字符。 while(!isnum(ci)&ij&flag=1) b=1; else if(ci-1=-&ci-2=) flag=2;/指数是负数情况记录。 while(isnum(ci)&ix=a; p-z=b; return p; /创建一个结点，表示多项式的一项。把12X3这样字符串转化成一个只有系数、指数、后继的结构体。pnode create_duo(char *c,int m) if(cm=0) return NULL; int i,j; pnode p,q,*t; i=m; if(ci=+|ci=-)i+; j=i; while(cj!=0&cj!=+&(cj!=-|cj-1=) j+; /移动到多项式字符串的从下标m起第一项末。if(ci!=0) p=create(c,i,j-1); if(i0&ci-1=-) p-x=-(p-x); q=create_duo(c,j);/处理下一项 if(q=NULL) p-next=q; else if(q&q-zz) p-next=q; else if(q) t=&q; while(*t!=NULL)t=&(*t)-next; *t=(pnode)malloc(sizeof(node); *t=p; (*t)-next=NULL; p=q; return p;else return create_duo(c,j); /系数为0项，不建立，跳过。/把一元多项式的字符串用链式存储。pnode plus(pnode p,pnode q) pnode P,H,t,m,n; m=p; n=q; H=P=(pnode)malloc(sizeof(node); while(m!=NULL&n!=NULL) t=(pnode)malloc(sizeof(node); if(m-zn-z) t-x=m-x; t-z=m-z; m=m-next; else if(m-z=n-z) if(m-x=-(n-x) m=m-next; n=n-next; continue; /指数相同，系数相反，情况处理。 t-x=m-x+n-x; t-z=n-z; m=m-next; n=n-next; else t-x=n-x; t-z=n-z; n=n-next; P-next=t; P=P-next; while(m!=NULL) t=(pnode)malloc(sizeof(node); t-x=m-x; t-z=m-z; m=m-next; P-next=t; P=P-next; while(n!=NULL) t=(pnode)malloc(sizeof(node); t-x=n-x; t-z=n-z; n=n-next; P-next=t; P=P-next; P-next=NULL; P=H; H=H-next; free(P); return H;/两个一元多项式的相加。pnode minus(pnode p,pnode q) if(q=NULL) return p; pnode t,h,g,q1; t=q; h=(pnode)malloc(sizeof(node); h-x=-(t-x); h-z=t-z; t=t-next; q1=h; g=h; while(t!=NULL) h=(pnode)malloc(sizeof(node); h-x=-(t-x); h-z=t-z; g-next=h; g=g-next; t=t-next; g-next=NULL; if(p=NULL) return q1; return (plus(p,q1);/两个一元多项式的差。 void print(pnode p) if(p=NULL) cout0x=-1&p-z!=0)coutx!=1|p-z=0) coutx; if(p-z) coutz!=1) coutz; p=p-next; if(p!=NULL&p-x0) cout+; coutendl;/输出链式存储多项式。void main()cout*endl;cout*一元多项式的计算(和差积)*endl;cout*endl;char ch1N;/=30X45-X-9;char ch2