Try   HackMD

2025q1 Homework1 (lab0)

contributed by < Cactex >

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [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 字元

開發環境

​$ hostnamectl
Operating System: Ubuntu 24.04.1 LTS              
Kernel: Linux 6.11.0-19-generic
​             
​$ 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
Address sizes:            39 bits physical, 48 bits virtual
Byte Order:               Little Endian
CPU(s):                   8
On-line CPU(s) list:      0-7
Vendor ID:                GenuineIntel
Model name:               Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
CPU family:               6
Model:                    165
Thread(s) per core:       2
Core(s) per socket:       4
Socket(s):                1
Stepping:                 2
CPU(s) scaling MHz:       93%
CPU max MHz:              4100.0000
CPU min MHz:              800.0000
BogoMIPS:                 4800.00   
L1d:                      128 KiB (4 instances)
L1i:                      128 KiB (4 instances)
L2:                       1 MiB (4 instances)
L3:                       8 MiB (1 instance)             
NUMA node(s):             1
NUMA node0 CPU(s):        0-7

實作指定的佇列操作

在實作 queue.c 的函式之前，應閱讀 queue.h中對應之函式說明。

並且在執行 git commit 前，使用 clang-format 工具

​$ clang-format -i *.[ch]

來調整程式碼以符合作業要求的風格

q_new

commit 0e4d305

建立空佇列並且將 next 和 prev 都指向自己

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

q_free

commit e37136f

釋放佇列element_t 使用的所有記憶體空間，若傳入值 head 是 NULL則不需要做任何操作

void q_free(struct list_head *head)
{
    if (!head)
        return;
    if (list_empty(head)) {
        free(head);
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        element_t *target_ele = list_entry(node, element_t, list);
        q_release_element(target_ele);
    }
    free(head);
}

q_insert_head

commit 0e4d305

建立新的佇列元素並且將其插入到 head 和 head->next 中間
需要注意的是如果 head 為 NULL 或呼叫 malloc() 分配記憶體失敗則須回傳 false

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    new_element->value = malloc(strlen(s) + 1);
    if (!new_element->value) {
        q_release_element(new_element);
        return false;
    }
    strlcpy(new_element->value, s, strlen(s) + 1);
    list_add(&new_element->list, head);
    return true;
}

q_insert_tail

commit 0e4d305

基本上和 q_insert_head 一樣，只是將元素加到佇列尾端

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    new_element->value = malloc(strlen(s) + 1);
    if (!new_element->value) {
        q_release_element(new_element);
        return false;
    }
    strlcpy(new_element->value, s, strlen(s) + 1);
    list_add_tail(&new_element->list, head);
    return true;
}

q_remove_head

commit 0e4d305

"移出"佇列中第一個元素，並且回傳該地址
並將元素的值複製到 sp ，大小由 bufsize 決定，須注意 bufsize 中包含 \0

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *target_node = head->next;
    element_t *target_ele = list_entry(target_node, element_t, list);
    strlcpy(sp, target_ele->value, bufsize);
    list_del(target_node);
    return target_ele;
}

q_remove_tail

commit 0e4d305

"移出"佇列中最後一個元素，並且回傳該地址
並將元素的值複製到 sp ，大小由 bufsize 決定，須注意 bufsize 中包含 \0

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *target_node = head->prev;
    element_t *target_ele = list_entry(target_node, element_t, list);
    strlcpy(sp, target_ele->value, bufsize);
    list_del(target_node);
    return target_ele;
}

q_delete_mid

commit 1691d92

若 head 為 NULL 或 佇列為空則回傳 false
實做方法為兩個節點，一個向前 traverse，另外一個向後，直到兩個節點相遇

討論
另一種作法為兩節點同方向 traverse ，其中一個節點速度為另一個兩倍，直到節點相遇

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *nprev = head->prev;
    struct list_head *nnext = head->next;
    while ((nprev != nnext) && (nnext->next != nprev)) {
        nprev = nprev->prev;
        nnext = nnext->next;
    }
    list_del(nprev);
    q_release_element(list_entry(nprev, element_t, list));
    return true;
}

q_delete_dup

commit 9ae6e83

前提預設為 sorted list

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 *node, *safe;
    bool isdup = 0;
    list_for_each_safe (node, safe, head) {
        element_t *curr = list_entry(node, element_t, list);
        element_t *next = list_entry(safe, element_t, list);
        if(strcmp(curr->value, next->value) == 0){
            list_del(&curr->list);
            q_release_element(curr);
            isdup = true;
            continue;
        }
        if(isdup){
            list_del(&tmp->list);
            q_release_element(curr);
            isdup = false;
        }
    }
    return true;
}

實做以上程式碼遇到 0xdeadbeef
使用Valgrind工具發現問題在 strcmp ，以上程式碼會比較現在節點和下個節點的value，導致訪問到 head 節點的 value

 $ valgrind -q --leak-check=full ./qtest
