周立功闡釋高效的雙向鏈表如何用

近日周立功教授公開(kāi)了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無(wú)償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對(duì)本書內(nèi)容進(jìn)行連載。

>>>>1.1.1 添加結(jié)點(diǎn)

假定還是將結(jié)點(diǎn)添加到鏈表尾部，其函數(shù)原型為：

int dlist_add_tail(dlist_head_t *p_head, dlist_node_t *p_node);

其中，p_head為指向鏈表頭結(jié)點(diǎn)的指針，p_node為指向待添加結(jié)點(diǎn)的指針，其使用范例詳見(jiàn)程序清單3.38。

程序清單3.38 dlist_add_tail()函數(shù)使用范例

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add_tail(&head, &node);

8 // ……

為了實(shí)現(xiàn)該函數(shù)，可以先查看添加結(jié)點(diǎn)前后鏈表的變化，詳見(jiàn)圖3.18。

圖3.18 添加結(jié)點(diǎn)示意圖

由此可見(jiàn)，添加一個(gè)結(jié)點(diǎn)至鏈表尾部，需要4個(gè)指針（圖中虛線箭頭）：

● 新結(jié)點(diǎn)的p_prev指向尾結(jié)點(diǎn)；

● 新結(jié)點(diǎn)的p_next指向頭結(jié)點(diǎn)；

● 尾結(jié)點(diǎn)的p_next由指向頭結(jié)點(diǎn)變?yōu)橹?/span>

向新結(jié)點(diǎn)；

● 頭結(jié)點(diǎn)的p_prev由指向尾結(jié)點(diǎn)修改為指向新結(jié)點(diǎn)。

通過(guò)這些操作后，當(dāng)結(jié)點(diǎn)添加到鏈表尾部后，就成為了新的尾結(jié)點(diǎn)，詳見(jiàn)程序清單3.39。

程序清單3.39 dlist_add_tail()函數(shù)實(shí)現(xiàn)

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_node -> p_prev = p_head->p_prev; // 新結(jié)點(diǎn)的p_prev指向尾結(jié)點(diǎn)

7 p_node -> p_next = p_head; // 新結(jié)點(diǎn)的p_next指向頭結(jié)點(diǎn)

8 p_head -> p_prev->p_next = p_node; // 尾結(jié)點(diǎn)的p_next指向新結(jié)點(diǎn)

9 p_head -> p_prev = p_node; // 頭結(jié)點(diǎn)的p_prev指向新結(jié)點(diǎn)

10 return 0;

實(shí)際上循環(huán)鏈表，無(wú)論是頭結(jié)點(diǎn)、尾結(jié)點(diǎn)還是普通結(jié)點(diǎn)，其本質(zhì)上都是一樣的，均為p_next成員指向下一個(gè)結(jié)點(diǎn)，p_prev成員指向其上一個(gè)結(jié)點(diǎn)。因此，對(duì)于添加結(jié)點(diǎn)而言，無(wú)論將結(jié)點(diǎn)添加到鏈表頭、鏈表尾還是其它任意位置，其操作方法完全相同。為此，需要提供一個(gè)更加通用的函數(shù)，可以將結(jié)點(diǎn)添加到任意結(jié)點(diǎn)之后，其函數(shù)原型為：

int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node);

其中，p_head為指向鏈表頭結(jié)點(diǎn)的指針，p_pos指定了添加的位置，新結(jié)點(diǎn)即添加在該指針指向的結(jié)點(diǎn)之后；p_node為指向待添加結(jié)點(diǎn)的指針。比如，同樣將結(jié)點(diǎn)添加到鏈表尾部，其使用范例詳見(jiàn)程序清單3.40。

程序清單3.40 dlist_add()函數(shù)使用范例

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add(&head, &(head.p_prev), &node);

8 // ……

由此可見(jiàn)，將尾結(jié)點(diǎn)作為結(jié)點(diǎn)添加的位置，同樣可以將結(jié)點(diǎn)添加至尾結(jié)點(diǎn)之后，即添加到鏈表尾部。顯然，也就沒(méi)有必要再編寫dlist_add_tail()實(shí)現(xiàn)代碼了，使用dlisd_add()即可，修改dlist_add_tail()函數(shù)的實(shí)現(xiàn)，詳見(jiàn)程序清單3.41。

程序清單3.41 dlist_add_tail()函數(shù)實(shí)現(xiàn)

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head->p_prev, p_node);

為了實(shí)現(xiàn)dlist_add()函數(shù)，可以先查看添加一個(gè)結(jié)點(diǎn)到任意結(jié)點(diǎn)之后的情況，詳見(jiàn)圖3.19。圖中展示的是一種通用的情況，由于結(jié)點(diǎn)的添加位置（頭、尾或其它任意位置）與添加結(jié)點(diǎn)的方法沒(méi)有關(guān)系，因此沒(méi)有特別標(biāo)明頭結(jié)點(diǎn)和尾結(jié)點(diǎn)。

