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

第三章為算法與數(shù)據(jù)結(jié)構(gòu)，本文為3.2.3 接口。

>>> 3.2.3接口

在實(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)的指針。

雖然操作簡(jiǎ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)的效率將隨著鏈表長(zhǎng)度的增加逐漸降低，如果鏈表很長(zhǎng)，則效率將變得十分低下，因?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)行對(duì)比發(fā)現(xiàn)，其不再需要尋找尾結(jié)點(diǎn)的過程，無(wú)論鏈表多長(zhǎng)，都可以通過這兩步完成結(jié)點(diǎn)的添加。加結(jié)點(diǎn)到鏈表頭部的函數(shù)原型（slist.h）為：

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

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

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

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

將node3添加到鏈表頭部，查看修改后的最終輸出結(jié)果發(fā)生了什么變化？

既然可以將結(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）為：

其中，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)至鏈表任意位置的范例程序

盡管此函數(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ù)的范例程序

顯然，添加結(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)至頭部和尾部

如果要將一個(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）為：

其中，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ū)的范例程序

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

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

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

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

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

與添加一個(gè)結(jié)點(diǎn)對(duì)應(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）為：

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

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

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

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

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

程序清單3.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)存，也不需要添加額外的對(duì)內(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)存）

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

雖然這樣定義使得學(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é)生記錄。比如：

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

程序清單3.32 綜合程序范例

綜上所述，雖然鏈表比數(shù)組更靈活，很容易在鏈表中插入和刪除結(jié)點(diǎn)，但也失去了數(shù)組的“隨機(jī)訪問”能力。如果結(jié)點(diǎn)距離鏈表的開始處很近，那么訪問它就會(huì)很快；如果結(jié)點(diǎn)靠近鏈表的結(jié)尾處，則訪問它就會(huì)很慢。但單向鏈表也存在不能“回溯”的缺點(diǎn)，即在向鏈表中插入結(jié)點(diǎn)時(shí)，必須知道插入結(jié)點(diǎn)前面的結(jié)點(diǎn)；從鏈表中刪除結(jié)點(diǎn)時(shí)，必須知道被刪除結(jié)點(diǎn)前面的結(jié)點(diǎn)；很難逆向遍歷鏈表。如果是雙向鏈表，就可以解決這些問題。