【数据结构链表】之五单链表
一：鏈表基礎
1、鏈表基礎----------------摘錄自百度百科
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。 使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語言中實現(xiàn)。像Lisp和Scheme這樣的語言的內(nèi)建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語言或面向?qū)ο笳Z言，如C,C++和Java依靠易變工具來生成鏈表。 ? 2、鏈表特點 線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示每個數(shù)據(jù)元素與其直接后繼數(shù)據(jù)元素 之間的邏輯關(guān)系，對數(shù)據(jù)元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。由這兩部分信息組成一個"結(jié)點"，表示線性表中一個數(shù)據(jù)元素。線性表的鏈式存儲表示，有一個缺點就是要找一個數(shù)，必須要從頭開始找起，十分麻煩，不能像數(shù)組那樣隨機訪問。。 對于非線性的鏈表，可以參見相關(guān)的其他數(shù)據(jù)結(jié)構(gòu)，例如樹、圖。另外有一種基于多個線性鏈表的數(shù)據(jù)結(jié)構(gòu)：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣。 其中存儲數(shù)據(jù)元素信息的域稱作數(shù)據(jù)域（設域名為data），存儲直接后繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。 由分別表示,，…，的N 個結(jié)點依次相鏈構(gòu)成的鏈表，稱為線性表的鏈式存儲表示，由于此類鏈表的每個結(jié)點中只包含一個指針域，故又稱單鏈表或線性鏈表。 ? 3、循環(huán)鏈表、雙鏈表、單鏈表和順序表 循環(huán)鏈表是與單鏈表一樣，是一種鏈式的存儲結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個結(jié)點的指針是指向該循環(huán)鏈表的第一個結(jié)點或者表頭結(jié)點，從而構(gòu)成一個環(huán)形的鏈。 循環(huán)鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點： (1)在建立一個循環(huán)鏈表時，必須使其最后一個結(jié)點的指針指向表頭結(jié)點，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個結(jié)點后插入一個新的結(jié)點。 (2)在判斷是否到表尾時，是判斷該結(jié)點鏈域（指針域）的值是否是表頭結(jié)點，當鏈域值等于表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。 雙向鏈表 雙向鏈表其實是單鏈表的改進。 當我們對單鏈表進行操作時，有時你要對某個結(jié)點的直接前驅(qū)進行操作時，又必須從表頭開始查找。這是由單鏈表結(jié)點的結(jié)構(gòu)所限制的。因為單鏈表每個結(jié)點只有一個存儲直接后繼結(jié)點地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點地址的鏈域，又有存儲直接前驅(qū)結(jié)點地址的鏈域的這樣一個雙鏈域結(jié)點結(jié)構(gòu)呢？這就是雙向鏈表。 在雙向鏈表中，結(jié)點除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結(jié)點地址，一般稱之為左鏈域。 ? 4、鏈表包含以下特征：（1）.由n個節(jié)點離散分配；（2）.每個節(jié)點通過指針鏈連接（3）每一個節(jié)點由一個前驅(qū)節(jié)點和一個后驅(qū)節(jié)點（4）.首節(jié)點沒有前驅(qū)節(jié)點，尾節(jié)點沒有后驅(qū)節(jié)點；滿足上面的4條，我們就稱為鏈表；鏈表既然由很多個節(jié)點，那節(jié)點又由什么組成？節(jié)點由兩個部分組成，一是數(shù)據(jù)域，用來存放有效數(shù)據(jù)；二是指針域，用來指向下一個節(jié)點 二、單鏈表 1、 ? ? ? ? ? ? 2、節(jié)點的構(gòu)建 typedef ?struct Node { int data;//數(shù)據(jù)域 struct Node *pNext;//指針域 ??定義一個結(jié)構(gòu)體指針，指向下一次個與當前節(jié)點數(shù)據(jù)類型相同的節(jié)點?? }Node,*pNode; 3、鏈表的創(chuàng)建? ?在創(chuàng)建鏈表之前，我們需要需要了解一下專業(yè)術(shù)語：
? ?首節(jié)點：存放第一個有效數(shù)據(jù)的節(jié)點；
? ?尾節(jié)點：存放最后一個有效數(shù)據(jù)的節(jié)點；
? ?頭節(jié)點：頭節(jié)點的數(shù)據(jù)類型與首節(jié)點的數(shù)據(jù)類型相同，并且頭節(jié)點是首節(jié)點前面的那個節(jié)點，并不存放有效數(shù)據(jù)；頭節(jié)點的存在只是為了方便鏈表的插入和刪除等操作。
? ?頭指針：指向頭節(jié)點的指針；
? ?尾指針：指向尾節(jié)點的指針；
參考博客：http://blog.csdn.net/lpp0900320123/article/details/20356143 -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------1、數(shù)據(jù)元素的存儲結(jié)構(gòu)形式有兩種：順序存儲和鏈式存儲。
順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。
鏈式存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。
很顯然，這樣說的話鏈式存儲結(jié)構(gòu)的數(shù)據(jù)元素存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要用一個指針存放數(shù)據(jù)元素的地址，這樣子通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。
2、數(shù)據(jù)元素之間的關(guān)系：
(1)集合關(guān)系
(2)線形關(guān)系
(3)樹形關(guān)系
(4)圖形關(guān)系
3、
算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。對于給定的問題，是可以有多種算法來解決的。
算法具有五個基本特征：輸入、輸出、有窮性、確定性和可行性。
(1)輸入
算法具有零個或多個輸入。
盡管對于絕大多數(shù)算法來說，輸入?yún)?shù)都是必要的。但是有些時候，像打印“I love fishc.com”，就不需要啥參數(shù)啦。
(2)輸出
算法至少有一個或多個輸出。
算法是一定要輸出的，不需要它輸出，那你要這個算法來干啥？
輸出的形式可以是打印形式輸出，也可以是返回一個值或多個值等。
(3)有窮性
指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。
一個永遠都不會結(jié)束的算法，我們還要他來干啥？
(4)確定性
算法的每一個步驟都具有確定的含義，不會出現(xiàn)二義性。
算法在一定條件下，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果。
算法的每個步驟都應該被精確定義而無歧義。
(5)可行性
算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。
好的算法應該具備時間效率高和存儲量低的特點。
4、
算法效率一般是指算法的執(zhí)行時間，判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常常可以忽略，而更應該關(guān)注主項（最高項）的階數(shù)。
5、
算法時間復雜度的定義：在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。
算法的時間復雜度，也就是算法的時間量度，記作：T(n)= O(f(n))。
它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度，簡稱為時間復雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。
一般情況下，隨著輸入規(guī)模n的增大，T(n)增長最慢的算法為最優(yōu)算法。
6、怎么推導大O階呢？
用常數(shù)1取代運行時間中的所有加法常數(shù)。
在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。
得到的最后結(jié)果就是大O階。
[線性階]
一般含有非嵌套循環(huán)涉及線性階，線性階就是隨著問題規(guī)模n的擴大，對應計算次數(shù)呈直線增長。
int i , n = 100, sum = 0;
for( i=0; i < n; i++ )
{
sum = sum + i;
}
上面這段代碼，它的循環(huán)的時間復雜度為O(n)，因為循環(huán)體中的代碼需要執(zhí)行n次。
[平方階]
剛才是單個循環(huán)結(jié)構(gòu)，那么嵌套呢？
int i, j, n = 100;
for( i=0; i < n; i++ )
{
for( j=0; j < n; j++ )
{
printf(“I love FishC.comn”);
}
}
n等于100，也就是說外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)就執(zhí)行100次，那總共程序想要從這兩個循環(huán)出來，需要執(zhí)行100*100次，也就是n的平方。所以這段代碼的時間復雜度為O(n^2)。
那如果有三個這樣的嵌套循環(huán)呢？
沒錯，那就是n^3啦。所以我們很容易總結(jié)得出，循環(huán)的時間復雜度等于循環(huán)體的復雜度乘以該循環(huán)運行的次數(shù)。
剛剛我們每個循環(huán)的次數(shù)都是一樣的，如果：
int i, j, n = 100;
for( i=0; i < n; i++ )
{
for( j=i; j < n; j++ )
{
printf(“I love FishC.comn”);
}
}
分析下，由于當i=0時，內(nèi)循環(huán)執(zhí)行了n次，當i=1時，內(nèi)循環(huán)則執(zhí)行n-1次……當i=n-1時，內(nèi)循環(huán)執(zhí)行1次，所以總的執(zhí)行次數(shù)應該是：
n+(n-1)+(n-2)+…+1 = n(n+1)/2
大家還記得這個公式吧？恩恩，沒錯啦，就是搞死先生發(fā)明的算法丫。
那咱理解后可以繼續(xù)，n(n+1)/2 = n^2/2+n/2
用我們推導大O的攻略，第一條忽略，因為沒有常數(shù)相加。第二條只保留最高項，所以n/2這項去掉。第三條，去除與最高項相乘的常數(shù)，最終得O(n^2)。
[對數(shù)階]
對數(shù)，屬于高中數(shù)學內(nèi)容啦，對于有些魚油可能對這玩意不大理解，或者忘記了，也沒事，咱分析的是程序為主，而不是數(shù)學為主，不怕。
int i = 1, n = 100;
while( i < n )
{
i = i * 2;
}
由于每次i*2之后，就距離n更近一步，假設有x個2相乘后大于或等于n，則會退出循環(huán)。
于是由2^x = n得到x = log(2)n，所以這個循環(huán)的時間復雜度為O(logn)。
頭指針
頭指針是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針。
頭指針具有標識作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。
無論鏈表是否為空，頭指針均不為空。
頭指針是鏈表的必要元素。
頭結(jié)點
頭結(jié)點是為了操作的統(tǒng)一和方便而設立的，放在第一個元素的結(jié)點之前，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）。
有了頭結(jié)點，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點起操作與其它結(jié)點的操作就統(tǒng)一了。
頭結(jié)點不一定是鏈表的必須要素。
單鏈表圖例：
單鏈表圖例
?
空鏈表圖例：
空鏈表圖例
獲得鏈表第i個數(shù)據(jù)的算法思路：
聲明一個結(jié)點p指向鏈表第一個結(jié)點，初始化j從1開始；
當j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向一下結(jié)點，j+1；
若到鏈表末尾p為空，則說明第i個元素不存在；
否則查找成功，返回結(jié)點p的數(shù)據(jù)。
?單鏈表的插入
?
我們先來看下單鏈表的插入。假設存儲元素e的結(jié)點為s，要實現(xiàn)結(jié)點p、p->next和s之間邏輯關(guān)系的變化，大家參考下圖思考一下：
單鏈表的插入
?
我們思考后發(fā)覺根本用不著驚動其他結(jié)點，只需要讓s->next和p->next的指針做一點改變。
s->next = p->next;
p->next = s;
?
我們通過圖片來解讀一下這兩句代碼。
單鏈表的插入
?
那么我們考慮一下大部分初學者最容易搞壞腦子的問題：這兩句代碼的順序可不可以交換過來？
先 p->next = s;
再 s->next = p->next;
?
大家發(fā)現(xiàn)沒有？如果先執(zhí)行p->next的話會先被覆蓋為s的地址，那么s->next = p->next其實就等于s->next = s了。
所以這兩句是無論如何不能弄反的，這點初學者一定要注意咯~
?
單鏈表第i個數(shù)據(jù)插入結(jié)點的算法思路：
聲明一結(jié)點p指向鏈表頭結(jié)點，初始化j從1開始；
當j<1時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一結(jié)點，j累加1；
若到鏈表末尾p為空，則說明第i個元素不存在；
否則查找成功，在系統(tǒng)中生成一個空結(jié)點s；
將數(shù)據(jù)元素e賦值給s->data；
單鏈表的插入剛才兩個標準語句；
返回成功。
?代碼示例：
單鏈表的刪除
?
現(xiàn)在我們再來看單鏈表的刪除操作。
單鏈表的刪除
?
假設元素a2的結(jié)點為q，要實現(xiàn)結(jié)點q刪除單鏈表的操作，其實就是將它的前繼結(jié)點的指針繞過指向后繼結(jié)點即可。
那我們所要做的，實際上就是一步：
可以這樣：p->next = p->next->next;
也可以是：q=p->next; p->next=q->next;
?
單鏈表第i個數(shù)據(jù)刪除結(jié)點的算法思路：
聲明結(jié)點p指向鏈表第一個結(jié)點，初始化j=1；
當j<1時，就遍歷鏈表，讓P的指針向后移動，不斷指向下一個結(jié)點，j累加1；
若到鏈表末尾p為空，則說明第i個元素不存在；
否則查找成功，將欲刪除結(jié)點p->next賦值給q；
單鏈表的刪除標準語句p->next = q->next；
將q結(jié)點中的數(shù)據(jù)賦值給e，作為返回；
釋放q結(jié)點。
?
效率PK
?
我們最后的環(huán)節(jié)是效率PK，我們發(fā)現(xiàn)無論是單鏈表插入還是刪除算法，它們其實都是由兩個部分組成：第一部分就是遍歷查找第i個元素，第二部分就是實現(xiàn)插入和刪除元素。
從整個算法來說，我們很容易可以推出它們的時間復雜度都是O(n)。
?
再詳細點分析：如果在我們不知道第i個元素的指針位置，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線性表的順序存儲結(jié)構(gòu)是沒有太大優(yōu)勢的。
但如果，我們希望從第i個位置開始，插入連續(xù)10個元素，對于順序存儲結(jié)構(gòu)意味著，每一次插入都需要移動n-i個位置，所以每次都是O(n)。
?
而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O(n)，接下來只是簡單地通過賦值移動指針而已，時間復雜度都是O(1)。
顯然，對于插入或刪除數(shù)據(jù)越頻繁的操作，單鏈表的效率優(yōu)勢就越是明顯啦~
?三：單鏈表的頭插法和尾插法：指當鏈表新增一個節(jié)點是插入到每一個之前還是之后。 ?頭插法是插入到第一個節(jié)點（有可能是頭結(jié)點，也有可能是首節(jié)點）之前，尾插法是插入到最后一個節(jié)點之后。 頭插法是新增節(jié)點總是插在頭部，以帶頭節(jié)點鏈表為例，鏈表頭指針是Head，新增節(jié)點p，則： p->next=Head->next; Head->next=p 如果是不帶頭結(jié)點的鏈表對應： p->next=Head; Head=p; 而尾插法是將新增節(jié)點插在鏈表尾部 for(t=Head;t->next;t=t->next); ? ? ? ? ? ? ? ? ? ? ? ? ? //結(jié)束時t指向尾節(jié)點 p->next=NULL; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//進行插入 t->next=p; ?轉(zhuǎn)載于:https://www.cnblogs.com/wycBlog/p/7145931.html
總結(jié)
以上是生活随笔為你收集整理的【数据结构链表】之五单链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 动态代理案例1:运用Proxy动态代理来
- 下一篇： Spring3+ibatis (SQL