Try   HackMD

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






%0



head
head



A

A



head->A





indirect
indirect



indirect->head





NULL
NULL



B

B



A->B





C

C



B->C





C->NULL





#5    node_t *new_node = malloc(sizeof(node_t));
#6    new_node->value = new_value;
#7    new_node->next = NULL;
    • 配置一個新增的節點 new_node






%0



new_node

new_node



NULL
NULL



new_node->NULL





#10    while (*indirect)
#11        indirect = &(*indirect)->next;
    • 迴圈測試 *indirect 取值是否為NULL,
      若不為 NULL,則將 indirect 設為指向 (*indirect)->next 的指標
      (即 將indirect設為指向(最後一個node)->next的指標)






%0



head
head



A

A



head->A





indirect
indirect



NULL
NULL



indirect->NULL





new_node

new_node



NULL1
NULL



new_node->NULL1





B

B



A->B





C

C



B->C





C->NULL





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






%0



head
head



A

A



head->A





indirect
indirect



new_node

new_node



indirect->new_node





NULL
NULL



new_node->NULL





B

B



A->B





NULL1
NULL



C

C



B->C





C->NULL1





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






%0



head
head



A

A



head->A





indirect
indirect



new_node

new_node



indirect->new_node





B

B



A->B





C

C



B->C





C->new_node





    • 因此, AA2 為 *indirect = new_node
  1. 由刪去法可知, 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






%0



n
node



head
head



n->head





A

A



head->A





NULL
NULL



B

B



A->B





C

C



B->C





C->NULL





  • 組內交換
#4    node_t *tmp = *node;






%0



n
node



head
head



n->head





A

A



head->A





tmp
tmp



tmp->A





NULL
NULL



B

B



A->B





C

C



B->C





C->NULL





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






%0



n
node



head
head



n->head





B

B



head->B





tmp
tmp



A

A



tmp->A





NULL
NULL



A->B





C

C



B->C





C->NULL





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






%0



n
node



head
head



n->head





B

B



head->B





tmp
tmp



A

A



tmp->A





C

C



A->C





NULL
NULL



B->C





C->NULL





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






%0



n
node



head
head



n->head





B

B



head->B





tmp
tmp



A

A



tmp->A





B->A





NULL
NULL



C

C



A->C





C->NULL





  • 補完程式碼:
  1. 根據 swap_pair 功能定義且已知BB1為迴圈的更新狀態,可推得BB1的效果為將 node 所指向的位址由 *node 的位址改為 (*node)->next->next 的位址
    因此, BB1 為 node = &(*node)->next->next
  2. 為使組內交換成功,可推得 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






%0



cursor
cursor



NULL
NULL



cursor->NULL





    • 反序
#4    while (head) 
    • while 回圈: head 不為 NULL 時可進入迴圈
#5        node_t *next = head->next;






%0



next
next



B

B



next->B





head
head



A

A



head->A





NULL
NULL



A->B





C

C



B->C





C->NULL





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






%0



cursor
cursor



A

A



cursor->A





next
next



B

B



next->B





head
head



head->A





NULL
NULL



C

C



B->C





C->NULL





A->cursor





#7        head = next;






%0



cursor
cursor



A

A



cursor->A





next
next



B

B



next->B





head
head



head->B





NULL
NULL



C

C



B->C





C->NULL





A->cursor





  • 補完程式碼
  1. 為使反序成功,可推得 CCC 為 head->next = cursor; cursor = head

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

Q2. 請用指標的指標來改寫swap_pairreverse,並避免回傳指標

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); }
  • 運作原理(簡單示意):

    • 初始狀態






%0



head
head(list)



A

A



head->A





cursor
cursor



NULL1
NULL



cursor->NULL1





NULL2
NULL



B

B



A->B





C

C



B->C





C->NULL2





    • rev_recursive(*head,cursor,head);






%0



head
head(list)



A

A



head->A





cursor
cursor



NULL1
NULL



cursor->NULL1





next
next



B

B



next->B





NULL2
NULL



A->NULL1





C

C



B->C





C->NULL2





    • rev_recursive(next, head, list);






%0



head
head(list)



A

A



head->A





cursor
cursor



NULL1
NULL



cursor->NULL1





next
next



B

B



next->B





next1
next1



C

C



next1->C





NULL2
NULL



A->NULL1





B->A





C->NULL2





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






%0



head
head(list)



C

C



head->C





cursor
cursor



NULL1
NULL



cursor->NULL1





next
next



B

B



next->B





next1
next1



next1->C





next2
next2



NULL2
NULL



next2->NULL2





C->B





A

A



B->A





A->NULL1





  • 結束遞迴,完成 reverse






%0



head
head(list)



C

C



head->C





NULL1
NULL



B

B



C->B





A

A



B->A





A->NULL1





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 即為結果