线性表的应用

线性表的合并

例子： 求解一般集合的并集问题。

已知两个集合 $A$ 和 $B$，现要求一个新的集合 $A=A\cup B$。例如，设

$$\begin{gathered} A=(7,5,3,11) \\ B=(2,6,3) \end{gathered}$$

合并后

$$A=(7,5,3,11,2,6)$$

算法如下：

/**
 * 线性表的合并
 * @param a 线性表 a
 * @param b 线性表 b
 */
export function union<T>(a: List<T>, b: List<T>) {
  let aLength = a.length
  for (let i = 1; i <= b.length; i++) {
    const ele = getElement(b, i)
    if (!find(a, ele)) {
      insert(a, ++aLength, ele)
    }
  }
}

假设 $A$、$B$ 长度分别为 $m$ 和 $n$，则时间复杂度为 $O(m\times n)$。

有序表的合并

若线性表中的元素之间可以比较，并且元素在线性表中依值递增或递减有序排列，则称该线性表为有序表（Ordered List）。

例子：求解有序集合的并集问题。

有序集合是指集合中的元素有序排列。已知有两个有序集合 $A$ 和 $B$，元素按值递增有序排列，现要求一个新的集合 $C=A\cup B$，使集合 $C$ 中的元素仍按值递增有序排列。例如，设

$$\begin{gathered} A=(3,5,8,11) \\ B=(2,6,8,9,11,15,20) \end{gathered}$$

则

$$C=(2,3,5,6,8,9,11,15,20)$$

算法如下：

/**
 * 有序表的合并
 * @param a 有序表 a
 * @param b 有序表 b
 */
export function unionOrdered<T>(a: List<T>, b: List<T>) {
  let preva = a.headNode.next
  let prevb = b.headNode.next
  const _union = new List<T>()
  let prevc = _union.headNode

  while (preva && prevb) {
    if (!preva.data || !prevb.data)
      throw new Error('Elements must be sortable!')

    if (preva.data <= prevb.data) {
      if (preva.data === prevb.data) {
        prevb = prevb.next
      }
      prevc.next = new ListNode(preva.data)
      prevc = prevc.next
      preva = preva.next
    } else {
      prevc.next = new ListNode(prevb.data)
      prevc = prevc.next
      prevb = prevb.next
    }
    _union.length++
  }

  prevc.next = preva ?? prevb

  while (prevc.next) {
    _union.length++
    prevc = prevc.next
  }
  return _union
}

假设 $A$、$B$ 长度分别为 $m$ 和 $n$，则时间复杂度为 $O(m+n)$。

一元多项式的运算

一元多项式按升幂写成：

$$P_n(x)=p_0+p_{1}x+p_2{x}^2+\dots +p_n{x}^n$$

要求：实现两个一元多项式的相加运算。

可以看出，一元多项式由 $n+1$ 个系数唯一确定，因此，可以将一元多项式 $P_n(x)$ 抽象为一个由 $n+1$ 个元素组成的有序序列，可用一个线性表 $P$ 来表示：

$$P=(p_0,p_1,p_2,\dots ,p_n)$$

每一项的指数 $i$ 隐含在其系数 $p_i$ 的序号中。

假设 $Q_m(x)$ 是一元多项式，同样可用线性表 $Q$ 来表示：

$$Q=(q_0,q_1,q_2,\dots ,q_m)$$

设 $m⩽n$，则两个多项式相加的结果 $R_n(x)=P_n(x)+Q_m(x)$ 可用线性表 $R$ 表示：

$$R=(p_0+q_0,p_1+q_1,p_2+q_2,\dots ,p_m+q_m,p_{m+1},\dots ,p_n)$$

对于此类线性表，我们可以使用数组来实现。

数组 $p$：数组中每个元素 $p[i]$ 代表多项式每项系数 $p_i$，下标 $i$ 代表对应项的指数。

例如：$P(x)=10+5x-4x^2+3x^3+2x^4$ 用数组表示如下。

指数（下标 $i$）	0	1	2	3	4
系数 $p[i]$	10	5	-4	3	2

算法如下：

/**
 * 两个一元多项式相加
 * @param p 一元多项式
 * @param q 一元多项式
 */
export function add(p: number[], q: number[]) {
  const length = Math.max(p.length, q.length)
  const result: number[] = []

  for (let i = 0; i < length; i++) {
    result[i] = (p[i] ?? 0) + (q[i] ?? 0)
  }
  return result
}

稀疏多项式

在通常的应用中，我们更可能遇到的多项式是稀疏多项式^[1]。

例如：$S(x)=1+3x^{10000}+2x^{20000}$

在处理上面这种多项式时，就要用一个长度为 20001 的线性表表示，但表中只有 3 个非零元素。此时将极大地浪费存储空间。由于线性表的元素可以包含多个数据项，由此可改变元素设定，对多项式的每一项，使用（系数，指数）唯一确定。则一元多项式可写成一下形式：

$$p_n(x)=p_1{x}^{e_1}+p_2{x}^{e_2}+\dots +p_m{x}^{e_m}$$

其中，$p_i$ 是指数为 $e_i$ 的项的非零系数，且满足

$$0⩽e_1<e_2<\dots <e_m=n$$

若用一个长度为 $m$ 且每个元素有两个数据项（系数和指数）的线性表

$$((p_1,e_1),(p_2,e_2),\dots ,(p_m,e_m))$$

则可唯一确定多项式 $P_n(x)$。在最坏情况下，$m$ 个系数不为零，也只比存储每项系数的方案多使用一倍存储空间。但是，对于稀疏多项式将大大节省空间。

多项式链表创建算法如下：

/**
 * 创建多项式链表
 * @param ele coef: 系数; expn: 指数
 */
export function createPolynList(ele: { coef: number; expn: number }[]) {
  const list = new List<{ coef: number; expn: number }>()
  list.length = ele.length

  ele.forEach((e) => {
    const newNode = new ListNode(e)
    let prev = list.headNode.next
    let tmp = list.headNode

    while (prev && newNode.data!.expn > prev.data!.expn) {
      tmp = prev
      prev = prev.next
    }
    newNode.next = prev
    tmp.next = newNode
  })

  return list
}

---

1. 多项式的次数可能很高且变化很大 ↩︎