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

一、鏈表引入的緣由：

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

二、什么是鏈表？

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

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

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

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

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

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

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

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

b、為什么要使用堆呢？

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

c、基本概念：

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

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

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

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

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

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

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

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

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

a＝10；

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

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

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

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

實(shí)例：

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

四、實(shí)例演示：

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

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

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

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

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

a、什么是頭指針？

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

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

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

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