长沙学院课程设计说明书题目一元多项式计算问题系(部) 计算机系专业(班级) 10级软件D班姓名向栋良学号*******D08指导教师邓旭东起止日期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+x1B=-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 答辩指导教师签名：日期：教研室主任签名：日期：系主任签名：日期：长沙学院课程设计鉴定表摘要本文是关于一个一元稀疏多项式计算器的问题。
一元稀疏多项式计算内容包括输入并建立多项式，多项式相加，多项式相减，以及其输出多项式。
本程序运用面向对象的设计方法，使用C++语言，利用microsoft visual C++ 6.0开发工具，还有数据结构中学到的链式存储架构，存储一元多项式，从而实现程序的基本功能，在程序中定义了各种类型的运算模块，通过主程序的调用来完成它们之间的配合，从而使程序正确运行。
关键词：数据结构；一元多项式；链表；C++语言目录摘要第一章需求分析 01.1 输入的形式和输入值的范围： 01.2 输出的形式 01.3程序所能达到的功能 02.1 设计思路 0第三章详细设计 (1)3.1、创建一个结点，表示多项式的一项 (1)3.2、链式存储多项式 (3)3.3 、多项式的计算 (4)3.4、释放结点 (8)第四章运行界面 (9)4.1、输入界面如图4-1： (9)4.3、用户选择功能界面如图4-3 (9)4.4、各功能运行界面如图4-4： (9)参考文献 (10)附录: (11)源代码; (11)第一章需求分析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(j<i) return NULL;int a=0,b=0,flag=0;//a系数,b指数，flag指数正负记录。
if(!isnum(c[i]))a=1;elsewhile(isnum(c[i])&&i<=j){a=a*10+c[i]-'0';i++;}//跳过系数与指数间非数字字符。
while(!isnum(c[i])&&i<=j){flag=1;i++;}//处理指数。
if(i>j&&flag==1) b=1;else {if(c[i-1]=='-'&&c[i-2]=='^') flag=2;//指数是负数情况记录。
while(isnum(c[i])&&i<=j){b=b*10+c[i]-'0';i++;}}if(flag==2) b=-b;//指数是负数情况处理。
pnode p;p=(pnode)malloc(sizeof(node));p->x=a;p->z=b;return p;}//创建一个结点，表示多项式的一项。
把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
3.2、链式存储多项式pnode create_duo(char *c,int m){if(c[m]=='\0') return NULL;int i,j;pnode p,q,*t;i=m;if(c[i]=='+'||c[i]=='-')i++;j=i;while(c[j]!='\0'&&c[j]!='+'&&(c[j]!='-'||c[j-1]=='^')){j++;}//移动到多项式字符串的从下标m起第一项末。
if(c[i]!='0'){p=create(c,i,j-1);if(i>0&&c[i-1]=='-') p->x=-(p->x);q=create_duo(c,j);//处理下一项if(q==NULL)p->next=q;else if(q&&q->z<p->z)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;}elsereturn 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->z>n->z) {t->x=m->x;t->z=m->z;m=m->next;}elseif(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-1 4.2、显示输出数据如图4-2：图4-2 4.3、用户选择功能界面如图4-3图4-3 4.4、各功能运行界面如图4-4：图4-4第五章总结C++语言功能强,使用灵活, 可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件通过这次课程设计我觉得我们学习《数据结构》的方法存在一定的弊端,《数据结构》的效果直接影响到我们对其它专业课的学习和今后业务的成长。