數據結構

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

數據結構（粵拼：sou3 geoi3 git3 gau3；英文：data structure）係指一部電腦內部組織數據嘅方法[1][2]。精確啲噉講嘅話，一款數據結構係描述數據嘅代數結構，會指明嗮以下嘅資訊[3]：

  • 啲數據同埋佢哋嘅數值、
  • 唔同數據之間嘅關係、同埋
  • 屬呢種數據結構嘅數據可以攞啲咩算子計或者擺入啲乜嘢函數嗰度。

舉個具體啲嘅例子說明，陣列（array）就係一種成日用到嘅數據結構，一個一維嘅陣列會包含若干個通常同類型嘅變數嘅數值（即係例如冚唪唥都係整數），會指明每個數喺邊個位嗰度，每件數據都掕咗個整數表示佢喺個陣列嘅邊個位；常用於陣列身上嘅工作有「將陣列入面嗰啲元件逐個逐個（foreach）俾出嚟做輸出」[1]。

一部電腦有好多種唔同嘅數據結構可以用，唔同嘅數據結構可能會擅長做唔同嘅工作，又有好多重要嘅演算法係要求輸入數據實要係屬某種數據結構先行得嘅－喺廿一世紀初嘅世界，數據結構係電腦科學研究同電腦程式編寫等嘅工作上不可或缺嘅知識之一[4]。

結構類型[編輯]

常用嘅數據結構有以下呢啲[4][5]：

  • 陣列（array）：陣列係用嚟裝相關嘅數據嘅；一個陣列正路會有個整數 n 表示佢嘅大細（裝到幾多件數據），大細嘅數值可能係固定嘅但又可能可變（睇程式語言而定）；一個陣列會包含最多 n 咁多件嘅數據，會有次序（每件數據掕若干個整數，表示佢喺個陣列邊個位），而且啲數據通常（但唔一定）冚唪唥都屬同一隻類型。喺應用上，設計者通常會攞一個陣列嚟儲住一柞彼此相關嘅數據，例如遊戲程式好興用一個陣列嚟儲住啲玩家嘅得分[6]。以下係一個一維、11 件數據咁長嘅陣列：
Merkkijono.svg
  • 鏈結串列（linked list）：都係攞嚟裝相關嘅數據嘅；一條鏈結串列會有若干件次序固定嘅數據，條鏈結串列當中每個位（node）都會有「件數據嘅數值係乜」、「件數據指住嘅下一件數據係邊件」同「件數據嘅前一件數據係邊件」（固定次序；下圖噉）嘅資訊，一位用家搜尋一條鏈結串列嗰陣一定要焗住跟條串列個次序（或者前後掉轉）噉嚟搜尋，冇得話例如（好似陣列噉）隨機噉揀是但一件數據嚟讀取[註 1]，不過鏈結串列好處係可以容易噉由柞數據當中攞走其中一件而唔使重新排過嗮柞數據（一個陣列攞走咗其中一件再排過就要改嗮後面嗰啲數據嘅位置數值[註 2][7]。
Singly-linked-list.svg
  • 堆疊（stack）：柞數據係最後入嘅最先出（last in first out，LIFO）嘅，即係話嗰柞數據有次序之分，當中排最尾嗰件數據會優先噉被提取，就好似一疊洗好咗嘅碟噉，最尾擺入疊碟嗰隻碟會最先俾人攞走；可以對堆疊做嘅運算最基本有 push（擺件數據落堆疊上面）同 pop（刪除堆疊最上面嗰件數據），可以睇下圖嘅圖解。堆疊喺回溯法（backtracking）上成日用－例如想像家陣有個人工智能程式喺度行迷宮，個程式要一路記住自己行過嘅位置，一去到掘頭路就返轉頭，即係話「過去嘅位置」會成一個堆疊，要返轉頭行每一步嗰陣就將最近嗰件數據（個堆疊最頂嗰件）攞走[8]。睇埋遞歸。
Lifo stack.png
  • 隊列（queue）：柞數據係最先入嘅最先出（first in first out，FIFO）嘅，即係話嗰柞數據有次序之分，當中排最先嗰件數據會優先噉被提取，就好似一班人喺度排隊噉；可以對堆疊做嘅運算最基本有 enqueue（擺件數據落隊列最後）同 dequeue（刪除堆疊最先嗰件數據），可以睇下圖嘅圖解。喺實際應用上，隊列最常見嘅用途嚟攞嚟「排隊」－俾部電腦知有啲咩數據等緊要處理，並且將啲數據優先處理，呢種做法喺好多電腦系統當中都會用到[9]。
