C++一元多项式计算问题-课程设计说明书

学院课程设计说明书题目一元多项式计算问题系(部)计算机科学与技术系专业(班级)计算机科学与技术专业姓名学号指导教师起止日期第十三、十四周课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1)A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2(2)A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7(3)A+BA=x3+x1B=-x3-x1(4)A+BA=0B=x7+x5+x3+x1(5)A-BA=100x100+50x50+20x20+xB=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：班级：计科3班指导教师：刘钢钦周次星期地点设计方式13星期一1-2节A多1讲授内容星期二3-4节科1608答疑星期二5-8节1403上机调试星期三1-4节科1608答疑星期四1-4节1404上机调试星期四5-8节科1608答疑1414星期二3-4节科1608答疑星期二5-8节1403上机调试星期三1-4节科1608答疑星期四1-4节1404上机调试星期四5-8节科1608答疑星期四9-10节1403答辩指导教师签名：　　　　　　　　　日期：　　　　　　　　教研室主任签名：　　　　　　　日期：　　　　　　　　系主任签名：　　　　　　　　　日期：　　　　　　　　长沙学院课程设计鉴定表姓名学号专业计算机科学与技术专业班级设计题目一元多项式计算问题指导教师指导教师意见：评定等级：教师签名：日期：答辩小组意见：评定等级：　　　　　答辩小组长签名：　　　　　日期：　　　　教研室意见：教研室主任签名：日期：　系（部）意见：系主任签名：　　　　　　　　日期：　　　　　说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；摘要本文是关于一个一元稀疏多项式计算器的问题。一元稀疏多项式计算内容包括输入并建立多项式,多项式相加，多项式求值，多项式求乘积以及输出多项式。本程序运用面向对象程序设计方法，使用C++语言，利用MicrosoftVisualC++6.0开发工具，还有数据结构课中学到的链式存储结构，存储一元稀疏多项式，从而实现程序的基本功能。在程序中定义了各种类型的运算的模块，通过主程序的调用来完成它们之间的配合，进而使得一元稀疏多项式计算器的顺利运行。关键词：数据结构；一元稀疏多项式；链表；C++语言目录1设计内容与要求…………………………………………………………………………………12.设计说明…………………………………………………………………………………………12.1问题描述与功能设计…………………………………………………………………………12.2数据结构与算法………………………………………………………………………………12.3函数定义………………………………………………………………………………………32.4界面设计………………………………………………………………………………………42.5编码……………………………………………………………………………………………52.6测试……………………………………………………………………………………………103总结…………………………………………………………………………………………………14参考文献……………………………………………………………………………………………15附录A源代码………………………………………………………………………………………16⒈设计内容与要求设计内容：设计一个稀疏多项式简单计算器，能够进行简单的基本运算。如：多项式相加、多项式相减、多项式求值……等等。基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；创新要求：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积2.设计说明2.1问题描述与功能设计本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积的运算。2.2数据结构与算法数据结构多项式的逻辑结构：视为线性表p(x)=3x14-8x8+6x2+2数据元素(coef,exp)表示多项式项coef·Xexp，coef是该项的系数，exp是变元X的指数。为了实现任意多项式的运算，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个成员。算法多项式的输入与建立调用CreatePolyn（）函数建立链表，将多项式每一项的系数与指数作为链表一个结点的数据，按照指示输入每一项的系数与指数时，将调用Insert（）函数，将输入的结点信息按指数降序排列的方式插入到之前建立的链表中，并合并同类项。依次输入、建立一元多项式pa和pb。如下图。多项式的输出调用PrintPolyn（）函数将多项式链表中的结点数据按照一元多项式的格式(如：6x^5+3x^3+7x+3)输出到屏幕上。两个多项式的加法调用AddPolyn（）函数直接对两个多项式的链表的结点成员的系数与指数按照数学中多项式相加的原则进行操作。其中要调用compare（）函数对两个多项式的指数或是项数进行比较。相加所得的多项式存放到新建的第三个多项式中。再对第三个多项式输出即可。两个多项式的减法调用SubtractPolyn（）函数对两个多项式减法运算。首先对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减。所得的多项式存放到新建的第三个多项式中，再对第三个多项式输出即可。多项式的求值调用ValuePolyn（）函数对多项式求值。在用户输入X的值后，对链表每个结点的数据进行求值，然后求和即多项式在X为某一值的值。其中用到C语言中的数学函数：pow。其功能为计算x的y次幂，所在头文件：math.h。两个多项式的乘法调用MultiplyPolyn（）函数对两个多项式进行乘法运算。根据数学知识，依次用一个多项式的每一项乘以另一个多项式的每一项，再求和、合并同类项即两个多项式的乘积。当中用了多两个多项式的while循环，以确保两个多项式的每一项都得到相应的运算，每一次运算后调用Insert()函数把乘积插入到新建的链表中，以得到一个结点信息按指数降序排列的方式排列，并以合并同类项的链表。2.3函数定义为了程序功能的顺利实现，在本程序中定义了如下函数：函数名功能Insert()链表结点数据的插入与排序CreatePolyn()链表头结点的创建DestroyPolyn()链表的销毁PrintPolyn()链表数据的多项式形象化输出Compare()两个多项式的指数或是项数进行比较AddPolyn()两个多项式的加法SubtractPolyn()两个多项式的减法ValuePolyn()多项式的求值MultiplyPolyn()两个多项式的乘法desktop()程序界面的实现2.4界面设计程序数据初始界面：程序操作主界面：2.5编码链表建立的函数,该函数在多项式信息输入时按照指数降序排列建立链表，并在出现同类项时合并。voidInsert(Polynp,Polynh){if(p-coe==0)deletep;//当前结点的coe成员等于0的时候删除当前结点else{Polynq1,q2;q1=h;q2=h-next;while(q2&&p-expq2-exp)//查找插入位置{q1=q2;q2=q2-next;}if(q2&&p-exp==q2-exp)//将指数相同相合并{q2-coe+=p-coe;deletep;if(!q2-coe){q1-next=q2-next;deleteq2;}}else//指数为新时将结点插入{p-next=q2;q1-next=p;}}}链表信息按照多项式形式输出。voidPrintPolyn(PolynP){Polynq=P-next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0cout0;coutendl;return;}while(q){if(q-coe0&&flag!=1)cout+;//系数大于0且不是第一项时就输出+if(q-coe!=1&&q-coe!=-1)//系数非1或-1的普通情况{coutq-coe;if(q-exp==1)coutX;//当前结点exp为1时elseif(q-exp)coutX^q-exp;}else{if(q-coe==1)系数为1的特殊情况{if(!q-exp)cout1;//指数不存在elseif(q-exp==1)coutX;/指数等于一elsecoutX^q-exp;}if(q-coe==-1)系数为-1的特殊情况情况{if(!q-exp)cout-1;//指数不存在elseif(q-exp==1)cout-X;//指数等于一elsecout-X^q-exp;}}q=q-next;//当前指针指向下一结点flag++;//项序数自加1}coutendl;}两个多项式的加法。intcompare(Polyna,Polynb)//对两个多项式的系数或项数进行比较{if(a&&b){//两个多项式都存在if(!b||a-expb-exp)return1;当b多项式不存在或者a多项式的指数大于b的的时候，返回1elseif(!a||a-expb-exp)return-1;当a多项式不存在或者b多项式的指数大于a的的时候，返回-1elsereturn0;//其他情况返回0}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(Polynpa,Polynpb){Polynqa=pa-next;Polynqb=pb-next;Polynheadc,hc,qc;hc=newPolynomial;//建立一个新的结点hc-next=NULL;headc=hc;while(qa||qb){qc=newPolynomial;//新建一个结点switch(compare(qa,qb)){//调用compare函数对两个多项式进行比较case1://a多项式的指数大于b的{qc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;}case0://有同类项则合并{qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;}case-1:a多项式的指数小于b的{qc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break;}}if(qc-coe!=0){//当相加系数不为0时qc-next=hc-next;hc-next=qc;hc=qc;}elsedeleteqc;//当相加系数为0时，释放该结点}returnheadc;}两个多项式的减法。两个多项式的减法是建立在加法的的基础上，对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减PolynSubtractPolyn(Polynpa,Polynpb){Polynh=pb;