跳去內容

數據結構

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

數據結構sou3 geoi3 git3 gau3（當中構又可以做構kau3；英文：data structure）係指電腦內部組織數據嘅方法，設計嚟係為咗俾用家更加有效率噉使用數據嘅[1][2]。啲人討論一款數據結構嗰時，好多時會用抽象資料類型（ADT）嘅概念，即係唔諗實行方面嘅嘢住（唔諗例如隻程式語言會用咩陳述式，唔諗啲記憶體點樣儲住啲數據）－淨係定義啲抽象化嘅嘢，包括[3]:p. 7：

  • 款數據結構點樣由原始資料類型（好似係整數呀噉）砌出嚟；
  • 攞住一拃屬呢款結構嘅數據，可以做啲咩運算；或者
  • 可以點樣由拃數據度攞一件特定嘅數據出嚟；

... 呀噉。舉個具體例子，陣列（array）就係寫程式嗰陣成日用嘅一款數據結構。一條 1D 嘅陣列會包含若干個數值俾相同類型嘅變數，即係例如冚唪唥都係整數呀噉；噉樣即係條陣列指明係儲住咗咩數據。每件數據都會褦埋整數，整數會指明嗰件數據喺條陣列邊個位度，亦即係指明咗數據之間嘅關係。而常用於陣列身上嘅操作就有「指定一件啱類型嘅數據同指定個位，將件數據擺落去條陣列指定個位度」噉，即係指明攞啲數據可以攞嚟做乜[4][5]。

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

篇文跟住落嚟嘅內容，以 Python 做中心，而且假設睇嘅人已經有齊嗮運算理論、演算法同資料類型等嘅基礎知識。

陣列

