當前位置︰技術分享 > 技術參考 > 正文

常見數據結構和Javascript實現總結2019-08-13 13:42:51 | 編輯︰hely | 查看︰ | 評論︰0

做前端的同學不少都是自學成才或者半路出家,計算機基礎的知識比較薄弱,尤其是數據結構和算法這塊,所以今天整理了一下常見的數據結構和對應的Javascript的實現,希望能幫助大家完善這方面的知識體系。

做前端的同學不少都是自學成才或者半路出家,計算機基礎的知識比較薄弱,尤其是數據結構和算法這塊,所以今天整理了一下常見的數據結構和對應的Javascript的實現,希望能幫助大家完善這方面的知識體系。

1. Stack(棧)

 

 

Stack的特點是後進先出(last in first out)。生活中常見的Stack的例子比如一摞書,你最後放上去的那本你之後會最先拿走;又比如瀏覽器的訪問歷史,當點擊返回按鈕,最後訪問的網站最先從歷史記錄中彈出。

Stack一般具備以下方法︰

push︰將一個元素推入棧頂

pop︰移除棧頂元素,並返回被移除的元素

peek︰返回棧頂元素

length︰返回棧中元素的個數

Javascript的Array天生具備了Stack的特性,但我們也可以從頭實現一個 Stack類︰

 

 

2. Queue(隊列)

 

 

Queue和Stack有一些類似,不同的是Stack是先進後出,而Queue是先進先出。Queue在生活中的例子比如排隊上公交,排在第一個的總是最先上車;又比如打印機的打印隊列,排在前面的最先打印。

Queue一般具有以下常見方法︰

enqueue︰入列,向隊列尾部增加一個元素

dequeue︰出列,移除隊列頭部的一個元素並返回被移除的元素

front︰獲取隊列的第一個元素

isEmpty︰判斷隊列是否為空

size︰獲取隊列中元素的個數

Javascript中的Array已經具備了Queue的一些特性,所以我們可以借助Array實現一個Queue類型︰

 

 

Priority Queue(優先隊列)

Queue還有個升級版本,給每個元素賦予優先級,優先級高的元素入列時將排到低優先級元素之前。區別主要是enqueue方法的實現︰

 

 

測試一下︰

 

 

結果︰

 

 

3. Linked List(鏈表)

 

 

顧名思義,鏈表是一種鏈式數據結構,鏈上的每個節點包含兩種信息︰節點本身的數據和指向下一個節點的指針。鏈表和傳統的數組都是線性的數據結構,存儲的都是一個序列的數據,但也有很多區別,如下表︰

 

 

一個單向鏈表通常具有以下方法︰

size︰返回鏈表中節點的個數

head︰返回鏈表中的頭部元素

add︰向鏈表尾部增加一個節點

remove︰刪除某個節點

indexOf︰返回某個節點的index

elementAt︰返回某個index處的節點

addAt︰在某個index處插入一個節點

removeAt︰刪除某個index處的節點

單向鏈表的Javascript實現︰

 

 

4. Set(集合)

 

 

集合是數學中的一個基本概念,表示具有某種特性的對象匯總成的集體。在ES6中也引入了集合類型Set,Set和Array有一定程度的相似,不同的是Set中不允許出現重復的元素而且是無序的。

一個典型的Set應該具有以下方法︰

values︰返回集合中的所有元素

size︰返回集合中元素的個數

has︰判斷集合中是否存在某個元素

add︰向集合中添加元素

remove︰從集合中移除某個元素

union︰返回兩個集合的並集

intersection︰返回兩個集合的交集

difference︰返回兩個集合的差集

subset︰判斷一個集合是否為另一個集合的子集

使用Javascript可以將Set進行如下實現,為了區別于ES6中的Set命名為MySet︰

 

 

5. Hash Table(哈希表/散列表)

 

 

Hash Table是一種用于存儲鍵值對(key value pair)的數據結構,因為Hash Table根據key查詢value的速度很快,所以它常用于實現Map、Dictinary、Object等數據結構。如上圖所示,Hash Table內部使用一個hash函數將傳入的鍵轉換成一串數字,而這串數字將作為鍵值對實際的key,通過這個key查詢對應的value非常快,時間復雜度將達到O(1)。Hash函數要求相同輸入對應的輸出必須相等,而不同輸入對應的輸出必須不等,相當于對每對數據打上唯一的指紋。

