近日周立功教授公開了數年的心血之作《程序設計與數據結構》，電子版已無償性分享到電子工程師與高校群體下載，經周立功教授授權，特對本書內容進行連載。

>>>>1.1.1 添加結點

假定還是將結點添加到鏈表尾部，其函數原型為：

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

其中，p_head為指向鏈表頭結點的指針，p_node為指向待添加結點的指針，其使用范例詳見程序清單3.38。

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

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 // ……

為了實現該函數，可以先查看添加結點前后鏈表的變化，詳見圖3.18。

圖3.18 添加結點示意圖

由此可見，添加一個結點至鏈表尾部，需要4個指針（圖中虛線箭頭）：

● 新結點的p_prev指向尾結點；

● 新結點的p_next指向頭結點；

● 尾結點的p_next由指向頭結點變為指

向新結點；

● 頭結點的p_prev由指向尾結點修改為指向新結點。

通過這些操作后，當結點添加到鏈表尾部后，就成為了新的尾結點，詳見程序清單3.39。

程序清單3.39 dlist_add_tail()函數實現

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; // 新結點的p_prev指向尾結點

7 p_node -> p_next = p_head; // 新結點的p_next指向頭結點

8 p_head -> p_prev->p_next = p_node; // 尾結點的p_next指向新結點

9 p_head -> p_prev = p_node; // 頭結點的p_prev指向新結點

10 return 0;

實際上循環鏈表，無論是頭結點、尾結點還是普通結點，其本質上都是一樣的，均為p_next成員指向下一個結點，p_prev成員指向其上一個結點。因此，對于添加結點而言，無論將結點添加到鏈表頭、鏈表尾還是其它任意位置，其操作方法完全相同。為此，需要提供一個更加通用的函數，可以將結點添加到任意結點之后，其函數原型為：

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

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

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

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 // ……

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

程序清單3.41 dlist_add_tail()函數實現

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);

為了實現dlist_add()函數，可以先查看添加一個結點到任意結點之后的情況，詳見圖3.19。圖中展示的是一種通用的情況，由于結點的添加位置（頭、尾或其它任意位置）與添加結點的方法沒有關系，因此沒有特別標明頭結點和尾結點。

其實，對比圖3.18和圖3.19可以發現，圖3.18展示的只是圖3.19的一個特例，即恰好圖3.19中的新結點之前的結點就是尾結點，添加結點的過程同樣需要修改4個指針的值。為便于描述，將新結點前的結點稱之為前結點，新結點之后的結點稱之為后結點。顯然，在添加新結點之前，前結點的下一個結點即為后結點。對設置4個指針值的描述如下：

● 新結點的p_prev指向前結點；

● 新結點的p_next指向后結點；

● 前結點的p_next由指向后結點變為指向新結點；

● 后結點的p_prev由指向前結點修改為指向新結點。

對比將結點添加到鏈表尾部的描述，只要將描述中的“前結點”換為“尾結點”，“后結點”換為“頭結點”，它們的含義則完全一樣，顯然將結點添加到鏈表尾部只是這里的一個特例，添加結點的函數實現詳見程序清單3.42。

程序清單3.42 dlist_add()函數實現

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; // 新結點的p_prev指向前結點

7 p_node->p_next = p_pos->p_next; // 新結點的p_next指向后結點

8 p_pos->p_next->p_prev = p_node; // 后結點的p_prev指向新結點

9 p_pos->p_next = p_node; // 前結點的p_next指向新結點

10 return 0;

盡管上面的函數在實現時并沒有用到參數p_head，但還是將p_head參數傳進來了，因為實現其它的功能時將會用到p_head參數，比如，判斷p_pos是否在鏈表中。

有了該函數，添加結點到任意位置就非常靈活了，比如，提供一個添加結點到鏈表的頭部，使其作為鏈表的第一個結點的函數，其函數原型為：

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

此時，頭結點即為新添加結點的前結點，直接調用dlist_add()即可實現，其實現范例詳見程序清單3.43。

程序清單3.43 dlist_add_head()函數實現

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 刪除結點

基于添加結點到任意位置的思想，需要實現一個刪除任意結點的函數。其函數原型為：

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

