數據結構

一個陣列嘅抽象圖解；個陣列嘅名叫 Data，2D，而 Data[1][3] 表示 Data 第 1 行第 3 格嗰個位件數據（由 0 開始數起）。

數據結構（粵拼：sou3 geoi3 git3 gau3；英文：data structure）係指電腦內部組織數據嘅方法，用嚟俾用家更有效率噉使用數據。精確啲噉講嘅話，數據結構分好多唔同款，一款數據結構會指明嗮以下嘅資訊：

• 款結構會儲住咩數據、
• 儲住咗嘅每件數據之間成乜嘢關係、同埋
• 屬呢種數據結構嘅數據可以攞啲咩算子計或者擺入啲乜嘢函數嗰度。

舉個具體例子，陣列（array）就係一種寫程式嗰陣成日都用嘅數據結構，一個 1D 嘅陣列會包含若干個相同類型嘅變數嘅數值，即係例如冚唪唥都係整數（儲住咩數據）；會指明每個數喺邊個位嗰度，每件數據都掕咗個整數，表示佢喺個陣列邊個位（數據之間嘅關係）；而常用於陣列身上嘅工作就有「指定一件啱類型嘅數據，將件數據加落去個陣列最尾度」噉（可以攞嚟做啲乜）。

除咗陣列之外，數據結構仲有好多款，唔同嘅數據結構各有自己嘅優缺點，一個有返咁上下複雜嘅電腦程式通常會用到多種唔同嘅數據結構，而好多有用嘅演算法都往往會需要 input 數據屬某種指定嘅數據結構。因為噉，有關數據結構嘅知識响電腦科學研究以及電腦程式編寫等嘅工作上不可或缺。

篇文跟住落嚟嘅內容，假設睇嘅人已經具備有關演算法同資料類型嘅基礎知識。

陣列

陣列（array）係最常用最基本嘅數據結構之一：一條陣列好多時會掕住個整數 n 表示佢嘅大細－大細指「裝到幾多件數據」；一條陣列會

• 包含最多 n 咁多件嘅數據；
• 會有次序－每件數據掕若干個整數，表示佢喺條陣列嘅邊個位（0 做最頭嗰個位）；
• 啲數據冚唪唥都屬同一隻類型；

好似下圖就係一個 1D、11 件數據咁長嘅陣列嘅抽象圖解，條陣列喺 0 位件數據係 M、喺 1 位件數據係 e... 如此類推：

喺進階啲嘅使用當中，陣列仲可以有多過一個維度。

編程實踐

喺寫程式嗰陣，常用嚟做喺陣列身上嘅作業有以下呢啲（啲碼係用 Python 寫嘅）：

• 初始化，講明條陣列 n 係幾多、啲數據屬咩類型... 等嘅資訊，例：

  import array as arr
  
  x = arr.array("i", [3, 6, 9, 12]) # 定義 x 呢條陣列，條陣列屬整數類型 ("i")，有 4 嚿數據 [3, 6, 9, 12]。
  

• 攞條陣列入面某件數據嚟用，例：

  y = x[0] # y 嘅值會變成同 x 第 0 嚿數據一樣，即係 y 嘅值會變成 3。
  

• 俾出個數值表示「條陣列有幾長」，例：

  y = len(x) # y 嘅值會變成 x 嘅「長度」，x 有 4 件數據，所以 y 嘅值會變成 4。
  

• 加數據落條陣列度，例：

  x.append(4) # 將 4 加入去 x 度，x 會變成 [3, 6, 9, 12, 4]。
  

• 將數據由條陣列度清走，例：

  x.pop(4) # 將 x 入面第 4 嚿數據剷走，即係會變返成 [3, 6, 9, 12]。
  

... 呀噉。

抽象資料類型

串列

串列（list）係種抽象資料類型，同陣列好相似：陣列同串列兩者最主要嘅分別在於，串列冇特定嘅資料類型，可以（例如）一格裝整數另一格裝浮點數，而一個陣列有指定資料類型，一個講明咗係屬整數類型嘅陣列冇得攞去裝浮點數；例如以下呢段 Python 碼噉：

my_list = [3, 6, 9, 12] # list 係一條串列，[3, 6, 9, 12]

empty_list = [] # 創建一條空嘅串列，叫 empty_list

my_list.append([4,5]) # 將 [4,5] 當一嚿數據噉加落去，即係會變成 [3, 6, 9, 12, [4, 5]]。

my_list.extend([4,5]) # 將 4 同 5 分開噉加落去，即係會變成 [3, 6, 9, 12, [4, 5], 4, 5]。

my_list.insert(1, 4) # 將 4 加落去第 1 個位度，即係會變成 [3, 4, 6, 9, 12, [4, 5], 4, 5]。

一段串列唔使格格都裝同一種類型嘅數據，所以以下噉嘅 Python 碼係行得通嘅：

