2024q1 Homework1 (lab0)

contributed by < v0103 >

Reviewed by Vincent550102

Reviewd by vax-r

• 只完成部分 queue.c 之操作函式，而且也沒有進行任何改進
• github commit message 依舊過於簡短並且沒有完整表達 why v.s. how

1. q_sort、q_ascend、q_descend、q_merge 尚未實作
2. q_reverseK 可善用 list_cut_position、list_splice_init 等內建巨集，例如：

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    struct list_head *li, *safe, *tmp = head;
    LIST_HEAD(tmp_head);
    int i = 0;
    list_for_each_safe (li, safe, head) {
        if (++i == k) {
            list_cut_position(&tmp_head, tmp, li);
            q_reverse(&tmp_head);
            list_splice_init(&tmp_head, tmp);
            tmp = safe->prev;
            i = 0;
        }
    }
}

Reviewed by w96086123

1. q_insert_head 中有提出必須檢查的條件，這時的排版應該要以編號來表示而不是直接使用換行來表達，這樣會讓人不知道這裡是在表達什麼意思。
2. 不需要把程式碼完整呈現出來。

Reviewed by vestata

1. 若是在修改的地方附上 commit 連結可以加快查閱速度。
2. git commit message 不符合 如何寫好 Git Commit Message 中的規範。
3. 開發紀錄中應減少使用第一人稱「我」，以便更清晰地傳達資訊。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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):                  6
  On-line CPU(s) list:   0-5
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-9400F CPU @ 2.90GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  1
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5799.77

針對佇列操作的程式實作

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

q_new

這裡的 if 條件是為了確保前面的 malloc 函式能夠成功配置足夠大小的記憶體給 new 指標。若配置失敗， malloc 會返回 NULL ，因此在這種情況下，函式會直接回傳 NULL 。
初始化部分原本是以手動方式實作，後來發現在list.h中已經有適用的函式，因此決定直接使用該函式。這樣的做法有助於提高程式碼的重用性和可讀性，避免重複造輪子。

閱讀 Wikipedia: Reinventing the wheel，思考前後文是否合理。

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;
    INIT_LIST_HEAD(new);
    return new;
}

q_free

不知道就說不知道，不要說「不太知道」，工程人員說話要精準。

這題我也想使用 list.h 裡的函式或巨集，但是不太知道 怎麼使用，因此參考 alanjian85。
因此這裡使用 list.h 的巨集 list_for_each_entry_safe ，走訪整個佇列，用 safe 來指向 entry->next ，不使用 list_for_each_entry 是因為執行 q_release_element 會將entry刪掉以致於執行 entry->next 會出錯，整個佇列會遺失，至於 list_for_each_entry 的參數list則是要看 queue.h 裡的 element_t 結構的命名。另外如果佇列是 NULL，則會在一開始就結束該函式。

void q_free(struct list_head *head) {
    if(!head)
        return ;
    element_t *entry, *safe;
    list_for_each_entry_safe(entry, safe, head, list)
        q_release_element(entry);
    free(head);
}

1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 留意資訊科技詞彙翻譯及詞彙對照表
3. 改進你的漢語表達

q_insert_head

避免非必要的項目縮排 (即 * )，以清晰、明確，且流暢的漢語書寫。

這裡有個要檢查的點
輸入的 list 是否為 NULL
malloc new 有沒有成功
strdup 函式本身會呼叫 malloc 因此也需要檢查是否成功

都沒問題才能將該 new 插入到 list 裡。

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

    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }

    list_add(&new->list, head);
    return true;
}

q_insert_tail

和上述 q_insert_head 相似，僅需將 list_add 改成 list_add_tail 即可完成。

q_remove_head

作業說明有提到，remove 和 delete 的差別，remove 不會將節點抹除，因此這裡只有使用 list_del 來 unlink，沒有使用 free 來釋放該節點的記憶體。兩個要注意的點是

