單項(xiàng)鏈接的接口問題

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

>>>>1.1.1 接口

在實(shí)際使用中，僅有添加到鏈表尾部、遍歷鏈表這些接口函數(shù)是不夠的。如在結(jié)點(diǎn)添加函數(shù)中，當(dāng)前只是按照人們的習(xí)慣，將結(jié)點(diǎn)添加到鏈表尾部，使后添加的結(jié)點(diǎn)處在先添加的結(jié)點(diǎn)后面。而在編寫函數(shù)時(shí)知道，將一個(gè)結(jié)點(diǎn)添加至尾部的實(shí)現(xiàn)過程，需要修改原鏈表尾結(jié)點(diǎn)中p_next值，將其從NULL修改為指向新結(jié)點(diǎn)的指針。

雖然操作簡單，但執(zhí)行該操作的前提是要找到添加結(jié)點(diǎn)前鏈表的尾結(jié)點(diǎn)，則需要從指向頭結(jié)點(diǎn)的p_head指針開始，依次遍歷每個(gè)結(jié)點(diǎn)，直到找到結(jié)點(diǎn)中p_next值為NULL（尾結(jié)點(diǎn)）時(shí)為止。可想而知，添加一個(gè)結(jié)點(diǎn)的效率將隨著鏈表長度的增加逐漸降低，如果鏈表很長，則效率將變得十分低下，因?yàn)槊看翁砑咏Y(jié)點(diǎn)前都要遍歷一次鏈表。

既然將結(jié)點(diǎn)添加到鏈表尾部會(huì)由于需要尋找尾結(jié)點(diǎn)而導(dǎo)致效率低下，何不換個(gè)思路，將結(jié)點(diǎn)添加到鏈表頭部。由于鏈表存在一個(gè)p_head指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)可以拿來就用，根本不要尋找，則效率將大大提高。將一個(gè)結(jié)點(diǎn)添加至鏈表頭部時(shí)，鏈表的變化詳見圖 3.11。

圖 3.11添加一個(gè)結(jié)點(diǎn)至鏈表頭部

在其實(shí)現(xiàn)過程中，需要完成兩個(gè)指針的修改：（1）修改新結(jié)點(diǎn)中的p_next，使其指向頭結(jié)點(diǎn)中p_next指向的結(jié)點(diǎn)；（2）修改頭結(jié)點(diǎn)的p_next，使其指向新的結(jié)點(diǎn)。

與添加結(jié)點(diǎn)至鏈表尾部的過程進(jìn)行對比發(fā)現(xiàn)，其不再需要尋找尾結(jié)點(diǎn)的過程，無論鏈表多長，都可以通過這兩步完成結(jié)點(diǎn)的添加。加結(jié)點(diǎn)到鏈表頭部的函數(shù)原型（slist.h）為：

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

其中，p_head指向鏈表頭結(jié)點(diǎn)，p_node為待添加的結(jié)點(diǎn)，其實(shí)現(xiàn)詳見程序清單3.21。

程序清單3.21 新增結(jié)點(diǎn)至鏈表頭部的范例程序

1 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 p_node->p_next = p_head->p_next;

4 p_head->p_next = p_node;

5 return 0;

6 }

由此可見，插入結(jié)點(diǎn)至鏈表頭部的程序非常簡單，無需查找且效率高，因此在實(shí)際使用時(shí)，若對位置沒有要求，則優(yōu)先選擇將結(jié)點(diǎn)添加至鏈表頭部。

修改程序清單3.20中的一行代碼作為測試，比如，將第26行改為：

26 slist_add_head(&head, &(node3.node));

既然可以將結(jié)點(diǎn)添加至頭部和尾部，何不更加靈活一點(diǎn)，提供一個(gè)將結(jié)點(diǎn)至任意位置的接口函數(shù)呢？當(dāng)結(jié)點(diǎn)添加至p_pos指向的結(jié)點(diǎn)之后，則鏈表的變化詳見圖 3.12。

圖 3.12 添加結(jié)點(diǎn)至任意位置示意圖

