2023q1 Homework1 (lab0)

contributed by < oEric0929o >

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           167
Model name:                      11th Gen Intel(R) Core(TM) i5-11400F @ 2.60GHz
Stepping:                        1
CPU MHz:                         2600.000
CPU max MHz:                     4400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5184.00

開發過程

拿到這份作業的一開始可以說是毫無頭緒，自己嘗試閱讀資料後不知道要如何開始，直到詢問 Thegoatistasty 同學，他建議我依照測資順序一步一步完成，才慢慢開始有進度。撰寫程式的過程大多是先想辦法讀懂同學的程式碼，再自己寫出來，過程中有明顯感覺到自己有進步，最後有幾個函式靠自己查資料完成，很有成就感。能完成這份作業真的很感謝 Thegoatistasty 同學的幫忙，給了我方向也解答了我很多疑問。

q_new

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *p = malloc(sizeof(struct list_head));
    if (!p)
        return NULL;
    INIT_LIST_HEAD(p);
    return p;
}

q_free

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *temp, *safe;
    list_for_each_entry_safe (temp, safe, l, list) {
        list_del(&temp->list);
        free(temp->value);
        free(temp);
    }
    free(l);
}

q_insert_head

原本用 strcpy ，執行時報錯，參考文件後改用 snprintf

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_node = (element_t *) malloc(sizeof(element_t));
    if (!new_node)
        return false;

    new_node->value = (char *) malloc(strlen(s) + 1);
    if (!new_node->value) {
        free(new_node);
        return false;
    }

    snprintf(new_node->value, strlen(s) + 1, "%s", s);
    list_add(&new_node->list, head);
    return true;
}

q_insert_tail

將 q_insert_head 中的 list_add 改成 list_add_tail 即可

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_node = (element_t *) malloc(sizeof(element_t));
    if (!new_node)
        return false;

    new_node->value = (char *) malloc(strlen(s) + 1);
    if (!new_node->value) {
        free(new_node);
        return false;
    }

    snprintf(new_node->value, strlen(s) + 1, "%s", s);
    list_add_tail(&new_node->list, head);
    return true;
}

q_remove_head

一開始想了很久想不出 sp 的功能，仔細看了 queue.h 中的敘述才發現是用來儲存刪除節點的字串內容

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head) || !sp)
        return NULL;

    element_t *p = list_entry(head->next, element_t, list);
    strncpy(sp, p->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    list_del(&p->list);
    return p;
}

q_remove_tail

q_remove_head 刪除 head 的下一個節點，而因為是雙向鏈結串列，所以 q_remove_tail 只要改成刪除 head 的前一個節點即可

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head) || !sp)
        return NULL;

    element_t *p = list_entry(head->prev, element_t, list);
    strncpy(sp, p->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    list_del(&p->list);
    return p;
}

q_size

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

運用快慢指標找到中間的節點並刪除

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *fast, *slow;
    fast = head->next->next;
    slow = head->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }

    list_del(slow);
    element_t *del = list_entry(slow, element_t, list);
    free(del->value);
    free(del);

    return true;
}

q_delete_dup

參考 GeeksforGeeks 的作法刪除多餘重複節點，再刪除每組重複節點的第一個節點

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;

    struct list_head *current = head->next;
    element_t *cur_node, *next_node;
    bool dup = false;
    while (current->next != head) {
        cur_node = list_entry(current, element_t, list);
        next_node = list_entry(current->next, element_t, list);
        if (strcmp(cur_node->value, next_node->value) == 0) {
            dup = true;
            list_del(&next_node->list);
            q_release_element(next_node);
        } else {
            current = current->next;
            if (dup == true) {
                list_del(&cur_node->list);
                q_release_element(cur_node);
                dup = false;
            }
        }
    }
    if (dup) {
        list_del(&cur_node->list);
        q_release_element(cur_node);
    }
    return true;
}

q_swap

利用 list_move 進行交換，將 p 放到 p->next 後方之後 p->next 剛好會是下一個要交換的節點

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *p;
    for (p = head->next; p->next != head && p != head; p = p->next)
        list_move(p, p->next);
}

q_reverse

利用 list_move 依序將每個節點放到最前面，即完成反轉

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
}

q_reverseK

利用 count 計數，當 count 到達 k 時用 list_move 做反轉，並移動 temp 來記錄下一次反轉的起始點

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || k <= 1)
        return;

    struct list_head *node, *safe, *temp = head;
    int count = 0;
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            struct list_head *cur_node = temp->next,
                             *next_node = temp->next->next;
            while (count != 0) {
                list_move(cur_node, temp);
                cur_node = next_node;
                next_node = next_node->next;
                count--;
            }
            temp = safe->prev;
        }
    }
}

q_sort

採用 merge sort ，參考你所不知道的 C 語言: linked list 和非連續記憶體中雙指標的方法實作 merge_two_lists ，再以遞迴的方式實作 merge sort ，排序前將頭尾切開，完成排序後再接起來

/* Merge two sorted lists */
struct list_head *merge_two_lists(struct list_head *l1,
                                  struct list_head *l2,
                                  bool descend)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;
    for (; l1 && l2; ptr = &(*ptr)->next) {
        element_t *a = list_entry(l1, element_t, list);
        element_t *b = list_entry(l2, element_t, list);
        if ((strcmp(a->value, b->value) <= 0 && !descend) ||
            (strcmp(a->value, b->value) > 0 && descend)) {
            *ptr = l1;
            l1 = l1->next;
        } else {
            *ptr = l2;
            l2 = l2->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}

/* Merge sort recursively */
struct list_head *merge_sort(struct list_head *head, bool descend)
{
    if (!head || !head->next)
        return head;
    struct list_head *fast, *slow;
    fast = slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    slow->prev->next = NULL;
    struct list_head *l1 = merge_sort(head, descend);
    struct list_head *l2 = merge_sort(slow, descend);
    return merge_two_lists(l1, l2, descend);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = merge_sort(head->next, descend);
    head->next->prev = head;
    struct list_head *p = head;
    while (p->next) {
        p->next->prev = p;
        p = p->next;
    }
    head->prev = p;
    p->next = head;
}

q_descend

以反序走訪，遇到較小的節點就刪除。架構和 q_delete_dup 很相似，將刪除的條件判斷從相等改為小於

/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    struct list_head *current = head->prev;
    element_t *cur_node = NULL, *prev_node = NULL;
    int len = 1;
    while (current->prev != head) {
        cur_node = list_entry(current, element_t, list);
        prev_node = list_entry(current->prev, element_t, list);
        if (strcmp(cur_node->value, prev_node->value) < 0) {
            list_del(&prev_node->list);
            q_release_element(prev_node);
        } else {
            len++;
            current = current->prev;
        }
    }
    return len;
}

q_merge

一開始對 queue_contex_t 和 list_head 不夠了解，一直想不明白 next 代表的意義，查看 queue.h 才發現這裡的參數 head 和其他函式不同，是 header of chain ，所以 head->next 是會在 chain 之間移動而不是 list 。將 chain 中的每一條 list 接在一起再做排序即可完成 merge

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *p = list_entry(head->next, queue_contex_t, chain);
    if (list_is_singular(head))
        return p->size;

    struct list_head *node;
    for (node = head->next->next; node != head; node = node->next) {
        queue_contex_t *tmp = list_entry(node, queue_contex_t, chain);
        list_splice_init(tmp->q, p->q);
    }
    q_sort(p->q, descend);
    return p->size;
}