單元 1.4.2 資料結構

結構

記錄

一個無序的資料結構，其元素透過屬性名稱訪問。這使得結構更易於使用，因為屬性名稱描述了儲存的資料。

所有屬性必須在記錄可以使用之前定義。這使得結構的初始化更復雜。

person
first_name	last_name	email
John	Smith	john.smith@example.com

person.first_name // John
person.email // john.smith@example.com

列表

一個有序的資料結構，其元素透過索引訪問。

employee_ids
0	1	2
0048_jsmith	0064_jbloggs	0073_jdoe

employee_ids[0] // 0048_jsmith
employee_ids[2] // 0073_jdoe

元組

一個不可變的列表（儲存的資料不能修改）。

對於需要保持不變但可以透過索引訪問的資料很有用。

連結串列

連結串列是儲存資料的列表，其中包含指向列表中下一項的指標。列表中的最後一項的指標為 0 或 null，表示列表的結尾。

除了動態之外，連結串列的主要優勢在於元素可以高效地插入到任何位置 - 只需更改幾個指標即可。

以下是用表格表示的連結串列示例：名稱指向字母表中下一個人的位置。

start = 3 //表示連結串列從 3 開始（因為 A 在字母表的開頭）

nextFree = 4 //表示一個可用的空間，下一個要新增的專案將被新增在這裡

索引	姓名	指標
0	Lain	2
1	JoJo	0
2	Miku	null
3	Ash	1
4		null

假設我們要將 Mikasa 插入連結串列

我們首先將 Mikasa 放入由 nextFree 指標給出的空間中。
接下來，我們會弄清楚我們想要將 Mikasa 放在列表中的哪個位置。因為我們決定連結到字母表中的下一個專案，所以 Mikasa 將出現在 Miku 之前，但出現在 Lain 之後。因此，Mikasa 需要成為列表中的第 4 項。例如，insert(3, "Mikasa") //3 指的是第 4 個位置，因為連結串列從 0 開始
Lains 指標被更改為指向 Mikasa（設定為 4）
Mikasa 的指標被設定為指向 Miku（設定為 2）
最後，nextFree 指標將被設定為 5（下一個空閒位置）

因此，更新後的連結串列將如下所示

start = 3 //表示連結串列從 3 開始（因為 A 在字母表的開頭）

nextFree = 5 //表示一個可用的空間，下一個要新增的專案將被新增在這裡

索引	姓名	指標
0	Lain	2 4
1	JoJo	0
2	Miku	null
3	Ash	1
4	Mikasa	~~null~~ 2
5		null

連結串列的可能用途

實現撤銷功能
處理瀏覽器快取
幫助作業系統作業佇列

描述陣列和連結串列之間的區別。[2]

答案

連結串列是一種動態資料結構 (1)，而陣列是靜態的 (1)。陣列可以訪問任何元素（即隨機訪問） (1)，而連結串列需要遍歷到找到所需元素為止 (1)。陣列的內容在記憶體中是連續儲存的 (1)，而連結串列的內容可能不是 (1)。

陣列

陣列是一種有序的資料結構，透過索引訪問。它包含一組通常為相同型別的元素。因此，它是一種複合型別，因為它用預先存在的資料型別形成資料結構。預設情況下，陣列在定義時需要指定其大小，這是其中的元素數量。不能將元素新增到超出此大小的索引中。這在大多數程式語言中都是遵守的，但一些語言（特別是 Python 和 JavaScript 是例外，因為它們使用列表作為所有定義陣列的底層資料結構）打破了規則。

一維陣列

一維陣列包含一組屬性，每個屬性都透過其索引訪問。它們幾乎與列表近似，只是它們的大小是固定的。

employee_ids
0	1	2
0048_jsmith	0064_jbloggs	0073_jdoe

employee_ids[0] // 0048_jsmith
employee_ids[2] // 0073_jdoe

多維陣列

雖然陣列可以定義為單個維度並儲存一組值，如前所述，但它們也可以宣告為多維陣列。這意味著陣列的每個索引都儲存另一個數組，直到定義的維度數量。這意味著在二維陣列（如下所示）中，陣列將是一個數組的陣列，這些陣列都將包含值。它們可用於儲存表格資料或應透過 x 和 y 座標訪問的資料，例如遊戲中的畫素或圖塊。

