周立功教授數(shù)年之心血之作《程序設計與數(shù)據(jù)結構》以及《面向AMetal框架與接口的編程（上）》，書本內容公開后，在電子行業(yè)掀起一片學習熱潮。經周立功教授授權，本公眾號特對《程序設計與數(shù)據(jù)結構》一書內容進行連載，愿共勉之。

第三章為算法與數(shù)據(jù)結構，本文為3.2 單向鏈表中的3.2.1 存值與存址和3.2.2 數(shù)據(jù)與p_next分離。

>>> 3.2.1存值與存址

1、存值

在結構體中，雖然不能用“當前結構體類型”作為結構體成員的類型，但可以用“指向當前結構體類型的指針”作為結構體成員的類型。比如：

其中，slist 是single list 的縮寫，表明該結點是單向鏈表結點。由于AMetal平臺規(guī)定字母大小寫不能混用，且類型名、變量名、函數(shù)名等只能使用小寫字母，宏定義只能使用大寫字母，因此為了與AMetal平臺保持一致，類型名中的字母全部使用小寫。

由于p_next是指針類型而不是結構體，它所指向的是同一種類型的結構體變量。事實上，編譯器在確定結構體的長度之前就已經知道了指針的長度，因此這種類型的自引用是合法的。p_next不僅是struct _slist_node類型中的一員，而且又指向struct _slist_node類型的數(shù)據(jù)，接著開始為這個結構體創(chuàng)建類型名slist_node_t。即：

AMetal規(guī)定使用typedef定義的新類型名必須以“_t”結尾，為了與AMetal保持一致，后續(xù)的類型名結尾為“_t”。但一定要警惕下面這樣的聲明陷阱：

在聲明p_next指針時，typedef還沒有結束，slist_node_t還不能使用，所以編譯器報告錯誤信息。當然，也可以在定義結構體前先用typedef，即可在聲明p_next指針時，使用類型定義slist_node_t。比如：

最后也可以結合上述2種方法按照以下形式進行定義：

即定義了一個結構體類型，這種方法常用于鏈表（list）、樹（tree）與許多其它的動態(tài)數(shù)據(jù)結構。p_next稱為鏈（link），每個結構將通過p_next鏈接到后面的結構，詳見圖 3.1。其中，data用于存放結點中的數(shù)據(jù)，該數(shù)據(jù)是由調用者（應用程序）提供的，p_next用于存放指向鏈表中下一個結點的指針（地址）。其中的箭頭表示鏈，p_next的值是下一個結點的地址，當p_next的值為NULL（0），表示鏈表已經結束。因此可以將鏈表想象為一系列連續(xù)的元素，元素與元素之間的鏈接關系只是為了確保所有的元素都可以被訪問。如果錯誤地丟失了一個鏈接，則從這個位置開始往后的所有元素都無法訪問。

圖 3.1 鏈表示意圖

通常需要定義一個指向鏈表頭結點的指針p_head，便于從鏈表的頭結點開始，順序地訪問鏈表中所有的結點。比如：

添加頭結點p_head后，完整的鏈表示意圖詳見圖3.2。

圖3.2 添加指向鏈表頭結點的指針

此時，只要獲取p_head的值，即可依次遍歷（訪問）鏈表的所有結點。比如：

對于操作鏈表的函數(shù)，必須進行測試，以確保在操作空鏈表是也是正確的。如果直接使用p_head訪問各個結點，當遍歷結束后，則p_head的值為NULL，它不再指向第一個結點，從而丟失了整個鏈表，因此必須通過一個臨時指針變量訪問鏈表的各個結點。比如：

接下來，考慮將結點添加到鏈表的尾部。在初始狀態(tài)下，鏈表是一個不包含任何結點的空表，此時p_head為NULL，那么新增的結點就是頭結點，直接修改p_head的值，使其從NULL變?yōu)橹赶蛐陆Y點的指針，鏈表的變化詳見圖3.3。

圖3.3 鏈表為空時新增結點

由于新結點添加在鏈表的尾部，因此新結點中p_next的值為NULL，詳見程序清單3.6。

程序清單3.6 新增結點范例程序（鏈表為空）

現(xiàn)在我們來編寫一個簡單的示例，驗證結點是否添加成功，詳見程序清單3.7。

程序清單3.7 添加結點范例程序（1）

如果結點加入成功，則可以通過printf將數(shù)據(jù)1打印出來。遺憾的是，運行該程序后，什么現(xiàn)象都沒有看到。當鏈表為空時，添加一個結點的核心工作是“修改p_head的值，使其從NULL變?yōu)橹赶蛐陆Y點的指針”。在調用slist_add_tail()后，p_head被修改了嗎？

當將指針傳遞給函數(shù)時，其傳遞的是值。如果想要修改原指針，而不是指針的副本，則需要傳遞指針的指針。p_head是在主程序中定義的，其后僅僅是將NULL值作為實參傳遞給了slist_add_tail()的形參。此后p_head與slist_add_tail()再無任何關聯(lián)，因此slist_add_tail()根本不可能修改p_head。要想在調用時修改p_head，則必須將該指針的地址傳遞給slist_add_tail()，詳見程序清單3.8。

