線性表--鏈?zhǔn)酱鎯Y(jié)構(gòu)--單鏈表
一、定義
1.特點(diǎn)：
- 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以存在內(nèi)存中未被占用的任意位置。
- 比起順序存儲結(jié)構(gòu)每個數(shù)據(jù)元素只需要存儲一個位置就可以了〈亟粒現(xiàn)在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，除了要存儲數(shù)據(jù)元素信息外软吐，還要存儲它的后繼元素的存儲地址（指針）瘩将。
- 也就是說除了存儲其本身的信息外，還需存儲一個指示其直接后繼的存儲位置的信息凹耙。
2.定義：
- 我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域姿现，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈肖抱。這兩部分信息組成數(shù)據(jù)元素稱為存儲映像备典，稱為結(jié)點(diǎn)(Node)。
- n個結(jié)點(diǎn)鏈接成一個鏈表虐沥，即為線性表(a1, a2, a3, …, an)的鏈?zhǔn)酱鎯Y(jié)構(gòu)熊经。
- 因?yàn)榇随湵淼拿總€結(jié)點(diǎn)中只包含一個指針域泽艘，所以叫做單鏈表欲险。
我們把鏈表中的第一個結(jié)點(diǎn)的存儲位置叫做頭指針镐依，最后一個結(jié)點(diǎn)指針為空(NULL)。
頭結(jié)點(diǎn)的數(shù)據(jù)域一般不存儲任何信息
3.頭指針與頭結(jié)點(diǎn)的異同
頭指針
- 頭指針是指鏈表指向第一個結(jié)點(diǎn)的指針天试，若鏈表有頭結(jié)點(diǎn)槐壳，則是指向頭結(jié)點(diǎn)的指針。
- 頭指針具有標(biāo)識作用喜每，所以常用頭指針冠以鏈表的名字（指針變量的名字）务唐。
- 無論鏈表是否為空，頭指針均不為空带兜。
- 頭指針是鏈表的必要元素枫笛。
頭結(jié)點(diǎn)
- 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一個元素的結(jié)點(diǎn)之前刚照，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）刑巧。
- 有了頭結(jié)點(diǎn)，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)起操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了无畔。
- 頭結(jié)點(diǎn)不一定是鏈表的必須要素啊楚。
二、單鏈表存儲結(jié)構(gòu)
C語言中可以用結(jié)構(gòu)指針來描述單鏈表：
typedef struct Node
{
ElemType data; // 數(shù)據(jù)域
struct Node* Next; // 指針域
} Node;
typedef struct Node* LinkList;
結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成浑彰。
例1：假設(shè)p是指向線性表第i個元素的指針恭理，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data的值是一個數(shù)據(jù)元素，結(jié)點(diǎn)ai的指針域可以用p->next來表示郭变，p->next的值是一個指針颜价。
那么p->next指向第i+1個元素。也就是指向ai+1的指針诉濒。
例2：如果p->data = ai周伦，那么p->next->data = ?
p->next->data = ai+1。
三循诉、單鏈表的操作--讀取横辆、插入和刪除
1.讀取
對于單鏈表實(shí)現(xiàn)獲取第i個元素的數(shù)據(jù)的操作GetElem，在算法上相對要麻煩一些：
獲得鏈表第i個數(shù)據(jù)的算法思路：
- 聲明一個結(jié)點(diǎn)p指向鏈表第一個結(jié)點(diǎn)茄猫，初始化j從1開始狈蚤；
- 當(dāng)j<i時，就遍歷鏈表划纽，讓p的指針向后移動脆侮，不斷指向一下結(jié)點(diǎn)，j+1勇劣；
- 若到鏈表末尾p為空靖避，則說明第i個元素不存在潭枣；
- 否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)幻捏。
使用代碼實(shí)現(xiàn)GetElem.c：
/* 初始條件：順序線性表L已存在盆犁，1<=i<=ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值 */
Status GetElem( LinkList L, int i, ElemType *e )
{
int j;
LinkList p;
p = L->next;
j = 1;
while( p && j<i )
{
p = p->next;
++j;
}
if( !p || j>i )
{
return ERROR;
}
*e = p->data;
return OK;
}
就是從頭開始找，直到第i個元素為止：
- 由于這個算法的時間復(fù)雜度取決于i的位置篡九，當(dāng)i=1時谐岁，則不需要遍歷，而i=n時則遍歷n-1次才可以榛臼。因此最壞情況的時間復(fù)雜度為O(n)伊佃。
- 由于單鏈表的結(jié)構(gòu)中沒有定義表長，所以不能實(shí)現(xiàn)知道要循環(huán)多少次沛善，因此也就不方便使用for來控制循環(huán)航揉。
- 其核心思想叫做“工作指針后移”，這其實(shí)也是很多算法的常用技術(shù)金刁。
2.插入
單鏈表的插入：假設(shè)存儲元素e的結(jié)點(diǎn)為s帅涂，要實(shí)現(xiàn)結(jié)點(diǎn)p、p->next和s之間邏輯關(guān)系的變化胀葱，如圖：
要將結(jié)點(diǎn)s插入到ai和ai+1之間漠秋，只需要讓s->next和p->next的指針做一點(diǎn)改變。
s->next = p->next;
p->next = s;
如圖：
這兩句代碼的順序可不可以交換過來抵屿？
先p->next = s;
再s->next = p->next;
如果先執(zhí)行p->next的話會先被覆蓋為s的地址庆锦，那么s->next = p->next其實(shí)就等于s->next = s了。
所以這兩句是無論如何不能弄反的轧葛。
單鏈表第i個數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：
- 聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn)搂抒，初始化j從1開始；
- 當(dāng)j<1時尿扯，就遍歷鏈表求晶，讓p的指針向后移動，不斷指向下一結(jié)點(diǎn)衷笋，j累加1芳杏；
- 若到鏈表末尾p為空，則說明第i個元素不存在辟宗；
- 否則查找成功爵赵，在系統(tǒng)中生成一個空結(jié)點(diǎn)s；
- 將數(shù)據(jù)元素e賦值給s->data泊脐；
- 單鏈表的插入剛才兩個標(biāo)準(zhǔn)語句空幻；
- 返回成功。
代碼實(shí)現(xiàn)：
/* 初始條件：順序線性表L已存在容客，1<=i<=ListLength(L) */
/* 操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e秕铛，L的長度加1 */
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
j = 1;
while( p && j<i ) // 用于尋找第i個結(jié)點(diǎn)
{
p = p->next;
j++;
}
if( !p || j>i )
{
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
3.刪除
假設(shè)元素a2的結(jié)點(diǎn)為q约郁，要實(shí)現(xiàn)結(jié)點(diǎn)q刪除單鏈表的操作，其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過指向后繼結(jié)點(diǎn)即可但两。
那我們所要做的鬓梅，實(shí)際上就是一步：
可以這樣：p->next = p->next->next;
也可以是：q=p->next; p->next=q->next;
單鏈表第i個數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：
- 聲明結(jié)點(diǎn)p指向鏈表第一個結(jié)點(diǎn)，初始化j=1镜遣；
- 當(dāng)j<1時己肮，就遍歷鏈表士袄，讓P的指針向后移動悲关，不斷指向下一個結(jié)點(diǎn)，j累加1娄柳；
- 若到鏈表末尾p為空寓辱，則說明第i個元素不存在；
- 否則查找成功赤拒，將欲刪除結(jié)點(diǎn)p->next賦值給q秫筏；
- 單鏈表的刪除標(biāo)準(zhǔn)語句p->next = q->next；
- 將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e挎挖，作為返回这敬；
- 釋放q結(jié)點(diǎn)。
代碼實(shí)現(xiàn)：
/* 初始條件：順序線性表L已存在蕉朵，1<=i<=ListLength(L) */
/* 操作結(jié)果：刪除L的第i個數(shù)據(jù)元素崔涂，并用e返回其值，L的長度-1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while( p->next && j<i )
{
p = p->next;
++j;
}
if( !(p->next) || j>i )
{
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
效率問題：
無論是單鏈表插入還是刪除算法始衅，它們其實(shí)都是由兩個部分組成：
第一部分就是遍歷查找第i個元素冷蚂，
第二部分就是實(shí)現(xiàn)插入和刪除元素。
它們的時間復(fù)雜度都是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)调卑，接下來只是簡單地通過賦值移動指針而已抡砂，時間復(fù)雜度都是O(1)。
- 顯然恬涧，對于插入或刪除數(shù)據(jù)越頻繁的操作注益，單鏈表的效率優(yōu)勢就越是明顯
四、單鏈表的整表創(chuàng)建
單鏈表的存儲結(jié)構(gòu)溯捆，它的數(shù)據(jù)可以是分散在內(nèi)存各個角落的丑搔，他的增長也是動態(tài)的。對于每個鏈表來說提揍，它所占用空間的大小和位置是不需要預(yù)先分配劃定的啤月，可以根據(jù)系統(tǒng)的情況和實(shí)際的需求即時生成。
單鏈表的整表創(chuàng)建：
創(chuàng)建單鏈表的過程是一個動態(tài)生成鏈表的過程劳跃，從“空表”的初始狀態(tài)起谎仲，依次建立各元素結(jié)點(diǎn)并逐個插入鏈表。
單鏈表整表創(chuàng)建的算法思路如下：
- 聲明一結(jié)點(diǎn)p和計數(shù)器變量i；
- 初始化一空鏈表L；
- 讓L的頭結(jié)點(diǎn)的指針指向NULL疫鹊，即建立一個帶頭結(jié)點(diǎn)的單鏈表；
- 循環(huán)實(shí)現(xiàn)后繼結(jié)點(diǎn)的賦值和插入辙诞。
①頭插法建立單鏈表
頭插法從一個空表開始，生成新結(jié)點(diǎn)轻抱，讀取數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中飞涂，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到結(jié)束為止十拣。
就是把新加進(jìn)的元素放在表頭后的第一個位置：
- 先讓新節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)之后
- 然后讓表頭的next指向新節(jié)點(diǎn)
代碼實(shí)現(xiàn)：
/* 頭插法建立單鏈表示例 */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); // 初始化隨機(jī)數(shù)種子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for( i=0; i < n; i++ )
{
p = (LinkList)malloc(sizeof(Node)); // 生成新結(jié)點(diǎn)
p->data = rand()%100+1;
p->next = (*L)->next;
(*L)->next = p;
}
}
②尾插法建立單鏈表
頭插法建立鏈表雖然算法簡單封拧，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。
我們可以把思維逆過來：把新結(jié)點(diǎn)都插入到最后夭问，這種算法稱之為尾插法泽西。
代碼實(shí)現(xiàn)：
/* 尾插法建立單鏈表演示 */
void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for( i=0; i < n; i++ )
{
p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->next = p;
r = p; //
}
r->next = NULL;
}
五、單鏈表的整表刪除
當(dāng)我們不打算使用這個單鏈表時缰趋，我們需要把它銷毀捧杉；其實(shí)也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用秘血。
單鏈表整表刪除的算法思路如下：
- 聲明結(jié)點(diǎn)p和q味抖；
- 將第一個結(jié)點(diǎn)賦值給p，下一結(jié)點(diǎn)賦值給q灰粮；
- 循環(huán)執(zhí)行釋放p和將q賦值給p的操作仔涩；
代碼實(shí)現(xiàn)：
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
這段算法代碼里，常見的錯誤就是有同學(xué)會覺得q變量沒有存在的必要粘舟，只需要在循環(huán)體內(nèi)直接寫free(p); p = p->next; 即可熔脂？
p是一個結(jié)點(diǎn)佩研，它除了有數(shù)據(jù)域，還有指針域霞揉。當(dāng)我們做free(p);時旬薯，其實(shí)是對它整個結(jié)點(diǎn)進(jìn)行刪除和內(nèi)存釋放的工作。而我們整表刪除是需要一個個結(jié)點(diǎn)刪除的适秩，所以我們就需要q來記載p的下一個結(jié)點(diǎn)绊序。
六、單鏈表結(jié)構(gòu)與順序存儲結(jié)構(gòu)優(yōu)缺點(diǎn)
分別從存儲分配方式秽荞、時間性能骤公、空間性能三方面來做對比：
1.存儲分配方式：
- 順序存儲結(jié)構(gòu)用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
- 單鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)蚂会，用一組任意的存儲單元存放線性表的元素淋样。
2.時間性能：
查找：
- 順序存儲結(jié)構(gòu)O(1)
- 單鏈表O(n)
插入和刪除：
- 順序存儲結(jié)構(gòu)需要平均移動表長一半的元素，時間為O(n)
- 單鏈表在計算出某位置的指針后胁住，插入和刪除時間僅為O(1)
3.空間性能：
- 順序存儲結(jié)構(gòu)需要預(yù)分配存儲空間，分大了刊咳，容易造成空間浪費(fèi)彪见，分小了，容易發(fā)生溢出娱挨。
- 單鏈表不需要分配存儲空間余指，只要有就可以分配，元素個數(shù)也不受限制跷坝。
結(jié)論：
- 若線性表需要頻繁查找酵镜，很少進(jìn)行插入和刪除操作時，宜采用順序存儲結(jié)構(gòu)柴钻。
- 若需要頻繁插入和刪除時淮韭，宜采用單鏈表結(jié)構(gòu)。
- 比如說游戲開發(fā)中贴届，對于用戶注冊的個人信息靠粪，除了注冊時插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取毫蚓，所以應(yīng)該考慮用順序存儲結(jié)構(gòu)占键。
- 而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過程中元潘，可能會隨時增加或刪除畔乙，此時再用順序存儲就不太合適了，單鏈表結(jié)構(gòu)就可以大展拳腳了翩概。
- 當(dāng)線性表中的元素個數(shù)變化較大或者根本不知道有多大時牲距，最好用單鏈表結(jié)構(gòu)袖订，這樣可以不需要考慮存儲空間的大小問題。
- 而如果事先知道線性表的大致長度嗅虏，比如一年12個月洛姑，一周就是星期一至星期日共七天，這種用順序存儲結(jié)構(gòu)效率會高很多皮服。
總之楞艾，線性表的順序存儲結(jié)構(gòu)和單鏈表結(jié)構(gòu)各有其優(yōu)缺點(diǎn)，不能簡單的說哪個好龄广，哪個不好硫眯，需要根據(jù)實(shí)際情況，來綜合平衡采用哪種數(shù)據(jù)結(jié)構(gòu)更能滿足和達(dá)到需求和性能择同。
