概要
參考《大話數據結構》，把常用的基本數據結構梳理一下。
線性表
定義
線性表(List)：零個或多個數據元素的有限序列。
若將線性表記為 \((a_1, \cdots, a_{i-1}, a_i, a_{i+1}, \cdots, a_n)\)，則表中 \(a_{i-1}\) 領先于 \(a_i\)，\(a_i\) 領先于 \(a_{i+1}\)，稱 \(a_{i-1}\) 是 \(a_i\) 的直接前驅元素，\(a_{i+1}\) 是 \(a_i\) 的直接后繼元素。線性表的元素個數 \(n\) 定義為線性表的長度，當 \(n=0\) 時，稱為空表。
線性表的順序存儲結構
線性表的順序存儲結構就是在內存中找了塊地兒，通過占位的形式，把一定的內存空間給占了，然后把相同數據類型的數據元素依次存放在這塊空地中。因此可以用一維數組來實現順序存儲結構，即把第一個數據元素存到數組下標為 \(0\) 的位置中，接著把線性表相鄰的元素存儲在數組中相鄰的位置。
來看看線性表的順序存儲結構的代碼。
# define MAXSIZE 20 //存儲空間初始分配量
typedef int ElemType; // ElemType 類型根據實際情況而定，這里假設為 int
typedef struct
{
ElemType data[MAXSIZE]; // 數組存儲數據元素，最大值為 MAXSIZE
int length; // 線性表當前長度
}SqList;
這里注意描述順序存儲結構需要三個屬性：
存儲空間的起始位置：數組 data，它的存儲位置就是存儲空間的存儲位置
線性表的最大存儲容量：數組長度 MAXSIZE(注意不等于線性表的長度)。
線性表的當前長度：length.
線性表順序存儲結構的優缺點
線性表的順序存儲結構，在存、讀數據時，不管是哪個位置，時間復雜度都是 \(O(1)\)；而插入或刪除時，時間復雜度都是 \(O(n)\). 這就說明它比較適合元素個數不太變化，而更多是存取數據的應用。優缺點總結如下：
優點：
無須為表示表中元素之間的邏輯關系而增加額外的存儲空間
可以快速地存取表中任一位置的元素
缺點：
插入和刪除操作需要移動大量元素
當線性表長度變化較大時，難以確定存儲空間的容量
造成存儲空間的 “碎片”
線性表的鏈式存儲結構
在鏈式結構中，除了要存數據元素信息外，還要存儲它的直接后繼元素的存儲地址，我們把存儲數據元素信息的域稱為數據域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。這兩部分信息組成數據元素 \(a_i\) 的存儲映像，稱為結點。\(n\) 個結點鏈結成一個鏈表，即為線性表 \((a_1, a_2, \cdots, a_n)\) 的鏈式存儲結構*，因為此鏈表的每個結點只包含一個指針域，所以叫做單鏈表**。
對于線性表來說，總得有個頭有個尾，我們把鏈表中第一個結點的存儲位置叫做頭指針，那么整個鏈表的存取就必須是從頭指針開始進行了。之后的每一個結點，其實就是上一個后繼指針指向的位置。最后一個結點的指針為“空”(通常用 NULL 或 “^” 符號來表示)。
有時，為了更加方便地對鏈表進行操作，會在單鏈表的第一個結點前附設一個結點，稱為頭結點。頭結點的數據域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息，頭結點的指針域存儲指向第一個結點的指針，如圖
注意頭指針與頭結點的異同點：
頭指針：
頭指針是指鏈表指向第一個結點的指針，若鏈表有頭結點，則是指向頭結點的指針
頭指針具有標識作用，所以常用頭指針冠以鏈表的名字
無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素
頭結點
頭結點是為了操作的統一和方便而設立的，放在第一元素的結點之前，其數據域一般無意義(也可存放鏈表的長度)
有了頭結點，對在第一元素結點前插入結點和刪除第一結點，其操作與其它結點的操作就統一了
頭結點不一定是鏈表必須要素
來看看線性表的鏈式存儲結構的代碼。
// 線性表的單鏈表存儲結構
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; // 定義 LinkList
從這個結構定義中，我們也就知道，結點由存放數據元素的數據域存放后繼結點地址的指針域組成。假設 \(p\) 是指向線性表第 \(i\) 個元素的指針，則該結點 \(a_i\) 的數據域我們可以用 \(p->data\) 來表示，\(p->data\) 的值是一個數據元素，結點 \(a_i\) 的指針域可以用 \(p->next\) 來表示，\(p->next\) 的值是一個指針，指向第 \(i+1\) 個元素，即指向 \(a_{i+1}\) 的指針。也就是說，如果 \(p->data = a_i\)，那么 \(p->next->data = a_{i+1}\).
單鏈表結構與順序存儲結構優缺點
簡單地對單鏈表結構和順序結構做對比：
通過上面的對比，我們可以得出一些經驗性的結論
若線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結構。若需要頻繁插入和刪除時，宜采用單鏈表結構。
當線性表中的元素個數變化較大或者根本不知道有多大時，最好用單鏈表結構，這樣可以不需要考慮存儲空間的大小問題。如果事先知道線性表的大致長度，比如一年 12 個月，一周就是 7 天，這種用順序存儲結構效率會好很多
總之，線性表的存儲結構和單鏈表結構各有優缺點，視實際情況而定。
最后簡單說一下靜態鏈表。靜態鏈表是用數組描述的鏈表，我們讓數組的元素都是由兩個數域組成， data 和 cur. 也就是說，數組的每個下標都對應一個 data 和下一個 cur. 數據域 data，用來存放數據元素，也就是通常我們要處理的數據；而游標 cur 相當于單鏈表中的 next 指針，存放該元素的后繼在數組中的下標。所以它還有個別名：游標實現法。它有單鏈表的插入和刪除操作性能，但是沒有解決連續存儲分配帶來的表長難以確定的問題，而且失去了順序存儲結構隨機存取的特性。