其實(shí)，對(duì)比圖3.18和圖3.19可以發(fā)現(xiàn)，圖3.18展示的只是圖3.19的一個(gè)特例，即恰好圖3.19中的新結(jié)點(diǎn)之前的結(jié)點(diǎn)就是尾結(jié)點(diǎn)，添加結(jié)點(diǎn)的過(guò)程同樣需要修改4個(gè)指針的值。為便于描述，將新結(jié)點(diǎn)前的結(jié)點(diǎn)稱之為前結(jié)點(diǎn)，新結(jié)點(diǎn)之后的結(jié)點(diǎn)稱之為后結(jié)點(diǎn)。顯然，在添加新結(jié)點(diǎn)之前，前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即為后結(jié)點(diǎn)。對(duì)設(shè)置4個(gè)指針值的描述如下：

● 新結(jié)點(diǎn)的p_prev指向前結(jié)點(diǎn)；

● 新結(jié)點(diǎn)的p_next指向后結(jié)點(diǎn)；

● 前結(jié)點(diǎn)的p_next由指向后結(jié)點(diǎn)變?yōu)橹赶蛐陆Y(jié)點(diǎn)；

● 后結(jié)點(diǎn)的p_prev由指向前結(jié)點(diǎn)修改為指向新結(jié)點(diǎn)。

對(duì)比將結(jié)點(diǎn)添加到鏈表尾部的描述，只要將描述中的“前結(jié)點(diǎn)”換為“尾結(jié)點(diǎn)”，“后結(jié)點(diǎn)”換為“頭結(jié)點(diǎn)”，它們的含義則完全一樣，顯然將結(jié)點(diǎn)添加到鏈表尾部只是這里的一個(gè)特例，添加結(jié)點(diǎn)的函數(shù)實(shí)現(xiàn)詳見(jiàn)程序清單3.42。

程序清單3.42 dlist_add()函數(shù)實(shí)現(xiàn)

1 int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node)

2 {

3 if ((p_head == NULL) || (p_pos == NULL) || (p_node == NULL)){

4 return -1;

5 }

6 p_node->p_prev = p_pos; // 新結(jié)點(diǎn)的p_prev指向前結(jié)點(diǎn)

7 p_node->p_next = p_pos->p_next; // 新結(jié)點(diǎn)的p_next指向后結(jié)點(diǎn)

8 p_pos->p_next->p_prev = p_node; // 后結(jié)點(diǎn)的p_prev指向新結(jié)點(diǎn)

9 p_pos->p_next = p_node; // 前結(jié)點(diǎn)的p_next指向新結(jié)點(diǎn)

10 return 0;

盡管上面的函數(shù)在實(shí)現(xiàn)時(shí)并沒(méi)有用到參數(shù)p_head，但還是將p_head參數(shù)傳進(jìn)來(lái)了，因?yàn)閷?shí)現(xiàn)其它的功能時(shí)將會(huì)用到p_head參數(shù)，比如，判斷p_pos是否在鏈表中。

有了該函數(shù)，添加結(jié)點(diǎn)到任意位置就非常靈活了，比如，提供一個(gè)添加結(jié)點(diǎn)到鏈表的頭部，使其作為鏈表的第一個(gè)結(jié)點(diǎn)的函數(shù)，其函數(shù)原型為：

int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node);

此時(shí)，頭結(jié)點(diǎn)即為新添加結(jié)點(diǎn)的前結(jié)點(diǎn)，直接調(diào)用dlist_add()即可實(shí)現(xiàn)，其實(shí)現(xiàn)范例詳見(jiàn)程序清單3.43。

程序清單3.43 dlist_add_head()函數(shù)實(shí)現(xiàn)

1 int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head, p_node);

>>>>1.1.2 刪除結(jié)點(diǎn)

基于添加結(jié)點(diǎn)到任意位置的思想，需要實(shí)現(xiàn)一個(gè)刪除任意結(jié)點(diǎn)的函數(shù)。其函數(shù)原型為：

int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node);

其中，p_head為指向鏈表頭結(jié)點(diǎn)的指針， p_node為指向待刪除結(jié)點(diǎn)的指針，使用范例詳見(jiàn)程序清單3.44。

程序清單3.44 dlist_del()使用范例程序

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5 dlist_init(&head);

6 dlist_add_tail(&head, &node);

7 dlist_del(&head, &node);

8 //......

9 return 0;

