A-level 計算機/WJEC (Eduqas)/元件 1/資料結構
資料結構是**相關資料項的集合**，用於組織與現實世界問題相關的資料。它們由一維、二維或三維陣列組成，這些陣列根據索引儲存資料；記錄則基於代表性欄位；棧/佇列根據新增資料的順序儲存資料；二叉樹包含資料節點；連結串列使用指標儲存資料；雜湊表將資料儲存在一個儲存表中。
資料結構有兩種型別：靜態和動態。靜態資料結構在程式開始時具有預定義的大小，在程式執行時不能更改。靜態結構的優點是記憶體 (RAM) 需求是已知的。動態資料結構可以在程式執行時擴充套件和收縮。只要記憶體中有足夠的空間，就可以新增必要的資料。動態資料結構的唯一問題是它們更難實現。
每種資料結構都適用於不同的目的。效率的衡量標準是資料在元素數量增加時搜尋所需的時間。這可以透過大 O 符號來表示。
Set employees(5) As String = ["Alice", "Bob", "Cameron", "Courtney", "Daniel", "Emilia" ]
陣列是**相同資料型別**的靜態元素集合，以線性方式儲存。每個元素都透過其索引訪問，第一個元素的索引為 0，後續每個元素的索引依次遞增 1。要訪問陣列中的資料，請指定陣列的名稱以及要訪問的元素，例如 employees(0) 獲取第一個元素的資料。
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Alice | Bob | Cameron | Courtney | Daniel | Emilia |
Set employees(5, 1) = [ ["Alice", "Bob" "Cameron", "Courtney", "Daniel", "Emilia"], [ 20, 38, 23, 50, 40, 35 ] ]
二維 (2D) 陣列可以看作是表格，或者更簡單地說，是多個一維 (1D) 陣列。要訪問二維陣列中的元素，必須指定要訪問的列的索引和要訪問的行索引。格式為 (行, 列)。要宣告二維陣列，使用兩個方括號（一個表示二維陣列的開始，另一個表示元素的開始）。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 姓名 [0] | Alice | Bob | Cameron | Courtney | Daniel | Emilia |
| 工資 [1] | 20 | 38 | 23 | 50 | 40 | 35 |
Set employees(2, 1, 5) As String = [ // Sales for the month of January. [ ["Alice", 950] , ["Bob", 750], ["Cameron", 900], ["Courtney", 2500], ["Daniel", 2400], ["Emilia", 1500] ], // Sales for the month of February. [ ["Alice", 1000] , ["Bob", 700], ["Cameron", 800], ["Courtney", 3000], ["Daniel", 2500], ["Emilia", 1700] ] ]
三維 (3D) 陣列是多個二維陣列組合在一起，或者是一組表格。如果我們有表格編號、列和行，就可以訪問資料（表格編號、行、列）。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 姓名 [0] | Alice | Bob | Cameron | Courtney | Daniel | Emilia |
| 銷售額 [1] | 950 | 750 | 900 | 2500 | 2400 | 1500 |
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 姓名 [0] | Alice | Bob | Cameron | Courtney | Daniel | Emilia |
| 銷售額 [1] | 1000 | 700 | 800 | 3000 | 2500 | 1700 |
記錄是與單個個體或實體相關的多個數據項的集合。與陣列不同，記錄可以包含不同型別的資料。下面顯示了一個記錄的示例。
| 0 | 1 | 2 | |
|---|---|---|---|
| 姓名 (字串) | Alice | Bob | Daniel |
| 首字母 (字元) | A | B | D |
| 年齡 (整數) | 24 | 34 | 18 |
| 出生日期 (日期) | 08/04/1994 | 23/10/1984 | 09/12/2000 |
棧是一個 LIFO 資料結構：後進先出。這意味著資料以與新增順序相反的順序刪除，最近新增的條目最先刪除。把它想象成一堆薄餅 - 你必須先吃掉頂部的薄餅才能吃到下面的任何薄餅。棧的一個例子是“撤銷”功能；你最後寫的內容是第一個被刪除的內容。棧可以透過使用陣列簡單地實現；只需使用一個指標指向最上面的專案。將資料新增到棧中稱為入棧，而從棧中刪除資料稱為出棧。
另一方面，佇列是一個先進先出 (FIFO) 資料結構。資料按新增順序刪除，就像一個普通的佇列一樣。佇列在印表機中使用，以確保作業按到達的順序列印，並在鍵盤緩衝區中使用，以確保每個鍵按順序處理。佇列也可以透過使用陣列實現，但這需要一個指向頂部條目的指標，以及一個指向底部的指標，使其更難有效地執行。佇列中使用的兩種方法是“入隊”和“出隊”。
出棧（刪除）和入棧（新增）專案的虛擬碼如下
Def pop(topItem):
If Stack(topItem) = NULL Then
Output "Stack is empty - cannot pop."
Return NULL
Else
Value = Stack(topItem)
Stack(topItem) = NULL
topItem = topItem - 1 // We must point to the previous item in the stack.
Return Value
End If
Def Push(Value, TopItem):
If Stack Is Full Then
Output "Stack is full - cannot push."
Else
TopItem = TopItem + 1
Stack(TopItem) = Value
Output "Item added to the stack."
End If
你還應該知道入隊和出隊方法的虛擬碼
Def Enqueue(Data) If Queue Is Full Then
Output "Queue is full - cannot enqueue."Else
TopItem = TopItem + 1 Queue(TopItem) = Data Return TRUEEnd If
Def Dequeue If Queue Is Empty ThenOutput "Queue is empty - cannot dequeue."Else
Data = Queue(BottomItem) BottomItem = BottomItem + 1 Return TRUEEnd If
連結串列是資料元素的集合，其中**每個元素都包含資料本身以及指向下一個元素的指標**。最後一個元素有一個指向無效值的指標 (NULL)，表示列表的結束。使用連結串列的優點是可以在不重新排列所有其他元素的情況下將新專案插入連結串列。連結串列可以使用二維表實現，其中每行的第一個條目包含資料，而第二個條目是指標，包含指向下一個資料點的行索引。要從連結串列中刪除資料，請調整其之前的節點使其指向其後的專案，從而繞過連結，但保留專案的順序。
-
這是一個帶有指標和無效值“null”的連結串列。
二叉查詢樹由節點和它們之間的連結組成。每個節點最多有兩個節點從它延伸出來，類似於家譜或因數樹的設計。二叉查詢樹最重要的方面是，左分支上的資料必須小於根節點中的資料，而右分支上的資料必須大於根節點中儲存的資料。如果節點均勻分佈在樹中，則二叉樹被稱為平衡的，這將產生最小的高度。不平衡的樹在一側的節點比另一側多得多。
有三種主要方法可以遍歷二叉查詢樹。它們是
- 先序遍歷 (**N**LR) - 從根節點開始，遍歷左子樹，然後遍歷右子樹。這將得到 8, 3, 1, 6, 4, 7, 10, 14, 13
- 中序遍歷 (LNR) - 遍歷左子樹，訪問根節點，然後遍歷右子樹。這將給出 1, 3, 4, 6, 7, 8, 10, 13, 14
- 後序遍歷 (LRN) - 遍歷左子樹，然後遍歷右子樹，最後訪問根節點。這將給出 1, 4, 7, 6, 3, 13, 14, 10, 8
要將資料新增到二叉搜尋樹中，首先將新條目與當前節點進行比較。如果新資料更大，則沿著右指標移動，否則沿著左指標移動。重複此過程，直到沒有可供選擇的指標。在此處建立一個新的指標，指向比較結果指示的方向，並將新資料插入到末尾。如果您被要求根據資料列表繪製二叉搜尋樹，請按照此程式對每個資料片段進行操作，順序很重要。
您可以被要求使用二維陣列（表格）來表示二叉樹。每個元素將從左到右具有一個數字 ID（8 將是 1，3 將是 2，10 將是 3 等）。這可以像使用連結串列一樣完成，每一行包含資料、左指標和右指標（如果不存在指標，則使用 NULL）。
| ID | 左指標 | 資料 | 右指標 |
|---|---|---|---|
| 1 | 2 | 8 | 3 |
| 2 | 4 | 3 | 5 |
| 3 | NULL | 10 | 6 |
| 4 | NULL | 1 | NULL |
| 5 | 7 | 6 | 8 |
| 6 | 9 | 14 | NULL |
| 7 | NULL | 4 | NULL |
| 8 | NULL | 7 | NULL |
| 9 | NULL | 13 | NULL |
雜湊表是一種特殊型別的資料結構，其中資料的特性用於決定資料的儲存位置。雜湊表有兩個主要部分 - 雜湊函式和儲存表。
雜湊函式在雜湊表中起著關鍵作用。它是一個只有開發人員知道的秘密函式，它決定資料應該儲存的位置，基於從資料本身的屬性推匯出的可複製計算。雜湊函式通常非常複雜，但一個簡單的例子可以是length(data) MOD 11。這將找到資料條目中的字元數，然後找到該值除以 11 後的餘數。返回的數字可以作為儲存表中的索引。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 開始資料 | 雜湊函式操作 | 結束陣列位置 |
|---|---|---|
| 54 | 54 MOD 11 | 10 |
| 26 | 26 MOD 11 | 4 |
| 93 | 93 MOD 11 | 5 |
| 17 | 17 MOD 11 | 6 |
| 77 | 77 MOD 11 | 0 |
| 31 | 31 MOD 11 | 9 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 77 | 26 | 93 | 17 | 31 | 54 |
使用雜湊表的問題也源於雜湊函式。使用一個能夠將資料均勻地分佈在表中，最好是分佈在一個較寬範圍內的雜湊函式非常重要，以避免兩個不同的資料片段寫入同一個索引。然而，這在實踐中是不現實的，特別是如果雜湊演算法只有有限的輸出數量。一個更實用的解決方案是在每個索引處使用一個新的資料結構，以允許多個條目儲存在那裡。這可能是一個連結串列，甚至可能是一個具有其自身雜湊函式的新雜湊表，但這也會增加資料儲存和檢索所需的時間。