單鏈表學(xué)習(xí)的總結(jié)（一）

想必大多數(shù)人和我一樣，剛開始學(xué)數(shù)據(jù)結(jié)構(gòu)中的單鏈表還是蠻吃力的，特別是后面的雙鏈表操作更是如此。還有就是在實踐代碼操作時，你又會感到無從下手，沒有思路。造成這樣的緣由，還是沒有完全把鏈表吃透，今天剛好看書又看到了這里，總結(jié)一下，分享給大家，希望對大家有幫助。

一、鏈表引入的緣由：

在一開始，不知大家用了這么久的數(shù)組，你有沒有發(fā)現(xiàn)數(shù)組存在兩個明顯的缺陷？1）一個是數(shù)組中所有元素的類型必須一致；2）第二個是數(shù)組的元素個數(shù)必須事先制定并且一旦指定之后不能更改。于是乎為了解決數(shù)組的缺陷，先輩們發(fā)明的一些特殊方法來解決：a、數(shù)組的第一個缺陷靠結(jié)構(gòu)體去解決。結(jié)構(gòu)體允許其中的元素的類型不相同，因此解決了數(shù)組的第一個缺陷。所以說結(jié)構(gòu)體是因為數(shù)組不能解決某些問題所以才發(fā)明的；b、我們希望數(shù)組的大小能夠?qū)崟r擴展。譬如我剛開始定了一個元素個數(shù)是10，后來程序運行時覺得不夠因此動態(tài)擴展為20．普通的數(shù)組顯然不行，我們可以對數(shù)組進行封裝以達到這種目的；我們還可以使用一個新的數(shù)據(jù)結(jié)構(gòu)來解決，這個新的數(shù)據(jù)結(jié)構(gòu)就是鏈表（幾乎可以這樣理解：鏈表就是一個元素個數(shù)可以實時變大／變小的數(shù)組）。

二、什么是鏈表？

顧名思義，鏈表就是用鎖鏈連接起來的表。這里的表指的是一個一個的節(jié)點（一個節(jié)點可以比喻成大樓里面的空房子一樣用來存放東西的），節(jié)點中有一些內(nèi)存可以用來存儲數(shù)據(jù)（所以叫表，表就是數(shù)據(jù)表）；這里的鎖鏈指的是鏈接各個表的方法，C語言中用來連接2個表（其實就是2塊內(nèi)存）的方法就是指針。它的特點是：它是由若干個節(jié)點組成的（鏈表的各個節(jié)點結(jié)構(gòu)是完全類似的），節(jié)點是由有效數(shù)據(jù)和指針組成的。有效數(shù)據(jù)區(qū)域用來存儲信息完成任務(wù)的，指針區(qū)域用于指向鏈表的下一個節(jié)點從而構(gòu)成鏈表。

三、單鏈表中的一些細節(jié)：

1、單鏈表的構(gòu)成：

a、鏈表是由節(jié)點組成的，節(jié)點中包含：有效數(shù)據(jù)和指針。

b、定義的struct node只是一個結(jié)構(gòu)體，本身并沒有變量生成，也不占用內(nèi)存。結(jié)構(gòu)體定義相當(dāng)于為鏈表節(jié)點定義了一個模板，但是還沒有一個節(jié)點，將來在實際創(chuàng)建鏈表時需要一個節(jié)點時用這個模板來復(fù)制一個即可。例如：

1 struct node｛2 int data；／／有效數(shù)據(jù)34struct node ＊pNext；／／指向下一個節(jié)點的指針56 ｝；／／構(gòu)建一個鏈表的節(jié)點。

2、堆內(nèi)存的申請和使用：

a、先了解一下什么是堆：堆（heap）是種內(nèi)存管理方式，它的特點是：就是自由管理（隨時申請，靈活，大小塊隨意）。堆內(nèi)存是操作系統(tǒng)規(guī)劃給堆管理器（操作系統(tǒng)中的的一段代碼，屬于操作系統(tǒng)的內(nèi)存管理單元），來管理的，然后向使用者（用戶進程）提供api（malloc和free）來使用堆內(nèi)存。

b、為什么要使用堆呢？

需要內(nèi)存容量比較大的時候，需要反復(fù)使用及釋放時，需要反復(fù)使用及釋放很多數(shù)據(jù)結(jié)構(gòu)（譬如鏈表）的實現(xiàn)都要使用堆內(nèi)存；它的特點：容量不限（常規(guī)使用的需求容量都能滿足），申請及釋放都需要手工進行，手工進行的含義就是需要程序員寫代碼明確進行申請malloc及釋放free。如果程序員申請內(nèi)存并使用沒有釋放，這段內(nèi)存就丟失了（在堆管理器的記錄中，這段內(nèi)存仍然屬于你這個進程，但是進程自己又以為這段內(nèi)存已經(jīng)不用了，再用的時候又會申請新的內(nèi)存塊，這就叫吃內(nèi)存），稱為內(nèi)存泄漏。

