關于線性鏈表基本操作技巧

摘要： 筆者從事《數據結構》專業基礎課教學4年的時間，通過教學實踐和項目實踐，以及計算機專業考研輔導等各種方式和途徑，總結了學生在學習中的一些比較常見的問題。由于線性結構是數據結構學科中最基本最常用的結構，所以針對線性結構的各種算法和應用，筆者簡單地總結了其中的一部分技巧性的方法。

關鍵詞： 線性表 數據結構 基本操作 技巧

線性表是我們在數據結構的學習中碰到的第一個數據結構，其重要性不言而喻。學習線性表的重點是掌握順序表和單鏈表上實現的各種基本算法和相關的時間性能及空間性能的分析，難點就是使用本章所學的基本知識設計有效算法解決與線性表相關的應用問題。

就邏輯結構而言線性表非常簡單，是有限數據元素的順序序列，對于存儲結構我們初學者一般也只研究順序存儲和鏈式存儲兩種。即便如此，仍然有很多學生對線性表的綜合應用題目無從下手，這種現象甚至在許多學生考研過程中經常出現。問題的關鍵是學生只把線形表的各個知識點作為一個獨立的題目看待，沒有將它們聯系看待，此外在解決較為復雜的題目時不知道和簡單的基礎知識點作聯系。

例如關于線形鏈表（通常以單鏈表為例）的插入操作，已知單鏈表L，在第i個元素的前面插入一個新的元素e；一般程序實現如下：

單鏈表的這種基本插入算法，在數據結構的各種教材中都有描述，而且都是將其當作對單鏈表操作的第一個算法來學習。其寓意在于借助簡單算法解決較為復雜的算法。其中最為典型的就是利用插入算法完成構造單鏈表算法，經典的構造算法有“首插法”和“尾插法”。我們先來認識一下首插法。首插法簡單地理解就是通過在單鏈表的首部插入新節點完成單鏈表的構造任務。在數據結構中單鏈表一般指的就是帶頭節點的單鏈表，所以單鏈表的首部就是指頭節點后面的位置，算法的關鍵就成了如何始終在頭節點的后面插入新節點。問題分析完了大家就可以起筆描述算法了。

首先對算法分析可知，建立單鏈表的過程是一個動態生成的過程。即從“空表”的初始狀態起，依次建立。在該算法中核心語句為P->next=L->next；L->next=P。在頭節點的后面插入，不難發現這和前面的在單鏈表第i個位置之前插入新元素算法的核心語句幾乎等同，所以我們可以認為是插入基本操作解決了建立單鏈表問題。同樣如果我們繼續探索首插法就會發現，由首插法建立的單鏈表元素輸入順序和最終在單鏈表里的位置剛好逆置！這就是在考研中經常出現的題目，比如已知某某線性鏈表，編寫算法將該鏈表逆置；或者已知線性鏈表節點值非遞減有序，編寫算法完成該鏈表的非遞增有序排列……看來只要我們細心觀察分析，就能從很多簡單問題中得到解決復雜問題的突破口。

通過上面對“首插法”的分析，我們可能會得到一些相關的啟示。下面再通過對“尾插法”分析加深大家的理解。尾插法直觀地理解就是不斷地在單鏈表的尾部插入新節點，完成單鏈表的建立。同上面同樣的題目：建立具有n個節點的單鏈表L，條件是利用尾插法。算法描述如下：

前面的算法實現和首插法完全相同，關鍵是下面的核心語句體現在鏈表尾部插入。假設仍讓使用上一種算法的語句：P->next=L->next；L->next=P，先插入第一個節點。因為插入第一個節點的時候，該節點既是第一個節點又是最后一個節點（既是首部又是尾部），所以看不出兩種算法的差別。再結合畫圖分析插入第二個節點。在第一個節點的尾部插入，這時第二個節點就成了鏈表的尾部；同樣，插入第三個節點在第二個節點的尾部，結果第三個節點就成了尾部，將這種方法繼續下去就是尾插法。從插入的過程分析可以知道鏈表的尾部比較關鍵，所以需要定義一個Lnode型的結構體指針r始終指向尾部節點。原來的鏈表為空，可以令r=L，即指向頭節點，我們的目標就轉化成了每次把新節點P插入到r所指節點的尾部，則就有插入語句序列：P->next=r->next；r->next=P，這兩個命令在教材中是我們學習過的基本插入語句。但是最后的細節一定要注意到，為了保證r始終指向尾部，則應該r=r->next；或者r=P，都可以實現。我們的程序描述就完整了：

對尾插法的算法分析后，我們知道利用這種方法建立的單鏈表，元素的輸入次序和元素在單鏈表中的次序一致，利用這種特點我們也可以技巧性地處理一些問題，比如：“已知兩個線性鏈表La和Lb，元素均是遞增排列，編寫算法完成這兩個單鏈表的合并，并且合并以后的單鏈表保持元素的遞增特點；算法要求利用原來單鏈表中的節點存放歸并后的單鏈表。”這個算法的關鍵在于合并后保持遞增性，也就是跟合并前單鏈表的特性保持一致。根據這個提示我們可以分析一下：假設合并以后的單鏈表是Lc，Lc初始狀態為空鏈表，即只有頭節點，為了節約空間我們假借鏈表La的頭節點為Lc的頭節點，即Lc=La；下面的工作就是解決如何將La和Lb中的節點插入到Lc中去；假設La中的元素分別為（a ，a ，a ……a ）且a next，q=La->next；從第一個節點開始出發，將p和q所指的節點進行比較，if（p->data<=q->data），則將La中的節點p插入Lc中，否則插入Lb中的節點q，這時在Lc中的第一個節點值就是最小的，我們就在最小的節點后面插入第二小的，在第二小的節點后面插入第三小的……不斷地在Lc的尾部插入滿足條件的節點，這在本質上剛好使用了我們上面講過的“尾插法”建立單鏈表Lc，剩余的工作就是把算法賦予代碼了：

除此之外，通過對線性鏈表的簡單問題仔細分析和掌握，我們就可以攻克許多關于線性表甚至是非線性結構的較復雜問題。所以平時學習課本基礎知識的時候，不能只停留在知識的表面，應該充分理解，遇到復雜問題時我們不要恐懼，要學會跟基本的知識聯系，以基本的理論方法解決掉復雜的問題；同時我們還不難發現，在算法實現時考慮問題的全面性也非常重要；就像剛才合并算法中，雖然找出了算法的核心，但是當出了那個核心循環體，還要考慮到哪個鏈表中有節點剩余，這樣的情況時常會出現。綜合來看，按照上面所講的這種技巧性的思考方式，即在理解基礎知識之上進行發散思考，學生不但找到了許多復雜問題的解決途徑，同時也讓自己有了小小的成就感，學習更有興趣和信心了。這種技巧不僅在解決線性鏈表的各種問題中適用，在數據結構的其他方面同樣適用，只要平時多觀察、多思考、多練習，大家就可以找到更多更巧妙的方法。

參考文獻：

［１］嚴蔚敏.數據結構（C語言版）.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”189，