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

>>>>1.1.1 添加結(jié)點

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

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

其中，p_head為指向鏈表頭結(jié)點的指針，p_node為指向待添加結(jié)點的指針，其使用范例詳見程序清單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 // ……

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

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

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

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

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

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

向新結(jié)點；

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

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

程序清單3.39 dlist_add_tail()函數(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é)點的p_prev指向尾結(jié)點

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

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

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

10 return 0;

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

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

其中，p_head為指向鏈表頭結(jié)點的指針，p_pos指定了添加的位置，新結(jié)點即添加在該指針指向的結(jié)點之后；p_node為指向待添加結(jié)點的指針。比如，同樣將結(jié)點添加到鏈表尾部，其使用范例詳見程序清單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é)點作為結(jié)點添加的位置，同樣可以將結(jié)點添加至尾結(jié)點之后，即添加到鏈表尾部。顯然，也就沒有必要再編寫dlist_add_tail()實現(xiàn)代碼了，使用dlisd_add()即可，修改dlist_add_tail()函數(shù)的實現(xiàn)，詳見程序清單3.41。

程序清單3.41 dlist_add_tail()函數(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);

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

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

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

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

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

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

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

程序清單3.42 dlist_add()函數(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é)點的p_prev指向前結(jié)點

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

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

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

10 return 0;

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

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

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

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

程序清單3.43 dlist_add_head()函數(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é)點

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

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

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

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

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

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

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

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

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

程序清單3.45 dlist_del()函數(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é)點的p_next修改為指向后結(jié)點

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

8

9 p_node->p_next = NULL;

10 p_node->p_prev = NULL;

11 return 0;

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

>>>>1.1.3 遍歷鏈表

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

int dlist_foreach (dlist_head_t *p_head,

dlist_node_process_t pfn_node_process,

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

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

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

程序清單3.46 鏈表遍歷函數(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ù)下一個結(jié)點

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; // 指向下一個結(jié)點的指針

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

8 }dlist_node_t;

9

10 typedef dlist_node_t dlist_head_t;

11

12 // 鏈表遍歷時的回調(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é)點至指定位置

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

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

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

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

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

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

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

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

27

28 int dlist_foreach (dlist_head_t *p_head,

29 dlist_node_process_t pfn_node_process,

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

typedef struct _dlist_int{

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

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

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

程序清單3.48 綜合范例程序

1 #include

2 #include "dlist.h"

3

4 typedef struct _dlist_int{

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

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é)點

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é)點

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

31 return 0;

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

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