设计一个一元稀疏多项式计算器论文(1).doc

课程设计（论文）课程名称： 数据结构课程设计 题 目：一元稀疏多项式简单计算器 院 （系）： 信息与控制工程学院 专业班级： 计算机0901 姓 名： 张 强 学 号： 090620119 指导教师： 李智杰 2011年 9 月 9日西安建筑科技大学课程设计（论文）任务书专业班级： 计算机0901 学生姓名： 张强 指导教师（签名）：一、课程设计（论文）题目问题描述：设计一个一元稀疏多项式简单计算器。二、本次课程设计（论文）应达到的目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：熟练掌握数组、链表的各种应用。三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）基本要求（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b；（5）计算多项式在x处的值。（6）计算器的仿真界面。四、应收集的资料及主要参考文献：由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“数组、线性表”及其有关的基本操作。参考文献：1本年级用的教材：数据结构与算法分析（C+版）（第二版）影印版 2005，7；2C+程序设计技能百练，中国铁道出版社，2004，1 蒋立翔编著；3. 数据结构与C+，西安交通大学出版社，1999，11 周叶著；4C/C+与数据结构，清华大学出版社，2002，3，1 王立柱；5数据结构使用C+语言描述，东南大学出版社，2001，1，1 陈慧南；五、审核批准意见教研室主任（签字）设计总说明本文介绍了用C+语言编写一个一元稀疏多项式计算器。其内容包括输入并建立多项式, 两个多项式相加以及输出多项式：n, c1, e1, c2, e2, cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。利用这个程序可以方便的计算简单的一元稀疏多项式的基本运算。本课程设计就是对这样一个简单的计算器进行设计，用以实现一元稀疏多项式基本的运算问题。设计从小处着手，以小见大。运用所学的一些c+知识，构成整个计算器的形成框架。并在程序中定义了各种类型的运算的模块，本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积，多项式求商的运算，通过主程序的调用来完成他们之间的配合。来实现输入并建立多项式,两多项式的相加以及多项式的输出。目录一 问题描述 1二 需求分析 1三 概要设计 2四 详细设计 3五 源代码 4六 程序测试17七 使用说明21八 课设总结22九 参考文献23 西安建筑科技大学课程设计（论文） 数据结构课程设计 一元稀疏多项式简单计算器一、问题描述1、基本要求（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b；（5）计算多项式在x处的值。（6）计算器的仿真界面。2、设计目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用二、 需求分析1、 设计开发环境： 软件方面：系统 windows xp 编程软件：VC+ 6.02、思路分析：一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+pmxem 其中，p1是指数为ei的项的非零系数，且满足0e1e2em=n ,若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表（p1,e1）,(p2,e2),(pm,em)）便可惟一确定多项式pn(x)。用两个带表头结点的单链表分别存储两个多项式根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式” 三、概要设计菜单加法AddPolyn(ma,mb)减法SubtractPolyn(ma,mb)乘法MultiplyPolyn(ma,mb)求值ValuePolyn(ma,x)输入Insert(Polyn p,Polyn h)除法DevicePolyn(ma,mb)输出desktop() 图3-1功能模块图为实现上述程序功能，用带表头结点的单链表存储多项式。元素类型，节点类型，和指针类型：typedef struct Polynomialint coe; /系数int exp;/指数struct Polynomial *next;*Polyn,Polynomial;各个模块之间的调用如图3-1所示，调用insert（）函数将输入的多项式按降幂排列，通过主函数main（）中swith语句，选择用户所选择的对应的模块，然后又模块对应的功能函数对用户输入的数据进行相应的操作，最后通过desktop（）模块将最后结果输出。开始运行四、详细设计多项式加法计算器退出求积、商求和（差）输入多项式关闭运行多项式相加求和（差）多项式求积、商建立2个多项式输出结果输出求和（差）结果按任意键退出图4-1 功能实现流程图4.1 输入模块用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本模块会先判断谁否是第一次输入，如果是，创建节点，如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的指数较大，则刚输入的这一项继续与第二项比较指数，以此类推，如果发现刚输入的这一项的指数比比较的这一项的指数要大，则插入比较项的前面。4.2 求和、差模块用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输入模块，进行对两个要运算的多项式进行初始化，并按降幂排列。然后将两个多项式的幂进行一个对比，如果第一个数的第一项的系数大于第二个多项式的第一个项的系数，那么直接将第一项赋值于刚开始创建的链表的第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第二个数的第一项的系数相同，那么将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最后答案。4.3求积、商模块用户可通过该模块实现两个多项式的相乘（相除），此模块先调用输入模块，进行对两个要运算的多项式的初始化，并按降幂排列。然后将第一个数的系数、指数与第二个数的系数、指数分别相乘（相除），相加（相减），并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项与第二个数的第二项进行相应的操作.执行完之后最后调用输出模块将结果输出到屏幕上。4.4求值模块用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变量，最后将答案通过输出模块输出到屏幕上。五、 源代码我真诚地保证： 我自己独立地完成了整个程序从分析、设计到编码的全过程。 如果在上述过程中，我遇到了困难而求教于人，那么，我将在程序报告中详细地列举我所遇到的问题，以及别人给我的提示。在此，我感谢 同学老师对我的启发和帮助。下面的报告中，我还会具体地提到他们在各个方法对我的帮助。 我的程序里中凡是引用到其他程序或文档之处，例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。我从未抄袭过别人的程序，也没有盗用别人的程序，无论是修改式地抄袭还是原封不动地抄袭。我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。 第 5 页 共 23 页#include#include #include typedef struct Polynomialint coe; /系数int exp;/指数struct Polynomial *next;*Polyn,Polynomial; Polyn ma,mb;void Insert(Polyn p,Polyn h) if(p-coe=0) delete p; elsePolyn q1,q2;q1=h;q2=h-next;while(q2&p-expexp) q1=q2;q2=q2-next;if(q2&p-exp=q2-exp) q2-coe+=p-coe;delete p;if(!q2-coe) q1-next=q2-next;delete q2；else p-next=q2;q1-next=p;Polyn CreatePolyn(Polyn head,int m)int i;Polyn p;p=head=new Polynomial;head-next=NULL;for(i=0;im;i+)p=new Polynomial;cout请输入第i+1p-coe;coutp-exp;Insert(p,head);return head;void DestroyPolyn(Polyn p)Polyn t;while(p!=NULL)t=p;p=p-next;delete t;void PrintPolyn(Polyn Pm) Polyn qa=Pm-next; int flag=1;if(!qa) cout0; coutcoe0&flag!=1) coutcoe!=1&qa-coe!=-1)coutcoe; if(qa-exp=1) coutexp) coutXexp;elseif(qa-coe=1)if(!qa-exp) coutexp=1) coutX;else coutXexp;if(qa-coe=-1)if(!qa-exp) coutexp=1) cout-X; else cout-Xexp;qa=qa-next; flag+;coutexpb-exp) return 1;else if(!a|a-expexp) return -1;else return 0;else if(!a&b) return -1;else return 1;Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=new Polynomial;hc-next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;switch(compare(qa,qb)case 1:qc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;case 0: qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;case -1:qc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break; if(qc-coe!=0)qc-next=hc-next;hc-next=qc;hc=qc;else delete qc;return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=pb;Polyn p=pb-next;Polyn pd;while(p) p-coe*=-1;p=p-next;pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next) p-coe*=-1;return pd;Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;/Polyn qa=pa-next; /新建一个结点作为pa的后继结点Polyn qb=pb-next; /新建一个结点作为pb的后继结点hf=new Polynomial;hf-next=NULL;while(qa)/使用while循环，使得多项式的每项得以运算qb=pb-next;while(qb)pf=new Polynomial;pf-coe=qa-coe*qb-coe;pf-exp=qa-exp+qb-exp;Insert(pf,hf);/调用插入函数，将新的结点插入到新建链表中，并合并同类项qb=qb-next;qa=qa-next;return hf;/返回所得链表的头指针void DevicePolyn(Polyn pa,Polyn pb) Polyn quotient,remainder,temp1,temp2;Polyn qa=pa-next;Polyn qb=pb-next;quotient=new Polynomial; /建立头结点,存储商quotient-next=NULL;remainder=new Polynomial; /建立头结点，存储余数remainder-next=NULL;temp1=new Polynomial;temp1-next=NULL;temp2=new Polynomial;temp2-next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&qa-exp=qb-exp)temp2-next=new Polynomial;temp2-next-coe=(qa-coe)/(qb-coe);temp2-next-exp=(qa-exp)-(qb-exp);Insert(temp2-next,quotient);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2);qa=pa-next;temp2-next=NULL;remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb);pb=temp1;coutendlshangendl;/printf(t商：);PrintPolyn(quotient);coutyushunext; float result=0; while(p!=NULL) result+=(p-coe)*(float)pow(x,p-exp); p=p-next; return result; void desktop()system(cls);coutendlendlendl 一元多项式的计算endl; cout*endl; cout* 1.输出多项式a和b *endl; cout* 2.建立多项式a+b *endl; cout* 3.建立多项式a-b *endl;cout* 4.建立多项式a*b *endl;cout* 5.建立多项式a/b *endl;cout* 6.计算多项式a的值 *endl;cout* 7.退出 *endl;cout*endlendl;cout执行操作:;void input()int m,n;/Polyn pa,pb;coutm;ma=CreatePolyn(ma,m);coutendl;coutn;mb=CreatePolyn(mb,n);void main()/int m,n;float x,result;char key;/Polyn pa,pb;coutendlendlendlendl 欢迎您的使用！endl;cout 系统正在初始化数据，请稍后.key;switch (key)case1:input();cout多项式a：; PrintPolyn(ma); cout多项式b：; PrintPolyn(mb);break;case2:input();/pc=AddPolyn(pa,pb);cout多项式a：; PrintPolyn(ma); cout多项式b：; PrintPolyn(mb);cout多项式a+b：;PrintPolyn(AddPolyn(ma,mb);/DestroyPolyn(pc);break;case3:input();/pd=SubtractPolyn(pa,pb);cout多项式a：; PrintPolyn(ma); cout多项式b：; PrintPolyn(mb);cout多项式a-b：;PrintPolyn(SubtractPolyn(ma,mb);/DestroyPolyn(pd);break;case4:input();/pd=SubtractPolyn(pa,pb);cout多项式a：; PrintPolyn(ma); cout多项式b：; PrintPolyn(mb);cout多项式a*b：;PrintPolyn(MultiplyPolyn(ma,mb);/DestroyPolyn(pd);break;case5:input();/pd=SubtractPolyn(pa,pb);cout多项式a：; PrintPolyn(ma); cout多项式b：; PrintPolyn(mb);cout多项式a/b：;DevicePolyn(ma,mb);/DestroyPolyn(pd);break;case6:input();cout多项式a：; PrintPolyn(ma);coutx;result=ValuePolyn(ma,x);cout多项式a的值:resultendl;break;case7:DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:coutError!endl;coutendlendl;system(pause);六 、程序测试测试软件：Microsoft Visual C+ 6.0测试的数据：(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= 5x6+4x5+3x4 B= 6x6+5x5 (4) A= 5x6+4x5+3x4 X=2(5) A/B A=2x2 B=x2+1测试过程与结果：(1) A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 A+B=3x14+2x10-4x8+2图6-1加法测试图(2)A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A- B=9x14+3x10-x8+5x6-2 图6-2减法测试图6-2减法测试图(3)A= 5x6+4x5+3x4 B= 6x6+5x5 A*B =30x12+49x11+38x10+15x9 图6-3乘法测试图(4)A= 5x6+4x5+3x4 X=2 A=496、图6-4求值测试图（5）A=2x2 B=x2+1A/B=2余数是-2；图6-5除法测试图七、 使用说明 程序开始运行后，出现如图界面：图7-1界面初始图 1、如果要进行加法运算，请输入2，出现 请输入a的项数：请输入第一项的系数： 就是输入第一个多项式的每一项的系数和指数。 注意：输入是随便输入的。 如第一个多项式为5x5; 过程如下： 请输入a的项数：1请输入a的系数：5请输入a的指数：5 接着输入第2个多项式的每一项的系数和指数。 输入完以后就直接显示结果了：2、如果要进行减法运算，请输入3，过程和输入加法一样，输入个多项式即可。 3、如果要退出的话，请输入7即可结束程序的运行。八、 课设总结学完数据结构线性表一章后做此题，自觉就想到用带头结点的单链表来