算法学习 | 数据结构（一）

思考：如果我们需要用程序来表示一个多项式,如

$$

y = 3x^4+2x^2+1

我们可以使用哪些东西呢？

我们可以用一个数组a[i]来存储这个多项式

i

1

2

3

4

a[i]

我们可以看到这里我们用i来表示幂次，用a[i]来表示方程的系数。

但是这里有一个问题，如果我们要表示的式子是

y = 5x^2+x^9

我们需要一个分量为9的数组来存储这个多项式，我们仅仅用到了其中的两位。

每个节点存储多项式中的一个非零项

链表上每个元素含有指数和系数两个值，在使用链表之后我们存储上面的多项式只需要两个分量。

线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在顺序存储中元素在逻辑上和物理上都是相连的

在第i个位置插入一个值为X的元素

元素在逻辑上相连，在物理上不一定相连

时间复杂度O(n)

（1）先构造一个新结点

（2）找到第i-1个结点

（3）修改指针，插入结点

（1）先找到链表的第i-1个结点

（2）再用指针s指向要删除的结点

（3）然后修改指针，删除s结点

（4）释放s所指结点的空间

广义表是线性表的推广，在广义表中，这些元素不仅是单元素也可以是另外一个广义表

多重链表中结点的指针域会有多个，上面的程序中包含了Data和SubList两个指针域。

多重链表有广泛的用途，后面的树和图这样的数据结构都可以使用多重链表实现存储,我们将在后面和他有更深的接触！