如何定義鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)？

1.1.1 數(shù)據(jù)與p_next分離

由于鏈表只關(guān)心p_next指針，因此完全沒(méi)有必要在鏈表結(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; // 指向下一個(gè)結(jié)點(diǎn)的指針

3 }slist_node_t;

由于結(jié)點(diǎn)中沒(méi)有任何數(shù)據(jù)，因此節(jié)省了內(nèi)存空間，其示意圖詳見(jiàn)圖3.10。

圖3.10 鏈表示意圖

當(dāng)用戶(hù)需要使用鏈表管理數(shù)據(jù)時(shí)，僅需關(guān)聯(lián)數(shù)據(jù)和鏈表結(jié)點(diǎn)，最簡(jiǎn)單的方式是將數(shù)據(jù)和鏈表結(jié)點(diǎn)打包在一起。以int類(lèi)型數(shù)據(jù)為例，首先將鏈表結(jié)點(diǎn)作為它的一個(gè)成員，再添加與用戶(hù)相關(guān)的int類(lèi)型數(shù)據(jù)，該結(jié)構(gòu)體定義如下：

1 typedef struct _slist_int{

2 slist_node_t node; // 包含鏈表結(jié)點(diǎn)

3 int data; // int類(lèi)型數(shù)據(jù)

4 }slist_int_t;

由此可見(jiàn)，無(wú)論是什么數(shù)據(jù)，鏈表結(jié)點(diǎn)只是用戶(hù)數(shù)據(jù)記錄的一個(gè)成員。當(dāng)調(diào)用鏈表接口時(shí)，僅需將node的地址作為鏈表接口參數(shù)即可。在定義鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)時(shí)，由于僅刪除了data成員，因此還是可以直接使用原來(lái)的slist_add_tail()函數(shù)，管理int型數(shù)據(jù)的范例程序詳見(jiàn)程序清單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 }

由于用戶(hù)需要初始化head為NULL，且遍歷時(shí)需要操作各個(gè)結(jié)點(diǎn)的p_next指針。而將數(shù)據(jù)和p_next分離的目的就是使各自的功能職責(zé)分離，鏈表只需要關(guān)心p_next的處理，用戶(hù)只關(guān)心數(shù)據(jù)的處理。因此，對(duì)于用戶(hù)來(lái)說(shuō)，鏈表結(jié)點(diǎn)的定義就是一個(gè)“黑盒子”，只能通過(guò)鏈表提供的接口訪問(wèn)鏈表，不應(yīng)該訪問(wèn)鏈表結(jié)點(diǎn)的具體成員。

為了完成頭結(jié)點(diǎn)的初始賦值，應(yīng)該提供一個(gè)初始化函數(shù)，其本質(zhì)上就是將頭結(jié)點(diǎn)中的p_next成員設(shè)置為NULL。鏈表初始化函數(shù)原型為：

int slist_init (slist_node_t *p_head);

由于頭結(jié)點(diǎn)的類(lèi)型與其它普通結(jié)點(diǎn)的類(lèi)型一樣，因此很容易讓用戶(hù)誤以為，這是初始化所有結(jié)點(diǎn)的函數(shù)。實(shí)際上，頭結(jié)點(diǎn)與普通結(jié)點(diǎn)的含義是不一樣的，由于只要獲取頭結(jié)點(diǎn)就可以遍歷整個(gè)鏈表，因此頭結(jié)點(diǎn)往往是被鏈表的擁有者持有，而普通結(jié)點(diǎn)僅僅代表單一的一個(gè)結(jié)點(diǎn)。為了避免用戶(hù)將頭結(jié)點(diǎn)和其它結(jié)點(diǎn)混淆，需要再定義一個(gè)頭結(jié)點(diǎn)類(lèi)型(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)詳見(jià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)的類(lèi)型，因此添加結(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)詳見(jià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)前鏈表的遍歷采用的還是直接訪問(wèn)結(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 }

這里主要對(duì)鏈表作了三個(gè)操作：(1)得到第一個(gè)用戶(hù)結(jié)點(diǎn);(2)得到當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn);(3)判斷鏈表是否結(jié)束，與結(jié)束標(biāo)記(NULL)比較。

基于此，將分別提供三個(gè)對(duì)應(yīng)的接口來(lái)實(shí)現(xiàn)這些功能，避免用戶(hù)直接訪問(wèn)結(jié)點(diǎn)成員。它們的函數(shù)原型為(slist.h)：

slist_node_t *slist_begin_get (slist_head_t *p_head); // 獲取開(kāi)始位置，第一個(gè)用戶(hù)結(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)下一個(gè)結(jié)點(diǎn)的位置

其實(shí)現(xiàn)代碼詳見(jià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)