其中，p_head為指向鏈表頭結點的指針， p_node為指向待刪除結點的指針，使用范例詳見程序清單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;

為了實現dlisd_del()函數，可以先查看刪除任意結點的示意圖，圖 3.20（1）為刪除節點前的示意圖，圖 3.20（2）為刪除節點后的示意圖。

圖 3.20添加結點示意圖

由此可見，僅需要修改兩個指針的值：

● 將“刪除結點”的前結點的p_next修改為指向“刪除結點”的后結點；

● 將“刪除結點”的后結點的p_prev修改為指向“刪除結點”的前結點。

刪除結點函數的實現詳見程序清單3.45。

程序清單3.45 dlist_del()函數實現

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; // 前結點的p_next修改為指向后結點

7 p_node->p_next->p_prev = p_node->p_prev; // 后結點的p_prev修改為指向前結點

8

9 p_node->p_next = NULL;

10 p_node->p_prev = NULL;

11 return 0;

為了防止刪除頭結點，程序中對p_head與p_node進行了比較，當p_node為頭結點時，則直接返回錯誤。

>>>>1.1.3 遍歷鏈表

與單向鏈表類似，需要一個遍歷鏈表各個結點的函數，其函數原型（dlist.h）為：

int dlist_foreach (dlist_head_t *p_head,

dlist_node_process_t pfn_node_process,

其中，p_head指向鏈表頭結點，pfn_node_process為結點處理回調函數，每遍歷到一個結點時，均會調用該函數，便于用戶處理結點。dlist_node_process_t類型定義如下：

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

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

程序清單3.46 鏈表遍歷函數的實現

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) {??????????????????????????? // 不再繼續遍歷

18 return ret;

19 }

20 p_tmp = dlist_next_get(p_head, p_tmp); // 繼續下一個結點

21 }

22 return 0;

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

程序清單3.47 dlist.h文件內容

1 #ipragma once

2 #include

4

5 typedef struct _dlist_node{

6 struct _dlist_node *p_next; // 指向下一個結點的指針

7 struct _dlist_node *p_prev; // 指向下一個結點的指針

8 }dlist_node_t;

9

10 typedef dlist_node_t dlist_head_t;

11

12 // 鏈表遍歷時的回調函數類型

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); // 添加結點至指定位置

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

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

20 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node); // 刪除一個結點

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

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

24 dlist_node_t *dlist_tail_get (dlist_head_t *p_head); // 獲取尾結點

25 dlist_node_t *dlist_begin_get (dlist_head_t *p_head); // 獲取開始位置，第一個用戶結點

26 dlist_node_t *dlist_end_get (dlist_head_t *p_head); // 獲取結束位置，尾結點下一個結點的位置

27

28 int dlist_foreach (dlist_head_t *p_head,

29 dlist_node_process_t pfn_node_process,

同樣以int類型數據為例，來展示這些接口的使用方法。為了使用鏈表，首先應該定義一個結構體，將鏈表結點作為其一個成員，此外，再添加一些應用相關的數據，如定義如下包含鏈表結點和int型數據的結構體：

typedef struct _dlist_int{

dlist_node_t node; // 包含鏈表結點

int data; // int類型數據

綜合范例程序詳見程序清單3.48。

程序清單3.48 綜合范例程序

1 #include

2 #include "dlist.h"

3

4 typedef struct _dlist_int{

5 dlist_node_t node; // 包含鏈表結點

7 int data; // int類型數據

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; // 定義鏈表頭結點

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結點

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

31 return 0;

與單向鏈表的綜合范例程序比較可以發現，程序主體是完全一樣的，僅僅是各個結點的類型發生了改變。對于實際的應用，如果由使用單向鏈表升級為雙向鏈表，雖然程序主體沒有發生改變，但由于類型的變化，則不得不修改所有程序代碼。這是由于應用與具體數據結構沒有分離造成的，因此可以進一步將實際應用與具體的數據結構分離，將鏈表等數據結構抽象為“容器”的概念。

在公眾號后臺回復關鍵字“程序設計”，即可在線閱讀《程序設計與數據結構》；回復關鍵字“編程”，即可在線閱讀《面向AMetal框架與接口的編程（上）》。