為了實(shí)現(xiàn)dlisd_del()函數(shù)，可以先查看刪除任意結(jié)點(diǎn)的示意圖，圖 3.20（1）為刪除節(jié)點(diǎn)前的示意圖，圖 3.20（2）為刪除節(jié)點(diǎn)后的示意圖。

圖 3.20添加結(jié)點(diǎn)示意圖

由此可見(jiàn)，僅需要修改兩個(gè)指針的值：

● 將“刪除結(jié)點(diǎn)”的前結(jié)點(diǎn)的p_next修改為指向“刪除結(jié)點(diǎn)”的后結(jié)點(diǎn)；

● 將“刪除結(jié)點(diǎn)”的后結(jié)點(diǎn)的p_prev修改為指向“刪除結(jié)點(diǎn)”的前結(jié)點(diǎn)。

刪除結(jié)點(diǎn)函數(shù)的實(shí)現(xiàn)詳見(jiàn)程序清單3.45。

程序清單3.45 dlist_del()函數(shù)實(shí)現(xiàn)

1 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

4 return -1;

5 }

6 p_node->p_prev->p_next = p_node->p_next; // 前結(jié)點(diǎn)的p_next修改為指向后結(jié)點(diǎn)

7 p_node->p_next->p_prev = p_node->p_prev; // 后結(jié)點(diǎn)的p_prev修改為指向前結(jié)點(diǎn)

8

9 p_node->p_next = NULL;

10 p_node->p_prev = NULL;

11 return 0;

為了防止刪除頭結(jié)點(diǎn)，程序中對(duì)p_head與p_node進(jìn)行了比較，當(dāng)p_node為頭結(jié)點(diǎn)時(shí)，則直接返回錯(cuò)誤。

>>>>1.1.3 遍歷鏈表

與單向鏈表類似，需要一個(gè)遍歷鏈表各個(gè)結(jié)點(diǎn)的函數(shù)，其函數(shù)原型（dlist.h）為：

int dlist_foreach (dlist_head_t *p_head,

dlist_node_process_t pfn_node_process,

其中，p_head指向鏈表頭結(jié)點(diǎn)，pfn_node_process為結(jié)點(diǎn)處理回調(diào)函數(shù)，每遍歷到一個(gè)結(jié)點(diǎn)時(shí)，均會(huì)調(diào)用該函數(shù)，便于用戶處理結(jié)點(diǎn)。dlist_node_process_t類型定義如下：

typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

dlist_node_process_t類型參數(shù)為一個(gè)p_arg指針和一個(gè)結(jié)點(diǎn)指針，返回值為int類型的函數(shù)指針。每遍歷到一個(gè)結(jié)點(diǎn)均會(huì)調(diào)用pfn_node_process指向的函數(shù)，便于用戶根據(jù)需要自行處理結(jié)點(diǎn)數(shù)據(jù)。當(dāng)調(diào)用該回調(diào)函數(shù)時(shí)，傳遞給p_arg的值即為用戶參數(shù)，其值與dlist_traverse()函數(shù)的第3個(gè)參數(shù)一樣，即該參數(shù)的值完全是由用戶決定的；傳遞給p_node 的值即為指向當(dāng)前遍歷到的結(jié)點(diǎn)的指針。當(dāng)遍歷到某個(gè)結(jié)點(diǎn)時(shí)，如果用戶希望終止遍歷，此時(shí)，只要在回調(diào)函數(shù)中返回負(fù)值即可終止繼續(xù)遍歷。一般地，若要繼續(xù)遍歷，則函數(shù)執(zhí)行結(jié)束后返回0即可。dlist_foreach()函數(shù)的實(shí)現(xiàn)詳見(jiàn)程序清單3.46。

程序清單3.46 鏈表遍歷函數(shù)的實(shí)現(xiàn)

1 int dlist_foreach (dlist_head_t *p_head,

2 dlist_node_process_t pfn_node_process,

3 void *p_arg)

4 {

5 dlist_node_t *p_tmp, *p_end;

6 int ret;

7

8 if ((p_head == NULL) || (pfn_node_process == NULL)) {

10 }

11

12 p_tmp = dlist_begin_get(p_head);

13 p_end = dlist_end_get(p_head);

14

15 while (p_tmp != p_end) {

16 ret = pfn_node_process(p_arg, p_tmp);

17 if (ret < 0) {??????????????????????????? // 不再繼續(xù)遍歷

18 return ret;

19 }

20 p_tmp = dlist_next_get(p_head, p_tmp); // 繼續(xù)下一個(gè)結(jié)點(diǎn)

21 }

22 return 0;

為了便于查閱，如程序清單3.47所示展示了dlist.h文件的內(nèi)容。

程序清單3.47 dlist.h文件內(nèi)容

1 #ipragma once

2 #include

4

5 typedef struct _dlist_node{

6 struct _dlist_node *p_next; // 指向下一個(gè)結(jié)點(diǎn)的指針

7 struct _dlist_node *p_prev; // 指向下一個(gè)結(jié)點(diǎn)的指針

8 }dlist_node_t;

9

10 typedef dlist_node_t dlist_head_t;

11

12 // 鏈表遍歷時(shí)的回調(diào)函數(shù)類型

13 typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

14

15 int dlist_init (dlist_head_t *p_head); // 鏈表初始化

17 int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node); // 添加結(jié)點(diǎn)至指定位置

18 int dlist_add_tail(dlist_head_t *p_head, dlist_node_t *p_node); // 添加結(jié)點(diǎn)至鏈表尾部

19 int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node); // 添加結(jié)點(diǎn)至鏈表頭部