Data Queue.svg
  • 雜湊表（hash table）：一種用嚟整關聯陣列（associative array；抽象資料型別，用嚟將每件數據都掕個獨特嘅名俾佢）嘅數據結構；一幅雜湊表會用一個雜湊函數（hash function）嚟由一個輸入（key）嗰度計出一個號碼（index），用呢個號碼嚟由一個陣列（buckets）嘅位嗰度搵出想要嗰件數據，例如想像一個用嚟記住一個組織裏面每個員工嘅名同電話號碼嘅程式，會由查緊嗰個員工嘅名（key）嗰度計出一個號碼，個號碼表示嗰個員工嘅電話號碼喺個陣列嘅邊個位，然後個程式就可以用 output = buckets[n];（攞個陣列入面對應嗰件數據）噉嘅方法攞到想要嘅數據（下圖）[10]。
Hash table 3 1 1 0 1 0 0 SP.svg
  • 樹（tree）：柞數據有高低層之分，好似一幅樹狀圖噉；一樖數據樹會有若干個節點（node），而且啲節點分層，除咗做起始點嗰個節點（根節點；root）之外，每個節點有一個（而且頂櫳一個）母節點（parent；指喺嗰個節點上面，連住嗰個節點嘅另一個節點），於是就形成柞節點喺起始點嗰度一層層噉每層都分叉嘅樣；好似下圖噉，紅色 2 嗰點係根節點，而根節點下有一層層嘅節點，每個節點都有個母節點（例如 7 嗰點嘅母節點就係個根節點）。喺實際應用上，樹嘅數據結構可以攞嚟儲住一啲有關決策嘅資訊－決策呢家嘢可以想像成喺每個時間點（層）嗰度揀一個可能選擇（節點），再行去下一個時間點（去下一層）嗰度[11]，例如蒙地卡羅樹搜尋（Monte Carlo tree search）就用咗樹嘅數據結構嚟思考玩遊戲嗰陣嘅決策[12]。
Tree (computer science).svg
  • 圖（graph）：一幅圖數據有若干個節點，而且每個節點都最少有一條邊（edge）連去另外一個節點嗰度，而如果有兩個節點之間有條邊連住，佢哋就算係相鄰（adjacent）嘅；一幅圖數據嘅大細可以由節點嘅數量以及節點之間嘅邊嘅數量嚟反映。好似係下圖噉，下圖係一幅有 6 個節點嘅圖數據，當中節點 1 同節點 2 之間有連結（可以由節點 1 行去節點 2 或者相反）、節點 1 同節點 5 之間有連結（可以由節點 1 行去節點 5 或者相反）... 如此類推。有關圖數據嘅應用，可以睇吓搵路（pathfinding）呢種喺遊戲人工智能上成日用嘅演算法[13]。
6n-graf.svg

... 等等。

註釋[編輯]

  1. ↑ 陣列當中嘅一件數據可以用
    output = array[n];
    噉嘅方法嚟輕易讀取。
  2. ↑ 技術性啲講，即係話陣列做「插入一件數據」或者「刪除一件數據」嗰陣複雜度係 O(n) 咁多。

睇埋[編輯]

文獻[編輯]

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

攷[編輯]

  1. ↑ 1.0 1.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. ↑ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507-512.
  4. ↑ 4.0 4.1 8 Common Data Structures every Programmer must know. Towards Data Science.
  5. ↑ Seymour, Lipschutz (2014). Data structures (Revised first ed.). New Delhi, India: McGraw Hill Education.
  6. ↑ CS240 -- Lecture Notes: Arrays.
  7. ↑ Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. pp. 239-303.
  8. ↑ Backtracking.
  9. ↑ 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.
  10. ↑ McKenzie, B. J.; Harries, R.; Bell, T. (February 1990). "Selecting a hashing algorithm". Software Practice & Experience. 20 (2): 209-224.
  11. ↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.
  12. ↑ Monte Carlo Tree Search. Towards Data Science.
  13. ↑ Millington, I. (2019). AI for Games. CRC Press. Ch. 4.

拎[編輯]

由「https://zh-yue.wikipedia.org/w/index.php?title=數據結構&oldid=1706863」收