程序清單3.8 鏈表為空時新增結點的范例程序

如程序清單3.9所示的測試程序可以驗證添加結點是否成功，首先初始化鏈表為空，接著傳遞p_head的地址，然后從頭結點開始，依次訪問各個結點。

程序清單3.9 添加結點范例程序（2）

當鏈表不為空時，假定已經存在一個值為data1的結點，再添加一個值為data2的結點，鏈表的變化詳見圖3.4。

圖3.4 鏈表非空時新增結點

其實現(xiàn)的過程僅需要修改原鏈表尾結點p_next的值，使其從NULL指針變?yōu)橹赶蛐陆Y點的指針，詳見程序清單3.10。

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

現(xiàn)在可以在程序清單3.9的基礎上，添加更多的結點作為測試程序，詳見程序清單3.11。

程序清單3.11 添加結點范例程序（3）

通過該程序可以驗證結點添加成功，但仔細觀察程序清單3.10可以發(fā)現(xiàn)，新增一個結點時，需要判定當前鏈表是否為空，然后再根據(jù)實際情況作出相應的處理。產生條件判斷的原因是鏈表可能為空，沒有一個有效結點。如果鏈表初始時就存在一個結點head：

由于這是一個實際的結點，不再是指向頭結點的指針，因此鏈表不可能為空，鏈表示意圖詳見圖 3.5。

圖 3.5 鏈表示意圖

對于這種類型的鏈表，始終存在一個無需有效數(shù)據(jù)的頭結點，對于空鏈表，其至少包含該頭結點，空鏈表示意圖詳見圖3.6。由于在初始化時不包含其它任何結點，因此p_next的值為NULL。

圖3.6 空鏈表示意圖

當需要添加一個新的結點時，則從頭結點開始尋找尾結點。當找到尾結點時，則修改尾結點的p_next值，使其從NULL指針變?yōu)橹赶蛐陆Y點的指針，詳見程序清單3.12。

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

注意，這里的p_head始終指向存在的頭結點，與程序清單3.6中的p_head意義不同，可以使用如程序清單3.13所示的測試程序對其進行測試，由于初始化時無后繼結點，因此p_next域的值為NULL。

程序清單3.13 添加結點范例程序（4）

雖然如程序清單3.12所示的程序不再使用判斷語句，但又帶來了新的問題，頭結點的data被閑置，僅使用了p_next，則勢必浪費內存。當然，對于當前示例來講data是int類型數(shù)據(jù)，僅占用4個字節(jié)，浪費4個字節(jié)或許還能接受，如果data是其它類型呢？

如果鏈表的元素是學生記錄中的數(shù)據(jù)，由于學生記錄中的數(shù)據(jù)分別為不同類型的數(shù)據(jù)，因此結構體是最好的選擇。而作為范例程序無法面面俱到，所以僅以幾個典型的數(shù)據(jù)為例作為結構體的成員?；诖?，專門為學生記錄中的數(shù)據(jù)定義一個結構體類型與新的結構體類型名。其數(shù)據(jù)類型定義如下：

即可用此結構體存儲學生記錄中的數(shù)據(jù)，其成員在內存中的存儲關系詳見圖 3.7。如果將element_type_t聲明與student_t相同的類型，則鏈表數(shù)據(jù)結構為：

圖 3.7

即與應用程序相關的數(shù)據(jù)data的類型為另一個結構體類型student_t。

此時只要定義一個slist_node_t類型的變量node，即可引用結構體的成員：

那么該鏈表各成員在內存中的存儲關系就確定下來了，詳見圖 3.8。如果使用表達式

圖 3.8

即可通過node變量引用slist_node_t結構體的成員data。此時，只要將node.data看作一個student_t類型變量，即可使用表達式

引用student_t結構體成員data的成員name（學生記錄中的數(shù)據(jù)）。

當鏈表中的數(shù)據(jù)從int類型變?yōu)閟tudent_t時，浪費的空間將是student_t類型的大小。這里僅僅是一個示例，學生記錄可能包含更多其它的信息，比如，學號、年級、血型、宿舍號等，則頭結點浪費的空間將會更大。

同時，這里也隱含了一個問題，數(shù)據(jù)類型的改變將導致程序行為的改變，使得該程序無法做到通用，必須在編譯前確定好數(shù)據(jù)類型，則程序不能以通用庫的形式發(fā)布。如果要使代碼通用，就要使用能接受任意數(shù)據(jù)類型的void *。

2、存址

為了通用還是在鏈表中存放void *類型的元素，即可用鏈表存儲用戶傳入的任意指針類型數(shù)據(jù)，則鏈表結點的數(shù)據(jù)結構定義如下：

其中，結點的數(shù)據(jù)域類型為void *類型指針，data指向用戶數(shù)據(jù)，結點中的數(shù)據(jù)是由調用者（應用程序）提供的用戶數(shù)據(jù)。

