2023q1 Homework1 (lab0)

contributed by < charlie0822 >

開發環境

$ 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:         36 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) i7-3770 CPU @ 3.40GHz
    CPU family:          6
    Model:               58
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3900.0000
    CPU min MHz:         1600.0000
    BogoMIPS:            6784.20

開發過程

q_new

使用 malloc 配置新的記憶體配置失敗的話傳回 NULL ，成功的話利用 INIT_LIST_HEAD 初始化 head 並回傳 head。

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

新增 node 為 l->next，依序走訪每個節點並且將節點空間釋放，直到走回l。

void q_free(struct list_head *l)
{
    struct list_head *node = l->next;
    while (node != l) {
        element_t *tmp = list_entry(node, element_t, list);
        node = node->next;
        free(tmp->value);
        free(tmp);
    }
    free(l);
}  

q_insert_head

首先檢查 head 是否為 NULL，是的話回傳 false ，不是的話配置新的記憶體空間給 node ，如果配置失敗回傳NULL，使用 strdup 通過 malloc 分配記憶體並且將字串複製過去。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *node = malloc(sizeof(element_t));
    if (!node) {
        return false;
    }
    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }
    list_add(&node->list, head);
    return true;
}

q_insert_tail

邏輯跟 q_insert_head 一樣，最後用 list_add_tail 加入到list的尾端。

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

    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }
    list_add(&node->list, head);
    return true;
}

q_remove_head

首先先判斷 head 是否為 NULL 或是為 empty ，取得 head 之後第一個點的資訊後將 value 複製到 sp 上。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    element_t *node = list_entry(head->next, element_t, list);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
        list_del(&node->list);
    }

    return node;
}

q_remove_tail

邏輯跟 q_remove_head 一樣，不一樣是用 list_last_entry 取得最後一個節點的資訊。

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

q_delete_mid

拜訪 head 左右節點,如果節點是奇數的話，會同時到達中間節點，如果是偶數的話，刪除第 (總節點 / 2 + 1) 的節點。

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

q_delete_dup

目前想到使用龜兔賽跑演算法來實作，下圖是有重複數值的鏈結串列，當有重複數值時，就代表這個鏈結串列會有環的出現，可藉由演算法 ??? (需要詳述策略) 找出重複的數字。

最後沒有想到如何用龜兔賽跑演算法去實作，詢問同學實作邏輯，使用list_for_each_safe走訪當前節點並判斷是否重複，isNeedDel判斷當下節點是否需要刪除。

 bool q_delete_dup(struct list_head *head)
 {
     if (!head || list_empty(head)) {
         return false;
     }
 
     struct list_head *fast, *now = NULL;
     bool isNeedDel = false;
     list_for_each_safe (now, fast, head) {
         element_t *node = list_entry(now, element_t, list);
         element_t *dulNode = list_entry(fast, element_t, list);
         if (node->list.next != head &&
             strcmp(node->value, dulNode->value) == 0) {
             isNeedDel = true;
             list_del(fast);
             q_release_element(dulNode);
         } else if (isNeedDel) {
             list_del(now);
             q_release_element(node);
             isNeedDel = false;
         }
     }
     return true;
 }

使用 Graphviz 製圖！
注意 資訊科技詞彙翻譯。
:notes: jserv