c、基本概念：

作用域：起作用的區(qū)域，也就是可以工作的范圍。

代碼塊：所謂代碼塊，就是用｛｝括起來的一段代碼。

數(shù)據(jù)段：數(shù)據(jù)段存的是數(shù)，像全局變量就是存在數(shù)據(jù)段的。

代碼段：存的是程序代碼，一般是只讀的。

棧（stack）：先進后出。C語言中局部變量就分配在棧中。

這里隨便也講一下什么是棧：

棧是一種數(shù)據(jù)結(jié)構(gòu)，c語言中使用棧來保存局部變量。棧是被發(fā)明出來管理內(nèi)存的；它的特點：是先進后出；而先進先出，它是隊列的特點；棧的特點是入口即出口，另外一個口是堵死的。所以先進去的必須后出來隊列的特點是入口和出口都有，必須從入口進去，從出口出來，所以先進去的必須先出來，否則就堵住后面的。在c 語言中的局部變量是用棧來實現(xiàn)的。我們在c中定義一個局部變量時（int a ），編譯器會在棧中分配一段空間（4字節(jié)）給這個局部變量用（分配時棧頂指針會移動給出空間，給局部變量a用的意思就是，將這4字節(jié)的棧內(nèi)存地址和我們定義的局部變量名a 給關(guān)聯(lián)起來），對應(yīng)棧的操作時入棧。

注意：這里棧指針的移動和內(nèi)存分配是自動的（棧自己完成，不用我們寫代碼去操作）；然后等我們函數(shù)退出的時候，局部變量要滅亡。對應(yīng)棧的操作時出棧。出棧時也是棧頂指針移動將?？臻g中與a關(guān)聯(lián)的那4個字節(jié)空間釋放。這個動作也是自動的，也不用人去寫代碼去控制。棧的優(yōu)點：棧管理內(nèi)存，好處是方便，分配和最后回收都不用程序員操心，c語言自動完成。分析一個細節(jié)：c語言中，定義局部變量時如果未初始化，則值時隨機的為什么？定義局部變量，其實就是在棧中通過移動棧指針來給程序提供一個內(nèi)存空間和這個局部變量名綁定，因為這段內(nèi)存空間在棧上，而棧內(nèi)存是反復(fù)使用的（臟的，上次用完沒有清零的），所以說使用棧來實現(xiàn)的局部變量定義時如果不顯示初始化，值就是臟的。如果你顯示初始化會怎樣？

c語言是通過一個小手段來實現(xiàn)局部變量的初始化的。比如 int a＝10；相當(dāng)于 int a ；

a＝10；

棧的缺點：首先，棧是有大小的。所以棧內(nèi)存大小不好設(shè)置，如果太小怕溢出，太大跑浪費內(nèi)存；所以棧的溢出危害很大，一定避免。所以我們在c語言中定義局部變量時不能定義太多或者太大（譬如不能定義局部變量時int a［10000］）

使用遞歸來解決問題時一定要注意遞歸收斂．

d、注意：鏈表的內(nèi)存要求比較靈活，不能用棧，也不能用data數(shù)據(jù)段。只能用堆內(nèi)存。

使用堆內(nèi)存來創(chuàng)建一個鏈表節(jié)點的步驟：1、申請堆內(nèi)存，大小為一個節(jié)點的大?。z查申請結(jié)果是否正確）；2、清理申請到的堆內(nèi)存；3、把申請到的堆內(nèi)存當(dāng)作一個新節(jié)點；4、填充你哦個新節(jié)點的有效數(shù)據(jù)和指針區(qū)域。

實例：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 int main（void） 5｛ 6 ／／創(chuàng)建一個鏈表節(jié)點 7 struct node ＊p＝（struct node＊）malloc（sizeof（struct node））； 8 if（NULL＝＝p） 9 ｛10 printf（＂malloc error．n＂）；11 ｝12 ／／清理申請到的堆內(nèi)存13 bzero（p，sizeof（struct node））；14 ／／填充節(jié)點15 p－＞data＝1；16 p－＞pNext ＝NULL；／／將來要指向下一個節(jié)點的首地址；實際操作時將下 一 個節(jié)點malloc返回的指針賦值給這個17｝

四、實例演示：

