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

第三章為算法與數據結構，本文為3.2.3 接口。

>>> 3.2.3接口

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

雖然操作簡單，但執行該操作的前提是要找到添加結點前鏈表的尾結點，則需要從指向頭結點的p_head指針開始，依次遍歷每個結點，直到找到結點中p_next值為NULL（尾結點）時為止。可想而知，添加一個結點的效率將隨著鏈表長度的增加逐漸降低，如果鏈表很長，則效率將變得十分低下，因為每次添加結點前都要遍歷一次鏈表。

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

圖 3.11添加一個結點至鏈表頭部

在其實現過程中，需要完成兩個指針的修改：（1）修改新結點中的p_next，使其指向頭結點中p_next指向的結點；（2）修改頭結點的p_next，使其指向新的結點。

與添加結點至鏈表尾部的過程進行對比發現，其不再需要尋找尾結點的過程，無論鏈表多長，都可以通過這兩步完成結點的添加。加結點到鏈表頭部的函數原型（slist.h）為：

其中，p_head指向鏈表頭結點，p_node為待添加的結點，其實現詳見程序清單3.21。

程序清單3.21 新增結點至鏈表頭部的范例程序

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

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

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

既然可以將結點添加至頭部和尾部，何不更加靈活一點，提供一個將結點至任意位置的接口函數呢？當結點添加至p_pos指向的結點之后，則鏈表的變化詳見圖 3.12。

圖 3.12 添加結點至任意位置示意圖

在其實現過程中，需要修改兩個指針：（1）修改新結點中的p_next，使其指向p_pos指向結點的下一個結點；（2）修改p_pos指向結點的p_next，使其指向新結點。通過這兩步即可添加結點，添加結點至鏈表任意位置的函數原型（slist.h）為：

其中，p_head指向鏈表頭結點，p_node指向待添加的結點，p_pos指向的結點表明新結點添加的位置，新結點即添加在p_pos指向的結點后面，其實現詳見程序清單3.22。

程序清單3.22 新增結點至鏈表任意位置的范例程序

盡管此函數在實現時沒有用到參數p_head，但還是將p_head參數傳進來了，因為實現其它功能時將會用到p_head參數，比如，判斷p_pos是否在鏈表中。

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

程序清單3.23 管理int型數據的范例程序

顯然，添加結點至鏈表頭部和尾部，僅僅是添加結點至任意位置的特殊情況：

• 添加結點至鏈表頭部，即添加結點至頭結點之后；

• 添加結點至鏈表尾部，即添加結點至鏈表尾結點之后。

slist_add_head()函數和slist_add_tail()函數的實現詳見程序清單3.24。

程序清單3.24 基于slist_add()實現添加結點至頭部和尾部

如果要將一個結點添加至某一結點之前呢？實際上，添加結點至某一結點之前同樣也只是添加結點至某一結點之后的一種變形，即添加至該結點前一個結點的后面，詳見圖3.13。

圖3.13 添加結點至任意位置前示意圖

顯然，只要獲得某一結點的前驅，即可使用slist_add()函數添加結點至某一結點前面。為此，需要提供一個獲得某一結點前驅的函數，其函數原型（slist.h）為：

其中，p_head指向鏈表頭結點，p_pos指向的結點表明查找結點的位置，返回值即為p_pos指向結點的前一個結點。由于在單向鏈表的結點中沒有指向其上一個結點的指針，因此，只有從頭結點開始遍歷鏈表，當某一結點的p_next指向當前結點時，表明其為當前結點的上一個結點，函數實現詳見程序清單3.25。

程序清單3.25 獲取某一結點前驅的范例程序

由此可見，若p_pos的值為NULL，則當某一結點的p_next為NULL時就會返回，此時返回的結點實際上就是尾結點。為了便于用戶理解，可以簡單封裝一個查找尾結點的函數，其函數原型為：

其函數實現詳見程序清單3.26。

程序清單3.26 查找尾結點

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

程序清單3.27 查找尾結點

與添加一個結點對應，也可以從鏈表中刪除某一結點。假定鏈表中已經存在3個結點，現在要刪除中間的結點，則刪除前后的鏈表變化詳見圖3.14。

圖3.14 刪除結點示意圖

顯然，刪除一個結點也需要修改兩個指針的值：既要修改其上一個結點的p_next，使其指向待刪除結點的下一個結點，還要將刪除結點的p_next設置為NULL。

刪除結點的函數原型（slist.h）為：

其中，p_head指向鏈表頭結點，p_node為待刪除的結點，slist_del()函數的實現詳見程序清單3.28。

程序清單3.28 刪除結點范例程序

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

程序清單3.29 slist.h文件內容

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

程序清單3.30 綜合范例程序

程序中所有的結點都是按照靜態內存分配的方式定義的，即程序在運行前，各個結點占用的內存就已經被分配好了，而不同的是動態內存分配需要在運行時使用malloc()等函數完成內存的分配。

由于靜態內存不會出現內存泄漏，且在編譯完成后，各個結點的內存就已經分配好了，不需要再花時間去分配內存，也不需要添加額外的對內存分配失敗的處理代碼。因此，在嵌入式系統中，往往多使用靜態內存分配的方式。但其致命的缺點是不能釋放內存，有時候用戶希望在刪除鏈表的結點時，釋放掉其占用內存，這就需要使用動態內存分配。

實際上，鏈表的核心代碼只是負責完成鏈表的操作，僅需傳遞結點的地址（p_node）即可，鏈表程序并不關心結點的內存從何而來。基于此，若要實現動態內存分配，只要在應用中使用malloc()等動態內存分配函數即可，詳見程序清單3.31。

程序清單3.31 綜合范例程序（使用動態內存）

如果按照int型數據的示例，使用鏈表管理學生記錄，則需要在學生記錄中添加一個鏈表結點數據。比如：

雖然這樣定義使得學生信息可以使用鏈表來管理，但卻存在一個很嚴重的問題，因為修改了學生記錄類型的定義，就會影響所有使用該記錄結構體類型的程序模塊。在實際的應用上，學生記錄可以用鏈表管理，也可以用數組管理，當使用數組管理時，則又要重新修改學生記錄的類型。而node僅僅是鏈表的結點，與學生記錄沒有任何關系。不能將node直接放在學生記錄結構體中，應該使它們分離。基于此，需要定義一個新的結構體類型，將學生記錄和node關聯起來，使得可以用鏈表來管理學生記錄。比如：

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

程序清單3.32 綜合程序范例

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