2023q1 Homework1 (lab0)

contributed by < Thegoatistasty >

注意書寫規範：中英文間用一個半形空白字元區隔。

jserv

謝謝老師，有進行修改了

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            13
    CPU max MHz:         4500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5199.98

開發過程

q_new

struct list_head *q_new()
{
    struct list_head *head = (struct list_head*) malloc(sizeof(*head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

q_free

void q_free(struct list_head *l) {
    if(!l)
        return;
    element_t *save, *temp;

    list_for_each_entry_safe(temp, save, l, list)
        q_release_element(temp);
    free(l);
}

q_insert_{head,tail}

這邊曾經遇到的問題是沒有預留 '/0' 位置給 value，導致出現

ERROR: Corruption detected in block with address 0x55a707abb980 when attempting to free it

目前還沒找到是哪裡產生這樣的訊息，不過解決方法就是在 malloc 時多加一個 byte 的空間

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new = (element_t*) malloc(sizeof(element_t));
    if (!new)
        return false;
    
    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);//+1 for '/0'
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add(&new->list, head);


    return true;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new = (element_t*) malloc(sizeof(*new));
    if (!new)
        return false;

    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add_tail(&new->list, head);
    return true;
}

q_remove_head、q_remove_tail

遇到的問題類似，以q_remove_head為例

查詢教育部辭典「蠻」，改進你的漢語書寫。

jserv

收到！

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head)
        return NULL;
    
    sp = (char*) malloc(bufsize * sizeof(char*));
    if(!sp)
        return NULL;
    element_t* first_entry = list_first_entry(head, element_t, list);

    strncpy(sp, first_entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';

    list_del(head->next);
    return first_entry;
}

原本這麼寫，但會跑出

ERROR: Failed to store removed value

後來發現sp已經malloc過了(q_test.c裡do_remove的remove)，再malloc一次會在測試時找不到原本的位置，所以將malloc刪掉就好了

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head)
        return NULL;
    if(!sp)
        return NULL;
        
    element_t* last_entry = list_last_entry(head, element_t, list);
    strncpy(sp, last_entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    list_del(head->next);
    return last_entry;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new = (element_t*) malloc(sizeof(*new));
    if (!new)
        return false;

    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add_tail(&new->list, head);
    return true;
}

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    for(struct list_head* node = head->next; node->next != head; node = node->next){
        list_del(node);
        list_add(node, node->next);
    }
}

q_delete_mid

利用老師上課提到的『指標一快一慢』的方法（Hare & Tortoise Algorithm）

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    // Hare & Tortoise Algorithm
    struct list_head *fast, *slow;
    fast = slow = head->next;
    do{
        fast = fast->next;
        if(fast == head)
            break;
        slow = slow->next;
        fast = fast->next;
    }while(fast != head);
    list_del(slow);
    return true;
}

q_sort

參考 npes87184's blog的作法，再以自己的方法實作

為了實作 merge sort，我加入了兩個函式:

• struct list_head *merge_two_lists : 用來合併二個鏈結串列
• struct list_head *merge_sort : merge sort 的遞迴式

merge_two_lists 原本是這麼做的

struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
    struct list_head *temp = (struct list_head *)malloc(sizeof(temp));
    if(!temp)
        return list1;
    struct list_head *save = temp;
    while(list1 && list2){
        element_t *v1 = list_entry(list1, element_t, list);
        element_t *v2 = list_entry(list2, element_t, list);
        if(strcmp(v1->value, v2->value) >= 0){
            temp->next = list1;
            list1->prev = temp;
            temp = list1 = list1->next;
        }
        else{
            temp->next = list2;
            list2->prev = temp;
            temp = list2 = list2->next;
        }
    }
    if(!list1){
        temp->next = list2;
        list2->prev = temp;
    } 
    if(!list2){
        temp->next = list1;
        list1->prev = temp;
    } 
    free(temp);
    return save->next;

但當我 make test 時會顯示

FATAL ERROR: Calls to malloc disallowed

發現它不讓我使用 malloc，思來想去找不到好方法，於是尋找是否有人用類似的方法。結果找到 @seasonwang 和我參考的是同一個部落格，而且是用 indirect pointer 的方式，於是我將他的基礎上改進程式碼（減少一個 indirect pointer ），並改為