在其實(shí)現(xiàn)過程中，需要修改兩個(gè)指針：（1）修改新結(jié)點(diǎn)中的p_next，使其指向p_pos指向結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)；（2）修改p_pos指向結(jié)點(diǎn)的p_next，使其指向新結(jié)點(diǎn)。通過這兩步即可添加結(jié)點(diǎn)，添加結(jié)點(diǎn)至鏈表任意位置的函數(shù)原型（slist.h）為：

int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node);

其中，p_head指向鏈表頭結(jié)點(diǎn)，p_node指向待添加的結(jié)點(diǎn)，p_pos指向的結(jié)點(diǎn)表明新結(jié)點(diǎn)添加的位置，新結(jié)點(diǎn)即添加在p_pos指向的結(jié)點(diǎn)后面，其實(shí)現(xiàn)詳見程序清單3.22。

程序清單3.22 新增結(jié)點(diǎn)至鏈表任意位置的范例程序

1 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node)

2 {

3 p_node->p_next = p_pos->p_next;

4 p_pos->p_next = p_node;

5 return 0;

6 }

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

通過前面的介紹已經(jīng)知道，直接將結(jié)點(diǎn)添加至鏈表尾部的效率很低，有了該新增結(jié)點(diǎn)至任意位置的函數(shù)后，如果每次都將結(jié)點(diǎn)添加到上一次添加的結(jié)點(diǎn)后面，同樣可以實(shí)現(xiàn)將結(jié)點(diǎn)添加至鏈表尾部。詳見程序清單3.23。

程序清單3.23 管理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_node_t head;

18 slist_int_t node1, node2, node3;

19 slist_init(&head);

20 node1.data = 1;

21 slist_add(&head, &head, &node1.node); // 添加 node1 至頭結(jié)點(diǎn)之后

22 node2.data = 2;

23 slist_add(&head, &node1.node, &node2.node); // 添加 node2至node1之后

24 node3.data = 3;

25 slist_add(&head, &node2.node, &node3.node); // 添加 node3至node2之后

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

27 return 0;

28 }

顯然，添加結(jié)點(diǎn)至鏈表頭部和尾部，僅僅是添加結(jié)點(diǎn)至任意位置的特殊情況：

● 添加結(jié)點(diǎn)至鏈表頭部，即添加結(jié)點(diǎn)至頭結(jié)點(diǎn)之后；

● 添加結(jié)點(diǎn)至鏈表尾部，即添加結(jié)點(diǎn)至鏈表尾結(jié)點(diǎn)之后。

slist_add_head()函數(shù)和slist_add_tail()函數(shù)的實(shí)現(xiàn)詳見程序清單3.24。

程序清單3.24 基于slist_add()實(shí)現(xiàn)添加結(jié)點(diǎn)至頭部和尾部

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

2 {

3 slist_node_t *p_tmp = p_head; // 指向頭結(jié)點(diǎn)

4 while (p_tmp->p_next != NULL) { // 找到鏈表尾結(jié)點(diǎn)（直到結(jié)點(diǎn)的p_next的值為NULL）

5 p_tmp = p_tmp->p_next;

6 }

7 return slist_add(p_head, p_tmp, p_node); // 添加結(jié)點(diǎn)至尾結(jié)點(diǎn)之后

8 }

9

10 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

11 {

12 return slist_add(p_head, p_head, p_node); // 添加結(jié)點(diǎn)至頭結(jié)點(diǎn)之后

13 }

如果要將一個(gè)結(jié)點(diǎn)添加至某一結(jié)點(diǎn)之前呢？實(shí)際上，添加結(jié)點(diǎn)至某一結(jié)點(diǎn)之前同樣也只是添加結(jié)點(diǎn)至某一結(jié)點(diǎn)之后的一種變形，即添加至該結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的后面，詳見圖3.13。

圖3.13 添加結(jié)點(diǎn)至任意位置前示意圖