這些陣列對於儲存更復雜的資料非常有用，但也需要更復雜的程式設計來適應，因為您必須完全理解陣列的結構才能訪問正確的資料。

shopSales[]	0	1	2	3
0	128.90	135.52	145.31	156.65
1	50.11	30.34	40.32	45.43
2	67.54	142.81	76.51	130.72
3	156.14	135.41	91.25	109.49

在上面的示例中，shopSales 可以指連鎖店賺取的利潤，其中頂部索引是季度，左側索引是商店編號。值得注意的是，在許多示例中，您需要先訪問頂部索引，因為它將包含商店本身的陣列。但是，這取決於您初始化和定義陣列的方式，例如

let shopSales [4][4] = [
    [128.90, 50.11, 67.54, 156.13],
    [135.52, 30.34, 142.81, 135.41],
    [145.31, 40.32, 76.51, 91.25],
    [156.65, 45.43, 130.72, 109.49]
];
let cheltenham = 0;
let gloucester = 1;
let bristol = 2;
let london = 3;

shopSales[0][cheltenham]; //128.90 - The sales made in the Cheltenham store in the first quarter.
shopSales[3][london]; // 109.49 - The sales made in the London tore in the fourth quarter.
shopSales[2][1] // 40.32 - Gloucester store, second quarter

棧

棧是列表的修改實現。資料結構在實現時有一組規則需要遵循，但這種結構如何工作的確切實現將取決於它的程式設計方式。這是一個抽象資料型別的示例，因為我們不關心底層方法，只關心允許我們與之互動的抽象函式。

棧是LIFO或後進先出結構的示例。這意味著最後一個新增到棧的元素將是第一個被訪問的元素。棧有一組函式，無論它在哪裡都應該實現

函式	描述
`push(element)`	將元素推入堆疊頂端。
`pop()`	從堆疊頂端移除元素，然後返回它。
`empty()`	檢查堆疊是否為空。
`full()`	檢查堆疊是否已達到最大容量。

某些實現可能對這些函式使用略微不同的名稱，例如isFull和isEmpty()。

一些堆疊是定義為固定大小的，但這取決於具體的實現。堆疊的頂部和底部的概念是比較隨意的，你只需要確保記住，專案是新增到相同端，並從相同端移除。下面展示了堆疊使用的一個示例。

stack = new Stack(4); // Define a stack with a maximum capacity of 4 elements.
stack.empty(); // -> True

stack.push(10);
//Stack: [0] 10

stack.pop(); // -> 10
//Stack: empty

stack.push(23);
stack.push(53);
stack.push(12);
stack.push(1);
//Stack: [0] 1
//       [1] 12
//       [2] 53
//       [3] 23

stack.full() // -> True

stack.pop() // -> 1
//Stack: [0] 12
//       [1] 53
//       [2] 23

佇列

佇列類似於堆疊，它是一個抽象資料儲存，遵循一組規則。它是一種FIFO結構或先進先出，這意味著第一個新增的資料將在查詢時（佇列在現實生活中是如何工作的，通常）成為第一個返回的資料。

它定義了自己的函式集。

函式	描述
`enqueue(element)`	將元素推入佇列的頂端。
`dequeue()`	從佇列底部移除元素，然後返回它。
`empty()`	檢查佇列是否為空。
`full()`	檢查佇列是否已達到最大容量。

下面展示瞭如何使用它的示例，但它在現實世界的程式設計中有很多非常有用和實際的應用。例如，如果需要執行一組任務，可以使用佇列來確保它們按照新增的順序執行。

queue = new Queue(4); // Define a queue with a maximum of 4 elements.
queue.empty(); // -> True

queue.enqueue(23)
queue.enqueue(53);
queue.enqueue(12);
queue.enqueue(1);
// Queue: [0] 23
//        [1] 53
//        [2] 12
//        [3] 1

queue.full(); // -> True

queue.dequeue(); // -> 23
queue.dequeue(); // -> 53
// Queue: [0] 12
//        [1] 1

可遍歷結構

樹

樹是一種資料結構，由樹幹和樹葉組成。樹有很多不同的型別，但你只需要瞭解基礎知識和二叉搜尋樹的特徵。

樹由一組節點組成，每個節點都包含一個值。它們然後連線到另一個節點，該節點可能會分支到另一個節點，依此類推，或者會結束該鏈。旁邊顯示了樹的示例。

二叉搜尋樹