請查詢英文字典，理解 "optimize" 和 "improve" 的差異。
注意 資訊科技詞彙翻譯

jserv

struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
{
    struct list_head *temp = NULL;
    struct list_head **indirect = &temp;
    struct list_head *last = NULL;
    while (list1 && list2) {
        element_t *v1 = list_entry(list1, element_t, list);
        element_t *v2 = list_entry(list2, element_t, list);
        if (strcmp(v1->value, v2->value) <= 0) {
            list1->prev = *indirect;
            *indirect = list1;
            list1 = list1->next;
        } else {
            list2->prev = *indirect;
            *indirect = list2;
            list2 = list2->next;
        }
        last = *indirect;
        indirect = &((*indirect)->next);
    }
    if (!list1) {
        last->next = list2;
        list2->prev = last;
    }
    if (!list2) {
        last->next = list1;
        list1->prev = last;
    }
    return temp;
}

然後是遞迴的 merge sort

struct list_head *merge_sort(struct list_head *head)
{
    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;
    slow->prev = NULL;
    struct list_head *list1 = merge_sort(head);
    struct list_head *list2 = merge_sort(slow);
    
    return merge_two_lists(list1, list2);
}

再來是作業的 q_sort，當時忘記重新連結頭跟尾，debug 了很久

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if(list_empty(head))
        return;
    // break the list circle
    head->prev->next = NULL;
    head->prev = NULL;
    // merge sort
    head->next = merge_sort(head->next);
    // reconnect
    head->next->prev = head;
    struct list_head *t = head;
    while (t->next != NULL) {
        t->next->prev = t;
        t = t->next;
    }
    head->prev = t;
    t->next = head;
}

q_merge

我第一眼看到這個函式時，蠻疑惑為什麼會需要 merge多個 list，因為之前操作都是只有一個 list 的情形。於是閱讀了 qtest.c 的 do_merge 和 do_new 才發現一直以來操作的其實是 current->q。
而在 do_merge 呼叫 q_merge 時會傳入 &chain.head，並接收 merge 完後 list 的長度。所以要存取所有的 list 的話，需要用到 queue_context_t 這個 struct。

int q_merge(struct list_head *head)
{
    
    if(!head || list_empty(head))
        return 0;
    
    queue_contex_t *headchain = list_entry(head->next, queue_contex_t, chain);
    if(list_is_singular(headchain->q))
        return headchain->size;

    for(struct list_head *h = head->next->next; h != head; h = h->next){
        queue_contex_t *qctx = list_entry(h, queue_contex_t, chain);
        headchain->size += qctx->size;
        list_splice_tail_init(qctx->q, headchain->q);
    }
    q_sort(headchain->q);
    return headchain->size;
    // https://leetcode.com/problems/merge-k-sorted-lists/
}

q_descend

2487. Remove Nodes From Linked List

改以 Graphviz 製圖

jserv

最直觀的解法應該是從頭開始逐一節點檢查，但是這樣時間複雜度會是

$O(n^2)$。我觀察之後發現可以由最後一個 node 往前 traverse，遇到 value 比較小的直接 delete 掉，如此時間複雜度就變為

$O(n)$

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;

    int len = 1;
    element_t *t = list_entry(head->prev, element_t, list);
    char *v = t->value;
    struct list_head *h, *safe;
    for(h = head->prev->prev, safe = h->prev; h != head; h = safe, safe = h->prev){
        t = list_entry(h, element_t, list);
        if(strcmp(v, t->value) > 0){
            list_del(h);
            q_release_element(list_entry(h, element_t, list));
        }
        else{
            v = t->value;
            len++;
        }
    }
    return len;
}

q_reverse、q_reverseK

二者非常類似，我都是將 traverse 到的點用 list_move 移到head後面，比較不同的是 q_reverseK 需要額外用一個 counter 計數以及 head 的位置要調整而已

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

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_is_singular(head))
        return;
    struct list_head *node, *safe, *start;
    
    start = head;
    int counter = 0;
    list_for_each_safe(node, safe, head){
        counter++;
        if(counter == k){
            struct list_head *temp, *temp_safe;
            for(temp = start->next, temp_safe = temp->next; temp != safe; temp = temp_safe, temp_safe = temp->next)
                list_move(temp, start);
            counter = 0;
            start = safe->prev;
        }
    }
}

目前95/100