指標與 Linked List 筆記

Pass by Reference & Pass by Value

在 Python 裡面，假設我們有一個 object A 和一個 object B，那麼當我們去做 B = A，那麼如果我們去修改 B 的值，那麼 A 也會一起被改到。

A = [1]
B = A
B.append(2)
print(A) # [1, 2]

這個概念稱為「Pass by Reference」，也就是 A 傳了 位置 給 B，而 A 和 B 在這之後，會「共用」這個位置的值。這種方式在多數的高階程式語言（如：Java），都是用這樣的方式去實作的。而當我們希望兩個人是不同的 object 時，我們會需要做所謂的 Deep Copy，也就是將這個 object 內的所有東西複製成另一個東西。

而在 C++ 當中，我們也可以藉由 & 的符號（跟位址同個符號）去傳一個參考值給函數。範例就像下面這樣：

void f(int &x){
    x = 2;
}

int main(){
    int a = 1;
    f(a);
    cout << a << "\n"; // 2
}

不過 C 或 C++ 當中，內建的方式為「Pass by Value」，也就是在做 B = A 時，程式會自動複製一個新的 A 給 B。而 C 也沒有像 C++ 那樣有方便的 reference 可以使用，所以我們會需要用到所謂的「指標」

指標的概念

一個變數在 C 程式裡面的儲存大概長這樣，每個變數會存在一塊記憶體內，大小根據不同的型態會有所變化（int 佔 4 byte，char 佔 1 byte 等等）

在 C 裡面，有一種特別的運算子叫做 &，又被稱為「取址運算子」，用法為 &(變數名稱) 可以去得到一個變數在記憶體內所儲存的位址（Memory Address）。我們可以藉由下面這個程式大概去理解他的用法。

int main(){
    int x = 1;
    printf("Address: %p. Value: %d", &x, x);
}

而在 C 裡面，如果我們想要存取一個位址的值。我們需要用到另一個特別的運算子，稱為 dereference operator，也就是 *。他的用法為 *(位址)，可以去存取某個記憶體位址中的值。可以想成如果我有一個人的身份證字號，我想要知道他的名字，使用這個 operator 就可以知道他的值。用法如下：

int main() {
    int x = 1;
    printf("%d %d", *(&x), x); // 1 1
}

而我們在某些情況下，可能會想要「使用一個變數去儲存位址」，我們就會用到「指標」的概念。在 C 當中，假設我們想要宣告一個指標，我們會寫 [型態] *(指標名稱），而一個指標通常會指到某一個位址。詳細例子如下：

int main() {
    int x = 10;
    int *p = &x;
    printf("%d", *p); // 10
}

指標的型態，影響的其實是「一個指標所指到的空間大小」。這裡所講的空間，並不是指標本身的空間（如果你打 sizeof(int *)，或者是 sizeof(任何型態 *)，基本上都會是 4 or 8 byte）。他的概念比較難解釋，但畫成圖大概會長這樣（以 int x 為例）

一個指標其實會指到的是一個變數在記憶體內所儲存的第一格（第一個 byte）位置。也就是說，如果一個指標的型態是 int，那麼其實他佔用了後面的四格，而當我們去使用 *(&x) 時，他其實會去找的是後面這四格所代表的整數值會是多少。

因此，其實指標還有另一種叫做「Void Pointer」的東西，也就是任何型態都可以存的指標。但如果遇到他，要記得把他轉型成正確型態的指標。

陣列也是指標！

在 C/C++ 裡面，其實陣列就是一個指標。當我們去寫 int arr[5] 的時候，其實背後的原理是「程式會去找一塊 5 * (4 byte) 的記憶體空間」並且「將 arr 這個指標指到最前面的位置」。而當我們去寫 arr[i] 時，其實它等同於寫 *(arr + i)，它也等同於 i[arr] 的這種寫法，但不常用。

一個簡單的例子如下：

int arr[3] = {1, 2, 3};

printf("%d %d %d", arr[0], *(arr + 1), 2[arr]); // 1 2 3

指標的加減法

對於一個指標，假設它的變數型態占

$k$ byte，那麼當我們去做 ptr + 1，它就會跳到記憶體中後面

$k$ 個 byte 的位置。下圖示意了如果 ptr 是 int * 的話，會是什麼樣的狀況。

同樣的，假設我們用 ptr - 1，則它也會跳到前面

$k$ 個 byte 的位置。

如果有兩個指標 p1, p2，那 p1 - p2 會回傳一個整數，表示兩個指到的位置差了多少 byte。

用指標實現 pass by reference

因為在 C 裡面，所有的 assignment operator 和函式都是 pass by value。因此，我們會需要使用指標這種儲存變數位置的東西來幫助我們達成與高階程式語言的 pass by reference 相同的功能。

當我們希望能修改某一個位址的值時，用法會是 *(位址) = val （val 是我們想要給那個位址的值）。因此，我們可以做到下面這樣：

int x = 1;
int *p = &x;
*p = 2;
printf("%d", x); // 2

如果我們搭配函數，也可以做到同樣的事

// 錯誤示範 呼叫 swap1(a, b)
void swap1(int a, int b){
    int tmp = a;
    a = b;
    b = tmp;
}

//正確做法 呼叫 swap2(&a, &b)
void swap2(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

這個概念極其重要，當我們需要用另一個變數去修改到原本應該要修改的東西時，就要想到指標！

指標的指標

一個指標其實在 C 裡面也是一個變數，因此，我們也可以用另一個指標去指他

範例如下：

int x = 1;
int *p1 = &x;
int **p2 = &p1;

printf("%d %d %d", x, *p1, **p2); // 1 1 1

當我們要去取值的時候，打 **指標 其實等同於 *(*指標)。

這種多重指標，在我們需要去寫一個資料結構時，會變得非常重要！

Structure 的指標

假設我們今天有一個 structure，例如下面這樣

typedef struct point{
    int x, y;
} Point;

那麼，如果我們有一個 Point *ptr 的指標，那麼我們在獲取指標的值時，我們可以用 arrow operator 去取得他的值，也就是 ptr->x 這種寫法，它的運作方式與 (*ptr).x 相同。

動態記憶體配置（Dynamic Memory Allocation）

在剛剛的內容中，我們提到，其實當我們宣告一個陣列時，「程式會去找一塊 陣列長度 * (變數大小) 的記憶體空間」。而在 C 裡面，所有我們開好的變數、陣列，它的大小都不能夠被改變。因此，我們會需要動態的去配置我們的空間。

在 C 裡面，這個東西我們會使用到 malloc(size_t size) 這個函式。我們會傳我們需要用到的記憶體大小給他，而如果空間夠（基本上不可能會不夠），他就會回傳一個指標 void *。因此我們通常會把他轉型。

使用方法如下，假設我們要開一個長度為 5 的陣列：

int *arr = (int *) malloc(5 * sizeof(int));
arr[0] = 1, arr[1] = 2, arr[2] = 3, arr[3] = 4, arr[4] = 5;

for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]); // 1 2 3 4 5
}

