前端軟體工程工具箱:Data Structure 篇

Posted by kdchang on 2016-10-08

前言

事實上,要成為一個好的前端軟體工程師除了必須對於前端工程(Web 效能、build 工具、CSS layout 引擎)的部份有所了解外,也必須對於電腦科學的基礎知識有著堅實的基礎知識(資料結構、演算法、設計模式等)。在這系列的第一篇我們將來探討 JavaScript 常見資料結構。

JavaScript 實作常見資料結構

  1. Array
    陣列一連串有序串列,一般而言需要儲存相同類別的元素且長度固定,但在 JavaScript 中相對彈性。

  2. Linked List
    鏈結串列與陣列相比在新增刪除元素上更為便利,減少移動元素成本。

    function LinkedList() {
    const Node = function(value) {
    this.value = value;
    this.next = null;
    };

    let length = 0;
    let head = null;

    this.append = function(value) {};
    this.insert = function(position, value) {};
    this.removeAt = function(position) {};
    }
  3. Hash Table / Map
    { key: value } 所組成,在 ES6 中有提供原生 Map 資料結構。

    Hash Table 則是將 key 經過 hash function 產生 hash value 後進行對應。可以使用 linked list 、線性探查或更好的 hash function 來解決碰撞問題。

  4. Stack
    堆疊是一種遵循後進先出(LIFO)原則的有序集合。新增加或待刪除的元素都儲存在堆疊末尾,又稱堆疊頂部。

  5. Queue
    佇列是一種遵循先進先出(FIFO)原則的有序集合。新增加在尾部或待刪除的元素都儲存在佇列頂部,又稱堆疊頂部。

  6. Set
    與數學上概念相似,存有不重複的元素內容,[值, 值],ES6 中有提供原生 Set 資料結構。

  7. Tree(Binary Tree & Heap)

    • 樹(Tree)的定義
      樹是非線性資料結構,是由一個或多個節點所組成的資料結構。具有以下兩種特性:

      1. 具有一個特殊節點:樹根(root)
      2. 其餘節點被分為 n 個互斥(disjoint)集合 {T1, T2, ..., Tn},其中每一個集合也都是一個樹。我們稱 {T1, T2, ..., Tn} 為樹根的子樹(subtree)
    • 樹的基本名詞

      1. 分支度:每個節點所有子樹的個數
      2. 樹葉/終端節點:分支節點為零的節點
      3. 非終端節點:樹葉以外的所有節點
      4. 子節點:某節點所有子樹的樹根均為該節點的子節點
      5. 父節點:子節點的父親節點
      6. 兄弟節點:同一個父親的節點
      7. 祖先:節點中所有往上節點
      8. 樹的分支度:最大分支節點的分支度
      9. 階度:樹根為 1,往下都加 1
      10. 高度/深度:樹中擁有最大階度的節點階度
      11. 樹林:由 n 個互斥樹所組成的集合
      12. 左子右弟法
    • 二元樹
      二元樹是由一個有限節點所組成的集合,可能為空集合(不包含任何節點),或包含一個樹根及兩個互斥的二元樹,分別稱為左子樹和右子樹。

      1. 二元樹可以是空集合
      2. 二元樹中我們區分子樹的次序和子節點次序
      3. 二元樹的每一個節點分支分支度一定為 0 <= d <= 2
      4. 完滿二元樹:二元樹中每一階度都有最大的節點樹,即分支皆為 2,稱完滿二元樹。若有一棵完滿二元樹的深度 h,則它總節點為 2^h - 1
      5. 完整二元樹:與完滿二元樹唯一不同在於完整二元樹最高階度(最下面一層)沒有最大的節點數
    • 第一種二元樹追蹤

      1. 前序追蹤(preorder traversal):拜訪樹根 -> 追蹤左子樹 -> 追蹤右子樹。口訣:中左右
      2. 中序追蹤(inorder traversal):追蹤左子樹 -> 拜訪樹根 -> 追蹤右子樹。口訣:左中右
      3. 後序追蹤(postorder traversal):追蹤左子樹 -> 追蹤右子樹 -> 拜訪樹根。口訣:左右中
    • 第二種二元樹追蹤

      1. 深度優先(DFS):以頂點為起點開始,逐一檢視在頂點 V 相鄰的每一個頂點,若已拜訪過則忽略。若相鄰串列上有尚未拜訪過的頂點則印出頂點 W,接著對頂點 W 上相鄰節點進行深度優先搜尋,以此類推。適合使用堆疊實作
      2. 廣度優先(BFS):以頂點為起點開始,依序拜訪 V 相鄰的所有頂點,接著再拜訪與這些頂點相鄰的其他頂點,如此逐層(level-by-level)反覆下去。所用的起始頂點不同,搜尋結果頂點出現次序亦不相同,適合使用佇列實作。
    • 二分搜尋樹(Binary Search Tree)
      二元搜尋樹是一個二元樹,可能為空,若不為空,則具備:

      1. 每一個鍵值都是唯一,任何兩元素不會有相同鍵值
      2. 非空左子樹中所有節點的鍵值必定小於樹根的鍵值
      3. 非空右子樹中所有節點的鍵值必定大於樹根的鍵值
      4. 左子樹和右子樹也都是二元搜尋樹
      5. 二元搜尋樹的中序追蹤的結果為資料由小到大排序
    • 堆積(heap)
      heap 的資料結構是完整二元樹的應用,最常用途包括優先權佇列堆積排序法

      1. 最大堆積(max heap):是一棵完整二元樹,同時也是一棵最大樹。每一個節點的鍵值都不小於所有子節點鍵值
      2. 最小堆積(min heap):是一棵完整二元樹,同時也是一棵最小樹。每一個節點的鍵值都不大於所有子節點鍵值
    • 霍夫曼編碼(Huffman Code)
      為一種二元樹應用,主要目的是要縮短訊息的總長度,採用非固定長度的編碼方式,根據各別符號出現頻率來編碼,頻率較高者編碼長度較短

      1. 找出所有符號頻率
      2. 合併頻率最低的兩個,頻率相加
      3. 重複步驟 2,合併到只剩下一個為止
      4. 根據合併的關係,對每一次合併兩項皆配置一個位元,一個配置 0,另一個配置 1
    • 運算式
      運算式算是二元樹的綜合應用,一個運算式主要是由運算元(operands)、運算子(operators)和間隔符號(delimiters)所組成

      1. 運算處理原則:括號內先處理、優先權高先執行,例如先乘除後加減。優先權高的運算子則由結合性來決定是由左而右還是由右而左。相同優先權則由結合性來決定
      2. 運算子表示法:中序表示 a + b / 前序表示 +ab / 後序表示 ab+
      3. 表示法轉換:第一種方式:考慮運算子優先權及結合性將他們括號起來,再將運算子取代相對應括號,取代時運算子置左為前序,置右為後序。另外一種方式是:建立對應之二元樹,利用前序追蹤可以得前序表示法,利用後序追蹤可得後序表示法
      4. 前序和後序較中序為佳,這是因為前序與後序沒有左右結合性及優先權之考量,掃描一次即可求算結果。而前序與後序右以後續為好,因為後序使用的 stack 數目為一個,較前序少。最後要決定唯一的一棵二元樹(tree),需要中序及後序或是中序及前序兩種組合。
  8. Graph

    • 無向圖(Graph)
      無方向圖形,表示圖中邊的兩個頂點沒有次序關係,因此 (V1, V2)(V2, V1) 這兩個頂點對代表同一個邊。

      1. 完整圖
        具有 n 個頂點的無向途中,恰巧有 n*(n-1)/2

      2. 相鄰
        如果 (V1, V2) 是無向圖的一邊,我們就稱頂點 V1 與頂點 V2 相鄰

      3. 連結
        如果 (V1, V2) 是無向圖的一邊,我們就稱邊 (V1, V2) 是連結於點 V1, V2

      4. 子圖
        子圖是集合的概念,子圖 G’ 和原圖 G 滿足 V(G’) 屬於 V(G) 且 E(G’) 屬於 E(G)

      5. 簡單路徑
        指路徑中除起點與終點可能相同外,其他點頂點都是不同的

      6. 循環
        循環是一個簡單路徑,其起點與終點為同一個頂點

      7. 連通單元
        相連在一起的最大子圖稱為連通單元

    • 有向圖(Digraph)
      有方向的圖,在有向圖中,每一個邊用一個有序對 <v1, v2> 來表示,v1 是該邊的尾部,v2 是該邊的頭部。因此 <v1, v2><v2, v1> 表示不同邊。

      1. 完整圖
        具有 n 個頂點的無向途中,恰好有 n*(n-1) 個邊
      2. 相鄰
        如果 是有向圖的一邊,我們就稱頂點 v1 相鄰到頂點 v2
      3. 連結
        如果 是有向圖的一邊,我們就稱邊 連結於頂點 v1 和頂點 v2
      4. 路徑
        有向圖中從頂點到頂點的一條路徑是指,一連串由頂點所組成的連續有向序列,如 v1, v2, v3, …, v7,其中 , , 都是有向邊
      5. 強連通
        有向圖中,如果每個相異的頂點對 ,都有路經從 vi, 到 vj,同時也有另條路徑從 vj 到 vi 則有向圖我們稱為強連通
      6. 強連通單元
        強連通單元是只有向圖行中構成強連通的最大子圖
      7. 分支度
        一個頂點的分支度是指連接於該頂點上的邊個數。對於有向圖而言,可以細分為入分支度與出分支度。頂點 v 的入分支度是以頂點為箭頭的邊之個數,而出分支度則是以頂點 v 為箭尾的邊之個數。一頂點其入分支度與出分支度的和為其分支度
    • 圖形表示方式

      1. 相鄰矩陣
        若圖形 G = (V, E) 有 n 個頂點,圖形 G 可以使用 n n 的二維陣列表示,這個 n n 的矩陣記錄了圖形中任意兩個頂點是否相鄰,故稱為相鄰矩陣。如果頂點 vi 與 vj 之間有邊,則相鄰矩陣 (vi, vj) = 1,反之為 0

      2. 相鄰串列
        相鄰串列是以 n 個鏈結串列來取代相鄰矩陣的 n 個列。每個節點包含兩個欄位:1. 頂點(vertrx)2. 指標(link)

    • 圖形追蹤(Graph Traversal)

      1. 深度優先(DFS)
        類似樹的前序搜尋

      2. 廣度優先(BFS)
        類似樹的階度搜尋

      3. 展開樹(spanning tree)
        一個圖形的展開樹是以最少的邊連接所有頂點的最小子圖,而且不允許有循環在內。若相連圖形 G 有 n 個頂點,其展開樹具有下列特性:

      4. 只能用 G 中有的邊來建立展開樹 2. 恰好只用 n-1 個邊 3. 展開樹內的邊不可有循環存在 4. 任意兩頂點之間存在唯一的途徑

總結

以上介紹了前端工程工具箱:JavaScript 常見資料結構,在接下來的章節中我們將為大家打開前端工程的工具箱,介紹那些必須掌握的前端軟體工程知識。

延伸閱讀

  1. [資料結構] 概念與時間複雜度(Time Complexity)
  2. Data Structures in JavaScript
  3. Data Structures in JavaScript (ES5 and ES6)