1、單鏈表的實現(xiàn)：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構(gòu)建一個鏈表的節(jié)點 5 struct node 6 ｛ 7 int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10 int main（void）11 ｛12／／ 定義頭指針13struct node ＊pHeader ＝ NULL；14／／15／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關(guān)聯(lián)起來16／／ 創(chuàng)建一個鏈表節(jié)點17struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；18if （NULL ＝＝ p）19｛20 printf（＂malloc error．n＂）；21 return －1；22｝23／／ 清理申請到的堆內(nèi)存24bzero（p， sizeof（struct node））；25／／ 填充節(jié)點26p－＞data ＝ 1；27p－＞pNext ＝ NULL； ／／ 將來要指向下一個節(jié)點的首地址28 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個2930pHeader ＝ p； ／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 31／／33／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關(guān)聯(lián)起來34／／ 創(chuàng)建一個鏈表節(jié)點35struct node ＊p1 ＝ （struct node ＊）malloc（sizeof（struct node））；36if （NULL ＝＝ p1）37｛38 printf（＂malloc error．n＂）；39 return －1；40｝41／／ 清理申請到的堆內(nèi)存42bzero（p1， sizeof（struct node））；43／／ 填充節(jié)點44p1－＞data ＝ 2；45p1－＞pNext ＝ NULL； ／／ 將來要指向下一個節(jié)點的首地址46 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個474849p－＞pNext ＝ p1； ／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 505152／／5354／／5556／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關(guān)聯(lián)起來5758／／ 創(chuàng)建一個鏈表節(jié)點5960struct node ＊p2 ＝ （struct node ＊）malloc（sizeof（struct node））；61if （NULL ＝＝ p2）62｛63 printf（＂malloc error．n＂）；64 return －1；65｝66／／ 清理申請到的堆內(nèi)存67bzero（p2， sizeof（struct node））；68／／ 填充節(jié)點69p2－＞data ＝ 3；70p1－＞pNext ＝ p2； ／／ 將來要指向下一個節(jié)點的首地址71 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個 72／／73／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。7475／／ 下面是4．9．3節(jié)的代碼76／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用p、p1、p2，而只能77／／ 使用pHeader。7879／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)80printf（＂node1 data： ％d．n＂， pHeader－＞data）； 81printf（＂p－＞data： ％d．n＂， p－＞data）； ／／ pHeader－＞data等同于p－＞data8283／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)84printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 85printf（＂p1－＞data： ％d．n＂， p1－＞data）； 86／／ pHeader－＞pNext－＞data等同于p1－＞data8788／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)89printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 90printf（＂p2－＞data： ％d．n＂， p2－＞data）； 91／／ pHeader－＞pNext－＞pNext－＞data等同于p2－＞data9293return 0；94｝

編譯結(jié)果如下：

1 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file2．c2 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3 node1 data： 1．4 p－＞data： 1．5 node2 data： 2．6 p1－＞data： 2．7 node3 data： 3．8 p2－＞data： 3．

2、在鏈表末尾添加元素：

思路：由頭指針向后遍歷，直到走到原來的最后一個節(jié)點。原來最后一個節(jié)點里面的pNext是NULL，現(xiàn)在我們只要將它改成new就可以了。添加了之后新節(jié)點就變成了最后一個。代碼實例；

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構(gòu)建一個鏈表的節(jié)點 5 struct node 6｛ 7int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10／／ 作用：創(chuàng)建一個鏈表節(jié)點11／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址12struct node ＊ create＿node（int data）13｛14struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；15if （NULL ＝＝ p）16｛17 printf（＂malloc error．n＂）；18 return NULL；19｝20／／ 清理申請到的堆內(nèi)存21bzero（p， sizeof（struct node））；22／／ 填充節(jié)點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 void insert＿tail（struct node ＊pH， struct node ＊new）28 ｛29／／ 分兩步來完成插入30／／ 第一步，先找到鏈表中最后一個節(jié)點31struct node ＊p ＝ pH；32while （NULL ！＝ p－＞pNext）33｛34 p ＝ p－＞pNext； 35／／ 往后走一個節(jié)點36｝37／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部38p－＞pNext ＝ new；39 ｝40 int main（void）41 ｛42／／ 定義頭指針43／／struct node ＊pHeader ＝ NULL； 44／／ 這樣直接insert＿tail會段錯誤。45struct node ＊pHeader ＝ create＿node（1）；46insert＿tail（pHeader， create＿node（2））；47insert＿tail（pHeader， create＿node（3））；48insert＿tail（pHeader， create＿node（4））；49 ／＊50pHeader ＝ create＿node（1）；51 ／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 52pHeader－＞pNext ＝ create＿node（432）； 53／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 5455pHeader－＞pNext－＞pNext ＝ create＿node（123）； 56／／ 將來要指向下一個節(jié)點的首地址5758／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。59 ＊／60 ／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用p、p1、p2，而只能61 ／／ 使用pHeader。62／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)63printf（＂node1 data： ％d．n＂， pHeader－＞data）； 64／／printf（＂p－＞data： ％d．n＂， p－＞data）； 65 ／／ pHeader－＞data等同于p－＞data66／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)67printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 68／／printf（＂p1－＞data： ％d．n＂， p1－＞data）； 69／／ pHeader－＞pNext－＞data等同于p1－＞data70／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)71printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 72／／printf（＂p2－＞data： ％d．n＂， p2－＞data）； 73／／ pHeader－＞pNext－＞pNext－＞data等同于p2－＞data74return 0；75｝

