Try   HackMD

2020q1 Homework1 (lab0)

contributed by < Hsuhaoxiang >

實驗環境

$ uname -a
Linux haoxiang-System-Product-Name 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.

開發過程

q_size

  • 為了在
    O(1)
    完成這項操作所以在 queue_t 增加 size
  • 如果 q 為 NULL 必須回傳 0
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

q_new

  • 建立新的「空」佇列
  • 要注意的是 malloc 使否成功分配記憶體位置
  • 初始化 queue_t 中的變數 tail , head , size
queue_t *q_new()
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_insert_head

  • 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)
  • 首先若 q 為NULL則直接 retrun false ,每次 malloc 也需要確認記憶體
    是否分配成功,而在分配 value 的記憶體位置時,如果失敗要先回收
    newh 的記憶體,否會造成沒有指標指向該記憶體。
  • 使用 strcpy 會跳出 Dangerous function detected 警告無法 commit
    所以改用 strncpy
  • 當 queue 為空時應該要將 q->tail 指向新增的 newh
bool q_insert_head(queue_t *q, char *s)
{
    int Strlen = strlen(s);
    if (!q)
        return false;
    list_ele_t *newh;
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc((Strlen + 1) * sizeof(char));
    if (!(newh->value)) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, Strlen + 1);
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    if (q->size == 1)
        q->tail = newh;
    return true;
}

q_insert_tail

  • 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)
  • 此段程式碼與 q_insert_head 非常相似,不同的地方在於要將插入前的 tailnext 指向正要插入的這個元素
bool q_insert_tail(queue_t *q, char *s)
{
    int Strlen = strlen(s);
    if (!q)
        return false;
    list_ele_t *newh;
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc((Strlen + 1) * sizeof(char));
    if (!(newh->value)) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, Strlen + 1);
    newh->next = NULL;
    q->size += 1;
    if (q->size == 1)
        q->head = newh;
    else
        q->tail->next = newh;
    q->tail = newh;
    return true;
}

q_remove_head

  • 在佇列開頭 (head) 移除 (remove) 給定的元素。
  • 將 node 中的值複製到 sp 中
  • head 指向新的頭也就是 head->next
  • size 減一,並將此元素所用到的記憶體空間釋放
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || q->size == 0)
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    if (q->size == 1) {
        free(q->head->value);
        free(q->head);
        q->head = NULL;
        q->size -= 1;
        return true;
    }
    list_ele_t *tmp;
    tmp = q->head;

    q->head = q->head->next;
    q->size -= 1;
    free(tmp->value);
    free(tmp);
    if (q->size == 0)
        q->tail = NULL;
    return true;
}

q_reverse

  • 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列元素,換言之,它只能重排已經存在的元素
  • 如果 queue 的 size 為 0 或 1 直接結束
  • 否則一一將元素的連結反轉
void q_reverse(queue_t *q)
{
    if (!q || q->size == 0) {
        return;
    }
    if (q->size == 1) {
        return;
    }
    list_ele_t *pre, *cur, *pos;
    pre = pos = NULL;
    cur = q->head;
    while (cur) {
        pos = cur->next;
        cur->next = pre;
        pre = cur;
        cur = pos;
    }
    cur = q->head;
    q->head = q->tail;
    q->tail = cur;
}

q_free

  • 釋放佇列所佔用的記憶體
  • 使用 while 走訪所有元素並且釋放記憶體
void q_free(queue_t *q)
{
    if (!q) {
        return;
    }
    if (q->head) {
        list_ele_t *tmp;
        while (q->head) {
            tmp = q->head;
            q->head = tmp->next;
            free(tmp->value);
            free(tmp);
        }
    }
    free(q);
}

q_sort

  • 以遞增順序來排序鏈結串列的元素
  • 使用 merge sort 才能在時間內完成排序
  • merge sort 參考第一週隨堂測驗
void q_sort(queue_t *q)
{
    if (!q || !q->head) {
        return;
    }
    if (q->head == q->tail) {
        return;
    }
    q->head = merge_sort(q->head);
    list_ele_t *iter;
    iter= q->head;
    while (iter && iter->next) 
        iter = iter->next;
    q->tail = iter;
}

merge_sort

list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head || !head->next) {
        return head;
    }

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

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

    list_ele_t *left = head;
    list_ele_t *right = slow->next;
    slow->next = NULL;

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

考慮以下改寫:

static list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head || !head->next)
        return head;

    list_ele_t *slow = head, *fast;
    for (fast = head->next; fast && fast->next; fast = fast->next->next)
        slow = slow->next;

    list_ele_t *mid = slow->next;
    slow->next = NULL;
    return merge(merge_sort(head), merge_sort(mid));
}

要點:

  1. 更精簡的程式碼;
  2. 善用 for 迴圈;
  3. 更精準的變數命名;
  4. 宣告加上 static,提示編譯器施加更多最佳化;

:notes: jserv

merge

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    if (!left) {
        return right;
    }

    if (!right) {
        return left;
    }

    list_ele_t *start = NULL;

    for (list_ele_t *merge_ele = NULL; left || right;) {
        if (right == NULL || (left && strcmp(left->value, right->value) < 0)) {
            if (!merge_ele)
                start = merge_ele = left;
            else {
                merge_ele->next = left;
                merge_ele = merge_ele->next;
            }
            left = left->next;
        } else {
            if (!merge_ele)
                start = merge_ele = right;
            else {
                merge_ele->next = right;
                merge_ele = merge_ele->next;
            }
            right = right->next;
        }
    }
    return start;
}

考慮以下改寫:

static list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    list_ele_t *head = NULL;

    for (list_ele_t **iter = &head; true; iter = &((*iter)->next)) {
        if (!left) {
            (*iter) = right;
            break;
        }
        if (!right) {
            (*iter) = left;
            break;
        }
        if (strcmp(left->value, right->value) < 0) {
            (*iter) = left;
            left = left->next;
        } else {
            (*iter) = right;
            right = right->next;
        }
    }
    return head;
}

要點:

  1. 善用 pointer to pointer 的技巧;
  2. 分支的調整,使程式碼更緊湊

:notes: jserv

test rusult

# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---     trace-05-ops    5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---     trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---     trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

strnatcmp

  • 單純把 strcmp 改成 strnatcmp
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---     trace-05-ops    5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---     trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---     trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100