瑞士計(jì)算機(jī)科學(xué)家Niklaus Wirth在1976年寫了一本書，名為《算法+數(shù)據(jù)結(jié)構(gòu)=編程》。

40多年后，這個(gè)等式仍被奉為真理。這就是為什么在面試過(guò)程中，需要考察軟件工程師對(duì)數(shù)據(jù)結(jié)構(gòu)的理解。

幾乎所有的問(wèn)題都需要面試者對(duì)數(shù)據(jù)結(jié)構(gòu)有深刻的理解。無(wú)論你是初入職場(chǎng)的新兵(剛從大學(xué)或者編程培訓(xùn)班畢業(yè))，還是擁有幾十年經(jīng)驗(yàn)的職場(chǎng)老鳥。

有些面試題會(huì)明確提及某種數(shù)據(jù)結(jié)構(gòu)，例如，“給定一個(gè)二叉樹。”而另一些則隱含在面試題中，例如，“我們希望記錄每個(gè)作者相關(guān)的書籍?dāng)?shù)量。”

即便是對(duì)于一些非常基礎(chǔ)的工作來(lái)說(shuō)，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是必須的。那么，就讓我們先從一些基本概念開始入手。

什么是數(shù)據(jù)結(jié)構(gòu)?

簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)是以某種特定的布局方式存儲(chǔ)數(shù)據(jù)的容器。這種“布局方式”決定了數(shù)據(jù)結(jié)構(gòu)對(duì)于某些操作是高效的，而對(duì)于其他操作則是低效的。首先我們需要理解各種數(shù)據(jù)結(jié)構(gòu)，才能在處理實(shí)際問(wèn)題時(shí)選取最合適的數(shù)據(jù)結(jié)構(gòu)。

為什么我們需要數(shù)據(jù)結(jié)構(gòu)?

數(shù)據(jù)是計(jì)算機(jī)科學(xué)當(dāng)中最關(guān)鍵的實(shí)體，而數(shù)據(jù)結(jié)構(gòu)則可以將數(shù)據(jù)以某種組織形式存儲(chǔ)，因此，數(shù)據(jù)結(jié)構(gòu)的價(jià)值不言而喻。

無(wú)論你以何種方式解決何種問(wèn)題，你都需要處理數(shù)據(jù)——無(wú)論是涉及員工薪水、股票價(jià)格、購(gòu)物清單，還是只是簡(jiǎn)單的電話簿問(wèn)題。

數(shù)據(jù)需要根據(jù)不同的場(chǎng)景，按照特定的格式進(jìn)行存儲(chǔ)。有很多數(shù)據(jù)結(jié)構(gòu)能夠滿足以不同格式存儲(chǔ)數(shù)據(jù)的需求。

常見的數(shù)據(jù)結(jié)構(gòu)

首先列出一些最常見的數(shù)據(jù)結(jié)構(gòu)，我們將逐一說(shuō)明：

•   數(shù)組
•   棧
•   隊(duì)列
•   鏈表
•   樹
•   圖
•   字典樹(這是一種高效的樹形結(jié)構(gòu)，但值得單獨(dú)說(shuō)明)
•   散列表(哈希表)

數(shù)組

數(shù)組是最簡(jiǎn)單、也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)。棧、隊(duì)列等其他數(shù)據(jù)結(jié)構(gòu)均由數(shù)組演變而來(lái)。下圖是一個(gè)包含元素(1，2，3和4)的簡(jiǎn)單數(shù)組，數(shù)組長(zhǎng)度為4。

 

 

每個(gè)數(shù)據(jù)元素都關(guān)聯(lián)一個(gè)正數(shù)值，我們稱之為索引，它表明數(shù)組中每個(gè)元素所在的位置。大部分語(yǔ)言將初始索引定義為零。

以下是數(shù)組的兩種類型：

•   一維數(shù)組(如上所示)
•   多維數(shù)組(數(shù)組的數(shù)組)

數(shù)組的基本操作

•   Insert——在指定索引位置插入一個(gè)元素
•   Get——返回指定索引位置的元素
•   Delete——刪除指定索引位置的元素
•   Size——得到數(shù)組所有元素的數(shù)量

面試中關(guān)于數(shù)組的常見問(wèn)題

•   尋找數(shù)組中第二小的元素
•   找到數(shù)組中第一個(gè)不重復(fù)出現(xiàn)的整數(shù)
•   合并兩個(gè)有序數(shù)組
•   重新排列數(shù)組中的正值和負(fù)值

棧