顯然，只要獲得某一結(jié)點(diǎn)的前驅(qū)，即可使用slist_add()函數(shù)添加結(jié)點(diǎn)至某一結(jié)點(diǎn)前面。為此，需要提供一個(gè)獲得某一結(jié)點(diǎn)前驅(qū)的函數(shù)，其函數(shù)原型（slist.h）為：

slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos);

其中，p_head指向鏈表頭結(jié)點(diǎn)，p_pos指向的結(jié)點(diǎn)表明查找結(jié)點(diǎn)的位置，返回值即為p_pos指向結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。由于在單向鏈表的結(jié)點(diǎn)中沒有指向其上一個(gè)結(jié)點(diǎn)的指針，因此，只有從頭結(jié)點(diǎn)開始遍歷鏈表，當(dāng)某一結(jié)點(diǎn)的p_next指向當(dāng)前結(jié)點(diǎn)時(shí)，表明其為當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)，函數(shù)實(shí)現(xiàn)詳見程序清單3.25。

程序清單3.25 獲取某一結(jié)點(diǎn)前驅(qū)的范例程序

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

2 {

3 slist_node_t *p_tmp = p_head; // 指向頭結(jié)點(diǎn)

4 while ((p_tmp != NULL) && (p_tmp->p_next != p_pos)) { // 找到p_pos指向的結(jié)點(diǎn)

5 p_tmp = p_tmp->p_next;

6 }

7 return p_tmp;

8 }

由此可見，若p_pos的值為NULL，則當(dāng)某一結(jié)點(diǎn)的p_next為NULL時(shí)就會(huì)返回，此時(shí)返回的結(jié)點(diǎn)實(shí)際上就是尾結(jié)點(diǎn)。為了便于用戶理解，可以簡單封裝一個(gè)查找尾結(jié)點(diǎn)的函數(shù)，其函數(shù)原型為：

slist_node_t *slist_tail_get (slist_head_t *p_head) ;

其函數(shù)實(shí)現(xiàn)詳見程序清單3.26。

程序清單3.26 查找尾結(jié)點(diǎn)

1 slist_node_t *slist_tail_get (slist_head_t *p_head)

2 {

3 return slist_prev_get(p_head, NULL);

4 }

由于可以直接通過該函數(shù)得到尾結(jié)點(diǎn)，因此當(dāng)需要將結(jié)添加點(diǎn)至鏈表尾部時(shí)，也就無需再自行查找尾結(jié)點(diǎn)了，修改slist_add_tail()函數(shù)的實(shí)現(xiàn)詳見程序清單3.27。

程序清單3.27 查找尾結(jié)點(diǎn)

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

2 {

3 slist_node_t *p_tmp = slist_tail_get(p_head); // 找到尾結(jié)點(diǎn)

4 return slist_add(p_head, p_tmp, p_node); // 添加結(jié)點(diǎn)至尾結(jié)點(diǎn)之后

5 }

與添加一個(gè)結(jié)點(diǎn)對應(yīng)，也可以從鏈表中刪除某一結(jié)點(diǎn)。假定鏈表中已經(jīng)存在3個(gè)結(jié)點(diǎn)，現(xiàn)在要?jiǎng)h除中間的結(jié)點(diǎn)，則刪除前后的鏈表變化詳見圖3.14。

圖3.14 刪除結(jié)點(diǎn)示意圖

顯然，刪除一個(gè)結(jié)點(diǎn)也需要修改兩個(gè)指針的值：既要修改其上一個(gè)結(jié)點(diǎn)的p_next，使其指向待刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，還要將刪除結(jié)點(diǎn)的p_next設(shè)置為NULL。

刪除結(jié)點(diǎn)的函數(shù)原型（slist.h）為：

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

其中，p_head指向鏈表頭結(jié)點(diǎn)，p_node為待刪除的結(jié)點(diǎn)，slist_del()函數(shù)的實(shí)現(xiàn)詳見程序清單3.28。

程序清單3.28刪除結(jié)點(diǎn)范例程序