一個Hash Table通常具有下列方法︰

add︰增加一組鍵值對

remove︰刪除一組鍵值對

lookup︰查找一個鍵對應的值

一個簡易版本的Hash Table的Javascript實現︰

 

 

6. Tree(樹)

 

 

顧名思義,Tree的數據結構和自然界中的樹極其相似,有根、樹枝、葉子,如上圖所示。Tree是一種多層數據結構,與Array、Stack、Queue相比是一種非線性的數據結構,在進行插入和搜索操作時很高效。在描述一個Tree時經常會用到下列概念︰

Root(根)︰代表樹的根節點,根節點沒有父節點

Parent Node(父節點)︰一個節點的直接上級節點,只有一個

Child Node(子節點)︰一個節點的直接下級節點,可能有多個

Siblings(兄弟節點)︰具有相同父節點的節點

Leaf(葉節點)︰沒有子節點的節點

Edge(邊)︰兩個節點之間的連接線

Path(路徑)︰從源節點到目標節點的連續邊

Height of Node(節點的高度)︰表示節點與葉節點之間的最長路徑上邊的個數

Height of Tree(樹的高度)︰即根節點的高度

Depth of Node(節點的深度)︰表示從根節點到該節點的邊的個數

Degree of Node(節點的度)︰表示子節點的個數

我們以二叉查找樹為例,展示樹在Javascript中的實現。在二叉查找樹中,即每個節點最多只有兩個子節點,而左側子節點小于當前節點,而右側子節點大于當前節點,如圖所示︰

 

 

一個二叉查找樹應該具有以下常用方法︰

add︰向樹中插入一個節點

findMin︰查找樹中最小的節點

findMax︰查找樹中最大的節點

find︰查找樹中的某個節點

isPresent︰判斷某個節點在樹中是否存在

remove︰移除樹中的某個節點

以下是二叉查找樹的Javascript實現︰

 

 

測試一下︰

 

 

打印結果︰

 

 

7. Trie(字典樹,讀音同try)

 

 

Trie也可以叫做Prefix Tree(前綴樹),也是一種搜索樹。Trie分步驟存儲數據,樹中的每個節點代表一個步驟,trie常用于存儲單詞以便快速查找,比如實現單詞的自動完成功能。 Trie中的每個節點都包含一個單詞的字母,跟著樹的分支可以可以拼寫出一個完整的單詞,每個節點還包含一個布爾值表示該節點是否是單詞的最後一個字母。

Trie一般有以下方法︰

add︰向字典樹中增加一個單詞

isWord︰判斷字典樹中是否包含某個單詞

print︰返回字典樹中的所有單詞

 

 

8. Graph(圖)

 

 

Graph是節點(或頂點)以及它們之間的連接(或邊)的集合。Graph也可以稱為Network(網絡)。根據節點之間的連接是否有方向又可以分為Directed Graph(有向圖)和Undrected Graph(無向圖)。Graph在實際生活中有很多用途,比如︰導航軟件計算最佳路徑,社交軟件進行好友推薦等等。

Graph通常有兩種表達方式︰

Adjaceny List(鄰接列表)︰

 

 

鄰接列表可以表示為左側是節點的列表,右側列出它所連接的所有其他節點。

和 Adjacency Matrix(鄰接矩陣)︰

 

 

鄰接矩陣用矩陣來表示節點之間的連接關系,每行或者每列表示一個節點,行和列的交叉處的數字表示節點之間的關系︰0表示沒用連接,1表示有連接,大于1表示不同的權重。

訪問Graph中的節點需要使用遍歷算法,遍歷算法又分為廣度優先和深度優先,主要用于確定目標節點和根節點之間的距離,

在Javascript中,Graph可以用一個矩陣(二維數組)表示,廣度優先搜索算法可以實現如下︰

 

 

測試一下︰

 

 

打印︰

 

 

最後,推薦大家使用Fundebug,一款很好用的BUG監控工具~

本文旨在向廣大前端同學普及常見的數據結構,本人對這一領域也只是初窺門徑,說的有差池的地方歡迎指出。也希望大家能打牢基礎,在這條路上走的更高更遠!

作者︰MudOnTire來源︰SegmentFault.com

上一篇︰民生銀行數據中台體系的構建與實踐 流式數據處理在百度數據工廠應用與實踐下一篇︰