my_list.append('meh') # 將 'meh' 呢段字串加落去 my_list 度，my_list 會變成 [3, 6, 9, 12, 'meh']。

但好似以下噉嘅碼就會有問題：

x = arr.array("i", [3, 6, 9, 12]) 
x.append('meh')

－段碼講好咗，x 係個整數（"i"）陣列，'meh' 唔係整數，所以呢段碼會搞到個程式出錯。

順帶一提，响揀用陣列定串列嗰陣，「用緊乜程式語言」係其中一個重要考量－例如 Python 就支援串列多過陣列，串列可以直接用，但陣列就要引入特定嘅函式庫（NumPy）先至用得。亦都可以睇吓 Python 嘅多元組（tuple）數據結構，Python 多元組建立咗之後就唔准改，不過好處係比較慳記憶體。

關聯陣列

關聯陣列（associative array / dictionary）係種專攞嚟儲住名-值對（key-value pair）嘅數據結構。一對名-值對會將每件數據都掕個獨特嘅名俾佢，想像一本字典，會紀錄咗一大拃字（名），當中每隻字都會掕住段字表示佢嘅意思（值）。舉個具體例子，想像以下嘅 Python 碼，建立一個關聯陣列嚟將羅馬數字轉換做數：

my_dict = {'I': 1, 'V': 5, 'X': 10} # 創建一個關聯陣列，I 對應 1，V 對應 5，X 對應 10（詳情睇羅馬數字嘅嘢）。

print(my_dict['I']) # 呢行碼會 output「1」呢個整數，因為 my_dict 講咗 'I' 對應 1。

print(my_dict['V']) # 呢行碼會 output「5」呢個整數，因為 my_dict 講咗 'V' 對應 5。

print(my_dict['X']) # 呢行碼會 output「10」呢個整數，因為 my_dict 講咗 'X' 對應 10。

一個關聯陣列入面啲名-值對可以完全唔使用任何數，例如：

my_dict = {'First': 'Python', 'Second': 'Java', 'Third': 'C++'}

print(my_dict['First']) # 呢行碼會 output「Python」，因為 my_dict 講咗 'First' 對應 'Python'。

關聯陣列喺編程上好使好用－可以攞嚟指定「呢隻呢隻值嘅數據，通通轉換成嗰隻嗰隻值」噉嘅資訊。

堆疊

堆疊（stack）會儲住一拃數據，當中拃數據係最後入嘅最先出（last in first out，LIFO）嘅，即係話嗰拃數據有次序之分，當中排最尾嗰件數據會優先噉被提取，就好似一疊洗好咗嘅碟噉，最尾擺入疊碟嗰隻碟會最先俾人攞走；可以對堆疊做嘅運算最基本有

• push（擺件數據落堆疊上面）
• pop（刪除堆疊最上面嗰件數據）

... 呀噉。可以睇下圖嘅圖解。

响 Python 入面，堆疊可以輕易噉用對串列做嘅 append 同 pop 實現：

stack = []

# 下面三行碼將 'a'、'b' 同 'c' 加落去 stack 度。
stack.append('a')
stack.append('b')
stack.append('c')

print(stack) # 會出 ['a', 'b', 'c']

stack.pop() # 攞走 stack 最尾嗰件數據。

print(stack) # 會出 ['a', 'b']

堆疊喺回溯法（backtracking）上成日用－例如想像家陣有個人工智能程式喺度行迷宮，個程式要一路記住自己行過嘅位置，一去到掘頭路就返轉頭，即係話「過去嘅位置」會成一個堆疊，要返轉頭行每一步嗰陣就將最近嗰件數據（個堆疊最頂嗰件）攞走。睇埋遞歸。

隊列

隊列（queue）可以話係堆疊嘅相對。一條隊列會儲住一拃數據，當中拃數據係最先入嘅最先出（first in first out，FIFO）嘅，即係話嗰拃數據有次序之分，當中排最先嗰件數據會優先噉被提取，就好似一班人喺度排隊噉；可以對堆疊做嘅運算最基本有

• enqueue（擺件數據落隊列最後）
• dequeue（刪除堆疊最先嗰件數據）

... 呀噉。可以睇下圖嘅圖解。

响 Python 入面，隊列又係可以用對串列做嘅 append 同 pop 實現：

stack = []

# 下面三行碼將 'a'、'b' 同 'c' 加落去 stack 度。
stack.append('a')
stack.append('b')
stack.append('c')

print(stack) # 會出 ['a', 'b', 'c']

stack.pop(0) # 攞走 stack 最頭（位於第 0 個格）嗰件數據。

print(stack) # 會出 ['b', 'c']

喺實際應用上，隊列最常見嘅用途嚟攞嚟「排隊」－俾部電腦知有啲咩數據等緊要處理，並且將啲排隊先嘅數據優先處理，呢種做法喺好多電腦系統當中都會用到。

