鏈表
1. 常見的鏈表有單鏈表和雙鏈表
單鏈表
單鏈表的每個結點由用於存數據的 data 和指向下一個結點的指針 next 構成
typedef struct LNode{
ElemType data; // 單鏈表的數據域
struct LNode *next; // 單鏈表的指針域
} LNode, *LinkList; // LinkList為指向LNode的指針類型有 *LinkList 時，在定義單鏈表就可以寫成 LinkList L；若沒有，則只能寫成 LNode *L；
雙鏈表
雙鏈表的每個結點由用於存數據的 data、指向上一個節點的指針 prev 以及指向下一個節點的指針 next 構成
typedef struct LNode{
ElemType data;
struct LNode *prev, *next; // 指向上一個節點的指針prev和指向下一個節點的指針next
} DNode, *DLinkList;2. 鏈式存儲和順序存儲
鏈式存儲是一種非連續的物理存儲結構，其中數據元素存儲在分散的節點（Node）中，每個節點包含：數據域和指針域。
順序存儲是一種連續的物理存儲結構，其中數據元素按邏輯順序依次存儲在一組地址連續的存儲單元中。通常通過數組（Array）實現，可以通過基地址 + 偏移量直接計算任何元素的存儲位置。
|
操作
|
鏈式存儲
|
順序存儲
|
説明
|
|
訪問第i個元素
|
O(n)
|
O(1)
|
鏈表需要從頭遍歷
|
|
插入/刪除（頭部）
|
O(1)
|
O(n)
|
數組需要移動元素
|
|
插入/刪除（中間）
|
O(n) 查找 + O(1) 操作
|
O(n) 移動
|
鏈表查找慢，操作快
|
|
插入/刪除（尾部）
|
O(n) 或 O(1)（有尾指針）
|
O(1)（容量足夠）或 O(n)（擴容）
|
|
|
內存利用率
|
較低（有指針開銷）
|
較高（只有數據）
|
鏈表每個節點都有指針開銷
|
|
緩存友好性
|
差（內存不連續）
|
好（內存連續）
|
CPU緩存預取對數組更有利
|
常見的順序存儲的實例就是數組和順序表。
下面以數組來講解順序存儲的元素在內存中的定位問題：
對於數組 ElemType a[]
如果想訪問第n個元素，可以直接使用下標索引 a[n-1]
這裏第n個元素在內存中的地址就是：
address_n = address_a[0] + sizeof(ElemType) * n這裏補充一下數組的定義：
數組的定義有兩種方法
a. 靜態定義
ElemType data[MAXSIZE];b. 動態定義
ElemType *data;
data = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);這裏使用C++中的new操作符書寫：
ElemType* data = new ElemType[MAXSIZE];關於內存分配函數的一些知識
|
函數
|
malloc
|
calloc
|
realloc
|
|
參數
|
size (字節數)
|
num (元素個數), size (元素大小)
|
ptr (原指針), new_size (新大小)
|
|
是否初始化
|
不初始化（內容是隨機的）
|
初始化為0
|
保持原有數據（新空間不初始化）
|
|
性能
|
較快
|
較慢
|
取決於情況
|
|
常用場景
|
一般內存分配
|
需要清零的數組
|
動態調整數組大小
|
int *arr = (int*)malloc(n * sizeof(int)); // 分配n個整數的空間
int *arr = (int*)calloc(n, sizeof(int)); // 分配並清零一個整數數組
int *arr = (int*)malloc(3 * sizeof(int));
int *temp = (int*)realloc(arr, 5 * sizeof(int)); // 拓展原數組至5個整數的空間3. 頭指針，頭結點和首元結點
頭指針：指向鏈表中第一個結點的指針
首元結點：鏈表中存儲第一個數據元素a₁的結點
頭結點：在鏈表的首元結點前附設的一個結點，data域為空
4. 單鏈表建立的兩種方法
a. 頭插法
算法思路：
- 從一個空表開始，重複讀入數據
- 生成新的結點，將讀入的數據存放到新結點的數據域中
- 從最後一個結點開始，依次將各節點插入到鏈表前端
void CreateList_H(LinkList &L, int n){
L = new LNode;
L -> next = NULL;
for(int i = n; i > 0; i--){
p = new LNode;
cin >> p -> data;
p -> next = L -> next;
L -> next = p;
}
}b. 尾插法
算法思路：
- 從一個空表L開始，將新結點逐個插入到鏈表尾部，尾指針r指向鏈表的尾結點
- 初始時，r同L均指向頭結點，每讀入一個數據元素則申請一個新結點，將新結點插入到尾結點後，r指向新結點
void CreateList_R(LinkList &L, int n){
L = new LNode;
L -> next = NULL;
r = L;
for(int i = 0; i < n; i++){
p = new LNode;
cin >> p -> data;
p -> next = NULL;
r -> next = p;
r = p;
}
}