算法學習 | 資料結構（一）

思考：如果我們需要用程式來表示一個多項式,如

$$

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兩個指針域。

多重連結清單有廣泛的用途，後面的樹和圖這樣的資料結構都可以使用多重連結清單實作存儲,我們将在後面和他有更深的接觸！