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

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

>>> 3.2.1存值與存址

1、存值

在結(jié)構(gòu)體中，雖然不能用“當(dāng)前結(jié)構(gòu)體類型”作為結(jié)構(gòu)體成員的類型，但可以用“指向當(dāng)前結(jié)構(gòu)體類型的指針”作為結(jié)構(gòu)體成員的類型。比如：

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

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

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

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

最后也可以結(jié)合上述2種方法按照以下形式進(jìn)行定義：

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

圖 3.1 鏈表示意圖

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

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

圖3.2 添加指向鏈表頭結(jié)點的指針

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

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

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

圖3.3 鏈表為空時新增結(jié)點

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

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

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

程序清單3.7 添加結(jié)點范例程序（1）

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

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

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

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

程序清單3.9 添加結(jié)點范例程序（2）

當(dāng)鏈表不為空時，假定已經(jīng)存在一個值為data1的結(jié)點，再添加一個值為data2的結(jié)點，鏈表的變化詳見圖3.4。

圖3.4 鏈表非空時新增結(jié)點

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

程序清單3.10 新增結(jié)點范例程序

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

程序清單3.11 添加結(jié)點范例程序（3）

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

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

圖 3.5 鏈表示意圖

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

圖3.6 空鏈表示意圖

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

程序清單3.12 新增結(jié)點范例程序

注意，這里的p_head始終指向存在的頭結(jié)點，與程序清單3.6中的p_head意義不同，可以使用如程序清單3.13所示的測試程序?qū)ζ溥M(jìn)行測試，由于初始化時無后繼結(jié)點，因此p_next域的值為NULL。

程序清單3.13 添加結(jié)點范例程序（4）

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

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

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

圖 3.7

即與應(yīng)用程序相關(guān)的數(shù)據(jù)data的類型為另一個結(jié)構(gòu)體類型student_t。

此時只要定義一個slist_node_t類型的變量node，即可引用結(jié)構(gòu)體的成員：

那么該鏈表各成員在內(nèi)存中的存儲關(guān)系就確定下來了，詳見圖 3.8。如果使用表達(dá)式

圖 3.8

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

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

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

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

2、存址

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

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

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

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

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

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

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

分析當(dāng)前鏈表結(jié)點的定義，其主要包含兩個部分：鏈表關(guān)心的p_next指針和用戶關(guān)心的data數(shù)據(jù)。回顧如程序清單3.12所示的slist_add_tail()函數(shù)，沒有出現(xiàn)任何訪問data的代碼，從而說明data與鏈表無關(guān)。既然如此，是否可以將它們分離呢？

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

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

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

圖3.10 鏈表示意圖

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

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

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

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

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

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

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

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

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

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

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

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

程序清單3.16 新增結(jié)點范例程序

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

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

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

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

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

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

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

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

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

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

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

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

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

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