2025q1 Homework1 (lab0)

contributed by < EJ7289 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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):                   4
On-line CPU(s) list:      0-3
Thread(s) per core:       2
Core(s) per socket:       2
Socket(s):                1
NUMA node(s):             1
Vendor ID:                GenuineIntel
CPU family:               6
Model:                    142
Model name:               Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping:                 9
CPU(s) scaling MHz:       14%
CPU max MHz:              3500.0000
CPU min MHz:              400.0000
BogoMIPS:                 5799.77
Virtualization:           VT-x
L1d cache:                64 KiB (2 instances)
L1i cache:                64 KiB (2 instances)
L2 cache:                 512 KiB (2 instances)
L3 cache:                 4 MiB (1 instance)
NUMA node0 CPU(s):        0-3

針對佇列操作的程式碼實作

q_new

在 C 語言中， malloc 用來分配指定大小的記憶體空間，並且回傳指標，配置的空間尚未初始化。

C99 [7.20.3.3] The malloc function
#include <stdlib.h>
void * malloc(size_t size);
Description
The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.
Return
The malloc function returns either a null pointer or a pointer to the allocated space.

若記憶體配置失敗，須回傳空指標，但是 C 語言中的空指標用 NULL 表示。
補充：C++11 中的空指標用 nullptr 表示。

struct list_head *q_new(){
    struct list_head *h = (struct list_head *)malloc(sizeof(struct list_head));
    if (!h) {
        return NULL;
    }
    h->next = h;
    h->prev = h;
    return h;
}

q_free

注意事項：

list_head 為雙向循環鏈結串列， head 一直指向 next 也不會是 NULL
釋放記憶體，須將 elem 以及 elem->value 的記憶體都釋放
- 為什麼不能不能只釋放 elem 就好？
- 為什麼另外釋放 elem->value 不釋放 elem->list ？
最後也需要將 head 釋放

以下程式會陷入無窮迴圈：

void q_free(struct list_head *head)
{
    while(head) {
        struct list_head *next = head->next;
        free(head);
        head = next;
    }
}

放 github 的程式

free 函數的引數為指標。

C99 [7.20.3.2] The free function
#include <stdlib.h>
void free(void *ptr);

q_insert_head/q_insert_tail

原本的程式1：

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *newq = malloc(sizeof(element_t));
    if (!newq) { return false; }
    
    newq->value = s;
    newq->list.next = head;
    newq->list.prev = head->prev;
    return true;
}

以上程式的問題有：

若 s 是區域變數，會在離開函數時被釋放，導致外界無法取得。
該佇列為雙向循環鏈結串列，因此需要原本的鏈結串列指向新建的。

修改方法：

為了讓外界能讀取 s 的值，使用 strdup() 複製字串。 strdup() 會用 malloc 獲得新的字串，並且可用 free 釋放字串。
雙向循環的鏈結串列在新增節點時，需要打斷2條鏈和新增4條鏈。被打斷的鏈會使用到，因此需要注意新增4條鏈的順序。

改寫為程式2：

bool q_insert_tail(struct list_head *head, char *s)
{
    // Create a new queue 
    element_t *newq = malloc(sizeof(element_t));
    if (!newq) {
        return false;
    }

    // Duplicate s in global memory and storage in new queue
    newq->value = strdup(s);
    if (!newq->value) {
        free(newq);
        return false;
    }

    // Insert s at the tail of queue
    newq->list.next = head;
    newq->list.prev = head->prev;
    head->prev->next = &newq->list;
    head->prev = &newq->list;
    return true;
}

程式3：使用 API 簡化程式

放 github 的程式

q_remove_head/q_remove_tail

在 queue.h 說明：

q_remove_head(struct list_head *head, char *sp, size_t bufsize)
- head: header of queue
- sp: 插入要移除的字串
- bufsize: 字串 *sp 可以容納的做大空間

原本程式碼：

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

    // find the element of node
    element_t *h = list_entry(head, element_t, list);
    sp = h->value;
    list_del_init(head);
    return h;
}

以上程式的問題有：

head 為 dummy 而不是起始 node，真正的起始 node 為 head->next
- 改為 list_entry(head->next, element_t, list)
- 改為 list_del_init(head->next)
sp = h->value 無法回傳字串 - h 為區域變數
- 若用 *sp = *h->value 只能回傳一個字元，無法回傳字串
- 使用 strncpy 複製 sp 如果不複製為怎樣？

char 的使用

char 只能作為字元，例如 char a = 'a' char的字元宣告必須用單引號
char 不能作為字串的宣告，例如 ~~char a = "good"~~
char * 則作為字串的指標宣告
- char *a = "a" char的指標宣告必須用雙引號
- char *b = "good"

char *a = "a";
char *b = "banana";

printf("%c\n", a); // error
printf("%c\n", *a); // correct, a

printf("%c\n", b); // error
printf("%c\n", *b); // correct, b

printf("%s\n", b); // correct, banana
printf("%s\n", *b); // error

程式2:

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

    // find the element of node
    element_t *h = list_entry(head, element_t, list);
    if (sp) {
        sp = strncpy()
    }
    sp = h->value;
    list_del_init(head);
    return h;
}

q_size

解題思維：

