原文地址：
https://mp.weixin.qq.com/s/ZVwIUN-xf9FuxOFXW8H3Nw作者：業(yè)余碼農(nóng)
數(shù)據(jù)結(jié)構(gòu)想必大家都不會(huì)陌生，對(duì)于一個(gè)成熟的程序員而言，熟悉和掌握數(shù)據(jù)結(jié)構(gòu)和算法也是基本功之一。數(shù)據(jù)結(jié)構(gòu)本身其實(shí)不過(guò)是數(shù)據(jù)按照特點(diǎn)關(guān)系進(jìn)行存儲(chǔ)或者組織的集合，特殊的結(jié)構(gòu)在不同的應(yīng)用場(chǎng)景中往往會(huì)帶來(lái)不一樣的處理效率。
常用的數(shù)據(jù)結(jié)構(gòu)可根據(jù)數(shù)據(jù)訪問(wèn)的特點(diǎn)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)包括常見的鏈表、棧、隊(duì)列等，非線性結(jié)構(gòu)包括樹、圖等。數(shù)據(jù)結(jié)構(gòu)種類繁多，本文將通過(guò)圖解的方式對(duì)常用的數(shù)據(jù)結(jié)構(gòu)進(jìn)行理論上的介紹和講解，以方便大家掌握常用數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。
1 數(shù)組
數(shù)組可以說(shuō)是最基本最常見的數(shù)據(jù)結(jié)構(gòu)。數(shù)組一般用來(lái)存儲(chǔ)相同類型的數(shù)據(jù)，可通過(guò)數(shù)組名和下標(biāo)進(jìn)行數(shù)據(jù)的訪問(wèn)和更新。數(shù)組中元素的存儲(chǔ)是按照先后順序進(jìn)行的，同時(shí)在內(nèi)存中也是按照這個(gè)順序進(jìn)行連續(xù)存放。數(shù)組相鄰元素之間的內(nèi)存的址的間隔一般就是數(shù)組數(shù)據(jù)類型的大小。
2 鏈表
鏈表相較于數(shù)組，除了數(shù)據(jù)域，還增加了指針域用于構(gòu)建鏈?zhǔn)降拇鎯?chǔ)數(shù)據(jù)。鏈表中每一個(gè)節(jié)點(diǎn)都包含此節(jié)點(diǎn)的數(shù)據(jù)和指向下一節(jié)點(diǎn)地址的指針。由于是通過(guò)指針進(jìn)行下一個(gè)數(shù)據(jù)元素的查找和訪問(wèn)，使得鏈表的自由度更高。
這表現(xiàn)在對(duì)節(jié)點(diǎn)進(jìn)行增加和刪除時(shí)，只需要對(duì)上一節(jié)點(diǎn)的指針地址進(jìn)行修改，而無(wú)需變動(dòng)其它的節(jié)點(diǎn)。不過(guò)事物皆有兩極，指針帶來(lái)高自由度的同時(shí)，自然會(huì)犧牲數(shù)據(jù)查找的效率和多余空間的使用。
一般常見的是有頭有尾的單鏈表，對(duì)指針域進(jìn)行反向鏈接，還可以形成雙向鏈表或者循環(huán)鏈表。
鏈表和數(shù)組對(duì)比
鏈表和數(shù)組在實(shí)際的使用過(guò)程中需要根據(jù)自身的優(yōu)劣勢(shì)進(jìn)行選擇。鏈表和數(shù)組的異同點(diǎn)也是面試中高頻的考察點(diǎn)之一。這里對(duì)單鏈表和數(shù)組的區(qū)別進(jìn)行了對(duì)比和總結(jié)。
3 跳表
從上面的對(duì)比中可以看出，鏈表雖然通過(guò)增加指針域提升了自由度，但是卻導(dǎo)致數(shù)據(jù)的查詢效率惡化。特別是當(dāng)鏈表長(zhǎng)度很長(zhǎng)的時(shí)候，對(duì)數(shù)據(jù)的查詢還得從頭依次查詢，這樣的效率會(huì)更低。跳表的產(chǎn)生就是為了解決鏈表過(guò)長(zhǎng)的問(wèn)題，通過(guò)增加鏈表的多級(jí)索引來(lái)加快原始鏈表的查詢效率。這樣的方式可以讓查詢的時(shí)間復(fù)雜度從O(n)提升至O(logn)。
跳表通過(guò)增加的多級(jí)索引能夠?qū)崿F(xiàn)高效的動(dòng)態(tài)插入和刪除，其效率和紅黑樹和平衡二叉樹不相上下。目前redis和levelDB都有用到跳表。
從上圖可以看出，索引級(jí)的指針域除了指向下一個(gè)索引位置的指針，還有一個(gè)down指針指向低一級(jí)的鏈表位置，這樣才能實(shí)現(xiàn)跳躍查詢的目的。
4 棧
棧是一種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，常用一句話描述其特性，后進(jìn)先出。棧本身是一個(gè)線性表，但是在這個(gè)表中只有一個(gè)口子允許數(shù)據(jù)的進(jìn)出。這種模式可以參考腔腸動(dòng)物...即進(jìn)食和排泄都用一個(gè)口...
棧的常用操作包括入棧push和出棧pop，對(duì)應(yīng)于數(shù)據(jù)的壓入和壓出。還有訪問(wèn)棧頂數(shù)據(jù)、判斷棧是否為空和判斷棧的大小等。由于棧后進(jìn)先出的特性，?？梢宰鳛閿?shù)據(jù)操作的臨時(shí)容器，對(duì)數(shù)據(jù)的順序進(jìn)行調(diào)控，與其它數(shù)據(jù)結(jié)構(gòu)相結(jié)合可獲得許多靈活的處理。
5 隊(duì)列
隊(duì)列是棧的兄弟結(jié)構(gòu)，與棧的后進(jìn)先出相對(duì)應(yīng)，隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。顧名思義，隊(duì)列的數(shù)據(jù)存儲(chǔ)是如同排隊(duì)一般，先存入的數(shù)據(jù)先被壓出。常與棧一同配合，可發(fā)揮最大的實(shí)力。
6 樹
樹作為一種樹狀的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)節(jié)點(diǎn)之間的關(guān)系也如大樹一樣，將有限個(gè)節(jié)點(diǎn)根據(jù)不同層次關(guān)系進(jìn)行排列，從而形成數(shù)據(jù)與數(shù)據(jù)之間的父子關(guān)系。常見的數(shù)的表示形式更接近“倒掛的樹”，因?yàn)樗鼘⒏?，葉朝下。
樹的數(shù)據(jù)存儲(chǔ)在結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)有零個(gè)或者多個(gè)子結(jié)點(diǎn)。沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)在最頂端，成為根節(jié)點(diǎn)；沒(méi)有非根結(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；每個(gè)非根節(jié)點(diǎn)又可以分為多個(gè)不相交的子樹。
這意味著樹是具備層次關(guān)系的，父子關(guān)系清晰，家庭血緣關(guān)系明朗；這也是樹與圖之間最主要的區(qū)別。
別看樹好像很高級(jí)，其實(shí)可看作是鏈表的高配版。樹的實(shí)現(xiàn)就是對(duì)鏈表的指針域進(jìn)行了擴(kuò)充，增加了多個(gè)地址指向子結(jié)點(diǎn)。同時(shí)將“鏈表”豎起來(lái)，從而凸顯了結(jié)點(diǎn)之間的層次關(guān)系，更便于分析和理解。
樹可以衍生出許多的結(jié)構(gòu)，若將指針域設(shè)置為雙指針，那么即可形成最常見的二叉樹，即每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。二叉樹根據(jù)結(jié)點(diǎn)的排列和數(shù)量還可進(jìn)一度劃分為完全二叉樹、滿二叉樹、平衡二叉樹、紅黑樹等。
完全二叉樹：除了最后一層結(jié)點(diǎn)，其它層的結(jié)點(diǎn)數(shù)都達(dá)到了最大值；同時(shí)最后一層的結(jié)點(diǎn)都是按照從左到右依次排布。
滿二叉樹：除了最后一層，其它層的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。
平衡二叉樹
平衡二叉樹又被稱為AVL樹，它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。
二叉排序樹：是一棵空樹，或者：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；它的左、右子樹也分別為二叉排序樹。
樹的高度：結(jié)點(diǎn)層次的最大值
平衡因子：左子樹高度 - 右子樹高度
二叉排序樹意味著二叉樹中的數(shù)據(jù)是排好序的，順序?yàn)樽蠼Y(jié)點(diǎn)<根節(jié)點(diǎn)<右結(jié)點(diǎn)，這表明二叉排序樹的中序遍歷結(jié)果是有序的。（還不懂二叉樹四種遍歷方式[前序遍歷、中序遍歷、后序遍歷、層序遍歷]的同學(xué)趕緊補(bǔ)習(xí)?。?/p>
平衡二叉樹的產(chǎn)生是為了解決二叉排序樹在插入時(shí)發(fā)生線性排列的現(xiàn)象。由于二叉排序樹本身為有序，當(dāng)插入一個(gè)有序程度十分高的序列時(shí)，生成的二叉排序樹會(huì)持續(xù)在某個(gè)方向的字?jǐn)?shù)上插入數(shù)據(jù)，導(dǎo)致最終的二叉排序樹會(huì)退化為鏈表，從而使得二叉樹的查詢和插入效率惡化。
平衡二叉樹的出現(xiàn)能夠解決上述問(wèn)題，但是在構(gòu)造平衡二叉樹時(shí)，卻需要采用不同的調(diào)整方式，使得二叉樹在插入數(shù)據(jù)后保持平衡。主要的四種調(diào)整方式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。這里先給大家介紹下簡(jiǎn)單的單旋轉(zhuǎn)操作，左旋和右旋。LR和RL本質(zhì)上只是LL和RR的組合。
在插入一個(gè)結(jié)點(diǎn)后應(yīng)該沿搜索路徑將路徑上的結(jié)點(diǎn)平衡因子進(jìn)行修改，當(dāng)平衡因子大于1時(shí)，就需要進(jìn)行平衡化處理。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)，如果這三個(gè)結(jié)點(diǎn)在一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化，如果這三個(gè)結(jié)點(diǎn)位于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。
左旋：S為當(dāng)前需要左旋的結(jié)點(diǎn)，E為當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)。
左旋的操作可以用一句話簡(jiǎn)單表示：將當(dāng)前結(jié)點(diǎn)S的左孩子旋轉(zhuǎn)為當(dāng)前結(jié)點(diǎn)父結(jié)點(diǎn)E的右孩子，同時(shí)將父結(jié)點(diǎn)E旋轉(zhuǎn)為當(dāng)前結(jié)點(diǎn)S的左孩子。可用動(dòng)畫表示：
右旋：S為當(dāng)前需要左旋的結(jié)點(diǎn)，E為當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)。右單旋是左單旋的鏡像旋轉(zhuǎn)。
左旋的操作同樣可以用一句話簡(jiǎn)單表示：將當(dāng)前結(jié)點(diǎn)S的左孩子E的右孩子旋轉(zhuǎn)為當(dāng)前結(jié)點(diǎn)S的左孩子，同時(shí)將當(dāng)前結(jié)點(diǎn)S旋轉(zhuǎn)為左孩子E的右孩子?？捎脛?dòng)畫表示：
紅黑樹
平衡二叉樹（AVL）為了追求高度平衡，需要通過(guò)平衡處理使得左右子樹的高度差必須小于等于1。高度平衡帶來(lái)的好處是能夠提供更高的搜索效率，其最壞的查找時(shí)間復(fù)雜度都是O(logN)。但是由于需要維持這份高度平衡，所付出的代價(jià)就是當(dāng)對(duì)樹種結(jié)點(diǎn)進(jìn)行插入和刪除時(shí)，需要經(jīng)過(guò)多次旋轉(zhuǎn)實(shí)現(xiàn)復(fù)衡。這導(dǎo)致AVL的插入和刪除效率并不高。
為了解決這樣的問(wèn)題，能不能找一種結(jié)構(gòu)能夠兼顧搜索和插入刪除的效率呢？這時(shí)候紅黑樹便申請(qǐng)出戰(zhàn)了。
紅黑樹具有五個(gè)特性：
每個(gè)結(jié)點(diǎn)要么是紅的要么是黑的。
根結(jié)點(diǎn)是黑的。
每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn)）都是黑的。
如果一個(gè)結(jié)點(diǎn)是紅的，那么它的兩個(gè)兒子都是黑的。
對(duì)于任意結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。
紅黑樹通過(guò)將結(jié)點(diǎn)進(jìn)行紅黑著色，使得原本高度平衡的樹結(jié)構(gòu)被稍微打亂，平衡程度降低。紅黑樹不追求完全平衡，只要求達(dá)到部分平衡。這是一種折中的方案，大大提高了結(jié)點(diǎn)刪除和插入的效率。C++中的STL就常用到紅黑樹作為底層的數(shù)據(jù)結(jié)構(gòu)。
紅黑樹VS平衡二叉樹
除了上面所提及的樹結(jié)構(gòu)，還有許多廣泛應(yīng)用在數(shù)據(jù)庫(kù)、磁盤存儲(chǔ)等場(chǎng)景下的樹結(jié)構(gòu)。比如B樹、B+樹等。這里就先不介紹了誒，下次在講述相關(guān)存儲(chǔ)原理的時(shí)候?qū)?huì)著重介紹。（其實(shí)是因?yàn)閼校?/p>
7 堆
了解完二叉樹，再來(lái)理解堆就不是什么難事了。堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。堆的具體實(shí)現(xiàn)一般不通過(guò)指針域，而是通過(guò)構(gòu)建一個(gè)一維數(shù)組與二叉樹的父子結(jié)點(diǎn)進(jìn)行對(duì)應(yīng)，因此堆總是一顆完全二叉樹。
對(duì)于任意一個(gè)父節(jié)點(diǎn)的序號(hào)n來(lái)說(shuō)（這里n從0算），它的子節(jié)點(diǎn)的序號(hào)一定是2n+1，2n+2，因此可以直接用數(shù)組來(lái)表示一個(gè)堆。
不僅如此，堆還有一個(gè)性質(zhì)：堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆常用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，在面試中經(jīng)?？嫉膯?wèn)題都是與排序有關(guān)，比如堆排序、topK問(wèn)題等。由于堆的根節(jié)點(diǎn)是序列中最大或者最小值，因而可以在建堆以及重建堆的過(guò)程中，篩選出數(shù)據(jù)序列中的極值，從而達(dá)到排序或者挑選topK值的目的。
8 散列表
散列表也叫哈希表，是一種通過(guò)鍵值對(duì)直接訪問(wèn)數(shù)據(jù)的機(jī)構(gòu)。在初中，我們就學(xué)過(guò)一種能夠?qū)⒁粋€(gè)x值通過(guò)一個(gè)函數(shù)獲得對(duì)應(yīng)的一個(gè)y值的操作，叫做映射。散列表的實(shí)現(xiàn)原理正是映射的原理，通過(guò)設(shè)定的一個(gè)關(guān)鍵字和一個(gè)映射函數(shù)，就可以直接獲得訪問(wèn)數(shù)據(jù)的地址，實(shí)現(xiàn)O(1)的數(shù)據(jù)訪問(wèn)效率。在映射的過(guò)程中，事先設(shè)定的函數(shù)就是一個(gè)映射表，也可以稱作散列函數(shù)或者哈希函數(shù)。
散列表的實(shí)現(xiàn)最關(guān)鍵的就是散列函數(shù)的定義和選擇。一般常用的有以下幾種散列函數(shù)：
直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。
數(shù)字分析法：通過(guò)對(duì)數(shù)據(jù)的分析，發(fā)現(xiàn)數(shù)據(jù)中沖突較少的部分，并構(gòu)造散列地址。例如同學(xué)們的學(xué)號(hào)，通常同一屆學(xué)生的學(xué)號(hào)，其中前面的部分差別不太大，所以用后面的部分來(lái)構(gòu)造散列地址。
平方取中法：當(dāng)無(wú)法確定關(guān)鍵字里哪幾位的分布相對(duì)比較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為散列地址。這是因?yàn)椋河?jì)算平方之后的中間幾位和關(guān)鍵字中的每一位都相關(guān)，所以不同的關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的散列地址。
取隨機(jī)數(shù)法：使用一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，這種方式通常用于關(guān)鍵字長(zhǎng)度不同的場(chǎng)合。
除留取余法：取關(guān)鍵字被某個(gè)不大于散列表的表長(zhǎng) n 的數(shù) m 除后所得的余數(shù) p 為散列地址。這種方式也可以在用過(guò)其他方法后再使用。該函數(shù)對(duì) m 的選擇很重要，一般取素?cái)?shù)或者直接用 n。
確定好散列函數(shù)之后，通過(guò)某個(gè)key值的確會(huì)得到一個(gè)唯一的value地址。但是卻會(huì)出現(xiàn)一些特殊情況。即通過(guò)不同的key值可能會(huì)訪問(wèn)到同一個(gè)地址，這個(gè)現(xiàn)象稱之為沖突。
沖突在發(fā)生之后，當(dāng)在對(duì)不同的key值進(jìn)行操作時(shí)會(huì)使得造成相同地址的數(shù)據(jù)發(fā)生覆蓋或者丟失，是非常危險(xiǎn)的。所以在設(shè)計(jì)散列表往往還需要采用沖突解決的辦法。
常用的沖突處理方式有很多，常用的包括以下幾種：
開放地址法（也叫開放尋址法）：實(shí)際上就是當(dāng)需要存儲(chǔ)值時(shí)，對(duì)Key哈希之后，發(fā)現(xiàn)這個(gè)地址已經(jīng)有值了，這時(shí)該怎么辦？不能放在這個(gè)地址，不然之前的映射會(huì)被覆蓋。這時(shí)對(duì)計(jì)算出來(lái)的地址進(jìn)行一個(gè)探測(cè)再哈希，比如往后移動(dòng)一個(gè)地址，如果沒(méi)人占用，就用這個(gè)地址。如果超過(guò)最大長(zhǎng)度，則可以對(duì)總長(zhǎng)度取余。這里移動(dòng)的地址是產(chǎn)生沖突時(shí)的增列序量。
再哈希法：在產(chǎn)生沖突之后，使用關(guān)鍵字的其他部分繼續(xù)計(jì)算地址，如果還是有沖突，則繼續(xù)使用其他部分再計(jì)算地址。這種方式的缺點(diǎn)是時(shí)間增加了。
鏈地址法：鏈地址法其實(shí)就是對(duì)Key通過(guò)哈希之后落在同一個(gè)地址上的值，做一個(gè)鏈表。其實(shí)在很多高級(jí)語(yǔ)言的實(shí)現(xiàn)當(dāng)中，也是使用這種方式處理沖突的。
公共溢出區(qū)：這種方式是建立一個(gè)公共溢出區(qū)，當(dāng)?shù)刂反嬖跊_突時(shí)，把新的地址放在公共溢出區(qū)里。
目前比較常用的沖突解決方法是鏈地址法，一般可以通過(guò)數(shù)組和鏈表的結(jié)合達(dá)到?jīng)_突數(shù)據(jù)緩存的目的。
左側(cè)數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭。每發(fā)生一個(gè)沖突的數(shù)據(jù)，就將該數(shù)據(jù)作為鏈表的節(jié)點(diǎn)鏈接到鏈表尾部。這樣一來(lái)，就可以保證沖突的數(shù)據(jù)能夠區(qū)分并順利訪問(wèn)。
考慮到鏈表過(guò)長(zhǎng)造成的問(wèn)題，還可以使用紅黑樹替換鏈表進(jìn)行沖突數(shù)據(jù)的處理操作，來(lái)提高散列表的查詢穩(wěn)定性。
9 圖
圖相較于上文的幾個(gè)結(jié)構(gòu)可能接觸的不多，但是在實(shí)際的應(yīng)用場(chǎng)景中卻經(jīng)常出現(xiàn)。比方說(shuō)交通中的線路圖，常見的思維導(dǎo)圖都可以看作是圖的具體表現(xiàn)形式。
圖結(jié)構(gòu)一般包括頂點(diǎn)和邊，頂點(diǎn)通常用圓圈來(lái)表示，邊就是這些圓圈之間的連線。邊還可以根據(jù)頂點(diǎn)之間的關(guān)系設(shè)置不同的權(quán)重，默認(rèn)權(quán)重相同皆為1。此外根據(jù)邊的方向性，還可將圖分為有向圖和無(wú)向圖。
圖結(jié)構(gòu)用抽象的圖線來(lái)表示十分簡(jiǎn)單，頂點(diǎn)和邊之間的關(guān)系非常清晰明了。但是在具體的代碼實(shí)現(xiàn)中，為了將各個(gè)頂點(diǎn)和邊的關(guān)系存儲(chǔ)下來(lái)，卻不是一件易事。
鄰接矩陣
目前常用的圖存儲(chǔ)方式為鄰接矩陣，通過(guò)所有頂點(diǎn)的二維矩陣來(lái)存儲(chǔ)兩個(gè)頂點(diǎn)之間是否相連，或者存儲(chǔ)兩頂點(diǎn)間的邊權(quán)重。
無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱矩陣，是因?yàn)檫叢痪哂蟹较蛐裕裟軓拇隧旤c(diǎn)能夠到達(dá)彼頂點(diǎn)，那么彼頂點(diǎn)自然也能夠達(dá)到此頂點(diǎn)。此外，由于頂點(diǎn)本身與本身相連沒(méi)有意義，所以在鄰接矩陣中對(duì)角線上皆為0。
有向圖由于邊具有方向性，因此彼此頂點(diǎn)之間并不能相互達(dá)到，所以其鄰接矩陣的對(duì)稱性不再。
用鄰接矩陣可以直接從二維關(guān)系中獲得任意兩個(gè)頂點(diǎn)的關(guān)系，可直接判斷是否相連。但是在對(duì)矩陣進(jìn)行存儲(chǔ)時(shí)，卻需要完整的一個(gè)二維數(shù)組。若圖中頂點(diǎn)數(shù)過(guò)多，會(huì)導(dǎo)致二維數(shù)組的大小劇增，從而占用大量的內(nèi)存空間。
而根據(jù)實(shí)際情況可以分析得，圖中的頂點(diǎn)并不是任意兩個(gè)頂點(diǎn)間都會(huì)相連，不是都需要對(duì)其邊上權(quán)重進(jìn)行存儲(chǔ)。那么存儲(chǔ)的鄰接矩陣實(shí)際上會(huì)存在大量的0。雖然可以通過(guò)稀疏表示等方式對(duì)稀疏性高的矩陣進(jìn)行關(guān)鍵信息的存儲(chǔ)，但是卻增加了圖存儲(chǔ)的復(fù)雜性。
因此，為了解決上述問(wèn)題，一種可以只存儲(chǔ)相連頂點(diǎn)關(guān)系的鄰接表應(yīng)運(yùn)而生。
鄰接表
在鄰接表中，圖的每一個(gè)頂點(diǎn)都是一個(gè)鏈表的頭節(jié)點(diǎn)，其后連接著該頂點(diǎn)能夠直接達(dá)到的相鄰頂點(diǎn)。相較于無(wú)向圖，有向圖的情況更為復(fù)雜，因此這里采用有向圖進(jìn)行實(shí)例分析。
在鄰接表中，每一個(gè)頂點(diǎn)都對(duì)應(yīng)著一條鏈表，鏈表中存儲(chǔ)的是頂點(diǎn)能夠達(dá)到的相鄰頂點(diǎn)。存儲(chǔ)的順序可以按照頂點(diǎn)的編號(hào)順序進(jìn)行。比如上圖中對(duì)于頂點(diǎn)B來(lái)說(shuō)，其通過(guò)有向邊可以到達(dá)頂點(diǎn)A和頂點(diǎn)E，那么其對(duì)應(yīng)的鄰接表中的順序即B->A->E，其它頂點(diǎn)亦如此。
通過(guò)鄰接表可以獲得從某個(gè)頂點(diǎn)出發(fā)能夠到達(dá)的頂點(diǎn)，從而省去了對(duì)不相連頂點(diǎn)的存儲(chǔ)空間。然而，這還不夠。對(duì)于有向圖而言，圖中有效信息除了從頂點(diǎn)“指出去”的信息，還包括從別的頂點(diǎn)“指進(jìn)來(lái)”的信息。這里的“指出去”和“指進(jìn)來(lái)”可以用出度和入度來(lái)表示。
入度：有向圖的某個(gè)頂點(diǎn)作為終點(diǎn)的次數(shù)和。
出度：有向圖的某個(gè)頂點(diǎn)作為起點(diǎn)的次數(shù)和。
由此看出，在對(duì)有向圖進(jìn)行表示時(shí)，鄰接表只能求出圖的出度，而無(wú)法求出入度。這個(gè)問(wèn)題很好解決，那就是增加一個(gè)表用來(lái)存儲(chǔ)能夠到達(dá)某個(gè)頂點(diǎn)的相鄰頂點(diǎn)。這個(gè)表稱作逆鄰接表。
逆鄰接表
逆鄰接表與鄰接表結(jié)構(gòu)類似，只不過(guò)圖的頂點(diǎn)鏈接著能夠到達(dá)該頂點(diǎn)的相鄰頂點(diǎn)。也就是說(shuō)，鄰接表時(shí)順著圖中的箭頭尋找相鄰頂點(diǎn)，而逆鄰接表時(shí)逆著圖中的箭頭尋找相鄰頂點(diǎn)。
鄰接表和逆鄰接表的共同使用下，就能夠把一個(gè)完整的有向圖結(jié)構(gòu)進(jìn)行表示?？梢园l(fā)現(xiàn)，鄰接表和逆鄰接表實(shí)際上有一部分?jǐn)?shù)據(jù)時(shí)重合的，因此可以將兩個(gè)表合二為一，從而得到了所謂的十字鏈表。
十字鏈表
十字鏈表似乎很簡(jiǎn)單，只需要通過(guò)相同的頂點(diǎn)分別鏈向以該頂點(diǎn)為終點(diǎn)和起點(diǎn)的相鄰頂點(diǎn)即可。
但這并不是最優(yōu)的表示方式。雖然這樣的方式共用了中間的頂點(diǎn)存儲(chǔ)空間，但是鄰接表和逆鄰接表的鏈表節(jié)點(diǎn)中重復(fù)出現(xiàn)的頂點(diǎn)并沒(méi)有得到重復(fù)利用，反而是進(jìn)行了再次存儲(chǔ)。因此，上圖的表示方式還可以進(jìn)行進(jìn)一步優(yōu)化。
十字鏈表優(yōu)化后，可通過(guò)擴(kuò)展的頂點(diǎn)結(jié)構(gòu)和邊結(jié)構(gòu)來(lái)進(jìn)行正逆鄰接表的存儲(chǔ)：（下面的弧頭可看作是邊的箭頭那端，弧尾可看作是邊的圓點(diǎn)那端）
data：用于存儲(chǔ)該頂點(diǎn)中的數(shù)據(jù)；
firstin指針：用于連接以當(dāng)前頂點(diǎn)為弧頭的其他頂點(diǎn)構(gòu)成的鏈表，即從別的頂點(diǎn)指進(jìn)來(lái)的頂點(diǎn)；
firstout指針：用于連接以當(dāng)前頂點(diǎn)為弧尾的其他頂點(diǎn)構(gòu)成的鏈表，即從該頂點(diǎn)指出去的頂點(diǎn)；
邊結(jié)構(gòu)通過(guò)存儲(chǔ)兩個(gè)頂點(diǎn)來(lái)確定一條邊，同時(shí)通過(guò)分別代表這兩個(gè)頂點(diǎn)的指針來(lái)與相鄰頂點(diǎn)進(jìn)行鏈接：
tailvex：用于存儲(chǔ)作為弧尾的頂點(diǎn)的編號(hào)；
headvex：用于存儲(chǔ)作為弧頭的頂點(diǎn)的編號(hào)；
headlink 指針：用于鏈接下一個(gè)存儲(chǔ)作為弧頭的頂點(diǎn)的節(jié)點(diǎn)；
taillink 指針：用于鏈接下一個(gè)存儲(chǔ)作為弧尾的頂點(diǎn)的節(jié)點(diǎn)；
以上圖為例子，對(duì)于頂點(diǎn)A而言，其作為起點(diǎn)能夠到達(dá)頂點(diǎn)E。因此在鄰接表中頂點(diǎn)A要通過(guò)邊AE（即邊04）指向頂點(diǎn)E，頂點(diǎn)A的firstout指針需要指向邊04的tailvex。同時(shí)，從B出發(fā)能夠到達(dá)A，所以在逆鄰接表中頂點(diǎn)A要通過(guò)邊AB（即邊10）指向B，頂點(diǎn)A的firstin指針需要指向邊10的弧頭，即headlink指針。依次類推。
十字鏈表采用了一種看起來(lái)比較繁亂的方式對(duì)邊的方向性進(jìn)行了表示，能夠在盡可能降低存儲(chǔ)空間的情況下增加指針保留頂點(diǎn)之間的方向性。具體的操作可能一時(shí)間不好弄懂，建議多看幾次上圖，弄清指針指向的意義，明白正向和逆向鄰接表的表示。
10 總結(jié)
數(shù)據(jù)結(jié)構(gòu)博大精深，沒(méi)有高等數(shù)學(xué)的諱莫如深，也沒(méi)有量子力學(xué)的玄乎其神，但是其在計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域都具有強(qiáng)大的力量。本文試圖采用圖解的方式對(duì)九種數(shù)據(jù)結(jié)構(gòu)進(jìn)行理論上的介紹，但是其實(shí)這都是不夠的。
即便是簡(jiǎn)單的數(shù)組、棧、隊(duì)列等結(jié)構(gòu)，在實(shí)際使用以及底層實(shí)現(xiàn)上都會(huì)有許多優(yōu)化設(shè)計(jì)以及使用技巧，這意味著還需要真正把它們靈活的用起來(lái)，才能夠算是真正意義上的熟悉和精通。但是本文可以作為常見數(shù)據(jù)結(jié)構(gòu)的一個(gè)總結(jié)，當(dāng)你對(duì)某些結(jié)構(gòu)有些淡忘的時(shí)候，不妨重新回來(lái)看看。
