2020q3 Homework1 (quiz1)

contributed by <RusselCK >

tags: `RusselCK`

題目描述

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

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

已知不存在 circular (環狀結構)

1. `append_entry` : 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference ，而非 copy













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;
}

程式碼(已知部分)：

#1    node_t **indirect = head;

- 建立一個指向head 的指標indirect

#5    node_t *new_node = malloc(sizeof(node_t));
#6    new_node->value = new_value;
#7    new_node->next = NULL;

- 配置一個新增的節點 new_node

#10    while (*indirect)
#11        indirect = &(*indirect)->next;

- 迴圈測試 *indirect 取值是否為NULL，
  若不為 NULL，則將 indirect 設為指向 (*indirect)->next 的指標
  (即將indirect設為指向(最後一個node)->next的指標)

補完程式碼：

由已知部分及 append_entry 的功能定義來推論， #10#11 完成後還缺少將 new_node 放置在linked list 的步驟。因此先考慮 *indirect = new_node 的位置：
- 若將 *indirect = new_node 放置在 AA1，則無法達成 append_entry 的功能。

- 若將 *indirect = new_node 放置在 AA2，可將 new_node 完美接在 linked list 之後。

- 因此， AA2 為 *indirect = new_node

由刪去法可知， AA1 為 assert(new_node)

The C library macro void assert(int expression) allows diagnostic information to be written to the standard error file. In other words, it can be used to add diagnostics in your C program.

#include <assert.h>

assert(int expression)
- Expression can be a variable or any C expression.
- If expression evaluates to TRUE, assert() does nothing. If expression evaluates to FALSE, assert() displays an error message on stderr (standard error stream to display error messages and diagnostics) and aborts program execution.

Source：https://www.tutorialspoint.com/c_standard_library/c_macro_assert.htm

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










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;
}

程式碼(已知部分)：

#3    for (node_t **node = &head; *node && (*node)->next; BB1)

for迴圈
- 起始狀態 node_t **node = &head ：建立一個指向 head 的指標
- testExpression *node && (*node)->next ：確認 *node 及 (*node)->next 是否為 NULL ，皆不為 NULL 才可進入迴圈
- 更新狀態 BB1

組內交換

#4    node_t *tmp = *node;

#5    BB2; //*node=(*node)->next

#6    tmp->next = (*node)->next;

#7    (*node)->next = tmp;

補完程式碼：

根據 swap_pair 功能定義且已知BB1為迴圈的更新狀態，可推得BB1的效果為將 node 所指向的位址由 *node 的位址改為 (*node)->next->next 的位址
因此， BB1 為 node = &(*node)->next->next
為使組內交換成功，可推得 BB2 為 *node=(*node)->next

3. `reverse`: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1










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

程式碼(已知部分)

#3    node_t *cursor = NULL;

- 建立一個空的node_t cursor

- 反序

#4    while (head)

- while 回圈： head 不為 NULL 時可進入迴圈

#5        node_t *next = head->next;

#6        CCC; //head->next = cursor; cursor = head

#7        head = next;

補完程式碼

為使反序成功，可推得 CCC 為 head->next = cursor; cursor = head

4.`remove_entry`: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)

Q2. 請用指標的指標來改寫`swap_pair` 和 `reverse`，並避免回傳指標

1. `swap_pair`











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

主程式呼叫


swap_pair(&head);

2. `reverse`












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

主程式呼叫


reverse(&head);

Q3. 以遞迴改寫上述的 `reverse`

注意，你可能因此需要建立新的函式，如 rev_recursive ，隨後在 reverse 函式中呼叫 rev_recursive


















void rev_recursive(node_t *head,node_t *cursor,node_t **list)
{
    node_t *next = head->next;
    head->next = cursor;    
    
    if (!next) {        
        *list = head;
        return; 
    }else 
        rev_recursive(next, head, list);
}

void reverse(node_t **head)
{
    node_t *cursor = NULL;
    if(*head)
        rev_recursive(*head,cursor,head);
}

運作原理(簡單示意)：
- 初始狀態

- rev_recursive(*head,cursor,head);

- rev_recursive(next, head, list);

- rev_recursive(next1, next, list);








if (!next) {        
        *list = head;
        return; 
}
// in this case, 
//  next is next2, 
//  list is head, 
//  head is next1

結束遞迴，完成 reverse

Q4. 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量

The basic method given for generating a random permutation of the numbers 1 through N goes as follows:
1. Write down the numbers from 1 through N.
2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
3. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.
4. Repeat from step 2 until all the numbers have been struck out.
5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.
Example (pancil-and-paper method)：

Range	Roll	Scratch	Result
		1 2 3 4 5 6 7 8
1-8	3	1 2 3 4 5 6 7 8	3
1-7	4	1 2 3 4 5 6 7 8	3 5
1-6	5	1 2 3 4 5 6 7 8	3 5 7
1-5	3	1 2 3 4 5 6 7 8	3 5 7 4
1-4	4	1 2 3 4 5 6 7 8	3 5 7 4 8
1-3	1	1 2 3 4 5 6 7 8	3 5 7 4 8 1
1-2	2	1 2 3 4 5 6 7 8	3 5 7 4 8 1 6
		1 2 3 4 5 6 7 8	3 5 7 4 8 1 6 2

實作：



































#include <time.h>

void shuffle(node_t **head)
{
    //Initial Range
    int range = 0;
    node_t **indirect = head;
    while (*indirect) {
        range++;
        indirect = &(*indirect)->next;
    }

    srand(time(NULL));

    node_t *cursor = NULL;
    while (range)
    {
        // roll
        int roll = rand()%range;

        // strick out the number
        indirect = head;
        while(roll)
        {
            indirect = &(*indirect)->next;
            roll--;
        }
        // upadate the result
        add_entry(&cursor,(*indirect)->value);
        // remmove the struck out number
        remove_entry(&(*head), *indirect);
        range--;
    }
    *head = cursor;
}

程式碼概述：

    //Initial Range
# 6 int range = 0;
# 7 node_t **indirect = head;
# 8 while (*indirect) {
# 9     range++;
#10     indirect = &(*indirect)->next;
    }

首先，先取得 Range ，即 linked list 長度 range
接下來會有重複range次的動作，依次取得結果，每完成一次，range就減 1

#15 node_t *cursor = NULL;

先建立 cursor 用來存放洗牌後的結果 ( Result )

#19     int roll = rand()%range;

1~range 隨機選出編號 roll

#22     indirect = head;
#23     while(roll)
        {
#25         indirect = &(*indirect)->next;
#26         roll--;
        }

找出編號 roll 的 node

#29     add_entry(&cursor,(*indirect)->value);

將找到的 node 的 value 加入 cursor

#31     remove_entry(&(*head), *indirect);

將找到的 node 從 head 刪除
迴圈結束後， cursor 即為結果

2020q3 Homework1 (quiz1)

tags: RusselCK

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

1. append_entry : 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference ，而非 copy

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

3. reverse: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

4.remove_entry: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)

Q2. 請用指標的指標來改寫swap_pair 和 reverse，並避免回傳指標

1. swap_pair

2. reverse

Q3. 以遞迴改寫上述的 reverse

Q4. 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量

實作：

程式碼概述：

Read more

VSCode 套件安裝

ARGB To BW

深入淺出物件導向分析與設計 筆記

TCL 讀書會(?