1、線性表的鏈式存儲結構
1.1啊楚、線性表鏈式存儲結構定義
線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素雨涛，這組存儲單元可以是連續(xù)的例驹，也可以是不連續(xù)的欧漱。這就意味著，這些元素可以存在內(nèi)存未被占用的任意位置膏孟。
以前在順序結構中眯分，每個元素數(shù)據(jù)只需要存儲數(shù)據(jù)元素信息就可以了。現(xiàn)在在鏈式結構中柒桑，除了要存數(shù)據(jù)元素信息外弊决，還要存儲它的后繼元素的存儲地址。
因此幕垦，為了表示每個數(shù)據(jù)元素ai與其直接后級元素ai+1之間的邏輯關系，對數(shù)據(jù)元素ai來說傅联，除了存儲其本身的信息之外先改，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域蒸走，把存儲直接后繼位置的域稱為指針域仇奶。指針域中存儲的信息稱作指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像比驻，稱為結點(Node)该溯。
n個結點(ai的存儲映像)鏈結成一個鏈表，即為線性表(a1,a2,….,an)的鏈式存儲結構别惦，因為此鏈表的每個結點中只包含一個指針域狈茉，所以叫做單鏈表。單鏈表正是通過每個結點的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起掸掸。
對于線性表來說氯庆，總得有個頭有個尾蹭秋，鏈表也不例外。我們把鏈表中第一個結點的存儲位置叫做頭指針堤撵，那么整個鏈表的存取就必須是從頭指針開始進行了仁讨。之后的每一個結點，其實就是上一個的后繼指針指向的位置实昨。
最后一個洞豁，當然意味著直接后繼不存在了，所以我們規(guī)定荒给，線性鏈表的最后一個結點指針為“空”（通常用NULL或“^”符號表示）丈挟。
有時，我們?yōu)榱烁臃奖愕貙︽湵磉M行操作锐墙，會在單鏈表的第一個結點前附設一個結點礁哄，稱為頭結點。頭結點的數(shù)據(jù)域可以不存儲任何信息溪北，也可以存儲如線性表的長度等附加信息桐绒，頭結點的指針域存儲指向第一個結點的指針。
1.2之拨、頭指針與頭結點的異同
頭指針與頭結點的異同點茉继。
頭指針 :
頭指針是指鏈表指向第一個結點的指針，若鏈表有頭結點蚀乔，則是指向頭結點的指針
頭指針具有標識作用烁竭，所以常用頭指針冠以鏈表的名字
無論鏈表是否為空，頭指針均不為空吉挣。頭指針是鏈表的必要元素派撕。
頭結點
頭結點是為了操作的統(tǒng)一和方便而設立的，放在第一元素的結點之間睬魂，其數(shù)據(jù)域一般無意義终吼。
有了頭結點，對在第一元素結點前插入結點氯哮，其操作與其它結點的操作就統(tǒng)一了际跪。
頭結點不一定是鏈表必須要素。
1.3喉钢、線性鏈表式存儲結構代碼描述
若線性鏈表為空表姆打，則頭結點的指針域為“空”。
單鏈表中肠虽，我們在C語言中可用結構指針來描述幔戏。
//線性表的單鏈表存儲結構
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;//定義LinkList
在這個結構定義中，我們也就知道税课，結點由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結點地址的指針域組成评抚。 假設p是指向線性表第i個元素的指針豹缀，則該結點ai的數(shù)據(jù)域我們可以用p->data來表示，p->data的值是一個數(shù)據(jù)元素慨代，結點ai的指針可以用p->next來表示邢笙，p->next的值是一個指針。p->next指向誰呢侍匙？當然是指向第i + 1個元素氮惯，即指向ai+1。也就是說p->data = ai想暗，那么p->next->data=ai+1
2妇汗、單鏈表的讀取
在線性表的順序存儲結構中，我們要計算任意一個元素的存儲位置使很容易的说莫。但在單鏈表中杨箭，由于第i個元素到底在哪？沒辦法一開始就知道储狭，必須從頭開始找互婿。因此，對于單鏈表實現(xiàn)獲取第i個元素的操作GetElem辽狈，在算法上慈参，相對麻煩一些。
獲得鏈表第i個數(shù)據(jù)的算法思路：
- 聲明一個指針p指向鏈表第一個結點刮萌，初始化j從1開始驮配。
- 當j < i 時，就遍歷鏈表着茸，讓p的指針向后移動壮锻，不斷指向下一結點，j累加1;
- 若鏈表末尾p為空涮阔，則說明第i個結點不存在猜绣；
- 否則查找成功，返回結點p的數(shù)據(jù)澎语。
實現(xiàn)代碼如下：
//初始條件:順序線性表L已存在,1 ≤ i ≤ ListLength(L)
//操作結果:用e返回L中第i個數(shù)據(jù)元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;//聲明一指針
p = L->next;//讓p指向鏈表L的第一個結點
j = 1;//j為計數(shù)器
while(p && j < i)//p不為空且計數(shù)器j還沒有等于i時途事，循環(huán)繼續(xù)
{
p = p->next;//讓p指向下也結點
++j;
}
if(p || j > i)
return ERROR;//第i個結點不存在
*e = p->data;//取第i個結點的數(shù)據(jù)
return OK;
}
說白了验懊，就是從頭開始找擅羞，直到第i個結點為止。
由于這個算法復雜度取決于i的位置义图，當i = 1時减俏，不需要變量，而當i = n時則遍歷n - 1次才可以碱工。因此最壞情況的時間復雜度是O(n)娃承。
由于單鏈表的結構沒有定義表長奏夫，所以不知道事先循環(huán)多少次，因此也就不方便使用for來控制循環(huán)历筝。
其主要核心思想是“工作指針后移”酗昼，這其實也是很多算法常用技術。
3梳猪、單鏈表的插入與刪除
3.1麻削、單鏈表的插入
假設存儲元素e的結點為s，要實現(xiàn)結點p春弥、p->next和s之間的邏輯關系的變化呛哟，只需要將s插到結點p和p->next之間即可。
根本不需要驚動其他結點匿沛，只需要讓s->next和p->next的指針做一點改變扫责。
單鏈表第i個數(shù)據(jù)插入結點的算法思路：
- 聲明一指針p指向鏈表頭結點，初始化j從1開始;
- 當j < i時逃呼，就遍歷鏈表鳖孤，讓p的指針向后移動，不斷指向下一結點,j累加1
- 若到鏈表末尾p為空蜘渣，則說明第i個結點不存在;
- 若查找成功淌铐，在系統(tǒng)中生成一個空節(jié)點s；
- 將數(shù)據(jù)元素e賦給s->data蔫缸；
- 單鏈表的插入標準語句s->next = p->next; p->next = s;
- 返回成功
實現(xiàn)代碼如下：
//初始條件:順序線性表L已存在,1≤i≤ListLength(L)
//操作結果:在L中第i個結點位置之前插入新的數(shù)據(jù)元素,L的長度加1
Status ListInsert(LinkList *L , int i , ElemType e)
{
int j = 1;
LinkList p,s;
p = *L;
while( p && j < i) //尋找第i個結點
{
p = p->next;
++j;
}
if( !p || j > i)
{
return ERROR;//第i個結點不存在
}
s = (LinkList)malloc(sizeof(Node));//生成新結點
s->data = e;
s->next = p->next;//將p的后繼結點賦值給s的后繼
p->next = s;//將s賦給p的后繼
return OK;
}
在這段算法代碼中腿准，我們用到了C語言的malloc標準函數(shù)，它的作用就是生成一個新的結點拾碌，其類型與Node是一樣的吐葱，其實質(zhì)就是在內(nèi)存中開辟了一段空間，用了存放數(shù)據(jù)e的s結點校翔。
注意：下面兩句不可交換順序(否則死循環(huán))
s->next = p->next;
p->next = s;
3.2弟跑、單鏈表的刪除
設存儲元素ai的結點為q，要實現(xiàn)將結點q刪除單鏈表的操作防症，其實就是將它的前繼結點的指針繞過孟辑，指向他的后繼結點即可。
我們所要做的蔫敲，實際上就是一步：
p->next = p->next->next;
用q來取代p->next即是：
q = p->next;
p->next = q->next;
也就是說把p的后繼結點改成p的后繼的后繼結點饲嗽。
單鏈表第i個數(shù)據(jù)刪除結點的算法思路：
- 聲明一指針p指向鏈表頭指針，初始化j從1開始奈嘿；
- 當j < i時貌虾，就遍歷鏈表，讓p的指針向后移動裙犹，不斷指向下一個結點尽狠，i累加1衔憨；
- 若到鏈表末尾p為空，則說明第i個結點不存在袄膏；
- 否則查找成功践图，將欲刪除的結點p->next 賦給q；
- 單鏈表的刪除標準與p->next = q->next沉馆；
- 將q結點中的數(shù)據(jù)賦給e平项，作為返回;
- 釋放q結點
- 返回成功
實現(xiàn)代碼如下：
/初始條件:順序線性表L已存在,1≤ i ≤ListLength(L)
//操作結果:刪除L的i個結點,并用e返回其值,L的長度減1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j=1;
Link p,q;
p = *L;
while(p->next && j < i)//遍歷尋找第i - 1個結點
{
p = p->next;
++j;
}
if( !(p->next) || j > i)//列表末端或找不到
return ERROR;
q = p->next;
p->next = q->next;//將q的后繼賦給p的后繼
*e = q->data;//將q結點中的數(shù)據(jù)給e
free(q);//讓系統(tǒng)回收此結點，釋放內(nèi)存
return OK;
}
分析一下剛才我們講解的單鏈表插入和刪除算法悍及，我們發(fā)現(xiàn)闽瓢，它們其實都是由兩部分組成：
第一部分就是遍歷查找第i個結點；
第二部分就是插入和刪除結點心赶。
從整個算法來說扣讼，我們很容易推導出：它們的時間復雜度都是O(n)。
如果我們不知道第i個結點的指針位置缨叫，單鏈表數(shù)據(jù)結構在插入和刪除操作上椭符，與線下順序存儲結構是沒有太大優(yōu)勢的。但如果耻姥，我們希望從第i個位置销钝，插入10個結點，對于順序結構意味著琐簇，每次都要移動n - i個結點蒸健，每次都是O(n)。而單鏈表婉商，我們只需在第一次時似忧，找到第i個位置的指針，此時為O(n)丈秩，接下來只是簡單地通過賦值移動指針而已盯捌，事件復雜度為O(1)。
顯然蘑秽，對于插入和刪除數(shù)據(jù)越頻繁的操作饺著，單鏈表的優(yōu)勢就越明顯。
4肠牲、單鏈表的整表創(chuàng)建
順序存儲結構的創(chuàng)建幼衰，其實就是一個數(shù)組的初始化，即聲明一個類型和大小的數(shù)組并賦值的過程埂材。而單鏈表和順序存儲結構就不一樣塑顺，它不像順序存儲結構這么幾種汤求，它可以很散俏险，是一種動態(tài)結構严拒。對于每個鏈表來說，它所占用空間的大小和位置使不需要預先分配劃定的竖独，可以根據(jù)系統(tǒng)的情況和實際的需求即可生成裤唠。
4.1、頭插法建立單鏈表
所以創(chuàng)建單鏈表的過程就是一個動態(tài)生成鏈表的過程莹痢。即從“空表”的初始狀態(tài)起种蘸，一次建立各元素結點，并逐個插入鏈表竞膳。
單鏈表整表創(chuàng)建的思路算法：
- 聲明一指針p和計數(shù)器變量1航瞭；
- 初始化一空鏈表；
- 讓L的頭結點的指針指向NULL坦辟，即建立一個帶頭結點的單鏈表刊侯；
- 循環(huán)：
(1).生成一新結點賦值給p;
(2).隨機生成一數(shù)字賦給p的數(shù)據(jù)域p->data;
(3).將p插到頭結點與前一個新節(jié)點之間的位置。
實現(xiàn)代碼如下：
//隨機產(chǎn)生n個元素的值锉走，建立帶表頭結點的單鏈表線性表L(頭插法)
void CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0));//初始化隨機數(shù)種子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;//先建立一個帶頭結點的單鏈表
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizoef(Node));//生成新的結點
p->data = rand() % 100 + 1;//隨機生成100以內(nèi)的數(shù)字
p->next = (*L)->next;
(*L)->next = p; //插入到表頭
}
}
4.2滨彻、尾插法建立單鏈表
可事實上，根據(jù)排隊時的正常思維挪蹭，我們還可以把新結點放在最后亭饵。我們每次新結點都插在終端結點的后面，這種算法稱之為尾插法梁厉。
實現(xiàn)代碼如下：
//隨機產(chǎn)生n個元素的值,建立帶表頭結點的單鏈線性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
LinkList p,r;
int i;
srand(time(0));//初始化隨機數(shù)種子
*L = (LinkList)malloc(sizeof(Node));//為整個線性表
r = *L;//r為指向尾部的結點
for(i = 0;i < n;i++)
{
p = (Node *)malloc(sizeof(Node));//生成新結點
p->data = rand() % 100 + 1;//隨機生成100以內(nèi)的數(shù)字
r->next = p;//將表尾終端結點的指針指向新結點
r = p; //就那個當前新結點定義為表尾終端結點
}
r->next = NULL;//表示當前鏈表結束
}
注意：
L與r的關系辜羊，L指整個單鏈表，而r指向尾節(jié)點的變量词顾，r會隨著循環(huán)不斷地變化結點只冻，而L則是隨著循環(huán)增長為一個多結點的鏈表。
r->next = p的意思计技，其實就是將剛才的表尾終端結點r的指針指向新結點p喜德。
5、單鏈表的整表刪除
當我們不打算使用這個單鏈表時垮媒，我們需要把它銷毀舍悯，其實也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用睡雇。
單鏈表整表刪除的算法思路如下：
- 聲明一結點p和q萌衬；
- 將第一個結點賦值給p；
- 循環(huán) :
(1).將下一結點賦值給q;
(2).釋放p;
(3).將q賦值給p它抱。
實現(xiàn)代碼如下：
//初始條件:順序線性表L已經(jīng)存在秕豫，操作結果：將L重置為空表
Status ClearList(LinkList *L)
{
LinkList p,q;
p = (*L)->next;//p指向第一個結點
while(p)//沒到表尾
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;//頭結點指針域為空
return OK;
}
6、單鏈表結構與順序存儲結構優(yōu)缺點
簡單地對單鏈表結構和順序存儲結構作對比。
6.1混移、存儲分配方式：
順序存儲結構有一段連續(xù)的存儲單元依然存儲線性表的數(shù)據(jù)元素祠墅。
單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的玩意歌径。
6.2毁嗦、時間性能：
查找：
- 順序存儲結構O(1)
- 單鏈表O(n)
插入與刪除
- 順序存儲結構需要平均移動表長一半的元素，時間為O(n)
- 單鏈表在線出某位置的指針后回铛，插入和刪除時間僅為O(1)
6.3狗准、空間性能
- 順序存儲結構需要預分配存儲空間，分大了茵肃，浪費腔长，分小了易發(fā)生上溢。
- 單鏈表不需要分配存儲空間验残，只要有就可以分配饼酿，元素個數(shù)也不受限制。
通過上面的對比胚膊，我們可以得出一些經(jīng)驗性的結論：
若線性表需要頻繁查找故俐，很少進入插入和刪除操作時，宜采用順序存儲結構紊婉。
若需要頻繁插入和刪除時药版，宜采用單鏈表結構。
比如游戲開發(fā)中喻犁，對于用戶注冊的個人信息槽片，除了注冊時插入數(shù)據(jù)外，絕大多數(shù)情況下都是讀取肢础，所以應該考慮用順序存儲結構还栓。而游戲中的玩家的武器或者裝備列表，隨著玩家游戲過程中传轰，可能隨時增加或刪除剩盒，此時應該用單鏈表比較合適。當然慨蛙，這只是簡單地類比×闪模現(xiàn)實生活中的軟件開發(fā)，要考慮的問題會復雜得多期贫。當線性表中的元素個數(shù)變化較大或者根本不知道有多大時跟匆，最好用單鏈表結構，這樣可以不用考慮存儲空間大小問題通砍。
而如果事先知道線性表的大致長度玛臂，比如一年12個月，這種用順序存儲結構效率會高很多。
總之迹冤，線性表的順序存儲結構和單鏈表結構各有其優(yōu)點讽营，不是簡單地說哪個不好，需要根據(jù)實際情況叁巨，來綜合平衡采用哪種數(shù)據(jù)更能滿足和達到需求和性能。
特別感謝：
魚C工作室小甲魚