利用 count 在迴圈內計算
head 為 dummy 並非直接指向第一個節點

insert github's commit

q_delete_mid

解題思維：

排除 head 為 NULL 或 empty 的情況
用快慢指標找到鏈結串列的中間點
移除鏈結串列的中間點 (利用 list_del())
釋放中間點 (須同時釋放 elem 和 elem->value)

insert github's commit

q_delete_dup

目的：將相鄰且相同的數值刪除

解法：

比較 curr 與 next 是否相同
若相同，將布林變數改成 true ；若不相同，將布林變數改成 false
布林變數為 false （不動作）；布林變數為 true 和布林變數為 true 變成 false （刪除前一個數值 prev ）

原本程式 1

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 *curr = head->next;
    struct list_head *next = curr->next;
    bool del = false;
    while(curr!=head) {
        element_t *elem = list_entry(curr, element_t, list);
        element_t *safe = list_entry(next, element_t, list);
        if (elem->value == safe->value) {
            del = true;
            list_for_each_entry_safe(elem, safe, head, list);
            free(elem->value);
            free(elem);
        } else if ((elem->value != safe->value) && (del == true)) {
            del = false;
            list_for_each_entry_safe(elem, safe, head, list);
            free(elem->value);
            free(elem);
        }
        curr = next;
        next = next->next;
    }

    return true;
}

程式 1 存在的問題：

elem->value 指向的是 value 的地址，因此要用 strcmp()

list_for_each_entry_safe() 的使用方式不正確
在 list.h 中說明list_for_each_entry_safe() 可用來代替一個 for 迴圈。

#define list_for_each_entry_safe(entry, safe, head, member)            \
for (entry = list_entry((head)->next, typeof(*entry), member),     \
    safe = list_entry(entry->member.next, typeof(*entry), member); \
     &entry->member != (head); entry = safe,                       \
    safe = list_entry(safe->member.next, typeof(*entry), member))

最基本的定義方式#define MACRO value => #define MAX 1000

須使用 list_del() 將指定數值從鏈結串列中移除
需要初始化 entry=NULL 和 safe=NULL

程式 2

github code

q_swap

利用 XOR 操作 swap 的行為，不適用在 struct 和 char* ，因此該題不適用。

XORswap(int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

因此，需要另外存取的空間 tmp 。
解題方法：不改 node ，指改變 *value 。（如下方程式所示）

for (; curr != head && curr->next != head;
     curr = curr->next->next, next = curr->next) {
    char *tmp = list_entry(curr, element_t, list)->value;
    list_entry(curr, element_t, list)->value = list_entry(next, element_t, list)->value;
    list_entry(next, element_t, list)->value = tmp;
}

github code

q_reverse

解題方法：

curr->next = prev 的概念
但該題目是雙向循環鏈結串列，用該方法修改連接的串列會更複雜一些。
=> 方法修改為頭尾互換（如圖所示）
=> 不改變 node 指改變 *value

q_reverseK

解題方法：

判斷是否能切成 K
K 個切成一個小 queue

github code

在 C99 [6.8.5.3] 中，解釋到 for 迴圈的使用如下，
for ( init-clause ; condition ; iteration-expression ) statement
其中：

init-clause：變數初始化（可為變數宣告或運算式）
condition：循環條件（當條件為 false（0）時停止迴圈）
iteration-expression：每次迴圈執行完後的運算式
statement：迴圈主體

範例：

for (int a=0, b=0; a<3, b<3; a++, b++, printf("a = %d\n", a)) {
    printf("b = %d\n\n", b);
}

輸出：

b = 0
    
a = 1
b = 1
    
a = 2
b = 2
    
a = 3

q_sort

原程式

struct list_head *qsort_split(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    struct list_head *base = head->next;
    struct list_head *curr = head->next->next;

    struct list_head *left; 
    struct list_head *right;
    INIT_LIST_HEAD(left);
    INIT_LIST_HEAD(right);

    for (; curr != head; curr = curr->next) {
        if (strcmp(list_entry(base, element_t, list)->value,
             list_entry(curr, element_t, list)->value) >= 0) {
            list_add_tail(curr, left);
        } else {
            list_add_tail(curr, right);
        }
    }
    if (descend == true) {
        struct list_head *tmp = left;
        left = right;
        right = tmp;
    }
    list_add_tail(base, left);

    list_splice(qsort_split(left, descend), qsort_split(right, descend));
    return left;
}

想建立一個新的 dummy 為什麼不能這樣寫？

struct list_head *dummy;
INIT_LIST_HEAD(dummy);

struct list_head *dummy = NULL;
INIT_LIST_HEAD(dummy);

為什麼必須這樣寫？

struct list_head dummy;
INIT_LIST_HEAD(&dummy);

q_ascend / q_descend

github code

q_merge

使用 queue_context_t 取出各個 queue
輸出 merge queue 時，需要以 head 作為 head ？

參考資料

C 語言動態記憶體的配置：https://blog.gtwang.org/programming/c-memory-functions-malloc-free/#google_vignette

2025q1 Homework1 (lab0)

開發環境

針對佇列操作的程式碼實作

q_new

q_free

q_insert_head/q_insert_tail

q_remove_head/q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend / q_descend

q_merge

參考資料

Read more

2025q1 Homework1 (ideas)