【CS50 學習筆記】week5 — Data Structure
Data Structures
資料結構存在的目的是為了有效地在在記憶體中「存儲」並「操作」資料，並且根據不同的場景下去選擇不同的組織形式（forms of organization），例如 Stack（堆疊）、Queue（佇列，佇：ㄓㄨˋ），Linked list（連結串列）等等。
Stacks（堆疊） and Queues（佇列）
Stacks 和 Queues 都是某一種儲存資料的形式。
Queues 的特性是 FIFO （first in first out），可以想像成要去排隊買蘋果最新產品，第一個人排的會是第一個買到先走，最後排隊的最後走，而加入排隊有有個專有名詞是 “Enqueue” ，相反的若從隊伍頭離開則稱 “Dequeue” 。
Stacks 的特性是 LIFO（Last in first out），想像成在吃自助餐時餐盤是一層層疊上去的，所以在拿的時候都會從上往下拿，所以在最上面的餐盤比下方的餐盤晚放，但最上面的餐盤會比較早被拿走，一樣有專有名詞，”Push” 是將項目加到 stack 的頂部，而 “Pop” 則是將項目從 stack 的頂部刪除，其應用的場景可以是瀏覽器上一頁的功能，任何編輯器（work、ppt 和 VS code 等等）的撤銷（undo）功能。以下為 stack 的範例，CAPACITY 代表這個 stack 最多可以容量多少的量，size 是目前有多少的量，這裡是以 50 作為上限。
const int CAPACITY = 50;
typedef struct
{
string name;
int age;
}
person;
typedef struct
{
person people[CAPACITY]; // [{name: 'David', age: 31}, {name: 'Joe', age: 33}, ...]
int size; // 4
}
stack;Resizing Arrays
在宣告一個 array 的時候，對電腦來說它做的事情就是分配一串連續的記憶體位置來儲存變數（block of contiguous memory），如以下宣告 int int values[] = {1,2,3}的 array。
但在記憶體中除了剛剛宣告的 array 以外還是有其他宣告的變數和函式來佔據記憶體，也可能是曾經被使用過的垃圾值，只是還沒被拿來使用。
但如果在 {1, 2, 3} 再加上一個 4 進去，有可能嗎，記得剛剛提到的一句話，array 是「一串連續的記憶體位置」，在上方的圖，除非你改寫了 h 那個字元成 4，但這樣不 make sence，所以就要透過重新取得記憶體的方式來做，以下用 code 來舉例，若透過 malloc 來分配了 3 * 4 bytes (int) 的記憶體並分別賦值 1, 2, 3 ，接著想要加上一個 4 進去的問題來了，這時就要重新的malloc 4 * 4 bytes (int) 的記憶體並且透過回圈來將 1, 2, 3 賦值到 tmp 的記憶體上，然後再將 tmp 的第三個位置賦值 4，接著去釋放 list 的記憶體，那 list 這個記憶體位置我不用了，但的這個字是我想一直使用的，所以我透過 list = tmp 的方式來讓 tmp 這個 pointer 的記憶體位置給 list，那因為 list 已經是新的記憶體位置（指向 array {1,2,3,4}），最後仍需要去釋放新的記憶體。
// Implements a list of numbers with an array of dynamic size
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
// List of size 3
int *list = malloc(3 * sizeof(int));
if (list == NULL) // avoid the situation that no memory could be allocate
{
return 1;
}
// Initialize list of size 3 with numbers
list[0] = 1;
list[1] = 2;
list[2] = 3;
// List of size 4
int *tmp = malloc(4 * sizeof(int));
if (tmp == NULL) // avoid the situation that no memory could be allocate
{
free(list);
return 1;
}
// Copy list of size 3 into list of size 4
for (int i = 0; i < 3; i++)
{
tmp[i] = list[i];
}
// Add number to list of size 4
tmp[3] = 4;
// Free list of size 3
free(list);
// Remember list of size 4
list = tmp;
// Print list
for (int i = 0; i < 4; i++)
{
printf("%i\n", list[i]);
}
// Free list
free(list);
return 0;
}其實有個函式 realloc 能做到剛剛的事情，第一個參數是你想改寫的 pointer，第二個參數是你要重新拿的記憶體空間，所以 realloc 是在做 queue/ stack 的增減時一個很強大的工具。
int *tmp = realloc(list, 4 * sizeof(int));
=========== 以上相當於取代以下 ===========
int *tmp = malloc(4 * sizeof(int));
// Copy list of size 3 into list of size 4
for (int i = 0; i < 3; i++)
{
tmp[i] = list[i];
}但這樣以上這種方式非常沒有效率，因為每當要加一個數字，就要把 n 個數字搬到新的記憶體，所以有另一種方式來處理。
Linked Lists
Linked Lists 這個資料結構的這種儲存方式相較於 Array 能夠讓你的一串數字不用侷限在「一串連續的記憶體位置」，而是可以分散在不同的記憶體空間（如下），並隨著資料的大小去做長度的增減。
那我們該如何把他們串在一起呢，我們這時候需要使用更多的記憶體去儲存說接下來的值是在哪裡，也就是用 pointer 去指示，而通常會用 NULL 表示沒有下個點了，然後在起始的點前多一個 pointer 來指示起始點在哪裡。
若將每個節點用程式碼表示會如下，node 是一個物件，包含其數字還指向下一個 node 的記憶體位置，這邊比較會有問題的是在這週課程之前在宣告pointer 時通常會用 int *variable （型態 *變數名稱 ）這種形式來宣告 ，但這裡因為 node 是我們自定義的型態，所以在 typedef struct的後面要放上該自定義的名稱，然後node *next 的前面加上 struct ，用意有點像是你宣告的函式若是在宣告前就使用，就要先在最上方先宣告他的 prototype，這部分算滿難懂，但這就是一個宣告 Linked Lists node 的範例。
==== 改寫前，一般認知的宣告方式 ====
typedef struct
{
int number;
node *next;
}
node;
==== 改寫後，因為使用到自己的結構，所以要多加 ====
typedef struct node
{
int number;
struct node *next;
}
node;Linked Lists 的好處在於你可以不用靠搬家的方式來增加 list，因為他是一個不連續記憶體的型態，但是：
- Arrays 較 Linked Lists 節省記憶體空間，因為 Linked Lists 每個節點要多存一個 pointer。
- 它不能以 index 的方式取出值，因此 Binary search 的演算法在此結構不可行。
在做出一個 linked list 之前要介紹一個新的符號 -> ，其用途在於去到該記憶體地址，並查看其結構並對其賦值或更改。
接著先以一張圖來表示我們想要達到的目標，一個值為 3 2 1 的 linked list，最後的 node 其下個 pointer 表示 NULL 的意思是該 list 的結尾。
先上完成的 code，以下會解釋，執行時會打 ./link 1 2 3 ，link 是程式檔案名稱。
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
// 宣告 linked list node
typedef struct node
{
int number;
struct node *next;
}
node;
int main(int argc, char *argv[])
{
// Memory for numbers
node *list = NULL; // <1>
// For each command-line argument // <2>
for (int i = 1; i < argc; i++) // <3>
{
// Convert argument to int
int number = atoi(argv[i]); // <4>
// Allocate node for number
node *n = malloc(sizeof(node)); // <5>
// Check if there is any short on memory
if (n == NULL)
{
return 1;
}
// asign number from argv // <6>
n->number = number;
// set pointer to be NULL in order to make sure there is no garbage value for last node's next pointer value
// <7>
n->next = NULL;
// Prepend node to list
// <8>
n->next = list;
// <9>
list = n;
}
// Print numbers
// <10>
node *ptr = list;
while (ptr != NULL)
{
printf("%i\n", ptr->number);
ptr = ptr->next;
}
// Free memory
// <11>
ptr = list;
while (ptr != NULL)
{
node *next = ptr->next;
free(ptr);
ptr = next;
}
}
搭配標記來看：
- 在一開始會先宣告一個 node 的 pointer 命名為 list
- 去做迴圈取出 argv 傳入的值
- index 0 為程式檔案名稱，所以從 index 1 開始取
- 需要透過 atoi 函式將 char 轉成 int
- 調用以 node 為大小的記憶體，為 n 為名稱的 pointer，若用圖示表示會是這樣
6. 透過 -> 符號去取 n 這個 pointer 指向位置上的 number ，並將其賦值，在第一個回圈就會是指 1。
7. 因為 n 這個 pointer 指向位置上的 next 可能是垃圾值，所以可以先賦值 NULL，而這個 node 也會是這個 list 的最後一個 node，所以現在會是這樣。
8. 這行的意思是要將 n 這個 pointer 指向位置上的 next 賦值 list 的 pointer，在意義上是在將該 node 去加到該 linked list 的前面（prepend），而在第一個回圈中 list 的 pointer 為 NULL，所以 n 這個 pointer 指向位置上的 next 還是 NULL。
9. list 的 pointer 去賦值 n 這個記憶體位置，所以現在其實就完成了一個只有一個 node 的 linked list。
接著在第二個回圈再調用 n 為名稱的 pointer，賦予其 number 為 2，而在 <8> 該行時 link 為 0x123，所以該 n 的 next 的值為 0x123，接著在 <9> 將其 list 指向該第二個回圈該 n 的記憶體位置。
最後繼續跑第三圈全圈直到結束，就會是最一開始想要達到的目標，完成一個 linked list。
10. 完成 linked list 後想將其值印出，在這裡雖然執行時會打的是 ./link 1 2 3 ，但因為是 prepend 的關係，所以會印出 3 2 1。然而也可以不要用 while 回圈而用 for 回圈。
// Print numbers
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
printf("%i\n", ptr->number);
}11. 最後需要釋放記憶體，而用 node *next = ptr->next; 主要原因在於需要先把該 ptr 該 next 的記憶體先暫時存起來，因為在釋放 ptr 後你就不能使用 ptr = ptr->next 這樣的方式來取值。
Linked Lists 時間複雜度
- 若想要做 search ，其時間會是 O(n)，最糟的情況全部搜尋。
2. 想做 insertion 的時間會是 O(1)，你可以將任何一個 node 以固定的時間去加入該 list。
Trees（Binary search trees）
剛剛提到 Linked Lists 其缺點，就是無法做 Binary search，但若今天想保有Linked Lists 的彈性又想做 Binary search，這時就需要 Trees。
我們在可以存資料時候可以將其一串數值以 Binary search 的形式來儲存，也就是將數列一直對半砍，然後透過 pointer 來將其 node 連結起來。
寫起來會像是以下，將 node 的 pointer 分成左邊和右邊，想當然最底下的 pointer 左右邊就都是 NULL，完整的 code 如下，實際的每行 code 的做法就不一一解釋了。
// Implements a list of numbers as a binary search tree
#include <stdio.h>
#include <stdlib.h>
// Represents a node
typedef struct node
{
int number;
struct node *left;
struct node *right;
}
node;
void free_tree(node *root);
void print_tree(node *root);
int main(void)
{
// Tree of size 0
node *tree = NULL;
// Add number to list
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->left = NULL;
n->right = NULL;
tree = n;
// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
free_tree(tree);
return 1;
}
n->number = 1;
n->left = NULL;
n->right = NULL;
tree->left = n;
// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
free_tree(tree);
return 1;
}
n->number = 3;
n->left = NULL;
n->right = NULL;
tree->right = n;
// Print tree
print_tree(tree);
// Free tree
free_tree(tree);
return 0;
}
void free_tree(node *root)
{
if (root == NULL)
{
return;
}
free_tree(root->left);
free_tree(root->right);
free(root);
}
void print_tree(node *root)
{
if (root == NULL)
{
return;
}
print_tree(root->left);
printf("%i\n", root->number);
print_tree(root->right);
}以下函式為搜尋的函示，可以傳入 tree 起始點的 pointer 和要找的 number 進去，接著中間會以 recursion 的方式來做尋找。
bool search(node *tree, int number)
{
if (tree == NULL)
{
return false;
}
else if (number < tree->number)
{
return search(tree->left, number);
}
else if (number > tree->number)
{
return search(tree->right, number);
}
else if (number == tree->number)
{
return true;
}
}但 trees 其缺點是一個 node 就要比 linked list 的 node 多存一個 pointer，所以佔據的記憶體是較多的。
其他資料結構
在課程還有講到 Dictionaries、Hashing and Hash Tables 和 Tries 的資料結構，但都是大概提到一些實現的概念，這裡就不詳細紀錄，主要還是怎麼透過一些方法去儲存資料，然後在取得資料時能花最少時間，但有些時候就是 big(O) 和記憶體空間的權衡。
筆記心得
卡在這週的課程真的滿久的，主要原因是要了解 linked list 前對於 pointer 還是得更熟悉，再來就是 linked list 的 node 宣告其實還滿難理解，所以嘗試找很多文章或教學來看，所以紀錄了很多為什麽要那樣實現的解釋，但仍舊有些抽象的東西不太懂，不過還是先往下走最重要，之後碰到不懂的再回過來補。
