Try   HackMD

2020q3 Homework1 (lab0)

contributed by <Sisker1111>

tags: 進階電腦系統理論與實作

簡介

養成良好coding習慣

lab 中使用許多工具協助養成良好的寫程式習慣，包含：

等…

詳細的環境設定以及lab的相關說明請參閱 I01: lab0、C Programming Lab: Assessing Your C Programming Skills

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
改寫自 CMU 計算機概論的作業

CMU (位於美國賓州匹茲堡的卡內基美隆大學) 電腦科學系的 Introduction to Computer Systems (ICS) 課程準備了 C Programming Lab 作為檢閱學生 C 語言程式設計的認知:

  • 記憶體管理;
  • 建立並管理需要透過指標操作的資料結構;
  • 字串操作;
  • 改善特定關鍵操作的效能;
  • 提高程式碼的穩固程度，例如能夠處理無效的參數，包含 NULL 指標;

在給定的程式碼中，queue.h 包含以下鏈結串列 (linked list) 結構定義:

/* Linked list element */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

接著用鏈結串列來實作佇列 (queue)

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    /* 其他自行定義的結構成員 */
} queue_t;

這過程可用下圖來表示：佇列的上層建構於 queue_t 類型的物件。一開始，此資料結構僅包含單一成員 head，之後陸續以鏈結串列增添給定的字串，如 "cab", "bead", "cab" 等等。佇列內的每個元素由單向的鏈結串列構成，每個元素由 list_ele_t 類型的物件來表示，後者包含真正保存字串的 value 和指向下個鏈結串列元素開頭地址的 next。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

圖 1: 透過鏈結串列實作的佇列。每個鏈結串列元素都有個 value 指標，指向一段連續的記憶體 (即 C-style string，以 NULL 字元結尾的字串)，字元依據 ASCII 編碼 (以十六進位顯示)。

C 語言中，字串以連續的char 型態物件的排列來表示，對多數的硬體來說，char 型態表示為 1 個 byte。，而為了儲存長度 l 的字串，需要至少 l + 1 個 char 元素，並在最後設定為 \0 字元。上圖的 [cab, bead, cab]，其中字元 a 和 e 以十六進位表示為 ASCII 編碼的 61 和 65。觀察上圖，字串 "cab" 和 "bead" 在執行時期可能對應到兩段不相鄰的記憶體。

在給定的 C Programming Lab 程式碼中，佇列透過 queue_t * 指標型態來操作，程式碼需要考慮以下二種特別狀況，作出對應的處置:

  1. NULL 佇列：是指標值為 NULL;
  2. 「空」(empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;

另一種解讀方式:
若你有空的紅包袋，裡面的東西是 empty;
若你連紅包袋都沒有，就可以說 NULL;

queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

  • q_new: 建立新的「空」佇列;
  • q_free: 釋放佇列所佔用的記憶體;
  • q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
  • q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
  • q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
  • q_size: 計算佇列中的元素數量。
  • q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
  • q_sort: 以遞增順序來排序鏈結串列的元素。

如何測試

測試所有的測資:

make test

基本實作

Queue structure






typedef struct {
​   list_ele_t *head; 
​   list_ele_t *tail;
​   int size;
} queue_t;

除了原始的head之外，加入了

  • tail: 指向 queue 的尾端，目的是為了
    O(1)     的 insert tail
  • size: 計算 queue 的大小，目的是為了
    O(1)     得到 queue size

q_new











queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->tail = NULL;
    q->head = NULL;
    q->size = 0;
    return q;
}

建立一個新的 queue，如果 malloc 失敗，則returnNULL，成功則 return 一個空的 queue.

q_free

















void q_free(queue_t *q)
{
    if (!q)
        return;
    if (q->head) {
        list_ele_t *tmp = q->head;
        while (q->head) {  // free all element in link-list
            q->head = q->head->next;
            free(tmp->value);
            free(tmp);
            tmp = q->head;
        }
    }

    free(q);
}

必須先檢查 queue 是否為NULL，將現有的 queue 整個釋放掉，注意要先將 queue 上的每個 element 都釋放掉，最後才釋放 queue 本身.

q_insert_head


























bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    /* TODO: What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)  // queue q is not exist || malloc return NULL
        return false;

    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);

    if (!q->head) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

Code Description

  1. 開頭一樣先判斷 queue 是否 為 NULL.
  2. 7~9行 malloc 一個新點newh並檢查是否有 malloc 成功.
  3. 11~15行 malloc 一個空間用來存放字串，同樣需檢查 malloc 是否成功，失敗需要將newh釋放.
  4. 16行 將 input 字串指派給newh->value
  5. 18~24行 將q->head指到newh，也將q->tail指到 queue 的最後一個 element .

q_insert_tail






























bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)  // queue q is not exist || malloc return NULL
        return false;

    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    if (!q->head) {
        newh->next = q->head;
        q->head = newh;
        q->tail = newh;
        q->size++;
        return true;
    }
    newh->next = NULL;
    q->tail->next = newh;
    q->tail = q->tail->next;
    q->size++;
    return true;
}

Code Description

  1. 開頭先判斷 queue 是否 為 NULL.
  2. 16~22行 用q->head是否為NULL來判斷要字串s是否為 queue 的第一個字串.
  3. 23~27行 把q->tail->next指到新點newh，並把q->tail指到newh.

q_remove_head
























bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* TODO: You need to fix up this code. */
    /* TODO: Remove the above comment when you are about to implement. */
    if (!q || !q->head)  // queue q is not exist
        return false;
    if (sp) {
        if (bufsize > strlen(q->head->value)) {
            strncpy(sp, q->head->value, strlen(q->head->value));
            sp[strlen(q->head->value)] = '\0';
        } else {
            strncpy(sp, q->head->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

Code Description

remove 一個 queue 中存在head的字串，並把此字串存入sp

  1. 7~15行 用來限制可以存入sp的最大字串長度.
  2. 17~22行 把q->head找到q->head->next並釋放原本head的記憶體.

q_size





int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

回傳 queue 的 size.

q_reverse
















void q_reverse(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *cursor = NULL;
    list_ele_t **indirect = &q->head;
    q->tail = q->head;
    while (*indirect) {
        list_ele_t *next = (*indirect)->next;
        (*indirect)->next = cursor;
        cursor = *indirect;
        *indirect = next;
    }
    *indirect = cursor;
}

將 queue 中的 element 反向串接，記得要把q->head & q->tail指到新的位置，方法類似於
quiz1 的 reverse .

q_sort

這題要自己從頭想真的有點難，最後還是參考網路上其他人的作法，參考網址如下:
https://www.techiedelight.com/merge-sort-singly-linked-list/






























































list_ele_t *merge(list_ele_t *left_list, list_ele_t *right_list)
{
    list_ele_t *tmp = NULL;
    if (strcmp(left_list->value, right_list->value) <= 0) {
        tmp = left_list;
        left_list = left_list->next;
    } else {
        tmp = right_list;
        right_list = right_list->next;
    }

    list_ele_t *head = tmp;
    while (left_list && right_list) {
        if (strcmp(left_list->value, right_list->value) <= 0) {
            tmp->next = left_list;
            tmp = tmp->next;
            left_list = left_list->next;
        } else {
            tmp->next = right_list;
            tmp = tmp->next;
            right_list = right_list->next;
        }
    }

    if (left_list) tmp->next = left_list;
    if (right_list) tmp->next = right_list;

    return head;
}

void merge_sort(list_ele_t **head)
{
    if (!(*head) || !(*head)->next)
        return;
    list_ele_t *fast = (*head)->next;
    list_ele_t *slow = *head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    merge_sort(head);
    merge_sort(&fast);

   *head = merge(*head, fast);
}


void q_sort(queue_t *q)
{
    if (!q)
        return;
    merge_sort(&q->head);
    if(!q->tail)
        return;
    while(q->tail->next)
        q->tail = q->tail->next;
}

Code Description

  1. 使用stcmp來做字串的比大小
  2. 排序時也會順便將q->head指到正確的位置，排序後記得也要把q->tail指到正確的地方

測試與分析

使用自動評分系統評分

  • trace-15-perf 我原本照著網址的做法直接做會跑不過，推測是因為memory過多或者遞迴太多次導致，後來簡化了一些寫法，以及把function合併後就對了.
  • trace-17-complexity 這個trace有時候會突然跑不過，目前還不確定是什麼原因.

Valgrind

可使用指令:

$ valgrind --tool=massif ./qtest -f ./traces/trace-02-ops.cmd
$ ms_print  massif.out.PID
$ massif-visualizer massif.out.PID

分析trace-02-ops.cmd

執行結果:

cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
q = [bear gerbil meerkat bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil meerkat bear gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = [meerkat bear gerbil]
cmd> rh meerkat
Removed meerkat from queue
q = [bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
Freeing queue

分析trace-09-robust.cmd

執行結果:

cmd> option fail 10
cmd> option malloc 0
cmd> new
q = []
cmd> ih bear
q = [bear]
cmd> rhq
Removed element from queue
q = []
cmd>
Freeing queue

分析trace-17-complexoty.cmd

執行結果:

cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue

Last changed by 
 
Fan Harry
有時會參考各位大大HackMD是如何作圖的，如有編輯到代表我再參考時不小心改到東西，都會馬上復原，請大大見諒QQ
0
327
Published on HackMD