如何定義鏈表結點的數據結構？
加入技術交流群
1.1.1 數據與p_next分離
本文引用地址：http://m.butianyuan.cn/article/201807/383764.htm由于鏈表只關心p_next指針，因此完全沒有必要在鏈表結點中定義數據域，那么只保留p_next指針就好了。鏈表結點的數據結構(slist.h)定義如下：
1 typedef struct _slist_node{
2 struct _slist_node *p_next; // 指向下一個結點的指針
3 }slist_node_t;
由于結點中沒有任何數據，因此節(jié)省了內存空間，其示意圖詳見圖3.10。
圖3.10 鏈表示意圖
當用戶需要使用鏈表管理數據時，僅需關聯數據和鏈表結點，最簡單的方式是將數據和鏈表結點打包在一起。以int類型數據為例，首先將鏈表結點作為它的一個成員，再添加與用戶相關的int類型數據，該結構體定義如下：
1 typedef struct _slist_int{
2 slist_node_t node; // 包含鏈表結點
3 int data; // int類型數據
4 }slist_int_t;
由此可見，無論是什么數據，鏈表結點只是用戶數據記錄的一個成員。當調用鏈表接口時，僅需將node的地址作為鏈表接口參數即可。在定義鏈表結點的數據結構時，由于僅刪除了data成員，因此還是可以直接使用原來的slist_add_tail()函數，管理int型數據的范例程序詳見程序清單3.14。
程序清單3.14 管理int型數據的范例程序
1 #include
2 typedef struct _slist_int{
3 slist_node_t node;
4 int data;
5 }slist_int_t;
6
7 int main (void)
8 {
9 slist_node_t head = {NULL};
10 slist_int_t node1, node2, node3;
11 slist_node_t *p_tmp;
12
13 node1.data = 1;
14 slist_add_tail(head, node1.node);
15 node2.data = 2;
16 slist_add_tail(head, node2.node);
17 node3.data = 3;
18 slist_add_tail(head, node3.node);
19 p_tmp = head.p_next;
20 while (p_tmp != NULL){
21 printf(%d , ((slist_int_t *)p_tmp)->data);
22 p_tmp = p_tmp->p_next;
23 }
24 return 0;
25 }
由于用戶需要初始化head為NULL，且遍歷時需要操作各個結點的p_next指針。而將數據和p_next分離的目的就是使各自的功能職責分離，鏈表只需要關心p_next的處理，用戶只關心數據的處理。因此，對于用戶來說，鏈表結點的定義就是一個“黑盒子”，只能通過鏈表提供的接口訪問鏈表，不應該訪問鏈表結點的具體成員。
為了完成頭結點的初始賦值，應該提供一個初始化函數，其本質上就是將頭結點中的p_next成員設置為NULL。鏈表初始化函數原型為：
int slist_init (slist_node_t *p_head);
由于頭結點的類型與其它普通結點的類型一樣，因此很容易讓用戶誤以為，這是初始化所有結點的函數。實際上，頭結點與普通結點的含義是不一樣的，由于只要獲取頭結點就可以遍歷整個鏈表，因此頭結點往往是被鏈表的擁有者持有，而普通結點僅僅代表單一的一個結點。為了避免用戶將頭結點和其它結點混淆，需要再定義一個頭結點類型(slist.h)：
typedef slist_node_t slist_head_t;
基于此，將鏈表初始化函數原型(slist.h)修改為：
int slist_init (slist_head_t *p_head);
其中，p_head指向待初始化的鏈表頭結點，slist_init()函數的實現詳見程序清單3.15。
程序清單3.15 鏈表初始化函數
1 int slist_init (slist_head_t *p_head)
2 {
3 if (p_head == NULL){
4 return -1;
5 }
6 p_head -> p_next = NULL;
7 return 0;
8 }
在向鏈表添加結點前，需要初始化頭結點。即：
slist_node_t head;
slist_init(head);
由于重新定義了頭結點的類型，因此添加結點的函數原型也應該進行相應的修改。即：
int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node);
其中，p_head指向鏈表頭結點，p_node為新增的結點，slist_add_tail()函數的實現詳見程序清單3.16。
程序清單3.16 新增結點范例程序
1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)
2 {
3 slist_node_t *p_tmp;
4
5 if ((p_head == NULL) || (p_node == NULL)){
6 return -1;
7 }
8 p_tmp = p_head;
9 while (p_tmp -> p_next != NULL){
10 p_tmp = p_tmp -> p_next;
11 }
12 p_tmp -> p_next = p_node;
13 p_node -> p_next = NULL;
14 return 0;
15 }
同理，當前鏈表的遍歷采用的還是直接訪問結點成員的方式，其核心代碼如下：
1 slist_node_t *p_tmp = head.p_next;
2 while (p_tmp != NULL){
3 printf(%d , ((slist_int_t *)p_tmp)->data);
4 p_tmp = p_tmp->p_next;
5 }
這里主要對鏈表作了三個操作：(1)得到第一個用戶結點;(2)得到當前結點的下一個結點;(3)判斷鏈表是否結束，與結束標記(NULL)比較。
基于此，將分別提供三個對應的接口來實現這些功能，避免用戶直接訪問結點成員。它們的函數原型為(slist.h)：
slist_node_t *slist_begin_get (slist_head_t *p_head); // 獲取開始位置，第一個用戶結點
slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos);// 獲取某一結點的后一結點
slist_node_t *slist_end_get (slist_head_t *p_head); // 結束位置，尾結點下一個結點的位置
其實現代碼詳見程序清單3.17。
程序清單3.17 遍歷相關函數實現
1 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos)
評論