認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【鏈表】
認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【鏈表】
認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)系列往期文章：
?認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【樹(shù)】?認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【數(shù)組】
回顧數(shù)組元素的訪問(wèn)
name 的第5個(gè)元素，我們可以使用下標(biāo)來(lái)獲取，例如 name[4]。#include <stdio.h>int main(){unsigned int numbers[] = {100, 200, 300, 400, 500};printf("單個(gè)unsigned int所占字節(jié)數(shù)：%d\n", sizeof(unsigned int));printf("numbers數(shù)組所占字節(jié)數(shù)：%d\n", sizeof(numbers));printf("數(shù)組numbers的元素個(gè)數(shù)：%d\n\n", sizeof(numbers) / sizeof(unsigned int));printf("numbers的指針地址：0x%x\n\n", &numbers);printf("元素numbers[0]的指針地址：0x%x\n", &numbers[0]);printf("元素numbers[1]的指針地址：0x%x\n", &numbers[1]);printf("元素numbers[2]的指針地址：0x%x\n", &numbers[2]);printf("元素numbers[3]的指針地址：0x%x\n", &numbers[3]);printf("元素numbers[4]的指針地址：0x%x\n", &numbers[4]);return 0;}
單個(gè)unsigned int所占字節(jié)數(shù)：4numbers數(shù)組所占字節(jié)數(shù)：20數(shù)組numbers的元素個(gè)數(shù)：5numbers的指針地址：0xc48df320元素numbers[0]的指針地址：0xc48df320元素numbers[1]的指針地址：0xc48df324元素numbers[2]的指針地址：0xc48df328元素numbers[3]的指針地址：0xc48df32c元素numbers[4]的指針地址：0xc48df330
注：您自己運(yùn)行的結(jié)果地址應(yīng)該和上面是不一樣的。
?每個(gè) unsigned int 占四個(gè)字節(jié)?numbers 數(shù)組所占字節(jié)數(shù) = 單個(gè) unsigned int 所占字節(jié) * numbers 數(shù)組元素個(gè)數(shù)?數(shù)組 numbers 的內(nèi)存地址和 其第一個(gè)元素 numbers[0] 的地址相同?numbers 每?jī)蓚€(gè)相鄰元素的地址相差一個(gè) unsigned int 的長(zhǎng)度
numbers 數(shù)組在內(nèi)存中應(yīng)該是如下圖的樣子：
numbers[2] 的值，則可以通過(guò)如下方式獲取：numbers指針地址0xc48df320 + 單個(gè)unsigned int的長(zhǎng)度4 * 2 = 0xc48df320 + 8 = 0xc48df328
內(nèi)存 [0xc48df328 , 0xc48df32c) 之間的數(shù)據(jù)就是 number[2] 的值
鏈表
鏈表的定義
鏈表的特點(diǎn)
鏈表的分類
線性鏈表（單鏈表）和非線性鏈表
?由分別表示 結(jié)點(diǎn)1，結(jié)點(diǎn)2，…，結(jié)點(diǎn)N的N個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示。由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表。?非線性的鏈表，可以參見(jiàn)相關(guān)的其他數(shù)據(jù)結(jié)構(gòu)，例如樹(shù)、圖。對(duì)比線性鏈表的定義可知，非線性鏈表的每個(gè)結(jié)點(diǎn)可能會(huì)包含多個(gè)指針域。
雙向鏈表
循環(huán)鏈表
1.在建立一個(gè)循環(huán)鏈表時(shí)，必須使其最后一個(gè)結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn)，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)。2.在判斷是否到表尾時(shí)，是判斷該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)，當(dāng)鏈域值等于表頭指針時(shí)，說(shuō)明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。
循環(huán)鏈表的舉例：約瑟夫還問(wèn)題，感興趣的朋友可以自己查找相關(guān)資料了解一下。
問(wèn)題來(lái)源：
據(jù)說(shuō)著名猶太歷史學(xué)家Josephus有過(guò)以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開(kāi)始，越過(guò)k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過(guò)），并殺掉第k個(gè)人。接著，再越過(guò)k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過(guò)程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問(wèn)題是，給定了和，一開(kāi)始要站在什么地方才能避免被處決。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。
鏈表的操作
遍歷
?對(duì)于線性鏈表的遍歷很容易。因?yàn)槊總€(gè)結(jié)點(diǎn)上有指向下一個(gè)結(jié)點(diǎn)的指針域，通過(guò)指針可以很容易的遍歷完整個(gè)鏈表。?對(duì)于非線性鏈表的遍歷稍微復(fù)雜一些，因?yàn)槊總€(gè)結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)的指針域有多個(gè)，這些多個(gè)指針域的遍歷順序不一樣則遍歷出來(lái)的結(jié)果也不一樣。此處不多說(shuō)了，關(guān)于樹(shù)的遍歷可以點(diǎn)擊文末關(guān)于樹(shù)的文章鏈接查看?對(duì)于循環(huán)鏈表來(lái)說(shuō)，需要注意的是如何決定終止條件，而使遍歷不會(huì)變成一個(gè)死循環(huán)
插入結(jié)點(diǎn)
結(jié)點(diǎn)A 和 結(jié)點(diǎn)C 之間插入 結(jié)點(diǎn)B，則僅僅需要把 結(jié)點(diǎn)A 的指針域指向 結(jié)點(diǎn)B，并且把 結(jié)點(diǎn)B 的指針域指向 結(jié)點(diǎn)C 即可。
刪除結(jié)點(diǎn)
A -> B -> C 這樣的鏈表中的 結(jié)點(diǎn)B 刪除僅僅需要將 結(jié)點(diǎn)A 的指針域指向 結(jié)點(diǎn)C 即可。結(jié)點(diǎn)B 指向 結(jié)點(diǎn)C 的指針域可以根據(jù)你的需要來(lái)決定是否刪除，不管刪除與否這都不影響在原來(lái)的鏈表中已經(jīng)移除了結(jié)點(diǎn)B。
最后
大家下期見(jiàn)~(●ˇ?ˇ●)
往期文章：
?認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【樹(shù)】?認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)之【數(shù)組】
歡迎關(guān)注我的公眾號(hào)“須彌零一”，原創(chuàng)技術(shù)文章第一時(shí)間推送。