2020q3 Homework1 (quiz1)

contributed by < ZhuMon >

tags: `sysprog2020`, `quiz`

2020q3 Homework1 (quiz1)

題目

考慮一個單向 linked list，其結構定義為:

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:

add_entry: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
remove_entry: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
swap_pair: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
reverse: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
對應的程式碼如下:








































































































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

typedef struct __node {
    int value;
    struct __node *next;
} node_t;

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    AA1;
    while (*indirect)
        indirect = &(*indirect)->next;
    AA2;
}

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        node_t *tmp = *node;
        BB2;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        CCC;
        head = next;
    }
    return cursor;
}

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    node_t *head = NULL;

    print_list(head);

    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    add_entry(&head, 110);
    add_entry(&head, 111);

    print_list(head);

    node_t *entry = find_entry(head, 101);
    remove_entry(&head, entry);

    entry = find_entry(head, 111);
    remove_entry(&head, entry);

    print_list(head);

    /* swap pair.
     * See https://leetcode.com/problems/swap-nodes-in-pairs/
     */
    head = swap_pair(head);
    print_list(head);

    head = reverse(head);
    print_list(head);

    return 0;
}

參考執行輸出: (第 1 行是換行符號)






72 101 108 109 110 111 
72 108 109 110 
108 72 110 109
109 110 72 108

請補完程式碼。

程式運作原理

以 add_entry(), find_entry(), remove_entry(), swap_pair(), reverse(), print_list() 等六個 function 組成

`add_entry()`














void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;

    *indirect = new_node;
}

目的：在 *head 所指向 linked list 的尾端插入一個 value 為 new_value 的 node
流程：使用 pointer to pointer (**indirect) 來找尋 linked list (**head) 的尾端，當 *indirect 到達尾端(*indirect == NULL)後，將新的 node (new_node) 插入linked list

詳細說明：

以三個 column 分別代表某一變數的 address, name, value

在呼叫 add_entry() 之前，可以看到 main() 先定義了一個指標 *head，並且沒有分配記憶體。
接著呼叫 print_list(head)，將 head 所指向的 linked list 印出來，由於目前head 為 NULL 因此只會印出一個換行符號。(稍後介紹 print_list)
然後呼叫 add_entry(&head, 72)，將 72 作為第一個 node 的值插入 linked list，並且藉由 pointer to pointer 的技巧，傳入 &head 直接在 add_entry() 中修改 main() 的 head 所指向的空間







int main(int argc, char const *argv[])
{
    node_t *head = NULL;
    
    print_list(head);
    
    add_entry(&head, 72);

Frame	Address	Parameter name	Value
main	0x7fffffffe2e8	head	0x0



void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

進入 add_entry 後，將 indirect 存放原先 head 的 address

Frame	Address	Parameter name	Value
main	0x7fffffffe2e8	head	0x0
add_entry	0x7fffffffe2a8	head	0x7fffffffe2e8
add_entry	0x7fffffffe2b0	indirect	0x7fffffffe2e8



    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

接著建立一個新的 node (new_node)，並且分配記憶體

Frame	Address	Parameter name	Value
main	0x7fffffffe2e8	head	0x0
add_entry	0x7fffffffe2a8	head	0x7fffffffe2e8
add_entry	0x7fffffffe2b0	indirect	0x7fffffffe2e8
add_entry	0x7fffffffe2b8	new_node	0x555555757670
add_entry	0x555555757670	*new_node	{value = 72, next = 0x0}






    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;

    *indirect = new_node;
}

assert 確保 new_node 正確分配記憶體(也可以將 assert 移至 malloc 後)
由於是建立第一個 node，所以會直接跳到第 21 行，將 indirect 所存放的 value 作為 adrress，更改該 address 存放的 value，將該 value 改為 new_node 的 value

Frame	Address	Parameter name	Value
main	0x7fffffffe2e8	head	0x555555757670
add_entry	0x7fffffffe2a8	head	0x7fffffffe2e8
add_entry	0x7fffffffe2b0	indirect	0x7fffffffe2e8
add_entry	0x7fffffffe2e8	*indirect	0x555555757670
add_entry	0x7fffffffe2b8	new_node	0x555555757670
add_entry	0x555555757670	*new_node	{value = 72, next = 0x0}

由於 address 太長，會導致圖變小，因此將 address 省略前半段

`find_entry()`







node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

從傳入的 linked list node (*head)，以 for-loop 找到在該 node 後，傳回存放的值為 value 的 node，用於刪除某一個 node

`remove_entry()`










void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

目的：在 linked list (**head) 中，找到 node (*entry)，並且刪除
方法：因為需要更動的 pointer，只有指向 entry 的 pointer，因此以 **indirect 存放該 pointer 的 address，最後只要藉由將該 pointer 指向 entry->next，便沒有其他 pointer 指向該處，因此便可以優雅地達到目的

實例：

由於不管是變數或指標都是由 address 和 value 所組成，因此以兩個 column 分別代表 address 和 value
以下用箭頭連起來的兩個格子內容相同，並且格子左邊代表 address，右邊代表 value
若有第二個 row 則代表存放 next 的資訊














    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    add_entry(&head, 110);
    add_entry(&head, 111);

    print_list(head);

    node_t *entry = find_entry(head, 101);
    remove_entry(&head, entry);

    entry = find_entry(head, 111);
    remove_entry(&head, entry);

此處先執行到 86 行，接著將 head 的 address，與要刪除的 node 的 address 作為參數，一起傳入remove_entry()

傳入的 head 的 value 是 main 的 head 的 address
此處讓 indirect 存放 head 存放的 value



void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

若是 (*indirect) != entry 便會進入 while，並且讓 indirect 的值為 *indirect 所指向的 object 的 next address，接著因為 *indirect 的值是否與 entry 的值相同，所以跳出 while


    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

讓 *indirect 所存放的值換為 entry->next，如此便可以達到刪除的目的


    *indirect = entry->next;

將刪除的 node 的記憶體釋放，由於只是釋放 entry 所指向的記憶體空間，因此存放 pointer entry 的空間並沒有釋放，不過在這個 function 結束後，就會自動釋放


    free(entry);

`swap_pair()`










node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        node_t *tmp = *node;
        BB2;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

BB1 = ?

(a) node = (*node)->next->next
(b) *node = (*node)->next->next
(c) *node = ((*node)->next)->next
(d) *node = &((*node)->next)->next
(e) node = &(*node)->next->next
(f) *node = &(*node)->next->next

BB2 = ?

(a) node = (*node)->next
(b) node = &(*node)->next
(c) *node = (*node)->next
(d) *node = &(*node)->next
(e) *node = &((*node)->next)

目的：交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
方法

2020q3 Homework1 (quiz1)

tags: sysprog2020, quiz

Table of Contents

題目

程式運作原理

add_entry()

find_entry()

remove_entry()

swap_pair()

Read more

透過 Netfilter 自動過濾廣告

2020q3 Homework3 (dict)

2020q3 Homework2 (quiz2)

2020q1 Homework1 (lab0)

tags: `sysprog2020`, `quiz`

`add_entry()`

`find_entry()`

`remove_entry()`

`swap_pair()`