本文轉(zhuǎn)載自公眾號“讀芯術(shù)”(ID：AI_Discovery)

就當是一場夢，醒了還是很悲痛，還是難以忘記被數(shù)據(jù)結(jié)構(gòu)折磨的慘痛。當你打開一本數(shù)據(jù)結(jié)構(gòu)和算法的教科書時，里面總是充滿復(fù)雜的數(shù)學(xué)，令人望而生畏。對于那些不太喜歡這門學(xué)科的人來說，這就是一場噩夢。

然而現(xiàn)實是，想要通過編程面試，必須求解算法，這就離不開數(shù)據(jù)結(jié)構(gòu)。別害怕，一旦了解了數(shù)據(jù)結(jié)構(gòu)，就會發(fā)現(xiàn)它們其實沒有看上去那么難了。

本文將會簡化和總結(jié)這些最基本的數(shù)據(jù)結(jié)構(gòu)，幫你搞定數(shù)據(jù)結(jié)構(gòu)。

[[323231]]

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

數(shù)據(jù)結(jié)構(gòu)是一種在計算機中組織數(shù)據(jù)以便高效使用的特殊方式：

“在計算機科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)組織、管理和存儲的格式，其允許高效地訪問和修改。更準確地說，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)值，數(shù)據(jù)值之間的關(guān)系，以及可應(yīng)用于數(shù)據(jù)的函數(shù)或操作的集合。”

我們必須將數(shù)據(jù)存儲到某種數(shù)據(jù)結(jié)構(gòu)中，選擇正確的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。

值得注意的是，數(shù)據(jù)結(jié)構(gòu)沒有好壞之分，每種數(shù)據(jù)結(jié)構(gòu)都有其優(yōu)缺點。有很多方法可以用來衡量一種數(shù)據(jù)結(jié)構(gòu)，這些也被稱為大O符號，這是衡量操作可伸縮性的一個指標。

現(xiàn)在來討論一下不同類型的數(shù)據(jù)結(jié)構(gòu)。

鏈表

鏈表的單位被稱為“節(jié)點”，一個節(jié)點包含一個值和一個指針(Pointer)。值只是一個數(shù)字，如12，而指針將該值鏈接到鏈中的下一個節(jié)點。這就是鏈表的連接部分，鏈表中的第一個節(jié)點被稱為頭，最后一個沒有指針的節(jié)點被稱為尾。

• 優(yōu)點：添加刪除節(jié)點很方便，只需要更改指針指向的地址即可。
• 缺點：不擅長檢索節(jié)點，盡管有索引或搜索功能。因為每個節(jié)點只知道相鄰節(jié)點的信息。

散列表(哈希表)

哈希映射或哈希表，也是一種關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。它類似于JavaScript中的對象和Python中的字典，在這種類型的數(shù)據(jù)結(jié)構(gòu)中，用戶為散列表提供一個單詞或者鍵，它將檢索定義或值。

其工作原理很像一個數(shù)組，該鍵通過名為“散列函數(shù)(哈希函數(shù))”的函數(shù)運行，該函數(shù)會找出鍵對應(yīng)的內(nèi)存地址。

不同之處在于，這些位置在內(nèi)存中不需要相鄰，而是可以在任意位置。因此，大小的增加不會存在問題。

但是，存在一個不同問題——根據(jù)使用的散列函數(shù)，兩個鍵可能會指向同一個內(nèi)存地址。這就是所謂的“沖突”，有很多種辦法可以解決這個問題，但是這一切都隱藏在函數(shù)內(nèi)。

• 優(yōu)點：正如已提及的，散列函數(shù)(哈希函數(shù))非常適合添加和讀取。
• 缺點：可能會導(dǎo)致鍵值沖突。

棧和隊列

這兩種結(jié)構(gòu)彼此非常相似，都是在數(shù)組的基礎(chǔ)上構(gòu)建了一些附加功能。

棧是后進先出的數(shù)據(jù)結(jié)構(gòu)。這類似于堆疊在一起的托盤，頂部的托盤在放入時是最后一個，在取出時是第一個。

將一個元素添加到棧頂稱為入棧，而從棧頂取出一個元素稱為出棧。每種語言都通過稱為調(diào)用堆棧的方式跟蹤已調(diào)用的函數(shù)。棧對于稱為深度優(yōu)先搜索(DFS)的算法非常重要。

另一方面，隊列是一種先進先出的結(jié)構(gòu)，就像公共汽車站的排隊，最后一個排隊的人最后上車。在末尾添加元素的操作稱為入隊，從隊首刪除元素稱為出隊。隊列被用于稱為廣度優(yōu)先搜索(BFS)的重要算法中。

• 優(yōu)點：兩種結(jié)構(gòu)在添加和刪除元素時都非常有效。
• 缺點：與其他的數(shù)據(jù)結(jié)構(gòu)相比，它們的用例數(shù)量有限。

數(shù)組

數(shù)組在所有的編程語言中都很常見，它是計算機內(nèi)存中連續(xù)的單元塊。

下面的示例表示了一個具有12個元素的整數(shù)數(shù)組。數(shù)組的索引從0開始，因此包含12個元素的數(shù)組具有從0到11的索引。

• 優(yōu)點：數(shù)組擅于檢索項，但前提是數(shù)組較小。
• 缺點：隨著數(shù)組規(guī)模不斷增大，會占用內(nèi)存中的其他項來運行。因此，數(shù)組的添加操作效率很低，因為可能需要將數(shù)組移動到內(nèi)存中的一個新位置以適應(yīng)其長度。

幸運的是，這種情況出現(xiàn)在高級語言中，比如JavaScript和Python。若在底層語言中，必須要事先聲明數(shù)組的大小。

圖和樹

計算機語言中有一個專門的部分叫做“圖論”，圖類似于鏈表有著指向其它節(jié)點的節(jié)點，只是這些指針被稱為“邊”，邊可以有權(quán)重或者被賦予編號。

有一種特殊的層圖稱為“樹”，其中的數(shù)據(jù)向一個方向拓展。它們可以用于指代很多事物，例如“家譜”，或者用于表示網(wǎng)絡(luò)。與數(shù)組、鏈表、棧和隊列這樣的線性數(shù)據(jù)結(jié)構(gòu)不同，樹是分層數(shù)據(jù)結(jié)構(gòu)。

• 優(yōu)點：樹提供了高效的插入和搜索能力，而且樹的數(shù)據(jù)格式非常靈活，允許以最小的工作量來移動子樹。
• 缺點：缺點在于，修改列表和檢索的時間長度為O(log n)。

入門算法求解離不開這些數(shù)據(jù)結(jié)構(gòu)，關(guān)鍵在于不要畏難。搏一搏，噩夢變美夢。祝你早日掌數(shù)據(jù)結(jié)構(gòu)。