有時候，我們可能也會拿來開一個 struct 的空間，例如 Linked List 要開一個新的 Node 就會用到這個函式。

Linked List

基本上是學 C 第一個學到的資料結構，他的長相如下：

是一個由很多個 Node 所組成的一種資料結構。

Singly Linked List

第一種我們會看到的是單向的 linked list，節點所儲存的內容如下：

typedef struct node {
    int val;
    struct node *nxt;
} Node;

也就是每個節點儲存了「值」和「下一個節點」。

我們在儲存一個 linked list 的時候，會儲存它 最前端的節點

接著在這個 list 上去做各式各樣的操作

以下是一個簡單的 linked list 宣告

node *list = NULL; // 將 list 的頭設成空的節點

接著，我們可以寫各種不同的功能。

有兩種遍歷一個 linked list 的方法

1. 開一個 curr 的 pointer，接著不斷的將 curr 往後移
2. 開兩個 pointer，分別是 curr 和 prev，在將 curr 往後移的過程中，順便更新 prev （這又叫做 Tom and Jerry Traversal）

印出整個 linked list

使用第一種方法。在移動 curr 的過程中，輸出它的值

void printList(Node *list){
    Node *curr = list;
    while(curr != NULL){
        printf("%d ", curr->val);
        curr = curr->nxt;
    }
    printf("\n");
}

在最後面插入

$x$

使用第一種方法。它的概念是，我們必須先找到 list 最尾端的節點，並在最尾端的節點後面開一個新的節點，而那個節點要存

$x$ 這個值。

void push_back(node **list, int x){
    if(*list == NULL){
        *list = (Node *)malloc(sizeof(Node));
        (*list)->val = val;
        (*list)->nxt = NULL;
    } else {
        Node *curr = *list;
        while (curr->nxt != NULL) {
            curr = curr->nxt;
        }
        curr->nxt = (Node *)malloc(sizeof(Node));
        curr->nxt->val = val;
        curr->nxt->nxt = NULL;
    }
}

特例：如果 list 原本是空的，必須額外判斷

在最前面插入

$x$

我們要開一個新的節點，把 list 的開頭設成那個節點，並且把那個節點的下一個人連到原本的開頭

void push_front(Node **list, int val){
    Node *tmp = *list;
    *list = (Node *)malloc(sizeof(Node));
    (*list)->val = val;
    (*list)->nxt = tmp;
}

刪除第

$i$ 個位置的元素

使用第二種方法。我們將 curr 移到第

$i$ 個位置。那我們只要將 prev 連到 curr 的下一個人。我們的 linked list 就將 curr 給移除了！

接著就只要打 free(curr) 就可以把那個元素整個刪除掉了。

void del(Node **list, int index){
    if(index == 0){
        *list = (*list)->nxt;
    } else{
        Node *curr = *list, *prev = NULL;
        int i = 0;
        while(i < index){
            prev = curr;
            curr = curr->nxt;
            i++;
        }
        prev->nxt = curr->nxt;
        free(curr);
    }
}

特例：我們的寫法在刪除開頭時會出現問題，要特判

反轉整個 linked list

使用第二個方法。概念是這樣：我們可以把每一個人都指到他前一個人，接著將 list 設城是最尾端的人。

void reverse(Node **list){
    Node *curr = *list, *prev = NULL;
    while(curr != NULL){
        Node *tmp = curr->nxt;
        curr->nxt = prev;
        prev = curr;
        curr = tmp;
    }
    *list = prev;
}

練習

https://codeforces.com/gym/469590