数据结构一元多项式的实现.PDF

数据结构一元多项式的实现 徐连龙 李 玲 (重庆正大软件技术学院) 1问题分析 3．2系统设计 内容 1．1问题描述 多项式运算程序具有 以下基本功能：1．界面输出，提示 设计一个n元多项式程序，并完成多项式的乘法运算。从 如何输入数据。要求先输入多项式的项数；2．创建多项式。接 实际的角度出发，这里设计的程序是基于一元n次多项式的数学 收输入的数据，并保存到链表中；3．显示程序的功能表，允许 模型。 使用者选择运算类型；4．显示已经创建好的多项式；6．实现 1．2问题的数学模型 加法运算；7．实现减法运算；8．实现乘法运算；9．清除内存 在数学上，一个～元多项式Pn(x)可按升幂写成：Pnx)--a 内容，销毁创建的链表，退出程序。 O+alx~a2x^2十_．+·anX^N一1．它由n+1个系数惟一确定，因 3．3功能算法描述与数据结构说明 此，在计算机里，它可用一个线性表P来表示：Pn=(aO，a1，a2， 该多项式程序除了main0函数外，主要有以下函数： … ， an)每一项的指数i隐含在其系数ai的序号里。 PolynCreatePolyn(Polynhead，intm)、voidInsert(Polyn 多项式的乘法规则：多次运用单项式与多项式相乘的法 P，Polyn h)、Polyn AddPolyn(Polyn pa，Polyn pb)、int 则得到的．计算时(a+h)m+n)，先把 (m+n)看成一个单项式， compare(Polyn a，Polyn b)、Polyn SubtractPolyn(Polyn (a+b)是一个多项式，运用单项式与多项式相乘的法则，得到 pa，Polyn pb)、PolynMultiplyP。lyn(Polynpa，Polynpb)。下 (a+b)(m十n)=a(m十n)+b(m十n)，然后再次运用单项式与多项式相乘 面对这些函数逐一介绍。 的法则。 (1)PolynCreatePolyn(Polynhead，intm) 1．3构造数据结构 该函数功能是创建新的多项式链表。intm保存的多项式 通过分析多项式的特征，不难看出多项式是由单项式构成 的项数，使用for语句，控制输入多项式的每一项。当创建的链 的，而每个单项式都具有系数和指数，当系数为0时，该项就 表长度为m时，将不再提示用户继续输入多项式的系数和指数。 失去了意义，在计算机内要表示一个多项式，至少以下数据信 (2)void Insert(PolynP，Polynh) 息：系数信息、指数信息和指向下一个单项式的指针。通过指 该函数功能：将新的节点P插入到现有链表的后面，并确 针，我们就可以把多个单项式连接起来，形式一个多项式，需 保多项式的指数exp是升序 。将S节点插入到head所指向的链 要说明的是从广义的角度讲，单项式也是一个多项式。基于以 表。在该函数的操作中，要注意指针是如何移动的。 上的分析，我们定义多项式的数据结构为如下形式： (3)PolynAddPolyn(Polynpa，Polynpb) publicclassPolyn( 该函数功能：实现两个多项式pa、pb相加，并将计算结果 floatcoef；／／系数 存储于新建立的pc中，它的原理是将指数相同的单项式相加， intexpn；／／指数 系数相加后为0，则pa、pb的指针都后移。在加法计算中要求 Polynnext；／／指向下一个结点 pa，与pb的幂次序都是升序，否则可能得到错误的结果。 ) ／／链表节点类构造