CS-第 5 週

資料結構

訊息結構是記憶中組織訊息的形式。在記憶體中組織資料的方法有很多種。

抽象資料結構是我們概念上想像的結構。熟悉這些抽象結構，以後在實務上實作資料結構就更容易了。

---

堆疊和佇列

隊列是一種抽象資料結構。
佇列資料結構依照 FIFO （先進先出，「第一個加入的元素先出現」） 規則運作。
可以想像為人們在景點排隊的例子：第一個排隊的人先進去，最後一個人最後進去。

可以使用

佇列執行以下操作：

• 入隊：將新元素加入隊列末端。
• 出隊：從隊列開頭移除一個元素。

Stack 資料結構依照 LIFO （後進先出，「最後新增的元素先出現」） 規則運作。 例如，廚房裡疊盤子：先拿最後一個盤子。

堆疊有以下操作：

• 壓入：將新元素放入堆疊。
• 彈出：從堆疊中移除一個元素。

---

大批

Array 是一種在記憶體中依序儲存資料的方法。數組可以可視化為：

記憶體可能包含其他程式、函數和變數儲存的其他值，以及先前使用過且不再使用的冗餘值：

如果我們想為陣列新增一個新元素 - 4 -，我們需要分配新的記憶體並將舊數組移入其中。這個新記憶體可能充滿了垃圾值

:

如果我們將元素移動到數組並添加新值，新值將覆蓋新分配的記憶體中舊的不必要的值：

這種方法的缺點是每次新增元素時都需要複製整個陣列。
如果我們把 4 放在記憶體的其他地方會怎麼樣？那麼，根據定義，這不再是一個數組，因為 4 與記憶體中的數組元素不連續。

有時，程式設計師會分配比所需更多的記憶體（例如，300 個元素對應30 個元素）。但這是一個糟糕的設計，因為它浪費了系統資源，而且在大多數情況下額外的記憶體是不必要的。因此，根據具體需要分配記憶體非常重要。

---

鍊錶

鍊錶是C程式語言中最強大的資料結構之一。它們允許將位於不同記憶體區域的值組合到一個清單中。它還允許我們根據需要動態擴展或縮小清單。

每個節點儲存兩個值：

• 值；
• 是一個指針，保存下一個節點的記憶體位址。 最後一個節點包含NULL，表示其後沒有其他元素。

我們將鍊錶第一個元素的位址保存到一個指標（指標）.

在C語言中，我們可以將節點寫成：

typedef struct node
{
    int number;
    struct node *next;
}
node;

我們來看看

鍊錶的建立過程：

• 我們聲明節點 *list:

• 為節點分配記憶體：

• 輸入節點的值：n->number = 1:

• 我們將節點的下一個索引設為 NULL： n->next = NULL:

• 讓我們將列表等於：

• 依照相同的順序，我們建立一個值為 2 的新節點：

• 為了連接兩個節點，我們將 n 的下一個索引設為列表：

• 最後，我們將列表設為 n。現在我們有一個由兩個元素組成的鍊錶：

在C語言中，我們可以將這個過程的程式碼寫成如下：

typedef struct node
{
    int number;
    struct node *next;
}
node;

使用鍊錶時有幾個缺點：

• 更多記憶體：對於每個元素，不僅需要儲存元素本身的值，還需要儲存指向下一個元素的指標。
• 透過索引呼叫元素：在陣列中我們可以透過索引來呼叫某個元素，但在鍊錶中這是不可能的。要找到特定元素的位置，需要從第一個元素開始依序遍歷所有元素。

---

樹

二元搜尋樹 (BST)是一種可以有效儲存、搜尋和擷取資料的資訊結構。
讓我們得到一個已排序的數字序列：

我們將中心的元素放在頂部，比中心元素小的值放在左邊，較大的值放在右邊：

我們使用指標將每個元素相互連接：

以下程式碼展示如何實作BST:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

我們為每個節點分配內存，其值以數位形式存儲，因此每個節點都有左和右指示器。 print_tree 函數從左到右依序遞歸列印每個節點。 free_tree 函數遞歸地從記憶體釋放資料結構的所有節點。

BST的優點：

• 動態性：我們可以有效地新增或刪除元素。
• 搜尋效率：在BST中搜尋給定元素所需的時間為O(log n)，因為每次搜尋時都會排除一半的樹。

BST 的缺點：

• 如果樹的平衡被打破（例如所有元素都放在一行），搜尋效率就會下降到O(n)。
• 需要為每個節點儲存左指針和右指針，這會增加電腦的記憶體消耗。

---

字典

字典就像一本字典，它包含一個單字及其定義，它的元素key (key)和value有（值）。

如果我們查詢

Dictionary 中的某個元素，它會在 O(1) 時間內傳回該元素。字典可以透過散列來提供精確的速度。

雜湊是使用特殊演算法將輸入數組中的資料轉換為位元序列的過程。

雜湊函數是一種從任意長度的字串產生固定長度位的字串的演算法。

雜湊表是陣列和鍊錶的完美組合。我們可以這樣想：

碰撞 （碰撞） 是指兩個不同的輸入產生一個雜湊值。在上圖中，發生碰撞的元素以鍊錶的形式連接起來。透過改進哈希函數，可以降低碰撞機率。

雜湊函數的一個簡單範例是：

typedef struct node
{
    int number;
    struct node *next;
}
node;

本文使用 CS50x 2024 原始碼。

以上是CS-第 5 週的詳細內容。更多資訊請關注PHP中文網其他相關文章！