雖然void *看起來是一個指針，其本質上則是一個整數(shù)，因為在大多數(shù)編譯器中指針與int占用的存儲空間大小一樣，所以通用鏈表是一個結點數(shù)據(jù)域類型為int型的鏈表，只不過結點的數(shù)據(jù)域中存儲的是與應用程序關聯(lián)的用戶數(shù)據(jù)的地址。

假設存儲在struct _student結構體學生記錄中的數(shù)據(jù)就是用戶數(shù)據(jù)，那么只要將存儲學生記錄的結構體變量的地址傳遞給鏈表結點的數(shù)據(jù)域就行了，即p->data指向用戶數(shù)據(jù)的結構體存儲空間，詳見圖 3.9。如果void *指針指向的不是結構體或者字符串，而是int型之類的簡單類型，那么只要在使用時進行強制類型轉換即可。

圖 3.9 data指向用戶數(shù)據(jù)

如果為了使鏈表數(shù)據(jù)與學生記錄結構體關聯(lián)，則必須先定義一個學生記錄，然后將鏈表結點中的void *指針指向該學生記錄。與之前直接將學生結構體作為鏈表結點的數(shù)據(jù)成員的鏈表相比，每個結點都會多耗費一個void *指針的空間。雖然一個結點耗費的空間并不多，但如果結點很多，其浪費的內存還是相當可觀的，特別是在一些內存資源本身就很緊張的嵌入式系統(tǒng)中。

顯然，要想節(jié)省內存空間，則不能定義void *類型指針，必須將數(shù)據(jù)（比如，學生記錄）和鏈表結點的p_next放在一起，但這樣做則無法做到重用鏈表程序。

分析當前鏈表結點的定義，其主要包含兩個部分：鏈表關心的p_next指針和用戶關心的data數(shù)據(jù)?；仡櫲绯绦蚯鍐?.12所示的slist_add_tail()函數(shù)，沒有出現(xiàn)任何訪問data的代碼，從而說明data與鏈表無關。既然如此，是否可以將它們分離呢？

>>> 3.2.2 數(shù)據(jù)與p_next分離

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

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

圖3.10 鏈表示意圖

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

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

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

由于用戶需要初始化head為NULL，且遍歷時需要操作各個結點的p_next指針。而將數(shù)據(jù)和p_next分離的目的就是使各自的功能職責分離，鏈表只需要關心p_next的處理，用戶只關心數(shù)據(jù)的處理。因此，對于用戶來說，鏈表結點的定義就是一個“黑盒子”，只能通過鏈表提供的接口訪問鏈表，不應該訪問鏈表結點的具體成員。

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

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

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

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

程序清單3.15 鏈表初始化函數(shù)

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

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

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

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

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

這里主要對鏈表作了三個操作：（1）得到第一個用戶結點；（2）得到當前結點的下一個結點；（3）判斷鏈表是否結束，與結束標記（NULL）比較。

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

其實現(xiàn)代碼詳見程序清單3.17。

程序清單3.17 遍歷相關函數(shù)實現(xiàn)

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

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

由此可見，slist_begin_get()和slist_end_get()的返回值決定了當前有效結點的范圍，其范圍為一個半開半閉的空間，即：[begin,end)，包括begin，但是不包括end。當begin與end相等時，表明當前鏈表為空，沒有一個有效結點。

在程序清單3.18所示的遍歷程序中，只有printf()語句才是用戶實際關心的語句，其它語句都是固定的模式，為此可以封裝一個通用的遍歷函數(shù)，便于用戶順序處理與各個鏈表結點相關聯(lián)的數(shù)據(jù)。顯然，只有使用鏈表的用戶才知道數(shù)據(jù)的具體含義，對數(shù)據(jù)的實際處理應該交由用戶完成，比如，程序清單3.18中的打印語句，因此訪問數(shù)據(jù)的行為應該由用戶定義，定義一個回調函數(shù)，通過參數(shù)傳遞給遍歷函數(shù)，每遍歷到一個結點時，都調用該回調函數(shù)處理對數(shù)據(jù)進行處理。遍歷鏈表的函數(shù)原型（slist.h）為：

其中，p_head指向鏈表頭結點，pfn_node_process為結點處理回調函數(shù)。每遍歷到一個結點時，都會調用pfn_node_process指向的函數(shù)，便于用戶根據(jù)需要自行處理結點數(shù)據(jù)。當調用該回調函數(shù)時，會自動將用戶參數(shù)p_arg作為回調函數(shù)的第1個參數(shù)，將指向當前遍歷到的結點的指針作為回調函數(shù)的第2個參數(shù)。

當遍歷到某個結點時，用戶可能希望終止遍歷，此時只要在回調函數(shù)中返回負值即可。一般地，若要繼續(xù)遍歷，函數(shù)執(zhí)行結束后返回0。slist_foreach()函數(shù)的實現(xiàn)詳見程序清單3.19。

程序清單3.19 遍歷鏈表范例程序

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

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