著名的撤銷操作幾乎遍布任意一個(gè)應(yīng)用。但你有沒有思考過(guò)它是如何工作的呢?這個(gè)問(wèn)題的解決思路是按照將最后的狀態(tài)排列在先的順序，在內(nèi)存中存儲(chǔ)歷史工作狀態(tài)(當(dāng)然，它會(huì)受限于一定的數(shù)量)。這沒辦法用數(shù)組實(shí)現(xiàn)。但有了棧，這就變得非常方便了。

可以把棧想象成一列垂直堆放的書。為了拿到中間的書，你需要移除放置在這上面的所有書。這就是LIFO(后進(jìn)先出)的工作原理。

下圖是包含三個(gè)數(shù)據(jù)元素(1，2和3)的棧，其中頂部的3將被最先移除：

 

 

棧的基本操作

•   Push——在頂部插入一個(gè)元素
•   Pop——返回并移除棧頂元素
•   isEmpty——如果棧為空，則返回true
•   Top——返回頂部元素，但并不移除它

面試中關(guān)于棧的常見問(wèn)題

•   使用棧計(jì)算后綴表達(dá)式
•   對(duì)棧的元素進(jìn)行排序
•   判斷表達(dá)式是否括號(hào)平衡

隊(duì)列

與棧相似，隊(duì)列是另一種順序存儲(chǔ)元素的線性數(shù)據(jù)結(jié)構(gòu)。棧與隊(duì)列的最大差別在于棧是LIFO(后進(jìn)先出)，而隊(duì)列是FIFO，即先進(jìn)先出。

一個(gè)完美的隊(duì)列現(xiàn)實(shí)例子：售票亭排隊(duì)隊(duì)伍。如果有新人加入，他需要到隊(duì)尾去排隊(duì)，而非隊(duì)首——排在前面的人會(huì)先拿到票，然后離開隊(duì)伍。

下圖是包含四個(gè)元素(1，2，3和4)的隊(duì)列，其中在頂部的1將被最先移除：

 

 

移除先入隊(duì)的元素、插入新元素

隊(duì)列的基本操作

•   Enqueue()?——?在隊(duì)列尾部插入元素
•   Dequeue()?——移除隊(duì)列頭部的元素
•   isEmpty()——如果隊(duì)列為空，則返回true
•   Top()?——返回隊(duì)列的第一個(gè)元素

面試中關(guān)于隊(duì)列的常見問(wèn)題

•   使用隊(duì)列表示棧
•   對(duì)隊(duì)列的前k個(gè)元素倒序
•   使用隊(duì)列生成從1到n的二進(jìn)制數(shù)

鏈表

鏈表是另一個(gè)重要的線性數(shù)據(jù)結(jié)構(gòu)，乍一看可能有點(diǎn)像數(shù)組，但在內(nèi)存分配、內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)插入和刪除的基本操作方面均有所不同。

鏈表就像一個(gè)節(jié)點(diǎn)鏈，其中每個(gè)節(jié)點(diǎn)包含著數(shù)據(jù)和指向后續(xù)節(jié)點(diǎn)的指針。 鏈表還包含一個(gè)頭指針，它指向鏈表的第一個(gè)元素，但當(dāng)列表為空時(shí)，它指向null或無(wú)具體內(nèi)容。

鏈表一般用于實(shí)現(xiàn)文件系統(tǒng)、哈希表和鄰接表。

這是鏈表內(nèi)部結(jié)構(gòu)的展示：

 

鏈表包括以下類型：

•   單鏈表(單向)
•   雙向鏈表(雙向)

鏈表的基本操作：

•   InsertAtEnd - 在鏈表的末尾插入指定元素
•   InsertAtHead - 在鏈接列表的開頭/頭部插入指定元素
•   Delete? - 從鏈接列表中刪除指定元素
•   DeleteAtHead - 刪除鏈接列表的第一個(gè)元素
•   Search? - 從鏈表中返回指定元素
•   isEmpty - 如果鏈表為空，則返回true

面試中關(guān)于鏈表的常見問(wèn)題

•   反轉(zhuǎn)鏈表
•   檢測(cè)鏈表中的循環(huán)
•   返回鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)
•   刪除鏈表中的重復(fù)項(xiàng)

圖

圖是一組以網(wǎng)絡(luò)形式相互連接的節(jié)點(diǎn)。節(jié)點(diǎn)也稱為頂點(diǎn)。 一對(duì)節(jié)點(diǎn)(x，y)稱為邊(edge)，表示頂點(diǎn)x連接到頂點(diǎn)y。邊可以包含權(quán)重/成本，顯示從頂點(diǎn)x到y(tǒng)所需的成本。

 

 

