课程设计-一元稀疏多项式计算器程序

课程设计成果学院:计算机工程学院班级:计算机科学与技术班学生姓名:学号:设计地点（单位）：设计题目:一元稀疏多项式计算器程序完成日期：年月日成绩(五级记分制):________________教师签名:_________________________荆楚理工学院课程设计任务书设计题目：学生姓名王巍课程名称数据结果专业班级13级计算机科学与技术1班地点起止时间设计内容及要求设计参数进度要求参考资料其它说明1.本表应在每次实施前一周由负责教师填写二份，教研室审批后交学院院备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任：指导教师：年月日目录1需求分析...........................................................................................................12设计概要...........................................................................................................22.1基本结构.......................................................................................................................22.2基本功能模块图..........................................................................................................23算法思想............................................................................................................33.1建立多项式...................................................................................................................33.2多项式相加...................................................................................................................33.3多项式相减...................................................................................................................33.4链表的输出...................................................................................................................34详细设计...........................................................................................................44.1函数功能介绍..............................................................................................................44.2结构体的定义...............................................................................................................44.3产生链表函数...............................................................................................................44.4插入结点.......................................................................................................................54.5多项式的相加函数.......................................................................................................54.6多项式相减函数...........................................................................................................74.7主函数...........................................................................................................................75测试结果及运行效果.....................................................................................10参考文献.............................................................................................................13附录全部代码...................................................................................................1411需求分析1、一元多项式简单计算器的基本功能是：1.1输入并建立多项式；1.2输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；1.3多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点2、设计思路：2.1定义线性表的动态分配顺序存储结构；2.2建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析：要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为序数coef指数expn指针域next运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：①若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。②若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。22设计概要2.1基本结构1、元素类型、结点类型和指针类型：typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;2、建立一个头指针为head、项数为m的一元多项式,建立新结点以接收数据,调用Insert函数插入结点:PolynCreatePolyn(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head-next=NULL;for(i=0;im;i++){p=(Polyn)malloc(sizeof(structPolynomial));printf(请输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);}returnhead;3、主函数和其他函数：voidmain(){intm,n,a,x;charflag;Polynpa=0,pb=0,pc;}floatValuePolyn(Polynhead,intx)//输入x值，计算并返回多项式的值2.2基本功能模块图主函数voidmain()多项式相加减PolynAddPolyn(Polynpa,Polynpb)PolynSubtractPolyn(Polynpa,Polynpb)创建单链表PolynCreatePolyn(Polynhead,intm)输出多项式voidPrintPolyn(PolynP)33算法思想3.1建立多项式一元多项式是由多个项的和组成的，将一元多项式的每个项用一结点表示，该结点中应包括该项的系数、该项的指数、指向下一项的指针，可以用线性表来依次输入各项结点，从而完成多项式链表的建立，为了使原多项式各项顺序不变，故采用尾插法建表。3.2多项式相加多项式的相加主要是通过将多项式的每一项的指数cxpn进行比较，当指数expn相同时，将两个结点中的系数coef相加存放在第一个链表中，然后释放第二条链表中的这个结点。当两个结点中的指数expn不相同时，按高次在前低次在后降序的插入到链表当中。3.3多项式相减多项式的相减过程，其实就是相同指数的项的系数相减，对于不同指数的项，若是被减多项式，则将该结点复制输出，若是减多项式，则将该结点的系数变为原系数的相反数输出，将结果用降幂输出函数输出。3.4链表的输出PrintPolyn(PolynP)函数接收链表的头结点地址，然后依次输出两个链表合并后的链表中的每个结点的中的系数和指数。44详细设计4.1函数功能介绍voidmain()//该函数根据用户的选择，完成指定的操作函数并根据用户的选择，完成指定的操作PolynCreatePolyn(Polynhead,intm)/*制造链表的头结点，并调用voidInsert(Polynp,Polynh)函数实现根据多项式项数创建对应数量个节点的链表*/voidInsert(Polynp,Polynh)/*向存储链表的多项式中插入结点*/voidDestroyPolyn(Polynp)/*该函数用来释放结点，在加减操作中当多项式一项的系数为0或两项的指数相同进行相加或相减时可用次函数来释放对应的结点*/intcompare(Polyna,Polynb)//该函数用于判断两个链表在加减状态中结点的状态PolynAddPolyn(Polynpa,Polynpb)//该函