圖型數據

一幅圖型數據（graph data）會有

• 若干個節點，而且
• 每個節點都最少有一條邊（edge）連去另外一個節點嗰度，

如果有兩個節點之間有條邊連住，佢哋就算係相鄰（adjacent）嘅；一幅圖數據嘅大細可以由節點嘅數量以及節點之間嘅邊嘅數量嚟反映。好似係下圖噉，下圖係一幅有 6 個節點嘅圖數據，當中節點 1 同節點 2 之間有連結（可以由節點 1 行去節點 2 或者相反）、節點 1 同節點 5 之間有連結（可以由節點 1 行去節點 5 或者相反）... 如此類推。

一個電腦程式可以對圖數據做多種有用嘅運算，例如：

• adjacent(G, x, y)：攞 G 呢幅圖以及 x 同 y 呢兩個節點，如果 x 同 y 係相鄰嘅，adjacent(G, x, y) 會出 1（真）；
• neighbors(G, x)：攞 G 呢幅圖以及 x 呢個節點，output 俾出嗮所有同 x 相鄰嘅節點；
• add_vertex(G, x)：攞 G 呢幅圖，加 x 呢個節點落去；

... 呀噉。有關圖數據嘅應用，可以睇吓搵路（pathfinding）呢種喺遊戲人工智能上成日都會用到嘅演算法。

樹型數據

樹（tree）係一種同圖好相似嘅數據結構，爭在拃數據有高低層之分（好似一幅樹狀圖噉）。一樖數據樹都係會

• 有若干個節點（node），而且
• 啲節點分層，除咗做起始點嗰個節點（根節點；root）之外，每個節點有一個（而且頂櫳一個）母節點（parent；指喺嗰個節點上面，連住嗰個節點嘅另一個節點）；

於是就形成拃節點喺起始點嗰度一層層噉每層都分叉嘅樣。

好似下圖噉，紅色 2 嗰點係根節點，而根節點下有一層層嘅節點，每個節點都有個母節點（例如 7 嗰點嘅母節點就係個根節點）。喺實際應用上，樹嘅數據結構可以攞嚟儲住一啲有關決策嘅資訊－決策呢家嘢可以想像成喺每個時間點（層）嗰度揀一個可能選擇（節點），再行去下一個時間點（去下一層）嗰度。

例如蒙地卡羅樹搜尋（Monte Carlo tree search）呢種用嚟教電腦玩遊戲嘅演算法噉，就用咗樹嘅數據結構嚟思考玩遊戲嗰陣嘅決策。

鏈結數據結構

鏈結數據結構（linked data structure）係一大類嘅數據結構，泛指一啲包含

• 一拃節點，每粒節點都係一件數據；
• 節點之間有參照連住，每件表示「下一粒節點喺邊」呢樣資訊；

嘅數據結構。例如鏈結串列（linked list）可以話係最出名嗰隻鏈結數據結構：一條鏈結串列會有若干件次序固定嘅數據，條鏈結串列當中每個位（node）都會有「件數據嘅數值係乜」、「件數據指住嘅下一件數據係邊件」同「件數據嘅前一件數據係邊件」（固定次序；下圖噉）嘅資訊。

一位用家搜尋一條鏈結串列嗰陣一定要焗住跟條串列個次序（或者前後掉轉）噉嚟搜尋，冇得話例如（好似陣列噉）隨機噉揀是但一件數據嚟讀取。不過鏈結串列嘅好處係，可以容易噉由拃數據當中攞走其中一件而唔使重新排過嗮拃數據－一個陣列攞走咗其中一件再排過就要改嗮後面嗰啲數據嘅位置數值。

例如以下嘅 Python 碼會建立一件鏈結串列物件（睇埋物件導向編程）：

class Node:
    # Node 係個物件類別
    def __init__(self, data):
        self.data = data  # Node 裝住件數據 (data)
        self.next = None  # 亦帶有 next（下一個 Node 係乜），呢個值初始化嗰陣係 None

睇埋

• 數據結構一覽
• 電腦數據
• 資料類型
• 雜湊表
• 代數結構
• 物件導向
• 序列化

文獻

• Peter Brass, (2008). Advanced Data Structures, Cambridge University Press, ISBN 978-0521880374
• Donald Knuth, (1997). The Art of Computer Programming, Vol. 1. Addison-Wesley, 3rd Ed, ISBN 978-0201896831
• Dinesh Mehta and Sartaj Sahni, (2004). Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, ISBN 1584884355
• Niklaus Wirth, (1985). Algorithms and Data Structures, Prentice Hall, ISBN 978-0130220059

拎

• Introduction to Data Structures. GeeksForGeeks.
• Data Structures. GeeksForGeeks.
• Data structures course.
• An Examination of Data Structures from .NET perspective.
• Schaffer, C. Data Structures and Algorithm Analysis.