符号多项式的操作,已经成为表处理的典型用例。
在数学上,一个一元多项式Pn(x)可按升幂写成:Pn(x)=p0+p1x+p2x2+….+pnxn它由n+1个系数唯一确定,因此,在计算机里,它可用一个线性表P来表示:P=(p0,p1,p2,…pn)每一项的指数i隐含在其系数pi的序号里。
假设Qm(x)是一元m次多项式,同样可用线性表Q来表示:Q=(q0,q1,q2,…qm)。
不失一般性,设m<n,则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)可用线性表R表示:R=(p0+q0,p1+q1,p2+q2,…,pm+qm,pm+1,…pn)。
显然,我们可以对P、Q和R采用顺序存储结构,使得多项式相加的算法定义十分简约。
至此,一元多项式的表示及相加问题似乎已经解决了。
然而在通常的应用中,多项式的次数可能很高且变化很大,使得顺序存储结构的最大长度很难决定。
特别是在处理形如:S(x)=1+3x10000+2x20000的多项式时,就要用一长度为20001的线性表来表示,表中仅有三个非零元素,这种对内存空间的浪费是应当避免的,但是如果只存储非零系数项则显然必须同时存储相应的指数。
一般情况下的一元n次多项式可写成:Pn(x)=p1xe1+p2xe2+…+pmxem其中pi,是指数为ei的项的非零系数,且满足0≤e1<e2<…<em=n,若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表便可唯一确定多项式Pn(x)。
((p1,e1),(p2,e2),…,(pm,em))在最坏情况下,n+1(=m)个系数都不为零,则比只存储每项系数的方案要多存储一倍的数据。
但是,对于S(x)类的多项式,这种表示将大大节省空间。
本题要求选用线性表的一种合适的存储结构来表示一个一元多项式,并在此结构上实现一元多项式的加法,减法和乘法操作
1