編譯結(jié)果：

1root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file3．c2root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3node1 data： 1．4node2 data： 2．5node3 data： 3．

3、在第一個節(jié)點插入元素：

在代碼演示之前，先名兩個概念：頭指針和頭節(jié)點

a、什么是頭指針？

頭指針并不是節(jié)點，而是一個普通指針，只占4字節(jié)。頭指針的類型是struct node ＊類型的，所以它才能指向鏈表的節(jié)點。一個典型的鏈表的實現(xiàn)就是：頭指針指向鏈表的第1個節(jié)點，然后第1個節(jié)點中的指針指向下一個節(jié)點，然后依次類推一直到最后一個節(jié)點。這樣就構(gòu)成了一個鏈。

b、什么是頭節(jié)點？

其實它和一般的節(jié)點差不多，只不過要注意的是：第一，它緊跟在頭指針后面。第二，頭節(jié)點的數(shù)據(jù)部分是空的（有時候不是空的，而是存儲整個鏈表的節(jié)點數(shù)），指針部分指向下一個節(jié)點，也就是第一個節(jié)點。

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構(gòu)建一個鏈表的節(jié)點 5 struct node 6 ｛ 7int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10 ／／ 作用：創(chuàng)建一個鏈表節(jié)點11 ／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址12 struct node ＊ create＿node（int data）13 ｛14struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；15if （NULL ＝＝ p）16｛17 printf（＂malloc error．n＂）；18 return NULL；19 ｝20／／ 清理申請到的堆內(nèi)存21bzero（p， sizeof（struct node））；22／／ 填充節(jié)點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 ／／ 思路：由頭指針向后遍歷，直到走到原來的最后一個節(jié)點。原來最后一個節(jié)點里面的pNext是NULL，現(xiàn)在我們只要將它改成new就可以了。添加了之后新節(jié)點就變成了最后一個。2829 ／／ 計算添加了新的節(jié)點后總共有多少個節(jié)點，然后把這個數(shù)寫進頭節(jié)點中。3031void insert＿tail（struct node ＊pH， struct node ＊new）32 ｛33int cnt ＝ 0；34／／ 分兩步來完成插入35／／ 第一步，先找到鏈表中最后一個節(jié)點36struct node ＊p ＝ pH；37while （NULL ！＝ p－＞pNext）38｛39 p ＝ p－＞pNext； 40 ／／ 往后走一個節(jié)點41 cnt＋＋；42｝43／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部44p－＞pNext ＝ new；45pH－＞data ＝ cnt ＋ 1；46 ｝47void insert＿head（struct node ＊pH， struct node ＊new）48｛49／／ 第1步： 新節(jié)點的next指向原來的第一個節(jié)點50new－＞pNext ＝ pH－＞pNext；51／／ 第2步： 頭節(jié)點的next指向新節(jié)點的地址52pH－＞pNext ＝ new；53／／ 第3步： 頭節(jié)點中的計數(shù)要加154pH－＞data ＋＝ 1；55 ｝56int main（void）57｛58／／ 定義頭指針59／／struct node ＊pHeader ＝ NULL； 60 ／／ 這樣直接insert＿tail會段錯誤。61struct node ＊pHeader ＝ create＿node（0）；62insert＿head（pHeader， create＿node（1））；63insert＿tail（pHeader， create＿node（2））；64insert＿head（pHeader， create＿node（3））；65 ／＊66pHeader ＝ create＿node（1）；6768／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 69pHeader－＞pNext ＝ create＿node（432）； 70／／ 將本節(jié)點和它前面的頭指針關(guān)聯(lián)起來 71pHeader－＞pNext－＞pNext ＝ create＿node（123）； 72／／ 將來要指向下一個節(jié)點的首地址73／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。74 ＊／75／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用 p、p1、p2，而只能76／／ 使用pHeader。77／／ 訪問鏈表頭節(jié)點的有效數(shù)據(jù)78printf（＂beader node data： ％d．n＂， pHeader－＞data）； 79／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)80printf（＂node1 data： ％d．n＂， pHeader－＞pNext－＞data）； 81／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)82printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 83／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)84printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞pNext－＞data）； 85return 0；86｝

編譯結(jié)果；

1 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file4．c2 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3 beader node data： 3．4 node1 data： 3．5 node2 data： 1．6 node3 data： 2．

五、總結(jié)：

通過本次鏈表的學(xué)習(xí)，讓自己對鏈表的理解更加深了，接下來雙鏈表的使用會在后面更新，歡迎大家來關(guān)注?。?/p>