20 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node); // 刪除一個(gè)結(jié)點(diǎn)

22 dlist_node_t *dlist_prev_get (dlist_head_t *p_head, dlist_node_t *p_pos); // 尋找某一結(jié)點(diǎn)的前一結(jié)點(diǎn)

23 dlist_node_t *dlist_next_get (dlist_head_t *p_head, dlist_node_t *p_pos); // 尋找某一結(jié)點(diǎn)的后一結(jié)點(diǎn)

24 dlist_node_t *dlist_tail_get (dlist_head_t *p_head); // 獲取尾結(jié)點(diǎn)

25 dlist_node_t *dlist_begin_get (dlist_head_t *p_head); // 獲取開(kāi)始位置，第一個(gè)用戶結(jié)點(diǎn)

26 dlist_node_t *dlist_end_get (dlist_head_t *p_head); // 獲取結(jié)束位置，尾結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的位置

27

28 int dlist_foreach (dlist_head_t *p_head,

29 dlist_node_process_t pfn_node_process,

同樣以int類型數(shù)據(jù)為例，來(lái)展示這些接口的使用方法。為了使用鏈表，首先應(yīng)該定義一個(gè)結(jié)構(gòu)體，將鏈表結(jié)點(diǎn)作為其一個(gè)成員，此外，再添加一些應(yīng)用相關(guān)的數(shù)據(jù)，如定義如下包含鏈表結(jié)點(diǎn)和int型數(shù)據(jù)的結(jié)構(gòu)體：

typedef struct _dlist_int{

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

int data; // int類型數(shù)據(jù)

綜合范例程序詳見(jiàn)程序清單3.48。

程序清單3.48 綜合范例程序

1 #include

2 #include "dlist.h"

3

4 typedef struct _dlist_int{

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

7 int data; // int類型數(shù)據(jù)

8 }dlist_int_t;

9

10 int list_node_process (void *p_arg, dlist_node_t *p_node)

11 {

12 printf("%d ", ((dlist_int_t *)p_node) -> data);

13 return 0;

15

16 int main(int argc, char *argv[])

17 {

18 dlist_head_t head; // 定義鏈表頭結(jié)點(diǎn)

19 dlist_int_t node1, node2, node3;

20 dlist_init(&head);

21

22 node1.data = 1;

23 dlist_add_tail(&head, &(node1.node));

24 node2.data = 2;

25 dlist_add_tail(&head, &(node2.node));

26 node3.data = 3;

27 dlist_add_tail(&head, &(node3.node));

29 dlist_del(&head, &(node2.node)); // 刪除node2結(jié)點(diǎn)

30 dlist_foreach(&head, list_node_process, NULL); // 遍歷鏈表，用戶參數(shù)為NULL

31 return 0;

與單向鏈表的綜合范例程序比較可以發(fā)現(xiàn)，程序主體是完全一樣的，僅僅是各個(gè)結(jié)點(diǎn)的類型發(fā)生了改變。對(duì)于實(shí)際的應(yīng)用，如果由使用單向鏈表升級(jí)為雙向鏈表，雖然程序主體沒(méi)有發(fā)生改變，但由于類型的變化，則不得不修改所有程序代碼。這是由于應(yīng)用與具體數(shù)據(jù)結(jié)構(gòu)沒(méi)有分離造成的，因此可以進(jìn)一步將實(shí)際應(yīng)用與具體的數(shù)據(jù)結(jié)構(gòu)分離，將鏈表等數(shù)據(jù)結(jié)構(gòu)抽象為“容器”的概念。

在公眾號(hào)后臺(tái)回復(fù)關(guān)鍵字“程序設(shè)計(jì)”，即可在線閱讀《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》；回復(fù)關(guān)鍵字“編程”，即可在線閱讀《面向AMetal框架與接口的編程（上）》。