Try   HackMD

2020q1 Homework1 (lab0)

contributed by < nickyanggg >

tags: linux2020

作業說明

作業要求

依照作業說明完成 queue.c & queue.h 二個檔案,主要功能如下:

  • q_new 建立新的 empty queue
  • q_free 釋放 queue 所用到的空間
  • q_insert_head 插入新的 element 至 queue 的開頭
  • q_insert_tail 插入新的 element 至 queue 的尾端
  • q_remove_head 刪除 queue 的開頭的 element
  • q_size 計算 queue 中的 element 數量
  • q_reverse 將 queue 中的 element 依反向順序排列
  • q_sort 將queue 中的 element 依遞增順序排列

實驗環境

$ uname -a
Linux ginoah-ubuntu-18 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

實作流程

queue.h

由於 q_insert_tailq_size 皆要求複雜度

O(1),因此將 queue_t 修改如下:

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

如此,當實作 q_insert_tailq_size 時,可以不用重頭 traverse 一遍,前者可以直接利用 tail 去做串接,而後者則是可以直接回傳 size 的值。

queue.c

  • q_new
    • 確認 malloc 是否成功。
queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; }
  • q_free
    • 確認 queue 是否存在。
    • 依序釋放各個 element 所用到的空間。
    • 最後在釋放 empty queue 所用到的空間。
void q_free(queue_t *q) { /* Free queue structure */ if (!q) return; list_ele_t *curr = q->head; list_ele_t *temp; for (int i = 0; i < q->size; ++i) { free(curr->value); temp = curr->next; free(curr); curr = temp; } free(q); }
  • q_insert_head
    • 確認 queue 是否存在。
    • 確認 malloc 是否成功。
    • 若在 malloc 空間給 value 失敗時,要回頭去 free 前面 malloc 給新進 element 的空間。
    • 維護 headtailsize
bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (!q) return false; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(strlen(s) + 1); if (!newh->value) { free(newh); return false; } strncpy(newh->value, s, strlen(s) + 1); newh->next = q->head; if (!q->head) q->tail = newh; q->head = newh; q->size++; return true; }
  • q_insert_tail
    • q_insert_head 的注意事項。
bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; list_ele_t *newt; newt = malloc(sizeof(list_ele_t)); if (!newt) return false; newt->value = malloc(strlen(s) + 1); if (!newt->value) { free(newt); return false; } strncpy(newt->value, s, strlen(s) + 1); newt->next = NULL; if (!q->head) q->head = newt; else q->tail->next = newt; q->tail = newt; q->size++; return true; }
  • q_remove_head
    • 確認 queue 是否存在,以及 size 是否為 0。
    • sp 存在,copy 欲刪的 element 的 value 進去,記得在最後面補上結束字元 '\0',詳情請參考 strncpy
    • 釋放所用到的空間,並且維護 headtailsize
bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->size) return false; if (sp) { strncpy(sp, q->head->value, bufsize - 1); *(sp + bufsize - 1) = '\0'; } free(q->head->value); list_ele_t *head = q->head; q->head = q->head->next; free(head); if (!q->head) q->tail = NULL; q->size--; return true; }
  • q_size
    • 確認 queue 是否存在。
int q_size(queue_t *q) { if (!q) return 0; return q->size; }
  • q_reverse
    • 確認 queue 是否存在以及 size <= 1 的狀況。
    • 利用 currprevtemp 來把 queue 中所有的 elements 逆向接起來。
    • headtail 的值調換。
void q_reverse(queue_t *q) { if (!q || q->size <= 1) return; list_ele_t *curr, *prev, *temp; curr = q->head; prev = NULL; for (int i = 0; i < q->size; ++i) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } temp = q->head; q->head = q->tail; q->tail = temp; }
  • q_sort
    • 確認 queue 是否存在以及 size <= 1 的狀況。
    • 由於複雜度得為
      O(nlogn)
      ,這邊是直接 call 另外實作的 merge_sort
    • 維護 tail 的值。
void q_sort(queue_t *q) { if (!q || q->size <= 1) return; q->head = merge_sort(q->head); list_ele_t *curr = q->head; for (int i = 0; i < q->size; ++i) { q->tail = curr; curr = curr->next; } }
  • merge_sort
    • 參考 Linked List Sort 的實作方式。
    • merge_sort
      • 由於假如每次在 divide 的時候 left 都 assign 成 head,而 right 則是 head->next 的話,也就是左半段的 queue 只有一個 element,而右半段的 queue 則是剩下的所有 element,這樣子的複雜度仍為
        O(n2)
        ,因此下面會介紹將 leftright 平均分配的方式。
      • leftright 前者每次跳一個 element,後者每次跳二個 element,當 right 到 queue 的尾端時,left 所指向的 element 剛好位於 queue 的中間,接著再將 right assign 成 left->next ( 也就是右邊半段的頭 ),再把 left->next assign 成 NULL ( 也就是斷開成二個 queue ),最後再把 left assign 成 head 即可,此時 leftright 各代表著左半段的 head 以及右半段的 head
    • 最後再利用遞迴去一直 divide,最後再 call merge 來把二段已經 sort 好的 queue 給 merge 起來。
list_ele_t *merge_sort(list_ele_t *head) { if (!head || !head->next) return head; list_ele_t *left = head; list_ele_t *right = head->next; while (right && right->next) { left = left->next; right = right->next->next; } right = left->next; left->next = NULL; left = merge_sort(head); right = merge_sort(right); return merge(left, right); }
  • merge
    • 由於測資所塞進的 element 過多,因此在呼叫 merge 的時候,不可利用遞迴的方式,不然會發生 stack overflow 導致 segmentation fault
// 非遞迴的版本 list_ele_t *merge(list_ele_t *left, list_ele_t *right) { list_ele_t *head, *curr; if (strcmp(left->value, right->value) <= 0) { head = left; left = left->next; } else { head = right; right = right->next; } curr = head; while (left && right) { if (strcmp(left->value, right->value) <= 0) { curr->next = left; left = left->next; } else { curr->next = right; right = right->next; } curr = curr->next; } if (left) curr->next = left; if (right) curr->next = right; return head; }
// 遞迴的版本 list_ele_t *merge(list_ele_t *left, list_ele_t *right) { if (!left) return right; if (!right) return left; if (strcmp(left->value, right->value) < 0) { left->next = merge(left->next, right); return left; } else { right->next = merge(left, right->next); return right; } }

測試結果

利用 make test 觀看結果

make test
scripts/driver.py -c
---	Trace		Points
+++ 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