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

>>>1.1.1 數據與p_next分離

由于鏈表只關心p_next指針，因此完全沒有必要在鏈表結點中定義數據域，那么只保留p_next指針就好了。鏈表結點的數據結構（slist.h）定義如下：

1 typedef struct _slist_node{

2 struct _slist_node *p_next; //指向下一個結點的指針

3 }slist_node_t;

由于結點中沒有任何數據，因此節省了內存空間，其示意圖詳見圖3.10。

圖3.10 鏈表示意圖

當用戶需要使用鏈表管理數據時，僅需關聯數據和鏈表結點，最簡單的方式是將數據和鏈表結點打包在一起。以int類型數據為例，首先將鏈表結點作為它的一個成員，再添加與用戶相關的int類型數據，該結構體定義如下：

1 typedef struct _slist_int{

2 slist_node_t node; //包含鏈表結點

3 int data; // int類型數據

4 }slist_int_t;

由此可見，無論是什么數據，鏈表結點只是用戶數據記錄的一個成員。當調用鏈表接口時，僅需將node的地址作為鏈表接口參數即可。在定義鏈表結點的數據結構時，由于僅刪除了data成員，因此還是可以直接使用原來的slist_add_tail()函數，管理int型數據的范例程序詳見程序清單3.14。

程序清單3.14管理int型數據的范例程序

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，且遍歷時需要操作各個結點的p_next指針。而將數據和p_next分離的目的就是使各自的功能職責分離，鏈表只需要關心p_next的處理，用戶只關心數據的處理。因此，對于用戶來說，鏈表結點的定義就是一個“黑盒子”，只能通過鏈表提供的接口訪問鏈表，不應該訪問鏈表結點的具體成員。

為了完成頭結點的初始賦值，應該提供一個初始化函數，其本質上就是將頭結點中的p_next成員設置為NULL。鏈表初始化函數原型為：

int slist_init (slist_node_t *p_head);

由于頭結點的類型與其它普通結點的類型一樣，因此很容易讓用戶誤以為，這是初始化所有結點的函數。實際上，頭結點與普通結點的含義是不一樣的，由于只要獲取頭結點就可以遍歷整個鏈表，因此頭結點往往是被鏈表的擁有者持有，而普通結點僅僅代表單一的一個結點。為了避免用戶將頭結點和其它結點混淆，需要再定義一個頭結點類型（slist.h）：

typedef slist_node_t slist_head_t;

基于此，將鏈表初始化函數原型（slist.h）修改為：

int slist_init (slist_head_t *p_head);

其中，p_head指向待初始化的鏈表頭結點，slist_init()函數的實現詳見程序清單3.15。

程序清單3.15鏈表初始化函數

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 }

在向鏈表添加結點前，需要初始化頭結點。即：

slist_node_t head;

slist_init(&head);

由于重新定義了頭結點的類型，因此添加結點的函數原型也應該進行相應的修改。即：

int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node);

其中，p_head指向鏈表頭結點，p_node為新增的結點，slist_add_tail()函數的實現詳見程序清單3.16。

程序清單3.16新增結點范例程序

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 }

同理，當前鏈表的遍歷采用的還是直接訪問結點成員的方式，其核心代碼如下：

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）得到第一個用戶結點；（2）得到當前結點的下一個結點；（3）判斷鏈表是否結束，與結束標記（NULL）比較。

基于此，將分別提供三個對應的接口來實現這些功能，避免用戶直接訪問結點成員。它們的函數原型為（slist.h）：

slist_node_t *slist_begin_get (slist_head_t *p_head); //獲取開始位置，第一個用戶結點

slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos);//獲取某一結點的后一結點

slist_node_t *slist_end_get (slist_head_t *p_head); //結束位置，尾結點下一個結點的位置

其實現代碼詳見程序清單3.17。

程序清單3.17遍歷相關函數實現

1 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos)

2 {

3 if (p_pos) { //找到p_pos指向的結點

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 }

程序中獲取的第一個用戶結點，其實質上就是頭結點的下一個結點，因此可以直接調用slist_next_get()實現。盡管slist_next_get()在實現時并沒有用到參數p_head，但還是將p_head參數傳進來了，因為實現其它的功能時將會用到p_head參數，比如，判斷p_pos是否在鏈表中。當有了這些接口函數后，即可完成遍歷，詳見程序清單3.18。

程序清單3.18使用各個接口函數實現遍歷的范例程序

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()的返回值決定了當前有效結點的范圍，其范圍為一個半開半閉的空間，即：[begin,end)，包括begin，但是不包括end。當begin與end相等時，表明當前鏈表為空，沒有一個有效結點。

在程序清單3.18所示的遍歷程序中，只有printf()語句才是用戶實際關心的語句，其它語句都是固定的模式，為此可以封裝一個通用的遍歷函數，便于用戶順序處理與各個鏈表結點相關聯的數據。顯然，只有使用鏈表的用戶才知道數據的具體含義，對數據的實際處理應該交由用戶完成，比如，程序清單3.18中的打印語句，因此訪問數據的行為應該由用戶定義，定義一個回調函數，通過參數傳遞給遍歷函數，每遍歷到一個結點時，都調用該回調函數處理對數據進行處理。遍歷鏈表的函數原型（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指向鏈表頭結點，pfn_node_process為結點處理回調函數。每遍歷到一個結點時，都會調用pfn_node_process指向的函數，便于用戶根據需要自行處理結點數據。當調用該回調函數時，會自動將用戶參數p_arg作為回調函數的第1個參數，將指向當前遍歷到的結點的指針作為回調函數的第2個參數。

當遍歷到某個結點時，用戶可能希望終止遍歷，此時只要在回調函數中返回負值即可。一般地，若要繼續遍歷，函數執行結束后返回0。slist_foreach()函數的實現詳見程序清單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;????? ???????????? //?不再繼續遍歷

17 p_tmp = slist_next_get(p_head, p_tmp); //繼續下一個結點

18 }

19 return 0;

20 }

現在可以使用這些接口函數，迭代如程序清單3.14所示的功能，詳見程序清單3.20。

程序清單3.20管理int型數據的范例程序

1 #include

2 #include "slist.h"

3

4 typedef struct _slist_int {

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

6 int data; // int類型數據

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

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); //遍歷鏈表，用戶參數為NULL

28 return 0;

29 }