2024q1 Homework1 (lab0)

contributed by < kuku000 >

開發環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
    CPU family:          6
    Model:               94
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4000.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6799.81
   arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    8 MiB (1 instance)

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

`q_new`

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

q_free

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

q_insert_head/tail

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *insert = malloc(sizeof(element_t));
    if (!insert) {
        free(insert);
        return false;
    }

    insert->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
    if (!insert->value) {
        free(insert->value);
        free(insert);
        return false;
    }
    strncpy(insert->value, s, strlen(s));
    *(insert->value + strlen(s)) = '\0';
    list_add(&insert->list, head);

    return true;
}

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

`q_delete_mid`

traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)

to pass or move over, along, or through.
to go to and fro over or along.

其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。

當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。

還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。

在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。

遍歷 (Ergodic) 源於以下二個希臘詞：

ergon (對應英語的 work)
odos (對應英語的 path 或 way)

最初這是由奧地利物理學家波茲曼 (Ludwig Boltzmann) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。

\to

資訊科技詞彙翻譯

TODO: 提供數學推導。

見分析「快慢指標」，該文特意忽略一些細節，給學員練習。

假設有一個有 9 個節點的鏈結串列,如果使用單向快慢指標快指標會奏訪完整的九個節點而慢指標只走訪五個節點一共走訪：9+5＝14個節點。

O (n) + O (\frac{n}{2}) = O (\frac{3}{2} n) .

使用雙向走訪的話，~~左指標~~ ? 以及~~右指標~~ ?? 皆走訪五個節點，一共走訪：5+5＝10個節點。

O (\frac{n}{2}) + O (\frac{n}{2}) = O (\frac{2}{2} n) = O (n) .

在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
改進你的漢語表達，使用清晰明確且精準的詞彙

{
    if (!head || list_empty(head))
        return false;
    struct list_head *left = head->prev;
    struct list_head *right = head->next;
    while (true) {
        if (left == right) {
            list_del(right);
            q_release_element(list_entry(right, element_t, list));
            break;
        } else if (right->prev == left) {
            list_del(left);
            q_release_element(list_entry(left, element_t, list));
            break;
        }
        right = right->next;
        left = left->prev;
    }
    return true;
}

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *cur = head->next;
    struct list_head *pre_cur;
    for (; cur != head->prev; cur = cur->next) {
        int count = 0;
        for (pre_cur = cur->next; pre_cur != head->prev;
             pre_cur = pre_cur->next) {
            if (list_entry(cur, element_t, list)->value ==
                list_entry(pre_cur, element_t, list)->value) {
                list_del(pre_cur);
                q_release_element(list_entry(pre_cur, element_t, list));
                count++;
            }
            if (count > 0) {
                list_del(cur);
                q_release_element(list_entry(cur, element_t, list));
            }
        }
    }
    return true;
}

發現測試時會發生以下問題：

l = [1 2 2]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [1 ... ]
ERROR:  Queue has more than 1 elements
cmd> size
ERROR: Computed queue size as 3, but correct value is 1
l = [1 ... ]
ERROR:  Queue has more than 1 elements

q_reverse

利用雙向迴圈鏈結串列特性由 head 為中心左右互換。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *left = head->prev;
    struct list_head *right = head->next;
    int size = q_size(head);
    for(int i = 0; i < size/2; i++)
    {   
        struct list_head *temp_l = left->prev;
        struct list_head *temp_r = right->next;
        list_move(left, right);
        list_move(right, temp_l);
        right = temp_r;
        left = temp_l;
    }
    return;
}

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

起初使用 for 迴圈並以 size/2 作為為圈結束的條件，但是會發現當鏈結串列節點數為偶數時會無法運作，因此我將程式改為：

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *left = head->prev;
    struct list_head *right = head->next;
    while (left != right && right->next != left)
    {   
        struct list_head *temp_l = left->prev;
        struct list_head *temp_r = right->next;
        list_move(left, right);
        list_move(right, temp_l);
        right = temp_r;
        left = temp_l;
    }
    return;
}

q_sort

為了方便理解，我先將鏈結串列中所有節點切斷存入陣列中，並參考你所不知道的 C 語言: linked list 和非連續記憶體中 merageKList 的方法來合併並且排序。

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