如何定義鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)？
掃描二維碼
隨時隨地手機(jī)看文章
1.1.1 數(shù)據(jù)與p_next分離
由于鏈表只關(guān)心p_next指針，因此完全沒有必要在鏈表結(jié)點(diǎn)中定義數(shù)據(jù)域，那么只保留p_next指針就好了。鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)(slist.h)定義如下：
1 typedef struct _slist_node{
2 struct _slist_node *p_next; // 指向下一個結(jié)點(diǎn)的指針
3 }slist_node_t;
由于結(jié)點(diǎn)中沒有任何數(shù)據(jù)，因此節(jié)省了內(nèi)存空間，其示意圖詳見圖3.10。
圖3.10 鏈表示意圖
當(dāng)用戶需要使用鏈表管理數(shù)據(jù)時，僅需關(guān)聯(lián)數(shù)據(jù)和鏈表結(jié)點(diǎn)，最簡單的方式是將數(shù)據(jù)和鏈表結(jié)點(diǎn)打包在一起。以int類型數(shù)據(jù)為例，首先將鏈表結(jié)點(diǎn)作為它的一個成員，再添加與用戶相關(guān)的int類型數(shù)據(jù)，該結(jié)構(gòu)體定義如下：
1 typedef struct _slist_int{
2 slist_node_t node; // 包含鏈表結(jié)點(diǎn)
3 int data; // int類型數(shù)據(jù)
4 }slist_int_t;
由此可見，無論是什么數(shù)據(jù)，鏈表結(jié)點(diǎn)只是用戶數(shù)據(jù)記錄的一個成員。當(dāng)調(diào)用鏈表接口時，僅需將node的地址作為鏈表接口參數(shù)即可。在定義鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)時，由于僅刪除了data成員，因此還是可以直接使用原來的slist_add_tail()函數(shù)，管理int型數(shù)據(jù)的范例程序詳見程序清單3.14。
程序清單3.14 管理int型數(shù)據(jù)的范例程序
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，且遍歷時需要操作各個結(jié)點(diǎn)的p_next指針。而將數(shù)據(jù)和p_next分離的目的就是使各自的功能職責(zé)分離，鏈表只需要關(guān)心p_next的處理，用戶只關(guān)心數(shù)據(jù)的處理。因此，對于用戶來說，鏈表結(jié)點(diǎn)的定義就是一個“黑盒子”，只能通過鏈表提供的接口訪問鏈表，不應(yīng)該訪問鏈表結(jié)點(diǎn)的具體成員。
為了完成頭結(jié)點(diǎn)的初始賦值，應(yīng)該提供一個初始化函數(shù)，其本質(zhì)上就是將頭結(jié)點(diǎn)中的p_next成員設(shè)置為NULL。鏈表初始化函數(shù)原型為：
int slist_init (slist_node_t *p_head);
由于頭結(jié)點(diǎn)的類型與其它普通結(jié)點(diǎn)的類型一樣，因此很容易讓用戶誤以為，這是初始化所有結(jié)點(diǎn)的函數(shù)。實(shí)際上，頭結(jié)點(diǎn)與普通結(jié)點(diǎn)的含義是不一樣的，由于只要獲取頭結(jié)點(diǎn)就可以遍歷整個鏈表，因此頭結(jié)點(diǎn)往往是被鏈表的擁有者持有，而普通結(jié)點(diǎn)僅僅代表單一的一個結(jié)點(diǎn)。為了避免用戶將頭結(jié)點(diǎn)和其它結(jié)點(diǎn)混淆，需要再定義一個頭結(jié)點(diǎn)類型(slist.h)：
typedef slist_node_t slist_head_t;
基于此，將鏈表初始化函數(shù)原型(slist.h)修改為：
int slist_init (slist_head_t *p_head);
其中，p_head指向待初始化的鏈表頭結(jié)點(diǎn)，slist_init()函數(shù)的實(shí)現(xiàn)詳見程序清單3.15。
程序清單3.15 鏈表初始化函數(shù)
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 }
在向鏈表添加結(jié)點(diǎn)前，需要初始化頭結(jié)點(diǎn)。即：
slist_node_t head;
slist_init(&head);
由于重新定義了頭結(jié)點(diǎn)的類型，因此添加結(jié)點(diǎn)的函數(shù)原型也應(yīng)該進(jìn)行相應(yīng)的修改。即：
int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node);
其中，p_head指向鏈表頭結(jié)點(diǎn)，p_node為新增的結(jié)點(diǎn)，slist_add_tail()函數(shù)的實(shí)現(xiàn)詳見程序清單3.16。
程序清單3.16 新增結(jié)點(diǎn)范例程序
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 }
同理，當(dāng)前鏈表的遍歷采用的還是直接訪問結(jié)點(diǎn)成員的方式，其核心代碼如下：
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)得到第一個用戶結(jié)點(diǎn);(2)得到當(dāng)前結(jié)點(diǎn)的下一個結(jié)點(diǎn);(3)判斷鏈表是否結(jié)束，與結(jié)束標(biāo)記(NULL)比較。
基于此，將分別提供三個對應(yīng)的接口來實(shí)現(xiàn)這些功能，避免用戶直接訪問結(jié)點(diǎn)成員。它們的函數(shù)原型為(slist.h)：
slist_node_t *slist_begin_get (slist_head_t *p_head); // 獲取開始位置，第一個用戶結(jié)點(diǎn)
slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos);// 獲取某一結(jié)點(diǎn)的后一結(jié)點(diǎn)
slist_node_t *slist_end_get (slist_head_t *p_head); // 結(jié)束位置，尾結(jié)點(diǎn)下一個結(jié)點(diǎn)的位置
其實(shí)現(xiàn)代碼詳見程序清單3.17。
程序清單3.17 遍歷相關(guān)函數(shù)實(shí)現(xiàn)
1 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos)[!--empirenews.page--]
2 {
3 if (p_pos) { // 找到p_pos指向的結(jié)點(diǎn)
4 return p_pos->p_next;
5 }
6 return NULL;
7 }
8
9 slist_node_t *slist_begin_get (slist_head_t *p_head)
10 {
11 return slist_next_get(p_head, p_head);
12 }
13
14 slist_node_t *slist_end_get (slist_head_t *p_head)
15 {
16 return NULL;
17 }
程序中獲取的第一個用戶結(jié)點(diǎn)，其實(shí)質(zhì)上就是頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)，因此可以直接調(diào)用slist_next_get()實(shí)現(xiàn)。盡管slist_next_get()在實(shí)現(xiàn)時并沒有用到參數(shù)p_head，但還是將p_head參數(shù)傳進(jìn)來了，因?yàn)閷?shí)現(xiàn)其它的功能時將會用到p_head參數(shù)，比如，判斷p_pos是否在鏈表中。當(dāng)有了這些接口函數(shù)后，即可完成遍歷，詳見程序清單3.18。
程序清單3.18 使用各個接口函數(shù)實(shí)現(xiàn)遍歷的范例程序
1 slist_node_t *p_tmp = slist_begin_get(&head);
2 slist_node_t *p_end = slist_end_get(&head);
3 while (p_tmp != p_end){
4 printf("%d ", ((slist_int_t *)p_tmp)->data);
5 p_tmp = slist_next_get(&head, p_tmp);
6 }
由此可見，slist_begin_get()和slist_end_get()的返回值決定了當(dāng)前有效結(jié)點(diǎn)的范圍，其范圍為一個半開半閉的空間，即：[begin,end)，包括begin，但是不包括end。當(dāng)begin與end相等時，表明當(dāng)前鏈表為空，沒有一個有效結(jié)點(diǎn)。
在程序清單3.18所示的遍歷程序中，只有printf()語句才是用戶實(shí)際關(guān)心的語句，其它語句都是固定的模式，為此可以封裝一個通用的遍歷函數(shù)，便于用戶順序處理與各個鏈表結(jié)點(diǎn)相關(guān)聯(lián)的數(shù)據(jù)。顯然，只有使用鏈表的用戶才知道數(shù)據(jù)的具體含義，對數(shù)據(jù)的實(shí)際處理應(yīng)該交由用戶完成，比如，程序清單3.18中的打印語句，因此訪問數(shù)據(jù)的行為應(yīng)該由用戶定義，定義一個回調(diào)函數(shù)，通過參數(shù)傳遞給遍歷函數(shù)，每遍歷到一個結(jié)點(diǎn)時，都調(diào)用該回調(diào)函數(shù)處理對數(shù)據(jù)進(jìn)行處理。遍歷鏈表的函數(shù)原型(slist.h)為：
typedef int (*slist_node_process_t) (void *p_arg, slist_node_t *p_node);
int slist_foreach(slist_head_t *p_head,
slist_node_process_t pfn_node_process,
void *p_arg);
其中，p_head指向鏈表頭結(jié)點(diǎn)，pfn_node_process為結(jié)點(diǎn)處理回調(diào)函數(shù)。每遍歷到一個結(jié)點(diǎn)時，都會調(diào)用pfn_node_process指向的函數(shù)，便于用戶根據(jù)需要自行處理結(jié)點(diǎn)數(shù)據(jù)。當(dāng)調(diào)用該回調(diào)函數(shù)時，會自動將用戶參數(shù)p_arg作為回調(diào)函數(shù)的第1個參數(shù)，將指向當(dāng)前遍歷到的結(jié)點(diǎn)的指針作為回調(diào)函數(shù)的第2個參數(shù)。
當(dāng)遍歷到某個結(jié)點(diǎn)時，用戶可能希望終止遍歷，此時只要在回調(diào)函數(shù)中返回負(fù)值即可。一般地，若要繼續(xù)遍歷，函數(shù)執(zhí)行結(jié)束后返回0。slist_foreach()函數(shù)的實(shí)現(xiàn)詳見程序清單3.19。
程序清單3.19 遍歷鏈表范例程序
1 int slist_foreach( slist_head_t *p_head,
2 slist_node_process_t pfn_node_process,
3 void *p_arg);
4
5 {
6 slist_node_t *p_tmp, *p_end;
7 int ret;
8
9 if ((p_head == NULL) || (pfn_node_process == NULL)){
10 return -1;
11 }
12 p_tmp = slist_begin_get(p_head);
13 p_end = slist_end_get(p_head);
14 while (p_tmp != p_end){
15 ret = pfn_node_process(p_arg, p_tmp);
16 if (ret < 0) return ret; // 不再繼續(xù)遍歷
17 p_tmp = slist_next_get(p_head, p_tmp); // 繼續(xù)下一個結(jié)點(diǎn)
18 }
19 return 0;
20 }
現(xiàn)在可以使用這些接口函數(shù)，迭代如程序清單3.14所示的功能，詳見程序清單3.20。
程序清單3.20 管理int型數(shù)據(jù)的范例程序
1 #include
2 #include "slist.h"
3
4 typedef struct _slist_int {
5 slist_node_t node; // 包含鏈表結(jié)點(diǎn)
6 int data; // int類型數(shù)據(jù)
7 }slist_int_t;
8
9 int list_node_process (void *p_arg, slist_node_t *p_node)
10 {
11 printf("%d ", ((slist_int_t *)p_node)->data);
12 return 0;
13 }
14
15 int main(void)
16 {
17 slist_head_t head; // 定義鏈表頭結(jié)點(diǎn)
18 slist_int_t nodel, node2, node3;
19 slist_init(&head);
20
21 node1.data = 1;
22 slist_add_tail(&head, &(node1.node));
23 node2.data = 2;
24 slist_add_tail(&head, &(node2.node));
25 node3.data = 3;
26 slist_add_tail(&head, &(node3.node));
27 slist_foreach(&head, list_node_process, NULL); // 遍歷鏈表，用戶參數(shù)為NULL
28 return 0;
29 }
下載文檔