1 int slist_del (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_prev = slist_prev_get(p_head, p_node);//找到待刪除結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)

4 if (p_prev) {

5 p_prev->p_next = p_node->p_next;

6 p_node->p_next = NULL;

7 return 0;

8 }

9 return -1;

10 }

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

程序清單3.29 slist.h文件內(nèi)容

1 #pragma once

2

3 typedef struct _slist_node {

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

5 } slist_node_t;

6

7 typedef slist_node_t slist_head_t; //頭結(jié)點(diǎn)類型定義

8 typedef int (*slist_node_process_t) (void *p_arg, slist_node_t *p_node); //遍歷鏈表的回調(diào)函數(shù)類型

9

10 int slist_init (slist_head_t *p_head); //鏈表初始化

12 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node); //添加一個(gè)結(jié)點(diǎn)

13 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node); //添加一個(gè)結(jié)點(diǎn)至鏈表尾部

14 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node); //添加一個(gè)結(jié)點(diǎn)至鏈表頭部

15 int slist_del (slist_head_t *p_head, slist_node_t *p_node); //刪除一個(gè)結(jié)點(diǎn)

16

17 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos); //尋找某一結(jié)點(diǎn)的前一結(jié)點(diǎn)

18 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos); //尋找某一結(jié)點(diǎn)的后一結(jié)點(diǎn)

19 slist_node_t *slist_tail_get (slist_head_t *p_head); //獲取尾結(jié)點(diǎn)

20 slist_node_t *slist_begin_get (slist_head_t *p_head); //獲取開始位置，第一個(gè)用戶結(jié)點(diǎn)

21 slist_node_t *slist_end_get (slist_head_t *p_head); //獲取結(jié)束位置，尾結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的位置

22

23 int slist_foreach(slist_head_t *p_head, //遍歷鏈表

24 slist_node_process_t pfn_node_process,

25 void *p_arg);

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

程序清單3.30綜合范例程序

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_head(&head, &(node3.node));

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

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

29 return 0;

30 }

程序中所有的結(jié)點(diǎn)都是按照靜態(tài)內(nèi)存分配的方式定義的，即程序在運(yùn)行前，各個(gè)結(jié)點(diǎn)占用的內(nèi)存就已經(jīng)被分配好了，而不同的是動(dòng)態(tài)內(nèi)存分配需要在運(yùn)行時(shí)使用malloc()等函數(shù)完成內(nèi)存的分配。

由于靜態(tài)內(nèi)存不會(huì)出現(xiàn)內(nèi)存泄漏，且在編譯完成后，各個(gè)結(jié)點(diǎn)的內(nèi)存就已經(jīng)分配好了，不需要再花時(shí)間去分配內(nèi)存，也不需要添加額外的對內(nèi)存分配失敗的處理代碼。因此，在嵌入式系統(tǒng)中，往往多使用靜態(tài)內(nèi)存分配的方式。但其致命的缺點(diǎn)是不能釋放內(nèi)存，有時(shí)候用戶希望在刪除鏈表的結(jié)點(diǎn)時(shí)，釋放掉其占用內(nèi)存，這就需要使用動(dòng)態(tài)內(nèi)存分配。

實(shí)際上，鏈表的核心代碼只是負(fù)責(zé)完成鏈表的操作，僅需傳遞結(jié)點(diǎn)的地址（p_node）即可，鏈表程序并不關(guān)心結(jié)點(diǎn)的內(nèi)存從何而來?；诖耍粢獙?shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配，只要在應(yīng)用中使用malloc()等動(dòng)態(tài)內(nèi)存分配函數(shù)即可，詳見程序清單3.31。

程序清單3.31綜合范例程序（使用動(dòng)態(tài)內(nèi)存）

1 #include

2 #include "slist.h"

3 #include

4

5 typedef struct _slist_int{

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

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

8 } slist_int_t;

9

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

11 {

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

13 return 0;

14 }

15

16 int my_list_add(slist_head_t *p_head, int data) // 插入一個(gè)數(shù)據(jù)

