CS50 week 5 - Data Structures 筆記

,
👀 3 min read 👀

大家好，我是 Cindy，最近跟同事小夥伴相約一起看 CS50 的課程，CS50 (Introduction to Computer Science）是一堂美國哈佛大學知名的通識課程，完全免費，在 edx 或 youtube 或 CS50-Study-Group github 都可以非常容易地看到。

這系列的文章會是我的個人筆記，歡迎有興趣的人一定要自己去看看 CS50 的課程歐。

今天這篇是 CS50 week 5 筆記，想先看之前筆記的人可以點選下面連結：

Data Structures

Arrays

Array 在記憶體中是連續存在的，當我們要在 array 新增一個值，本來儲存的記憶體位置可能會因為空間不夠而不能繼續存下去，這時候我們就會需要去換記憶體位子，將原本的 array 複製到記憶體的另一個長度夠的位子並插入新值，會花時間。

  • realloc 可以改變已配置的記憶體大小。

Linked Lists

Linked Lists 在記憶體中是不連續，利用紀錄下一個 address 的方式連接，因為需要紀錄下一個 node 的 address，所以會花空間。

資料結構如下，每個 node 除了要記錄的值以外，還要記錄下一個 node 的 address。

1
2
3
4
5
6
typedef struct node
{
    int number;
    struct node *next;
}
node;

產生一個 node 的範例如下：

1
2
3
4
5
6
7
8
node *n = malloc(sizeof(node));

if (n != NULL)
{
    // 這和 (*n).number = 1; 是一樣意思
    n->number = 1;
    n->next = NULL;
}

當我們想要在 linked list 裡插入另一個值時，操作的順序相當重要，必須讓要插入的值先指向 next 的 address，接著再讓前一個 node 的 next 改為新插入的值，範例如下：

1
2
3
// 假設我們已經有 linked list(變數名稱叫做 list)，我們想要在 list 的最前面插入一個 node(變數名稱為 n)
n->next = list;
list = n;

Binary Search Trees

       4
    /     \
   2       6
 /   \   /   \
1     3 5     7

我們可以用更抽象的樹狀結構的方式表示 Binary Search，每個節點的左邊都會小於節點，右邊會大於節點。

1
2
3
4
5
6
7
typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

Hash Tables

是 linked list 和 array 的結合，我們透過 Hash function 實現，最後可以讓我們用 input 找到特定的 output，只需要花費時間幾乎恆定的 O(1)，在設計程式的時候要注意 Collision 的問題。

我們在 Hash 做搜尋的時候，最糟糕的情況會花費 O(n)，例如我們先用分類的方式將資料放在不同的 bucket 裡，每個 bucket 的搜尋時間都會是 O(n)。

其他參考資料：

Tries

可以想成是一種樹狀結構，每個 node 都是一個 array 且指向下一個 node。搜尋或插入都會是 O(1) 一個常數的 Step，但這個做法會耗費大量的記憶體空間。

Queues

抽象的資料結構，First in first out(FIFO) 稱為 queue，enqueue 表示進入排隊的隊伍，dequeue表示已處理完離開排隊的隊伍。

Stacks

抽象的資料結構，Last in first out(LIFO) 稱為 stack，push 表示將值加入 stack，pop 表示從 stack 將值取出。

Dictionaries

抽象的資料結構，就像字典一樣可以透過 key 找到 value。

其他

這堂課教授說的一句話我覺得很好，就把它記下來分享給大家，Nothing is absolutely better than anything else，課程中教授不停的問學生這個資料結構付出的代價是什麼，大多數來說會是時間和空間的權衡，沒有任何一個完美的做法，只有當下最適合的選擇。