圖的類型

•   無(wú)向圖
•   有向圖

在程序語(yǔ)言中，圖可以用兩種形式表示：

•   鄰接矩陣
•   鄰接表

常見圖遍歷算法

•   廣度優(yōu)先搜索
•   深度優(yōu)先搜索

面試中關(guān)于圖的常見問(wèn)題

•   實(shí)現(xiàn)廣度和深度優(yōu)先搜索
•   檢查圖是否為樹
•   計(jì)算圖的邊數(shù)
•   找到兩個(gè)頂點(diǎn)之間的最短路徑

樹

樹形結(jié)構(gòu)是一種層級(jí)式的數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)(節(jié)點(diǎn))和連接它們的邊組成。 樹類似于圖，但區(qū)分樹和圖的重要特征是樹中不存在環(huán)路。

樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法，它可以提供解決問(wèn)題的有效存儲(chǔ)機(jī)制。

這是一個(gè)簡(jiǎn)單樹的示意圖，以及樹數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語(yǔ)：

 

 

•   Root - 根節(jié)點(diǎn)
•   Parent - 父節(jié)點(diǎn)
•   Child - 子節(jié)點(diǎn)
•   Leaf - 葉子節(jié)點(diǎn)
•   Sibling - 兄弟節(jié)點(diǎn)

以下是樹形結(jié)構(gòu)的主要類型：

•   N元樹
•   平衡樹
•   二叉樹
•   二叉搜索樹
•   AVL樹
•   紅黑樹
•   2-3樹

其中，二叉樹和二叉搜索樹是最常用的樹。

面試中關(guān)于樹結(jié)構(gòu)的常見問(wèn)題：

•   求二叉樹的高度
•   在二叉搜索樹中查找第k個(gè)最大值
•   查找與根節(jié)點(diǎn)距離k的節(jié)點(diǎn)
•   在二叉樹中查找給定節(jié)點(diǎn)的祖先節(jié)點(diǎn)

字典樹(Trie)

字典樹，也稱為“前綴樹”，是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)，對(duì)于解決字符串相關(guān)問(wèn)題非常有效。它能夠提供快速檢索，主要用于搜索字典中的單詞，在搜索引擎中自動(dòng)提供建議，甚至被用于IP的路由。

以下是在字典樹中存儲(chǔ)三個(gè)單詞“top”，“so”和“their”的例子：

 

 

這些單詞以頂部到底部的方式存儲(chǔ)，其中綠色節(jié)點(diǎn)“p”，“s”和“r”分別表示“top”，“thus”和“theirs”的底部。

面試中關(guān)于字典樹的常見問(wèn)題

•   計(jì)算字典樹中的總單詞數(shù)
•   打印存儲(chǔ)在字典樹中的所有單詞
•   使用字典樹對(duì)數(shù)組的元素進(jìn)行排序
•   使用字典樹從字典中形成單詞
•   構(gòu)建T9字典(字典樹+ DFS )

哈希表

哈希法(Hashing)是一個(gè)用于唯一標(biāo)識(shí)對(duì)象并將每個(gè)對(duì)象存儲(chǔ)在一些預(yù)先計(jì)算的唯一索引(稱為“鍵(key)”)中的過(guò)程。因此，對(duì)象以鍵值對(duì)的形式存儲(chǔ)，這些鍵值對(duì)的集合被稱為“字典”。可以使用鍵搜索每個(gè)對(duì)象�；�于哈希法有很多不同的數(shù)據(jù)結(jié)構(gòu)，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表。

哈希表通常使用數(shù)組實(shí)現(xiàn)。

散列數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個(gè)因素：

•   哈希函數(shù)
•   哈希表的大小
•   碰撞處理方法

下圖為如何在數(shù)組中映射哈希鍵值對(duì)的說(shuō)明。該數(shù)組的索引是通過(guò)哈希函數(shù)計(jì)算的。

 

 

面試中關(guān)于哈希結(jié)構(gòu)的常見問(wèn)題：

•   在數(shù)組中查找對(duì)稱鍵值對(duì)
•   追蹤遍歷的完整路徑
•   查找數(shù)組是否是另一個(gè)數(shù)組的子集
•   檢查給定的數(shù)組是否不相交

以上是在編程面試之前你應(yīng)該知曉的八大數(shù)據(jù)結(jié)構(gòu)。

標(biāo)簽： 大數(shù)據(jù) 搜索 搜索引擎 網(wǎng)絡(luò)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。