# 2020q3 Homework1 (lab0)
contributed by < `zzzxxx0001` >
## 開發環境
```shell=
$ uname -a
Linux itlab-right 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 作業要求
* 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: 以遞增順序來排序鏈結串列的元素
## 開發過程
* **queue.h**
* 根據題目q_insert_tail所需，達到時間複雜度$O(1)$的目標，必須新增tail指標，提供Queue快速尋訪。
* 為快速計算Queue中的node數量，達到時間複雜度$O(1)$的目標，加入`int size`，每成功新增一個節點size加1。
```cpp
typedef struct
{
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
* **q_new()**
* 透過`malloc`分配記憶體空間給Queue，在初始化之前先確認是否成功分配，以免造成空指標的操作。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if(q)
{
q->head = q->tail = NULL;
q->size = 0 ;
}
return q;
}
```
* **q_free**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`*temp`指標指向欲刪除的head node。
* 透過while迴圈訪問所有節點，將節點空間依序釋放。
```cpp
void q_free(queue_t *q)
{
if(!q) return ;
while(q->head)
{
list_ele_t *temp = q->head ;
q->head = q->head->next ;
temp->next = NULL ;
free(temp->value) ;
free(temp) ;
}
free(q);
}
```
* **q_insert_head**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`list_ele_t *newh = malloc(sizeof(list_ele_t))`分配記憶體給新的節點，並確認是否成功分配，以免後續操作錯誤。
* 透過`newh->value = malloc(sizeof(char)*( strlen(s)+1 ))`分配適當的記憶體空間，提供給`newh->value`複製`char *s`內容，預留多一格的長度==strlen(s)+1==置放字串終結字元('\0')。
* 透過`strncpy(newh->value, s, strlen(s)+1)`將字串含終結碼一併複製到`newh->value`，因此複製長度為**strlen(s)+1**
* insert head分為兩個case：
* 如果q->head不存在，則將head與tail指向newh
* 如果q->head已存在，newh成為新的head，並將newh->next指向原本的head
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if(!q) return false ;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if(!newh) return false ;
newh->value = malloc(sizeof(char)*( strlen(s)+1 )) ;
if(!newh->value)
{
free(newh) ;
return false ;
}
q->size ++ ;
strncpy(newh->value, s, strlen(s)+1);
if(!q->head)
{
newh->next = NULL ;
q->head = q->tail = newh ;
return true ;
}
newh->next = q->head;
q->head = newh;
return true;
}
```
* **q_insert_tail**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`list_ele_t *newh = malloc(sizeof(list_ele_t))`分配記憶體給新的節點，並確認是否成功分配，以免後續操作錯誤。
* 透過`newh->value = malloc(sizeof(char)*( strlen(s)+1 ))`分配適當的記憶體空間，提供給`newh->value`複製`char *s`內容，預留多一格的長度==strlen(s)+1==置放字串終結字元('\0')。
* insert tail分為兩個case：
* 如果q->head不存在，則將head與tail指向newh。
* 如果q->head已存在，則將tail->next指向newh，並將newh設為新的tail。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if(!q) return false ;
list_ele_t *newh = malloc(sizeof(list_ele_t)) ;
if(!newh)
return false ;
newh->value = malloc(sizeof(char)*(strlen(s) + 1));
if(!newh->value)
{
free(newh) ;
return false ;
}
q->size ++ ;
strncpy(newh->value, s, strlen(s)+1) ;
newh->next = NULL ;
if(!q->head)
{
q->head = q->tail = newh ;
}
else
{
q->tail->next = newh ;
q->tail = newh ;
}
return true;
}
```
* **q_remove_head**
* 操作前先確認Queue或Queue->head是否存在，以免造成後續執行錯誤。
* 依循題目提示，將條件寫入if條件式。
>If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)
* 透過`memset(sp, '\0', bufsize)`將陣列`sp`初始化。
* 因最後一格空間需保留給字串終結字元，因此實際複製字串長度為==bufsize-1==。
* 透過`rm_node`指標指向欲刪除的head node。
* head則由head->next進行取代。
* 將rm_node內所有資料記憶體釋放後，再將rm_node記憶體空間釋放。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if(q && q->head)
{
if(strlen(q->head->value) >= bufsize && !sp) return false ;
list_ele_t *rm_node = q->head ;
memset(sp, '\0', bufsize) ;
strncpy(sp, rm_node->value, bufsize-1) ;
q->head = q->head->next ;
rm_node->next = NULL ;
free(rm_node->value) ;
free(rm_node) ;
q->size -- ;
if(q->size == 0) q->tail = NULL ;
return true ;
}
return false ;
}
```
* **q_size**
* 操作前先確認Queue是否存在，如果不存在則回傳0。
* 直接將`q->size`回傳，代表Queue中的節點數量。
```cpp
int q_size(queue_t *q)
{
if(!q) return 0 ;
return q->size ;
}
```
* **q_reverse**
* 此部分參考[quiz_1](https://hackmd.io/@sysprog/sysprog2020-quiz1)中link list的`node_t *reverse(node_t *head)`。
* 操作前先確認Queue狀態，如果Queue不存在、Queue->head不存在或是Queue->size小於2都無法操作reverse，則直接return。
* reverse操作概念已在[quiz1_reverse](https://hackmd.io/y5g1z2z5Ta2Ru8itT39yPQ?view#reverse)中解釋。
* 預先將`q->tail`指向`q->head`，操作完reverse後，再將`q->head`指向目前的`head(cursor)`。
```cpp
void q_reverse(queue_t *q)
{
if(!q || !q->head || q->size<2) return ;
list_ele_t *cursor = NULL ;
q->tail = q->head ;
while(q->head)
{
list_ele_t *next = q->head->next ;
q->head->next = cursor ;
cursor = q->head ;
q->head = next ;
}
q->head = cursor ;
}
```
* **q_sort**
* Sort方始採merge sort，可達到時間複雜度$O(nlogn)$的理想目標。
* 演算法部分參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)。
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *head = NULL;
list_ele_t **temp = &head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) <= 0) {
*temp = l1;
l1 = l1->next;
} else {
*temp = l2;
l2 = l2->next;
}
temp = &((*temp)->next);
}
if (l1)
*temp = l1;
if (l2)
*temp = l2;
return head;
}
list_ele_t *mergeSortList(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) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
return merge(l1, l2);
}
void q_sort(queue_t *q)
{
if (!q || q->size == 1)
return;
q->head = mergeSortList(q->head);
while (q->tail)
q->tail = q->tail->next;
}
```
## 程式測試
* 透過 `make test` 驗證程式執行狀態是否合乎題意。
* 透過 `clang-format -i <filename>` 修正程式碼編排方式。
```
$ make test
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
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
```
Sign in with Wallet
Connect another wallet