tags: Linux核心

2020q3 Homework1 (quiz1)

contributed by < heysun0728 >

詳細題目內容點此

1. 解釋程式運作原理

To do

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

• #5~#7：為新建立的 node 分配空間，並設定 value 及 next 值
• assert(new_node);
  • 在 ISO/IEC 9899 (a.k.a C99 Standard) 中 7.2.1.1 內可查閱到 assert macro 功能
  • 此處是為確保 malloc 能正確為 new_node 分配到空間
• #10~#12：在 while 迴圈中 indirect 會從頭開始一一指向 list 中每一個 node，直到走到 list 尾端才會結束。此時 #12 會將 new_node 插入至最後一個 node 的 next 指標所指向之處。

函數作用：將 *head 指向的 list 尾端加入一個值為 new_value 的 new node

swap_pair

node_t *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;
    }
    return head;
}

reverse

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

2. 用指標的指標改寫 swap_pair 和 reverse

函式 swap_pair 和 reverse 需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標。

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

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

int main(int argc, char const *argv[])
{
    ...
    swap_pair(&head);
    print_list(head);

    reverse(&head);
    print_list(head);
}

3. 撰寫遞迴版 reverse

以遞迴改寫上述的 reverse。

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

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

4. 實做 Fisher-Yates shuffle

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

To do