順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法
通過(guò) 線性表之?dāng)?shù)組 這篇文章的介紹撑毛，我們知道線性表的順序存儲(chǔ)是有缺點(diǎn)的书聚，最大的缺點(diǎn)就是 插入、刪除時(shí)需要移動(dòng)大量元素藻雌，對(duì)于像數(shù)組這樣在編程中常用的數(shù)據(jù)結(jié)構(gòu)顯然會(huì)產(chǎn)生很低的效率雌续，那么有什么比較好的方法解決嗎?
俗話說(shuō) 解鈴還須系鈴人，要想解決這個(gè)問(wèn)題胯杭，我們必須要了解產(chǎn)生這個(gè)問(wèn)題的原因
為什么當(dāng)插入驯杜、刪除時(shí)需要移動(dòng)大量元素，仔細(xì)分析后我們發(fā)現(xiàn)除了頭做个、尾元素其他每?jī)蓚€(gè)相鄰元素之間沒(méi)有空隙鸽心，因?yàn)榫€性表的順序存儲(chǔ)內(nèi)存地址是連續(xù)的，所以就沒(méi)辦法快速的插入居暖，而當(dāng)刪除后顽频，當(dāng)中就會(huì)留有空隙，自然就需要彌補(bǔ)太闺，這就是問(wèn)題所在糯景。
聰明的計(jì)算機(jī)大師們?cè)鐬槲覀兲峁┝艘粋€(gè)很好的解題思路：如果要不想在插入、刪除時(shí)移動(dòng)大量元素省骂，那么我們就讓每?jī)蓚€(gè)相鄰元素之間留有 足夠多的空間蟀淮，那么這個(gè)足夠多的空間是多少呢?足夠多那肯定不會(huì)再是一個(gè)固定的值，既然這樣我們就干脆不再考慮相鄰位置了钞澳，哪里有空位就到哪里怠惶，只需要讓每個(gè)元素知道它的下一個(gè)元素在哪里，這樣略贮，我們可以在第一個(gè)元素時(shí)甚疟，就能知道第二個(gè)元素的位置(內(nèi)存地址)仗岖，而找到它；在第二個(gè)元素時(shí)览妖，再找到第三個(gè)元素的位置(內(nèi)存地址)轧拄。這樣所有的元素我們就能通過(guò)遍歷找到了
線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的讽膏，也可以是不連續(xù)的檩电。這就意味著這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置
以前在線性表的順序存儲(chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素只需要存儲(chǔ)數(shù)據(jù)元素信息就可以了「鳎現(xiàn)在在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中俐末，除了要存儲(chǔ)數(shù)據(jù)元素信息外，還要存儲(chǔ)它直接后繼元素的內(nèi)存地址
因此奄侠，為了表示每個(gè)數(shù)據(jù)元素 ai 和它直接后繼元素 ai + 1 的邏輯關(guān)系,對(duì)于數(shù)據(jù)元素 ai 除了要存儲(chǔ)它自身的數(shù)據(jù)信息外卓箫，還要存儲(chǔ)其直接后繼元素的內(nèi)存地址。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為 數(shù)據(jù)域垄潮，存儲(chǔ)其直接后繼元素內(nèi)存地址的域稱為 指針域烹卒。指針域中存儲(chǔ)的信息稱為 指針或鏈。這兩部分信息組成數(shù)據(jù)元素 ai 的存儲(chǔ)映像弯洗，稱為 結(jié)點(diǎn)(node)
n 個(gè)結(jié)點(diǎn)(數(shù)據(jù)元素 ai 的存儲(chǔ)映像)鏈接成一個(gè)鏈表旅急，即為線性表(a1、a2牡整、a3......ai)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)藐吮，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)只包含一個(gè)指針域，所以叫做 單鏈表逃贝。單鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按照其邏輯次序鏈接在一起谣辞，如下圖：
我們把鏈表中第一個(gè)結(jié)點(diǎn)的內(nèi)存地址稱為 頭指針，整個(gè)鏈表的存取就必須從頭指針開始進(jìn)行了秋泳，之后的每一個(gè)結(jié)點(diǎn)其實(shí)就是上一個(gè)結(jié)點(diǎn)指針域中存儲(chǔ)的指針指向的位置潦闲，而對(duì)于鏈表中的最后一個(gè)結(jié)點(diǎn)是沒(méi)有后繼元素的攒菠，所以我們規(guī)定迫皱，線性表的最后一個(gè)結(jié)點(diǎn)指針為 空(通常用 NULL 或者 ^ 符號(hào)表示)
有時(shí)候?yàn)榱烁臃奖銓?duì)鏈表進(jìn)行操作，我們會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)辖众，稱為 頭結(jié)點(diǎn)卓起。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何數(shù)據(jù)元素信息，但是也可以存儲(chǔ)線性表的長(zhǎng)度等附加信息凹炸，頭結(jié)點(diǎn)的指針域存儲(chǔ)的指針是第一個(gè)結(jié)點(diǎn)的內(nèi)存地址
注意：如果單鏈表是空表戏阅，那么頭結(jié)點(diǎn)的指針域?yàn)?空
線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意
我們一般使用如下示意圖表示單鏈表的存儲(chǔ)結(jié)構(gòu)：
若帶有頭結(jié)點(diǎn)的單鏈表則使用如下圖表示：
空鏈表使用如下圖表示：
根據(jù)前面的介紹我們知道 結(jié)點(diǎn)(node)是由存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域和存放其直接后繼結(jié)點(diǎn)內(nèi)存地址的指針域兩部分組成。 假設(shè) p 是指向單鏈表中第 i 個(gè)元素的指針啤它，則該結(jié)點(diǎn) ai 的數(shù)據(jù)域我們可以用 p->data 來(lái)表示奕筐，p->data 的值是一個(gè)數(shù)據(jù)元素舱痘，結(jié)點(diǎn) ai 的指針域可以用 p->next 表示，p->next 的值是一個(gè)指針离赫。p->next 指向誰(shuí)呢?當(dāng)然是指向第 i + 1 個(gè)元素芭逝，即指向 ai + 1 的指針。也就是說(shuō) p->data = ai渊胸，p->next->data = ai + 1旬盯，如下圖所示：
在 C 語(yǔ)言中可用結(jié)構(gòu)體指針來(lái)描述單鏈表：
typedef struct node
{
ElemType data;
struct node *next;
}Node,LinkList;
從這個(gè)結(jié)構(gòu)定義中更能清晰的看出，結(jié)點(diǎn)是由存放數(shù)據(jù)元素的數(shù)據(jù)域與存放后繼結(jié)點(diǎn)地址的指針域組成
單鏈表的讀取
在線性表的順序存儲(chǔ)結(jié)構(gòu)中翎猛，我們要想計(jì)算任意一個(gè)元素的內(nèi)存地址是很容易的胖翰，因?yàn)榫€性表的順序存儲(chǔ)結(jié)構(gòu)中內(nèi)存地址是連續(xù)的。但是在單鏈表中由于存儲(chǔ)單元可能不是連續(xù)的切厘，所以我們要想知道第 i 個(gè)元素的內(nèi)存地址萨咳，就必須要從頭指針開始。因此疫稿，對(duì)于單鏈表要想實(shí)現(xiàn)獲取第 i 個(gè)元素?cái)?shù)據(jù)某弦，在算法上相對(duì)麻煩一些
獲取單鏈表第 i 個(gè)數(shù)據(jù)的算法思路：
1.聲明一個(gè)結(jié)點(diǎn) cur，讓其指向單鏈表的第一個(gè)結(jié)點(diǎn)而克，初始化 j 為 1
2.當(dāng) j < i 時(shí)靶壮，就遍歷單鏈表，讓 cur 的指針向后移動(dòng)员萍，不斷指向下一個(gè)結(jié)點(diǎn)腾降，j 累加 1
3.若到鏈表末尾 cur 為空，則第 i 個(gè)元素不存在
4.反之查找成功碎绎，并返回該節(jié)點(diǎn)的數(shù)據(jù)
實(shí)現(xiàn)代碼算法如下：
Status getElement(LinkList *pList,int i,ElemType *e) {
// 判斷單鏈表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能獲取位置 1 以及以后的元素
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 聲明一個(gè)結(jié)點(diǎn) cur,讓其指向單鏈表的第一個(gè)結(jié)點(diǎn)
Node *cur = pList->next;
for(int j = 1;j < i;j+) {// j 為計(jì)數(shù)器螃壤，初始化為1
cur = cur->next;
if(cur == NULL) {
printf("dont find cur\n");
return FALSE;
}
}
// 獲取第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)
*e = cur->data;
return TRUE;
}
從上面的解題思路中可知，要想獲取第 i 個(gè)元素?cái)?shù)據(jù)筋帖，需要從頭開始直至第 i 個(gè)元素為止奸晴。那么，這個(gè)算法的時(shí)間復(fù)雜度就取決于 i日麸，最好的情況是第一個(gè)結(jié)點(diǎn)就是我們所要查找的數(shù)據(jù)即 i = 1,時(shí)間復(fù)雜度為 O(1)寄啼，最壞的情況是我們要查找的元素在單鏈表的最后一位或不在單鏈表中，那么此時(shí)需要遍歷 n 次代箭，此時(shí)時(shí)間復(fù)雜度為 O(n)
在單鏈表中獲取第 i 個(gè)元素?cái)?shù)據(jù)其核心思想是 工作指針后移墩划，從上述介紹中我們能感受到單鏈表并不適合查找，但是事物都是有兩面性的嗡综，根據(jù)前面的介紹我們也能想到單鏈表在 數(shù)據(jù)插入乙帮、刪除方面效率應(yīng)該比較高，下面我們來(lái)看下單鏈表的插入與刪除
單鏈表的插入與刪除
單鏈表的插入
假設(shè)存儲(chǔ)數(shù)據(jù)元素 e 的結(jié)點(diǎn)為 s,現(xiàn)在我們要把結(jié)點(diǎn) s 插入到 p极景、p->next 之間察净，我們?cè)撊绾尾迦肽兀?br>
注意：根據(jù)前面的介紹可知道 p->next 的值是一個(gè)指針驾茴，指向的是結(jié)點(diǎn) p 的直接后繼元素 ai + 1
要想實(shí)現(xiàn)上述元素插入，我們需要將 p->next氢卡、s->next 的值做一點(diǎn)改動(dòng)沟涨，現(xiàn)在 p->next、s->next 指向的都是其各自的直接后繼指針异吻，現(xiàn)在我們 把 p 的后繼結(jié)點(diǎn)改成 s 的后繼結(jié)點(diǎn)裹赴，再把 s 變成 p 的后繼結(jié)點(diǎn)，偽代碼實(shí)現(xiàn)如下：
s->next = p->next;p->next=s;
試想一下诀浪，如果我們把上面代碼的順序調(diào)整一下會(huì)怎么樣?
調(diào)整后的順序是：把 s 變成 p 的后繼結(jié)點(diǎn)棋返，再把 p 的后繼結(jié)點(diǎn)變成 s 的后繼結(jié)點(diǎn)
p->next = s;s->next = p->next;
仔細(xì)分析下，如果先把 s 變成 p 的后繼結(jié)點(diǎn)雷猪，那么這時(shí) p->next 指向的就是結(jié)點(diǎn) s,即 p->next 是結(jié)點(diǎn) s 在內(nèi)存中的地址睛竣，則 s->next = p->next 就相當(dāng)于 s->next = s，所以這個(gè)執(zhí)行順序是不能調(diào)整的求摇，插入結(jié)點(diǎn) s 之后如下圖所示：
單鏈表第 i 個(gè)位置之前插入新結(jié)點(diǎn)的算法思路：
1.聲明一個(gè)節(jié)點(diǎn) front 射沟，讓結(jié)點(diǎn) front 指向單鏈表的頭結(jié)點(diǎn)，初始化 j 從 1 開始
2.當(dāng) j < i 時(shí)与境，就遍歷單鏈表验夯，讓結(jié)點(diǎn) front 的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)摔刁，j 累加 1
3.若到鏈表末尾 front 為空挥转，則說(shuō)明第 i 個(gè)元素不存在
4.否則查找成功，在系統(tǒng)中創(chuàng)建一個(gè)新結(jié)點(diǎn) pTemp
5.將數(shù)據(jù)元素 e 賦值給 pTemp->data
6.執(zhí)行單鏈表插入標(biāo)準(zhǔn)語(yǔ)句 pTemp->next = front->next;front->next = pTemp;
7.返回成功
實(shí)現(xiàn)代碼如下：
Status insertList(LinkList *pList,int i,const ElemType e) {
// 判斷單鏈表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能在位置 1 以及后面插入
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 在這里我們聲明一個(gè)結(jié)點(diǎn) front,讓其指向單鏈表 pList 的頭結(jié)點(diǎn)
Node *front = pList;
for(int j = 1;j < i;j++) {// j 為計(jì)數(shù)器共屈，初始化為1
front = front->next;
if(front == NULL) {
printf("dont find front\n");
return FALSE;
}
}
// 創(chuàng)建一個(gè)新結(jié)點(diǎn)绑谣，存放要插入的新元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp){
printf("malloc error\n");
}
temp->data = e;
// 插入新結(jié)點(diǎn)
temp->next = front->next;
front->next = temp;
return TRUE;
}
注意：?jiǎn)捂湵聿迦胄陆Y(jié)點(diǎn)實(shí)現(xiàn)的難點(diǎn)在于如何找到 i 位置的前一個(gè)結(jié)點(diǎn)
頭部插入和尾部插入
單鏈表的頭部插入就是新結(jié)點(diǎn)始終在第一個(gè)結(jié)點(diǎn)的位置，這種算法簡(jiǎn)稱為 頭插法拗引，如下圖所示：
代碼實(shí)現(xiàn)如下：
Status inserListHead(LinkList *pList,cosnt ElemeType e) {
// 判斷單鏈表 pList 是否為空
if(!pList) {
printf("list not exist");
return FALSE;
}
// 聲明一個(gè)新結(jié)點(diǎn),讓該結(jié)點(diǎn)指向單鏈表的頭結(jié)點(diǎn)
Node *head = pList;
// 創(chuàng)建一個(gè)臨時(shí)結(jié)點(diǎn),存儲(chǔ)新插入的元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp) {
printf("malloc error");
}
temp->data = e;
// 執(zhí)行插入操作
temp->next = head->next;
head->next = temp;
return TRUE;
}
單鏈表的尾部插入就是將新結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)后面借宵，這種簡(jiǎn)稱 尾插法，如下圖所示：
代碼實(shí)現(xiàn)如下：
Status insertListTail(LinkList *pList,const ElemeType e) {
// 判斷單鏈表是否為空
if(!pList) {
printf("List is not exist");
return FALSE:
}
// 聲明一個(gè)結(jié)點(diǎn) cur,讓該結(jié)點(diǎn)指向單鏈表的頭結(jié)點(diǎn)
Node *cur = pList;
// 創(chuàng)建一個(gè)臨時(shí)結(jié)點(diǎn),用于存放新插入的數(shù)據(jù)元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp) {
printf("malloc error");
}
// 查找單鏈表的尾結(jié)點(diǎn),若到單鏈表的尾結(jié)點(diǎn),則為 NULL
while(cur->next) {
cur = cur->next;
}
temp->data = e;
// 執(zhí)行插入操作
temp->next = cur->next;
cur->next = temp;
return TRUE;
}
單鏈表的刪除
我們先來(lái)看一下單鏈表的存儲(chǔ)結(jié)構(gòu)示意圖
假設(shè)存儲(chǔ)數(shù)據(jù)元素 ai 的結(jié)點(diǎn)是 q,要想實(shí)現(xiàn)在單鏈表中刪除結(jié)點(diǎn) q 的操作矾削，其實(shí)就是將結(jié)點(diǎn) p 的直接后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)變成 p 的直接后繼結(jié)點(diǎn)壤玫，用偽代碼表示就是：
p->next = p->next->next;
使用 q 代替 p->next，代碼表示如下：
q = p->next;p->next = q->next;
單鏈表第 i 個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：
1.聲明一個(gè)節(jié)點(diǎn) front,讓其指向單鏈表的第一個(gè)結(jié)點(diǎn)怔软，初始化 j 為 1
2.當(dāng) j < i 垦细，遍歷單鏈表，讓 front 的指針向后移動(dòng)挡逼，不斷的指向下一個(gè)結(jié)點(diǎn)，j 累加 1
3.若到鏈表末尾 p 為空腻豌，則在單鏈表中沒(méi)有第 i 個(gè)元素
4.反之則查找成功家坎，查找到要?jiǎng)h除位置的前一個(gè)元素 front嘱能，并賦值給 pTemp
5.執(zhí)行單鏈表的刪除結(jié)點(diǎn)語(yǔ)句 front->next = front->next->next;
6.將 pTemp 結(jié)點(diǎn)的數(shù)據(jù)元素賦值給 e，并返回
7.釋放 pTemp 結(jié)點(diǎn)虱疏，并指向 NULL
8.返回成功
Status deleteList(LinkList *pList,int i,ElemType *e) {
// 判斷單鏈表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能刪除位置 1 以及后面的結(jié)點(diǎn)
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 在這里我們聲明一個(gè)結(jié)點(diǎn) front,讓其指向單鏈表 pList 的頭結(jié)點(diǎn)
Node *front = pList;
for(int j = 1;j < i;j++) {// j 為計(jì)數(shù)器惹骂，初始化為1
front = front->next;
if(front == NULL) {
printf("dont find front\n");
return FALSE;
}
}
// 提前保存要?jiǎng)h除的結(jié)點(diǎn)
Node *temp = front->next;
*e = temp->data;//將要?jiǎng)h除結(jié)點(diǎn)的數(shù)據(jù)賦值給e
// 刪除結(jié)點(diǎn)
front->next = front->next->next;
// 銷毀結(jié)點(diǎn)
free(temp);
temp = NULL;
return TRUE;
}
總結(jié)：通過(guò)上面對(duì)單鏈表的插入和刪除算法的介紹，可以看出來(lái)它們都包含兩部分：第一部分是先遍歷查找第 i 個(gè)元素;第二部分執(zhí)行插入和刪除操作做瞪。根據(jù)前面文章中介紹的復(fù)雜度分析法分析对粪，它們的時(shí)間復(fù)雜度都是 O(n)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)相比較線性表的順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)装蓬，在數(shù)據(jù)元素的讀取上沒(méi)有太大的優(yōu)勢(shì)著拭，線性表的順序存儲(chǔ)結(jié)構(gòu)支持隨機(jī)訪問(wèn)，根據(jù)下標(biāo)隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為 O(1);而對(duì)于單鏈表讀取第 i 個(gè)位置的數(shù)據(jù)元素時(shí)因?yàn)槠鋬?nèi)存地址不是連續(xù)的,都必須要先從頭指針開始遍歷,時(shí)間復(fù)雜度為 O(n)
在數(shù)據(jù)元素的插入和刪除方面牍帚，單鏈表的優(yōu)勢(shì)就比較明顯了儡遮，尤其是 插入或者刪除操作越頻繁，單鏈表的效率優(yōu)勢(shì)就更加明顯 假設(shè)現(xiàn)在我們要在第 i 個(gè)元素后插入 10 個(gè)元素,對(duì)于順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)暗赶，每一次插入都需要移動(dòng) n - i 個(gè)元素鄙币，每次都是 O(n);而對(duì)于單鏈表，我們只需要在第一次時(shí)蹂随，找到第 i 個(gè)元素指針十嘿，此時(shí)時(shí)間復(fù)雜度為 O(n)，接下來(lái)只是簡(jiǎn)單地通過(guò)賦值移動(dòng)指針而已岳锁，時(shí)間復(fù)雜度為 O(1)
知識(shí)點(diǎn)補(bǔ)充
- 關(guān)于 malloc 函數(shù)的用法
在 C 語(yǔ)言中, malloc 函數(shù)主要用于動(dòng)態(tài)內(nèi)存分配详幽，函數(shù)原型是：
void *malloc(unsigned int size)
此函數(shù)的返回值是分配內(nèi)存塊的起始地址(首地址)，或者說(shuō)浸锨，這是一個(gè)指針類型的函數(shù)唇聘，返回的指針指向該分配內(nèi)存塊的首地址，分配成功則返回指向分配內(nèi)存塊的首地址柱搜，反之返回空指針 NULL迟郎；此外需要注意的是，該函數(shù)返回的是 void 類型的指針聪蘸，void 類型說(shuō)明類型還未確定宪肖，因此該函數(shù)的返回值可以指向任意類型的數(shù)據(jù)，因此必要時(shí)需要做類型強(qiáng)制轉(zhuǎn)換
比如健爬，現(xiàn)在我們聲明了一個(gè)鏈表結(jié)構(gòu)體：
typedef struct Node
{
ElemeType data;
struct Node *next;
}list;
現(xiàn)在我們要定義一個(gè) Node 類型的指針變量控乾，可以使用如下語(yǔ)句：
*a = (list*)malloc(sizeof(list));
其中，(list *) 表示類型強(qiáng)制轉(zhuǎn)換娜遵，sizeof(list) 表示獲取 list 類型占用空間大小