[編輯]
内文：陣列
睇埋：程式迴圈

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

  • 包含最多 n 咁多件嘅數據；
  • 會有次序－每件數據掕若干個整數，表示佢喺條陣列嘅邊個位（位通常由 0 數起，因唔同嘅編程語言而異）；
  • 啲數據冚唪唥通常都屬同一隻類型 (因唔同嘅編程語言而異）；

好似下圖就係條 1D、10 件數據咁長嘅陣列嘅抽象圖解，幅圖冇指定啲數據係乜或者屬乜類型；叫條陣列做 a，條陣列喺 0 位件數據係 a[0]、喺 1 位件數據係 a[1]、喺 2 位件數據係 a[2]... 如此類推：

喺進階啲嘅使用當中，陣列仲可以有多過一個維度。想像家陣有條 m 咁多維（m > 1）嘅陣列，入面每件數據都會褦住 m 個整數，用呢啲整數表示件數據嘅位置，好似下圖裏面嗰條 2D 陣列噉[註 1]，嗌條陣列做 my_matrix，條陣列儲嘅數據類型係字符，噉

  • 喺 my_matrix[0][0] 嗰件數據係 A、
  • 喺 my_matrix[0][1] 嗰件數據係 N、
  • 喺 my_matrix[0][2] 嗰件數據係 N、

... 如此類推。3D 或者以上嘅陣列可以用同一道理想像[9]。

喺寫程式嗰陣，陣列成日都會配合迴圈（loop）嚟用[3]:Ch. 2，即係將某段運算，對陣列入面嘅每件數據逐件逐件行嗰段運算一次[註 2]，以下係一段 C♯ 例子碼：

// 假定 my_array 係條定義好咗嘅整數陣列...
int sum = 0;

for(int i = 0; i < (my_array.Length); i++) { // 開始嗰陣設 i 做 0 (i = 0)，如果 i < my_array 嘅長度就一路做下面嘅嘢，每次重複嗰陣都將 i 數值升 1 (i++)。

    sum = sum + my_array[i]; // sum 會加 my_array[i] 嘅值。

}
// 最後 sum 嘅數值會等如 my_array 入面嘅數冚唪唥加埋嘅總和。

串列相關

[編輯]
内文：串列 (抽象資料類型)
睇埋：集 (抽象資料類型)

串列（list）係同陣列好似嘅一種數據結構：喺 Python 程式語言裏面，串列可以話係陣列嘅廣義化；Python 串列都係儲住一拃數據，不過同陣列最主要嘅分別在於，串列冇特定嘅資料類型，可以（例如）一格裝住整數另一格裝住浮點數，而無論係咪 Python 都好，一條陣列會有指定資料類型，如果一條陣列講明咗係屬整數類型，條陣列就冇得攞去裝浮點數[10][11]。

用以下嘅 Python 碼做例子： 

my_list = [3, 6, 9, 12] # my_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, 4, 6, 9, 12, [4, 5], 4, 5, 'meh']。

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

import array as arr

my_array = arr.array("i", [3, 6, 9, 12]) # 建立 my_array 呢條陣列。
my_array.append('meh') # Python 會講：an integer is required。

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

鏈結串列

[編輯]
内文：鏈結串列
睇埋：鏈結數據結構同遞歸 (電腦科學)

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

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

嘅數據結構。例如鏈結串列（linked list）可以話係最出名嗰隻鏈結數據結構：一條鏈結串列會有若干件次序固定嘅數據，條鏈結串列當中每個位（node）都會有

  • 「件數據嘅數值係乜」同
  • 「件數據指住嘅下一件數據係邊件」（固定次序）

兩樣資訊。好似下圖噉：

想像

  • MakeList(element, list) 表示將 element 擺喺已經存在嘅鏈結串列 list 嘅最頂處；噉
  • MakeList(12, MakeList(99, MakeList(37, EmptyList))) 嘅碼可以表示「先後噉將 37、99 同 12 擺落 list 度」，得出上圖噉嘅鏈結串列（詳情可以睇吓遞歸）；

鏈結串列仲可以進階化帶出雙向鏈結串列（doubly linked list）。一條雙向鏈結串列嘅每個位都會褦住

  • 「打後嗰件數據係乜」同
  • 「打前嗰件數據係乜」，

加埋「件數據嘅數值係乜」，一共三樣資訊[3]:Ch. 3，好似下圖噉：

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

堆疊

[編輯]
内文：堆疊
睇埋：後入先出演算法

堆疊（stack）會儲住一拃數據，啲數據有明確嘅先後之分，當中拃數據係最後入嘅最先出（last in first out，LIFO）嘅，即係話嗰拃數據排最尾嗰件數據會優先噉被提取，就好似一疊洗好咗嘅碟噉，啲人想攞碟嗰陣會最先攞走最尾擺入疊碟嗰隻碟。可以對堆疊做嘅運算最基本有[3]:Ch. 3

  • push(element, stack)：將 element 擺落堆疊 stack 嘅最頂；
  • pop(stack)：剷走堆疊 stack 最頂嗰件數據；
  • isEmpty(stack)：如果堆疊 stack 係空嘅就出 1（真），否則就出 0（假）；

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

堆疊可以用多種方法實現，最常見嘅係用陣列或者鏈結串列。例如响 Python 入面，堆疊可以大致噉用對串列做嘅 append 同 pop 實現[13]： 

stack = [] # 整個空嘅串列，叫 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'] －好似堆疊噉，LIFO。

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

佇列

[編輯]
内文：佇列
睇埋：先入先出演算法

佇列（queue）可以話係堆疊嘅相反。一條佇列又係會儲住拃有明確嘅先後之分嘅數據，不過拃數據係最先入嘅最先出（first in first out，FIFO）嘅，即係話嗰拃排最先嗰件數據會優先噉被提取，就好似一班人喺度排隊噉，最先入隊嗰個會走先；可以對堆疊做嘅運算最基本有[3]:Ch. 3

  • push(element, queue)：將 element 擺落堆疊 queue 嘅最尾（enqueue）；
  • pop(queue)：剷走堆疊 queue 最前嗰件數據（dequeue）；
  • isEmpty(queue)：如果堆疊 queue 係空嘅就出 1（真），否則就出 0（假）；

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

佇列另一樣同堆疊相似嘅嘢係，响 Python 入面，佇列又係可以大致噉用對串列做嘅 append 同 pop 實現[15]： 

queue = []  # 整個空嘅串列，叫 queue

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

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

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

print(queue) # 會出 ['b', 'c'] －好似佇列噉，FIFO。

喺實際應用上，佇列可以攞嚟幫等緊做嘅嘢「排隊」－俾部電腦知有啲咩數據等緊要處理，並且將啲排隊先嘅數據優先處理，呢種做法喺好多電腦系統當中都會用到[16]。進階啲嘅佇列，仲可能會（例如）同每件數據掕返個數表示嗰件數據「有幾重要」－重要嘅數據有可能唔使排隊，得到優先處理[3]:Ch. 8.2。

關聯陣列

[編輯]
内文：關聯陣列

關聯陣列（associative array / dictionary）係種專攞嚟儲住名-值對（key-value pair）嘅數據結構，包括 Python 在內等嘅多種程式語言都支援。一對名-值對會將每件數據都褦個獨特嘅名俾佢，想像一本字典，會紀錄咗一大拃字（名；key），當中每隻字都會褦住段字表示佢嘅意思（值；value）[17][18]。

或者想像好似下圖噉嘅數據，有一對對嘅「人名（key）-電話號碼（value）」配對：

關聯陣列常用嘅運算有（啲例子用嘅係 Python 程式語言）[17]：

  • 建立關聯陣列，想像家陣創建一條關聯陣列（my_dict）用嚟講明羅馬數字點樣對應電腦能夠直接處理嘅數－I 對應 1，V 對應 5，X 對應 10（詳情睇羅馬數字嘅嘢），
    my_dict = {'I': 1, 'V': 5, 'X': 10}
  • 指定個名，攞個名對應嗰個值，想像繼續用上面嘅關聯陣列 my_dict－
    print(my_dict['I']) # 呢行碼會出「1」呢個整數，因為 my_dict 講咗 'I' 對應 1。

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

print(my_dict['X']) # 呢行碼會出「10」呢個整數，因為 my_dict 講咗 'X' 對應 10。
  • 加新嘅名-值對；
  • 剷走已有嘅名-值對；

... 等等。

樹型數據

[編輯]
内文：樹 (抽象資料類型)
睇埋：二元搜尋樹同樹狀圖

樹（tree）係一種好有用嘅數據結構，重點特性係拃數據有「高低層」之分。一樖數據樹都係會[3]:Ch. 6

  • 有若干粒節點（node），每粒節點都儲住咗件數據；而且
  • 啲節點分層－除咗做起始點嗰粒節點（根節點；root）之外，每粒節點有一粒（而且頂櫳一粒）母節點（parent；指喺嗰粒節點上面，連住嗰粒節點嘅另一粒節點）；
  • 一粒節點可以有若干粒子節點（child / children）；

於是就形成拃節點喺起始點嗰度一層層噉每層都分叉嘅樣，而是但攞粒根節點以外嘅節點，粒節點同根節點之間都有條獨一無二嘅路徑連住兩點。喺電腦科學上，啲人通常會將數據樹畫做樹狀圖噉嘅樣，根節點畫喺最頂，根節點嘅子節點會並排噉列喺根節點下面，根節點嘅子節點嘅子節點會並排噉列喺下一層... 如此類推。好似下面幅圖噉，幅圖表示緊樖數據樹，紅色嗰點係樖數據樹嘅根節點，根節點下一層嘅係佢啲子節點，再下一層嗰啲係根節點嘅子節點嘅子節點... 如此類推，而每粒節點入面嗰個整數就係粒節點裝住嗰件數據[19]。

對樹型數據可以做嘅簡單運算有以下呢啲[3]:Ch. 6：

  • EmptyTree，出一樖空嘅數據樹；
  • MakeTree(v, l, r)，建立一樖二元樹（binary tree；指樖樹每粒節點頂攏得兩粒子節點，好似下圖噉[20]），根節點係 v，由兩樖二元樹 l 同 r 組成；
  • Leaf(v) = MakeTree(v, EmptyTree, EmptyTree)－建立一樖得一粒節點 v 嘅二元樹；
  • isEmpty(t)，如果 t 係樖空嘅數據樹，噉 isEmpty(t) 會出 1（真），否則就出 0（假）；

建立一樖有咁上下複雜嘅二元樹可以用類似噉嘅碼（睇返遞歸）：

t = MakeTree(8, MakeTree(3,Leaf(1),MakeTree(6,EmptyTree,Leaf(7))), MakeTree(11,MakeTree(9,EmptyTree,Leaf(10)),MakeTree(14,Leaf(12),Leaf(15))))

喺實際應用上，樹呢款數據結構成日畀人攞嚟儲住一啲有關決策嘅資訊：想像家吓有人工智能研究者想教電腦玩遊戲，想部電腦識捉國際象棋；佢可以（簡化講）教部電腦將捉國際象棋嘅過程想像做一樖數據樹－捉國際象棋可以想像成喺每個時間點（層）度揀其中一個可能選擇（每粒節點表示其中一個可能選擇），跟住再行去下一個時間點（去下一層）嗰度，而每粒節點入面嗰件數據表示「揀呢個選擇嘅效益」。有關數據樹嘅具體應用例子，可以睇吓蒙地卡羅樹搜尋（MCTS）呢種演算法[21]。

圖型數據

[編輯]
内文：圖 (抽象資料類型)
睇埋：圖論同搵路

圖（graph）係款進階嘅數據結構。响最基本上，一幅圖會有[3]:Ch. 11

  • 若干粒節點，而且
  • 每粒節點都最少有一條邊（edge）連去另外一粒節點嗰度[註 4]；
  • 每粒節點通常仲會褦住若干件數據，一條邊都可以帶有數據；

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

一個電腦程式可以用 2D 陣列等嘅方法實現圖數據[3]:Ch. 11，即係創建返條 2D 陣列 adj，用陣列啲格仔入面嘅數表示啲節點之間嘅邊，例如 adj[i][j] 係 0 嘅話就表示節點 i 同節點 j 之間並冇邊連住[註 5]。電腦可以對圖數據做多種有用嘅運算，好似係[23]：

  • adjacent(G, x, y)：攞 G 呢幅圖以及 x 同 y 呢兩粒節點，如果 x 同 y 係相鄰嘅，adjacent(G, x, y) 會出 1（真），否則就出 0（假）；
  • neighbors(G, x)：攞 G 呢幅圖以及 x 呢粒節點，output 俾出嗮所有同 x 相鄰嘅節點；

... 呀噉。

喺實用上，啲人好興攞圖數據表示一啲空間性質嘅嘢，例如想像整一幅圖數據表示粵港澳地區嘅地圖，每粒節點表示一座重要城市，都褦住件數據表示座城市嘅名同位置（廣州、香港、珠海呀噉），而兩粒節點之間有邊就表示嗰兩座城市之間有高速公路可以直達，每條邊都褦住個數表示條路有幾長；至於具體啲嘅應用，可以睇吓搵路（pathing；下圖係用迪卡斯特拉演算法搵路嘅圖例）呢種喺電子遊戲 AI 上成日都會用到嘅演算法[24]。

註釋

[編輯]
  1. ↑ 2D 嘅陣列成日畀人嗌做「矩陣」。
  2. ↑ 條陣列好多時都會係事先排好咗嘅，即係例如事先做咗「將條陣列裝住嗰啲數由細至大排」嘅工作。
  3. ↑ 陣列當中嘅一件數據可以用
    output = array[n];
    噉嘅方法嚟輕易讀取。
  4. ↑ 進階嘅應用仲可以會諗到「一對節點之間可以有多過一條邊」嘅情況。
  5. ↑ 是但攞對 ij 嚟睇，adj[i][j] == adj[j][i] 都會係真。

睇埋

[編輯]

文獻

[編輯]

攷

[編輯]
  1. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.
  2. ↑ Black, Paul E. (15 December 2004). "data structure" (PDF). In Pieterse, Vreda; Black, Paul E. (eds.). Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. Retrieved 2018-11-06.
  3. ↑ 3.00 3.01 3.02 3.03 3.04 3.05 3.06 3.07 3.08 3.09 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.
  4. ↑ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507-512.
  5. ↑ Seymour, Lipschutz (2014). Data structures (Revised first ed.). New Delhi, India: McGraw Hill Education.
  6. ↑ 8 Common Data Structures every Programmer must know. Towards Data Science.
  7. ↑ data structure. Encyclopedia Britannica.
  8. ↑ Python Arrays. GeeksForGeeks.
  9. ↑ 9.0 9.1 Lecture Notes, Chapter #6, Arrays (PDF).
  10. ↑ Array vs. List in Python – What's the Difference?.
  11. ↑ Python Tuples: When to Use Them Over Lists 互聯網檔案館嘅歸檔，歸檔日期2022年8月14號，.. Towards Data Science.
  12. ↑ Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. pp. 239-303.
  13. ↑ Stack in Python. GeeksForGeeks.
  14. ↑ Backtracking 互聯網檔案館嘅歸檔，歸檔日期2022年1月21號，..
  15. ↑ Queue in Python. GeeksForGeeks.
  16. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd Edition. MIT Press and McGraw-Hill, 2001. Section 10.1: Stacks and queues, pp. 200-204.
  17. ↑ 17.0 17.1 Collins, Graham; Syme, Donald (1995). "A theory of finite maps". Higher Order Logic Theorem Proving and Its Applications. Lecture Notes in Computer Science. 971: 122-137.
  18. ↑ Andersson, Arne (1989). "Optimal Bounds on the Dictionary Problem". Proc. Symposium on Optimal Algorithms. Lecture Notes in Computer Science. Springer Verlag. 401: 106-114.
  19. ↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.
  20. ↑ Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620.
  21. ↑ Monte Carlo Tree Search. Towards Data Science.
  22. ↑ Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". Algorithm Design and Applications. Wiley. pp. 355-364.
  23. ↑ See, e.g. Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240-282.
  24. ↑ Millington, I. (2019). AI for Games. CRC Press. Ch. 4.

拎

[編輯]
維基同享有多媒體嘅嘢：
Data structures
由「https://zh-yue.wikipedia.org/w/index.php?title=數據結構&oldid=2181972」收