多项式的数组表示

Question

我正在阅读多项式的链表实现。它指出，

Compare this representation with storing the same
polynomial using an array structure.
In the array we have to have keep a slot for each exponent
of x, thus if we have a polynomial of order 50 but containing
just 6 terms, then a large number of entries will be zero in
the array.

我想知道我们如何在数组中表示多项式？请指导我。

谢谢

Answer 1

基于数组的多项式的完整 Java 实现在这里：https : //cs.lmu.edu/~ray/classes/dsa/assignment/2/answers/

基本思想是，如果你有一个多项式

4x^6-2x+5

那么你的数组看起来像

   0     1    2    3    4    5    6
+----+-----+----+----+----+----+----+
| 5  |  -2 |  0 |  0 |  0 |  0 |  4 |
+----+-----+----+----+----+----+----+

那是

• 系数 5 在数组的槽 0 中（代表 5x^0）
• 系数 -2 在数组的第 1 槽中（代表 -2x^1）
• 系数 4 在数组的第 6 槽中（代表 4x^6）

您可能会看到这种表示对于像这样的多项式来说是多么浪费

3x^5000 + 2

在这种情况下，您希望使用稀疏数组表示。最简单的方法是使用一个映射（字典），其键是指数，其值是系数。