二叉搜尋樹是樹的一種特定實現，遵循一組規則。這種樹將有一個“比較函式”或類似名稱的函式，它控制資料將在樹中的哪個位置插入。這可能是像“a > b”這樣的簡單內容，其中 a 是要插入的資料，b 是當前節點。任何只有 2 個分支的樹都被認為是二叉樹。

插入

當插入資料時，它使用比較函式沿著樹遍歷一條路徑。在旁邊顯示的影像中，如果我們要新增資料 9，它將進入根節點8。由於該值更大，因此它將進入右側並進入10節點。由於該值更小，因此它將進入左側。由於那裡沒有節點，因此它將在該位置新增節點。

如果左側有節點，該過程將繼續進行，直到到達沒有子節點的位置，然後將在那裡插入。重複項將在圖中的哪個位置放置取決於比較函式的編寫方式。

遍歷

樹可以以四種不同的方式遍歷，這決定了如何遍歷節點，因此控制了節點返回的順序。

先序遍歷

先序遍歷的正式步驟如下：

如果節點不為空，則繼續。
輸出當前節點的資料。
轉到左側，並從頭開始。
轉到右側，並從頭開始。

最後兩步是透過遞迴呼叫此函式來實現的。

手動執行時，你只需在節點左側畫一條線，並在節點周圍畫一條線，如圖右側所示。這種方法適用於每種遍歷，只是取決於你在哪裡畫線。

中序遍歷

中序遍歷的正式步驟如下：

如果節點不為空，則繼續。
轉到左側，並從頭開始。
輸出當前節點的資料。
轉到右側，並從頭開始。

第 2 步和第 4 步是透過遞迴呼叫此函式來實現的。

手動執行時，你只需從每個節點向下畫一條線，並在節點周圍畫一條線，如圖右側所示。這種方法適用於每種遍歷，只是取決於你在哪裡畫線。

後序遍歷

後序遍歷的正式步驟如下：

如果節點不為空，則繼續。
轉到左側，並從頭開始。
轉到右側，並從頭開始。
輸出當前節點的資料。

第 2 步和第 3 步是透過遞迴呼叫此函式來實現的。

手動執行時，你只需在節點右側畫一條線，並在節點周圍畫一條線，如圖右側所示。這種方法適用於每種遍歷，只是取決於你在哪裡畫線。

廣度優先遍歷

廣度優先遍歷沒有關於如何訪問節點的特定步驟，但很容易猜到。它按順序訪問樹的每一層，並從左到右輸出節點的內容。

你不需要知道如何實現它，但瞭解它的工作原理是有意義的。

圖

圖類似於樹，但複雜得多。它由節點和連線組成，就像樹一樣，但每個節點不只連線到下方，任何節點都可以連線到另一個節點。每個連線要麼與方向相關聯（例如 a 連線到 b），在這種情況下，圖被稱為有向圖，要麼沒有方向（例如a和b有連線），在這種情況下，它被稱為無向圖。

圖非常適合對大量複雜資料進行建模，因為它允許更自然地連線資料。有些圖將在連線旁邊顯示數字，這些數字被稱為權重，並影響使用 Dijkstra 等演算法進行遍歷時的工作方式。

您必須瞭解如何遍歷圖資料結構，這可以透過兩種演算法來實現。以下內容摘自 OCR 計算機書籍。

深度優先遍歷

PUSH the first node onto the stack
Mark as visited
Repeat
    Visit the next unvisited node to the one on the top of the stack
    Mark as visited
    PUSH this node onto the stack
    If no node to visit POP node off the stack
Until the stack is empty

廣度優先遍歷

PUSH the first node into the queue
Mark as visited
Repeat
    Visit the unvisited nodes connected to the first node
    PUSH nodes onto queue
Until all nodes visited
Repeat
    POP next node from queue
    Repeat
        Visit unvisited nodes connected to current node
        PUSH nodes into queue
    Until all nodes visited
Until queue empty

雜湊表

資料儲存在透過將資料的識別符號傳遞給雜湊函式生成的記憶體位置中。雜湊函式生成一個記憶體地址來儲存專案的 data，它總是對特定輸入識別符號返回相同的答案。

一些簡單的雜湊函式會為不同的資料項提供相同的記憶體地址。在這種情況下，將說明重新計算重複地址的方法。這可能會轉到下一個可用的記憶體地址，或者檢查之後每第三個記憶體地址，直到找到一個可用的地址。