這是好久之前的一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維的修訂版。之前那篇文章收到廣泛好評(píng),沒看過也沒關(guān)系,這篇文章會(huì)涵蓋之前的所有內(nèi)容,并且會(huì)舉很多代碼的實(shí)例,談?wù)勅绾问褂每蚣芩季S,并且給對(duì)于算法無從下手的朋友給一點(diǎn)具體可執(zhí)行的刷題建議。
首先,這里講的都是普通的數(shù)據(jù)結(jié)構(gòu)和算法,咱不是搞競(jìng)賽的,野路子出生,只解決常規(guī)的問題,以面試為最終目標(biāo)。另外,以下是我個(gè)人的經(jīng)驗(yàn)的總結(jié),沒有哪本算法書會(huì)寫這些東西,所以請(qǐng)讀者試著理解我的角度,別糾結(jié)于細(xì)節(jié)問題,因?yàn)檫@篇文章就是對(duì)數(shù)據(jù)結(jié)構(gòu)和算法建立一個(gè)框架性的認(rèn)識(shí)。
從整體到細(xì)節(jié),自頂向下,從抽象到具體的框架思維是通用的,不只是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法,學(xué)習(xí)其他任何知識(shí)都是高效的。
先說數(shù)據(jù)結(jié)構(gòu),然后再說算法。
一、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式
數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式只有兩種: 數(shù)組(順序存儲(chǔ))和鏈表(鏈?zhǔn)酱鎯?chǔ)) 。
這句話怎么理解,不是還有散列表、棧、隊(duì)列、堆、樹、圖等等各種數(shù)據(jù)結(jié)構(gòu)嗎?
我們分析問題,一定要有遞歸的思想,自頂向下,從抽象到具體。你上來就列出這么多,那些都屬于「上層建筑」,而數(shù)組和鏈表才是「結(jié)構(gòu)基礎(chǔ)」。因?yàn)槟切┒鄻踊臄?shù)據(jù)結(jié)構(gòu),究其源頭,都是在鏈表或者數(shù)組上的特殊操作,API 不同而已。
比如說 「隊(duì)列 」 、 「棧」 這兩種數(shù)據(jù)結(jié)構(gòu)既可以使用鏈表也可以使用數(shù)組實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn),就要處理擴(kuò)容縮容的問題;用鏈表實(shí)現(xiàn),沒有這個(gè)問題,但需要更多的內(nèi)存空間存儲(chǔ)節(jié)點(diǎn)指針。
「圖」 的兩種表示方法,鄰接表就是鏈表,鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速,并可以進(jìn)行矩陣運(yùn)算解決一些問題,但是如果圖比較稀疏的話很耗費(fèi)空間。鄰接表比較節(jié)省空間,但是很多操作的效率上肯定比不過鄰接矩陣。
「散列表」 就是通過散列函數(shù)把鍵映射到一個(gè)大數(shù)組里。而且對(duì)于解決散列沖突的方法,拉鏈法需要鏈表特性,操作簡(jiǎn)單,但需要額外的空間存儲(chǔ)指針;線性探查法就需要數(shù)組特性,以便連續(xù)尋址,不需要指針的存儲(chǔ)空間,但操作稍微復(fù)雜些。
「樹」 ,用數(shù)組實(shí)現(xiàn)就是「堆」,因?yàn)椤付选故且粋€(gè)完全二叉樹,用數(shù)組存儲(chǔ)不需要節(jié)點(diǎn)指針,操作也比較簡(jiǎn)單;用鏈表實(shí)現(xiàn)就是很常見的那種「樹」,因?yàn)椴灰欢ㄊ峭耆鏄?,所以不適合用數(shù)組存儲(chǔ)。為此,在這種鏈表「樹」結(jié)構(gòu)之上,又衍生出各種巧妙的設(shè)計(jì),比如二叉搜索樹、AVL 樹、紅黑樹、區(qū)間樹、B 樹等等,以應(yīng)對(duì)不同的問題。
了解 Redis 數(shù)據(jù)庫(kù)的朋友可能也知道,Redis 提供列表、字符串、集合等等幾種常用數(shù)據(jù)結(jié)構(gòu),但是對(duì)于每種數(shù)據(jù)結(jié)構(gòu),底層的存儲(chǔ)方式都至少有兩種,以便于根據(jù)存儲(chǔ)數(shù)據(jù)的實(shí)際情況使用合適的存儲(chǔ)方式。
綜上,數(shù)據(jù)結(jié)構(gòu)種類很多,甚至你也可以發(fā)明自己的數(shù)據(jù)結(jié)構(gòu),但是底層存儲(chǔ)無非數(shù)組或者鏈表, 二者的優(yōu)缺點(diǎn)如下 :
數(shù)組由于是緊湊連續(xù)存儲(chǔ),可以隨機(jī)訪問,通過索引快速找到對(duì)應(yīng)元素,而且相對(duì)節(jié)約存儲(chǔ)空間。但正因?yàn)檫B續(xù)存儲(chǔ),內(nèi)存空間必須一次性分配夠,所以說數(shù)組如果要擴(kuò)容,需要重新分配一塊更大的空間,再把數(shù)據(jù)全部復(fù)制過去,時(shí)間復(fù)雜度 O(N);而且你如果想在數(shù)組中間進(jìn)行插入和刪除,每次必須搬移后面的所有數(shù)據(jù)以保持連續(xù),時(shí)間復(fù)雜度 O(N)。
鏈表因?yàn)樵夭贿B續(xù),而是靠指針指向下一個(gè)元素的位置,所以不存在數(shù)組的擴(kuò)容問題;如果知道某一元素的前驅(qū)和后驅(qū),操作指針即可刪除該元素或者插入新元素,時(shí)間復(fù)雜度 O(1)。但是正因?yàn)榇鎯?chǔ)空間不連續(xù),你無法根據(jù)一個(gè)索引算出對(duì)應(yīng)元素的地址,所以不能隨機(jī)訪問;而且由于每個(gè)元素必須存儲(chǔ)指向前后元素位置的指針,會(huì)消耗相對(duì)更多的儲(chǔ)存空間。
二、數(shù)據(jù)結(jié)構(gòu)的基本操作
對(duì)于任何數(shù)據(jù)結(jié)構(gòu),其基本操作無非遍歷 + 訪問,再具體一點(diǎn)就是:增刪查改。
數(shù)據(jù)結(jié)構(gòu)種類很多,但它們存在的目的都是在不同的應(yīng)用場(chǎng)景,盡可能高效地增刪查改 。話說這不就是數(shù)據(jù)結(jié)構(gòu)的使命么?
如何遍歷 + 訪問?我們?nèi)匀粡淖罡邔觼砜?,各種數(shù)據(jù)結(jié)構(gòu)的遍歷 + 訪問無非兩種形式:線性的和非線性的。
線性就是 for/while 迭代為代表,非線性就是遞歸為代表。再具體一步,無非以下幾種框架:
數(shù)組遍歷框架,典型的線性迭代結(jié)構(gòu):
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 迭代訪問 arr[i]
}
}
鏈表遍歷框架,兼具迭代和遞歸結(jié)構(gòu):
/* 基本的單鏈表節(jié)點(diǎn) */
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代訪問 p.val
}
}
void traverse(ListNode head) {
// 遞歸訪問 head.val
traverse(head.next)
}
二叉樹遍歷框架,典型的非線性遞歸遍歷結(jié)構(gòu):
/* 基本的二叉樹節(jié)點(diǎn) */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}
你看二叉樹的遞歸遍歷方式和鏈表的遞歸遍歷方式,相似不?再看看二叉樹結(jié)構(gòu)和單鏈表結(jié)構(gòu),相似不?如果再多幾條叉,N 叉樹你會(huì)不會(huì)遍歷?
二叉樹框架可以擴(kuò)展為 N 叉樹的遍歷框架:
/* 基本的 N 叉樹節(jié)點(diǎn) */
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}
N 叉樹的遍歷又可以擴(kuò)展為圖的遍歷,因?yàn)閳D就是好幾 N 叉棵樹的結(jié)合體。你說圖是可能出現(xiàn)環(huán)的?這個(gè)很好辦,用個(gè)布爾數(shù)組 visited 做標(biāo)記就行了,這里就不寫代碼了。
所謂框架,就是套路。不管增刪查改,這些代碼都是永遠(yuǎn)無法脫離的結(jié)構(gòu),你可以把這個(gè)結(jié)構(gòu)作為大綱,根據(jù)具體問題在框架上添加代碼就行了,下面會(huì)具體舉例 。
-
算法
+關(guān)注
關(guān)注
23文章
4575瀏覽量
92339 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
569瀏覽量
40063 -
數(shù)組
+關(guān)注
關(guān)注
1文章
411瀏覽量
25858
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論