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

2 {

3 if (p_pos) { // 找到p_pos指向的結(jié)點(diǎn)

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 }

程序中獲取的第一個用戶結(jié)點(diǎn)，其實(shí)質(zhì)上就是頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)，因此可以直接調(diào)用slist_next_get()實(shí)現(xiàn)。盡管slist_next_get()在實(shí)現(xiàn)時并沒有用到參數(shù)p_head，但還是將p_head參數(shù)傳進(jìn)來了，因?yàn)閷?shí)現(xiàn)其它的功能時將會用到p_head參數(shù)，比如，判斷p_pos是否在鏈表中。當(dāng)有了這些接口函數(shù)后，即可完成遍歷，詳見程序清單3.18。

程序清單3.18 使用各個接口函數(shù)實(shí)現(xiàn)遍歷的范例程序

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

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

當(dāng)遍歷到某個結(jié)點(diǎn)時，用戶可能希望終止遍歷，此時只要在回調(diào)函數(shù)中返回負(fù)值即可。一般地，若要繼續(xù)遍歷，函數(shù)執(zhí)行結(jié)束后返回0。slist_foreach()函數(shù)的實(shí)現(xiàn)詳見程序清單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; // 不再繼續(xù)遍歷

17 p_tmp = slist_next_get(p_head, p_tmp); // 繼續(xù)下一個結(jié)點(diǎn)

18 }

19 return 0;

20 }

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

程序清單3.20 管理int型數(shù)據(jù)的范例程序

1 #include

2 #include slist.h

3

4 typedef struct _slist_int {

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

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

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; // 定義鏈表頭結(jié)點(diǎn)

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

28 return 0;

29 }