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

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

[[243206]]

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

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

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

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

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

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

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

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

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

[[243207]]

數(shù)組

數(shù)組是最簡單、也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)。棧、隊列等其他數(shù)據(jù)結(jié)構(gòu)均由數(shù)組演變而來。

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

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

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

數(shù)組的基本操作

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

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

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

棧

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

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

棧的基本操作

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

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

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

隊列

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

隊列的基本操作

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

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

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

鏈表

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

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

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

鏈表內(nèi)部結(jié)構(gòu)

程序員面試：八大數(shù)據(jù)結(jié)構(gòu)及常見面試題

鏈表包括以下類型：

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

鏈表的基本操作：

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

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

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

圖

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

圖的類型

• 無向圖
• 有向圖

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

• 鄰接矩陣
• 鄰接表

常見圖遍歷算法

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

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

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

樹

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

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

樹數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語

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

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

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

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

• 面試中關(guān)于樹結(jié)構(gòu)的常見問題
• 求二叉樹的高度
• 在二叉搜索樹中查找第k個最大值
• 查找與根節(jié)點距離k的節(jié)點
• 在二叉樹中查找給定節(jié)點的祖先節(jié)點

字典樹

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

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

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

哈希表

哈希法(Hashing)是一個用于唯一標(biāo)識對象并將每個對象存儲在一些預(yù)先計算的唯一索引(稱為“鍵(key)”)中的過程。因此，對象以鍵值對的形式存儲，這些鍵值對的集合被稱為“字典”?？梢允褂面I搜索每個對象?；诠７ㄓ泻芏嗖煌臄?shù)據(jù)結(jié)構(gòu)，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表。哈希表通常使用數(shù)組實現(xiàn)。

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

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

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

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