数据结构元稀疏计算器.docVIP

一、课程题目：一元稀疏多项式简单计算器 二、需求分析： ⒈一元稀疏多项式简单计算器的基本功能是： ⑴输入并建立多项式； ⑵输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,Cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； ⑶多项式a和b相加，建立多项式a+b； ⑷多项式a和b相减，建立多项式a-b； ⑸计算多项式在x处的值； ⑹求多项式a，b的导函数。 ⒉设计思路： 2.1定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next； 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式。 2.4 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的数据输入（滤去输入中的非法字符）建立的多项式和运行结果先是在屏幕上。 ⒊设计思路分析： 要解决多项式的加法运算，就必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将节点结构体定义为 运用尾插法建立两条单链表，以单链表poly p和poly head分别表示多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表poly p中的结点插入到poly head中），因此“和多项式“中的结点无需另外生成；为了实现处理，设p.q分别指向单链表poly a和poly b的当前项，比较p，q结点的指数项，由此得到下列运算规则： ①若p-expq-exp,则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 ②若p-exp=q-exp,则将这两个结点中的系数相加，当和不为0时修改结点p的系数。 ③若p-expq-exp, ,则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来连表上后移。 4.测试数据： ⑴(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7) ⑵(6x^-3-x+4.4x^2-1.2x^9)-(-6x^-3+5.4x^2+7.8x^15)=（-7.8x^15-1.2x^9+12x^-3-x） Poly CreateList(Poly head,int m) 操作结果：建立一个头指针为head、项数为m的一元多项式。 void DestroyList(Poly p) 初始条件：一元多项式p已存在。 操作结果：销毁一元多项式p。 int OutputList(Poly P) 初始操作：一元多项式p已存在。 操作结果:输出一元多项式p。 int compare(Poly a,Poly b) 初始操作：一元多项式a和b已存在。 操作结果：比较两个多项式是否非空。 Poly AddPoly(Poly pa,Poly pb) 初始条件：一元多项式pa和pb已存在。 操作结果：完成多项式相加运算，即pa=pa+pb并销毁一元多项式pb。 Poly SubtractPoly(Poly pa,Poly pb) 初始条件：一元多项式pa和pb已存在。 操作结果：完成多项式相减运算，即pa=pa-pb并销毁一元多项式pb。 Poly MultiplyPoly(Poly pa,Poly pb) 初始条件：一元多项式pa和pb已存在。 操作结果：完成多项式相乘运算，即pa=pa*pb并销毁一元多项式pb。 void DevicePoly(Poly pa,Poly pb) 初始条件：一元多项式pa和pb已存在。 操作结果：完成多项式相除运算，即pa=pa/pb并销毁一元多项式pb。 float ValuePoly(Poly head,float x) 操作结果：输入x值，计算并返回多项式的值。 Poly Derivative(Poly head) 操作结果：求解并建立