# 2020q1 Homework1 (lab0)
contributed by < `Hsuhaoxiang` >
## 實驗環境
```shell
$ 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
```cpp
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### q_new
* 建立新的「空」佇列
* 要注意的是 malloc 使否成功分配記憶體位置
* 初始化 queue_t 中的變數 tail , head , size
```cpp
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
```cpp
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` 非常相似，不同的地方在於要將插入前的 `tail` 的 `next` 指向正要插入的這個元素
```cpp
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` 減一，並將此元素所用到的記憶體空間釋放
```cpp
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 直接結束
* 否則一一將元素的連結反轉
```cpp
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 走訪所有元素並且釋放記憶體
```cpp
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 參考[第一週隨堂測驗](https://hackmd.io/@sysprog/linux2020-quiz1)
```cpp
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
```cpp
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);
}
```
:::danger
考慮以下改寫:
```cpp
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
```cpp
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;
}
```
:::danger
考慮以下改寫:
```cpp
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
```
Sign in with Wallet
Connect another wallet