m元多项式的表示

Published: by Creative Commons Licence

在一般的情况下使用的广义表多数既非递归表,也不为其他表所共享。

可以这样子来理解广义表:广义表中的一个数据元素可以是另一个广义表。(一个m元多项式的表示就是广义表的这种应用的典型实例)

在之前的博文一元多项式的表示及相加中有关于一元多项式的表示方法。

在文中,一个一元多项式可以用一个长度为m且每个数据元素有两个数据项(系数项、指数项)的线性表来表示。

那么问题来了,m元多项式如何表示呢?

一个m元多项式的每一项,最多有m个变元。如果用线性表来表示,则每个数据元素需要m+1个数据项(存储一个系数值和m个指数值)。这会产生两个问题:

  1. 无论多项式中各项的变元数是多少,若都按m个变元分配存储空间,则将造成空间浪费;反之,若按各项实际的变元数分配存储空间,就会造成结点的大小不均匀,给操作带来不便;
  2. 对m值不同的多项式,线性表中的结点大小也不同,这同样会引起存储管理的不便。

由于m元多项式中每一项的变化数目的不均匀性和变元信息的重要性,故不适合用线性表表示。

下面是一个三元多项式的例子:

三元多项式

因为各项的变元数目不尽相同,而某些因子又重复出现,于是我们改写为如下形式:

改写

改写的小技巧:先z后y

推广一波:

任何一个m元多项式都可以如此做,先分解出一个主变元,随后再分解出第二个主变元,等等…

由此,一个m元多项式首先是他主变元的多项式,而其系数又是第二主变元的多项式,由此可用广义表来表示m元多项式。

例如上述三元多项式可用如下广义表表示,广义表的深度即为变元个数:

P=z((A,2),(B,1),(15,0))

其中
	A = y((C,3),(D,2))
	C = x((1,10),(2,6))
	D = x((3,5))
	
	B = y((E,4),(F,1))
	E = x((1,4),(6,3))
	F = x((2,0))

至于广义表的存储结构,日后更。