2020q3 Homework1 (quiz1)

contributed by < ZhuMon >

tags: `sysprog2020`, `quiz`

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

Table of Contents

2020q3 Homework1 (quiz1)

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

題目

考慮一個單向 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

Image Not Showing Possible Reasons The image file may be corruptedThe server hosting the image is unavailableThe image path is incorrectThe image format is not supported Learn More → Table of Contents

Image Not Showing Possible Reasons The image file may be corruptedThe server hosting the image is unavailableThe image path is incorrectThe image format is not supported Learn More → 題目

程式運作原理

add_entry()

find_entry()

remove_entry()

swap_pair()

Read more

透過 Netfilter 自動過濾廣告

2020q3 Homework3 (dict)

2020q3 Homework2 (quiz2)

2020q1 Homework1 (lab0)