...
cmd> ih 4
l = [4 3 2 2]
cmd> dedup
==104311== Invalid read of size 1
==104311==    at 0x4850367: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104311==    by 0x110141: q_delete_dup (queue.c:142)
==104311==    by 0x10C3B6: do_dedup (qtest.c:467)
==104311==    by 0x10E76D: interpret_cmda (console.c:181)
==104311==    by 0x10ED32: interpret_cmd (console.c:201)
==104311==    by 0x10F81C: run_console (console.c:659)
==104311==    by 0x10DB5C: main (qtest.c:1444)
==104311==  Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==104311== 
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer==104311== 2 bytes in 1 blocks are still reachable in loss record 1 of 52

補上就沒問題了

+if(safe != head){
​           element_t *next = list_entry(safe, element_t, list);
​           if(strcmp(curr->value, next->value) == 0){
​               list_del(&curr->list);
​               q_release_element(curr);
​               isdup = true;
​               continue;
​           }
+        }
​}

q_swap

commit b29d3c2

目標是將佇列中每對相鄰的節點交換，可以想像成把第一個節點放到第二個節點後面

討論
另一種作法為兩節點同方向 traverse ，其中一個節點速度為另一個兩倍，直到節點相遇

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *nprev = head->prev;
    struct list_head *nnext = head->next;
    while ((nprev != nnext) && (nnext->next != nprev)) {
        nprev = nprev->prev;
        nnext = nnext->next;
    }
    list_del(nprev);
    q_release_element(list_entry(nprev, element_t, list));
    return true;
}

q_reverse

commit 1683868

目標是將佇列每個元素的順序翻轉，如果佇列為空或 NULL 不需要調整。
並且不能 allocate 或 free 任何佇列元素，僅調整原有元素之順序。

想法為將最後面的元素一直向前放

void q_reverse(struct list_head *head)
{
    for (struct list_head *last = head->prev, *front = head->next,
                          *current = head;
         last != front; last = head->prev, current = current->next) {
        head->prev = last->prev;
        last->prev->next = head;

        current->next->prev = last;
        last->next = current->next;
        last->prev = current;
        current->next = last;
    }
}

q_reverseK

commit 1683868

和q_reverse接近，但翻轉的大小為 k ，若佇列大小不足 k 則不須翻轉。
佇列為空或長度為1或 k 的大小為則不需要作任何動作。

若佇列長度和 k 大小一致，則和 q_reverse 相同。
一般 case 的實做則可以透過 list_cut_position 去切分佇列，將其翻轉後再接回原本佇列。

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 || list_is_singular(head))
        return;
    int length = q_size(head);
    if (length == k)
        q_reverse(head);
    int counter = 0;
    LIST_HEAD(tmp);
    LIST_HEAD(reverse);
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        if (++counter == k) {
            list_cut_position(&tmp, head, node);
            q_reverse(&tmp);
            list_splice_tail_init(&tmp, &reverse);
            counter = 0;
        }
    }
    list_splice_init(&reverse, head);
}

q_sort

commit 

void q_sort(struct list_head *head, bool descend) {}

q_ascend

commit 1f5fb10

透過移除佇列元素讓佇列達到升冪排列(可以有相同值)，空佇列和佇列長度為1不需要更改

將 list.h 中的 list_for_each_entry_safe 改寫，以達到逆向走訪的效果。

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    element_t *safe, *node;
    char const *tmpch = (list_entry(head->prev, element_t, list))->value;
    for (node = list_entry((head)->prev, typeof(*node), list),
        safe = list_entry(node->list.prev, typeof(*node), list);
         &node->list != (head);
         node = safe, safe = list_entry(safe->list.prev, typeof(*node), list)) {
        if (strcmp(node->value, tmpch) > 0) {
            list_del(&node->list);
            continue;
        }
        tmpch = node->value;
    }
    return q_size(head);
}

q_descend

commit 1f5fb10

透過移除佇列元素讓佇列達到降冪排列(可以有相同值)，空佇列和佇列長度為1不需要更改

內容和q_ascend差不多，只是變成降冪排列

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    element_t *safe, *node;
    char const *tmpch = (list_entry(head->prev, element_t, list))->value;
    for (node = list_entry((head)->prev, typeof(*node), list),
        safe = list_entry(node->list.prev, typeof(*node), list);
         &node->list != (head);
         node = safe, safe = list_entry(safe->list.prev, typeof(*node), list)) {
        if (strcmp(node->value, tmpch) < 0) {
            list_del(&node->list);
            continue;
        }
        tmpch = node->value;
    }
    return q_size(head);
}

q_merge

commit 

int q_merge(struct list_head *head, bool descend)
{
}
Last changed by 
 
Cactex
0
32
Published on HackMD