2020q3 Homework1 (quiz1)

contributed by < chi-ming5566 >

---

程式運作

以 add_entry(), find_entry(), remove_entry(), swap_pair(), reverse(), print_list() 等函式所組成

---

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;

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

• 答案

  • AA1為 (a) assert(new_node)
  • AA2為 (b) *indirect = new_node

• 說明

  • *head會指向 linked list 的尾端，在其插入一個 value 為 new_value 的 node。
  • **indirect 是用來尋找 linked list (**head) 的尾端，而當 *indirect 找到尾端時， *indirect == NULL，就會將 new_node 插入linked list。
  • 而 assert 是要確保 new_node 會正確分配記憶體，於是建立第一個 node，所以會直接跳到第 11 行，將 indirect 所存放的 value 當作 adrress，並且更改此 address 存放的 value，將該 value 改為 new_node 的 value。

---

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

• 說明
  • 用 for 迴圈找到*head 後，傳回存放的值為 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 *head 然後刪除。
  • 需要變更的 pointer 只有指向 entry 的 pointer，因此以 **indirect 存放此 pointer 的 address。
  • 最後將此 *indirect 指向 entry->next，就不會有其他 pointer 指向該處。

• 以作業為例:

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

先執行到第10行，接著將 head 的 address與要刪除的 node 的 address 當作參數，一起傳入remove_entry()。

---

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

head 的 value 是 main 的 head 的 address
indirect 存放 head 存放的 value

---

*indirect = entry->next;

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

---

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

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