17 {

18 slist_int_t *p_node = (slist_int_t *)malloc(sizeof(slist_int_t));

19 if (p_node == NULL) {

20 printf("The malloc memory failed!");

21 return -1;

22 }

23 p_node->data = data;

24 slist_add_head(p_head, &(p_node->node)); // 將結(jié)點(diǎn)加入鏈表中

25 return 0;

26 }

27

28 int my_list_del (slist_head_t *p_head, int data) //刪除一條數(shù)據(jù)

29 {

30 slist_node_t *p_node = slist_begin_get(p_head);

31 slist_node_t *p_end = slist_end_get(p_head);

32 while (p_node != p_end){

33 if (((slist_int_t *)p_node)->data == data){

34 printf(" delete the data %d :", data);

35 slist_del(p_head, p_node); //刪除結(jié)點(diǎn)

36 free(p_node);

37 break;

38 }

39 p_node = slist_next_get(p_head, p_node);

40 }

41 slist_foreach(p_head, list_node_process, NULL); //刪除結(jié)點(diǎn)后，再打印出所有結(jié)點(diǎn)的數(shù)據(jù)信息

42 return 0;

43 }

44

45 int main(void)

46 {

47 slist_head_t *p_head = (slist_head_t *)malloc(sizeof(slist_head_t));

48 slist_init(p_head);

49

50 my_list_add(p_head, 1);

51 my_list_add(p_head, 2);

52 my_list_add(p_head, 3);

53 slist_foreach(p_head, list_node_process, NULL); //打印出所有結(jié)點(diǎn)的數(shù)據(jù)信息

54 my_list_del(p_head, 1);

55 my_list_del(p_head, 2);

56 my_list_del(p_head, 3);

57 free(p_head);

58 return 0;

59 }

如果按照int型數(shù)據(jù)的示例，使用鏈表管理學(xué)生記錄，則需要在學(xué)生記錄中添加一個(gè)鏈表結(jié)點(diǎn)數(shù)據(jù)。比如：

typedef struct _student{

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

char name[10]; //姓名為字符串

char sex; //性別為字符型

float height, weight; //身高、體重為實(shí)型

}student_t;

雖然這樣定義使得學(xué)生信息可以使用鏈表來管理，但卻存在一個(gè)很嚴(yán)重的問題，因?yàn)樾薷牧藢W(xué)生記錄類型的定義，就會(huì)影響所有使用該記錄結(jié)構(gòu)體類型的程序模塊。在實(shí)際的應(yīng)用上，學(xué)生記錄可以用鏈表管理，也可以用數(shù)組管理，當(dāng)使用數(shù)組管理時(shí)，則又要重新修改學(xué)生記錄的類型。而node僅僅是鏈表的結(jié)點(diǎn)，與學(xué)生記錄沒有任何關(guān)系。不能將node直接放在學(xué)生記錄結(jié)構(gòu)體中，應(yīng)該使它們分離?；诖?，需要定義一個(gè)新的結(jié)構(gòu)體類型，將學(xué)生記錄和node關(guān)聯(lián)起來，使得可以用鏈表來管理學(xué)生記錄。比如：

typedef struct _slist_student{

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

student_t student; //學(xué)生記錄

}slist_student_t;

使用范例詳見程序清單3.32。

程序清單3.32綜合程序范例

1 #include

2 #include "slist.h"

3 #include

4

5 typedef struct _student{

6 char name[10]; //姓名為字符串

7 char sex; //性別為字符型

8 float height, weight; //身高、體重為實(shí)型

9 }student_t;

10

11 typedef struct _slist_student{

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

13 student_t student; //學(xué)生記錄

14 }slist_student_t;

15

16 int student_info_read (student_t *p_student) //讀取學(xué)生記錄，隨機(jī)產(chǎn)生，僅供測試

17 {

18 int i;

19

20 for (i = 0; i < 9; i++) {???????????????????? ?????? //?隨機(jī)名字，由'a' ~ 'z'組成

21 p_student->name[i] = (rand() % ('z' - 'a')) + 'a';

22 }

23 p_student->name[i]= '