• 檢查鏈結串列是否為 empty
• 為了確保在 strncpy 後 sp 有 null character 。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *tmp = list_first_entry(head, element_t, list);
    list_del(head->next);
    if (sp) {
        strncpy(sp, tmp->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return tmp;
}

q_remove_tail

和上述 q_remove_head 相似，僅需將 list_first_entry 改成 list_last_entry 即可完成。

q_delete_mid

這裡我使用快慢指標，fast 每次走 2 步，slow 每次走 1 步，當 fast 走訪完整個 list，slow 則會在鏈結串列的中間。
我嘗試幾次後發現有兩個要注意的點

• fast 和 slow 一開始要從 head->next 出發才是正確的
• fast 指到 head 或 head->prev 都算是走訪完 list

找完中點後，由於 delete 是要將該節點記憶體釋放，所以除了用 list_del unlink 要再使用 q_release_element 釋放整個 element 的記憶體。

改進漢語表達。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *fast = head->next;
    struct list_head *slow = head->next;
    for (; fast != head && fast != head->prev;
         fast = fast->next->next, slow = slow->next) {
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

針對環狀雙向佇列，提出更快的方法。

TO DO : 針對環狀雙向佇列可以使用兩個指標，一個往next，一個往prev

q_delete_dup

這段程式碼的目標是移除重複項目。程式使用 list_for_each_entry_safe 來走訪整個 list ，並使用 strcmp 函數比較項目的值。如果發現重複的項目，它將刪除所有重複的項目，但保留最後一個。為了將最後一項也刪掉，我使用 dup_last 變數，來確保最後一個重複的項目會被刪除。

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool dup_last = false;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        if (&safe->list != head && !strcmp(entry->value, safe->value)) {
            list_del(&entry->list);
            q_release_element(entry);
            dup_last = true;
        } else if (dup_last) {  // del dup last one
            list_del(&entry->list);
            q_release_element(entry);
            dup_last = false;
        }
    return true;
}

q_swap

由於 swap 只需要改變每個 element 的鏈結串列，不需要值 不需要改變節點當中的數值，所以我這裡使用的是 list_for_each_safe，再使用 list_del 和 list_add 就可以將兩者 swap (下方解釋)，最後 safe = node->next 可以確保都是兩個為一組 swap。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        if (safe != head) {
            list_del(node);
            list_add(node, safe);
            safe = node->next;
        }
    return;

後來看到 list_move 這個函式，剛好就是 list_del 和 list_add 的組合，在 list.h 裡可以看到他的敘述是 Move a list node to the beginning of the list 不過將輸入更改後便可以達到我要的功能 將節點 node 移至節點 safe 後。

    list_for_each_safe (node, safe, head)
        if (safe != head) {
-            list_del(node);
-            list_add(node, safe);
+            list_move(node, safe);
            safe = node->next;
        }

q_reverse

reverse 跟 swap 一樣都只需要更改鏈結串列的指向，我一樣使用 list_for_each_safe 走訪每個節點，並將他們都Move a list node to the beginning of the list，這次是使用他真正的功能了，如此一來整個鏈結串列就被 reverse 了。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
}

q_reverseK

我這裡使用最土炮的方法，在 q_reverse 的基礎上加上兩個計數器，count_turn 用來確認後面是否還有完整的 k 組 element，count_k 則是用來數已被 reverse 的節點數，若達到 k 個則將重新計數，並改變後面節點要插入的位置。

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node, *safe, *start = head;
    int count_k = 0, count_turn = 0;
    int turn = q_size(head) / k;

    list_for_each_safe (node, safe, head) {
        list_move(node, start);
        if (count_turn == turn)   /*no complete k-group*/
            return;
        if (++count_k == k) {     /*change start per kth node*/
            start = safe->prev;
            count_turn++;
            count_k = 0;
        }
    }
}

I-HSIN Cheng
這裡是開發筆記不是教學頁面，不需要闡述每個函式的邏輯與做法，程式碼本身應該清楚到不需文字解釋即可理解，除非有任何特別之處，應該寫出可改進之處，另外說明文字的贅字太多且解說不清晰。