# 2020q3 Homework1 (lab0)
contributed by < `CW-B-W` >
[github](https://github.com/CW-B-W/sysprog2020q3-lab0-c)
###### tags: `sysprog2020`
## Outline
[TOC]
## 作業要求
在 ``queue.[c/h]`` 中完成以下實作
* `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
* 1 `hehe`
* 1 `hehe`
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* points to the tail element, if q_size=1, then head=tail. */
size_t size;
} queue_t;
```
### queue.c
* **q_new**
* queue為空時，head, tail 都必須是 NULL，size 必須為 0
```cpp
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**
* `rm_node` 指向此次 iteration 需要 free 的 Node
```cpp
void q_free(queue_t *q)
{
if (!q) {
return;
}
while (q->head) {
list_ele_t* rm_node = q->head;
q->head = q->head->next;
free(rm_node->value);
free(rm_node);
}
free(q);
}
```
* **q_insert_head**
* 注意邊界情況: `當 q_size 為 0 時`
* 需要在 `newh = malloc` 前先檢查 `q == NULL`，否則可能多一次 `malloc`的成本，並容易忘記 `free` 而導致 `memory leak`
* `strlen` 不會將 `'\0'`算入，故需另外保留一個`sizeof(char)`給`'\0'`
* 當 `newh->value` `malloc`失敗後，要記得刪除 `newh = malloc(...)` 分配的記憶體
* 注意當 queue 為空時，要特別設置 `q->head` 與 `q->tail`
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/*
* DO NOT do this check after malloc
* Memory leak is prone to happen
*/
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->next = NULL;
newh->value = NULL;
/*
* Extra 1 bytes for '\0'
* Is calling strlen(s) bad for performance ??
*/
size_t copy_size = (sizeof(char) * strlen(s)) + (sizeof(char) * 1);
newh->value = (char*) malloc(copy_size);
if (!newh->value) {
/* Failed to construct newh, free it! */
free(newh);
return false;
}
memcpy(newh->value, s, copy_size);
if (!q->head) {
q->head = q->tail = newh;
} else {
newh->next = q->head;
q->head = newh;
}
q->size += 1;
return true;
}
```
* **q_insert_tail**
* 同 `q_insert_head(...)` 注意事項
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t* newt;
if (!q) {
return false;
}
newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
newt->next = NULL;
newt->value = NULL;
/*
* Extra 1 bytes for '\0'
* Is calling strlen(s) bad for performance ??
*/
size_t copy_size = (sizeof(char) * strlen(s)) + (sizeof(char) * 1);
newt->value = (char*) malloc(copy_size);
if (!newt->value) {
/* Failed to construct newt, free it! */
free(newt);
return false;
}
memcpy(newt->value, s, copy_size);
if (!q->tail) {
q->head = q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
q->size += 1;
return true;
}
```
* **q_remove_head**
* 注意邊界情況: `當 q_size 為 1 時`
* 若 `sp != NULL`，須將移除內容複製到buffer
* 注意 bufsize 大小限制。大小不足也須複製，但只可複製部分
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
list_ele_t* rm_node = q->head;
q->head = q->head->next;
q->size -= 1;
if (!q->head) {
q->tail = NULL;
}
size_t copy_size = (sizeof(char) * strlen(rm_node->value)) + (sizeof(char) * 1);
if (sp)
{
memcpy(sp, rm_node->value, copy_size <= bufsize ? copy_size : bufsize);
sp[bufsize-1] = '\0';
}
free(rm_node->value);
free(rm_node);
return true;
}
```
* **q_size**
* 直接在 struct 裡面新增 `size`
```cpp
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
* **q_reverse**
* 反轉過程只需用到 `q->head`，故可先 `q->tail = q->head;`
* 反轉完記得 `q->tail->next = NULL;`
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
q->tail = q->head;
list_ele_t* cur = q->head->next;
while (cur) {
list_ele_t* prev = q->head;
q->head = cur;
cur = cur->next;
q->head->next = prev;
}
q->tail->next = NULL;
}
```
* **q_sort**
* 使用 Merge sort 排序
* 利用兩個 step(步距) 不同的 Cursor ，找出 list 中央點
* 將一個 list 斷成兩段(`stp1->next = NULL;`)，並 recursively 求解
* Merge 時，若其中一段 List 以完全用完，可直接將剩下的另一段 List 直接接到 Tail
* 用自己寫的 Naive strcmp (i.e., 逐 char 慢慢比對)，會 Time Limit Exceeded
* 需減少"不必要" Function call 數量，不然也會 Time Limit Exceeded
```cpp
static list_ele_t* q_sort_mergesort(list_ele_t* p1)
{
if (!p1->next)
return p1;
list_ele_t* stp1 = p1;
list_ele_t* stp2 = p1->next;
while (stp2 && stp2->next) {
stp1 = stp1->next;
stp2 = stp2->next->next;
}
list_ele_t* p2 = stp1->next;
stp1->next = NULL;
p1 = q_sort_mergesort(p1);
p2 = q_sort_mergesort(p2);
/* make *p1 < *p2, i.e., make p1 be the head of list */
if (strcmp(p1->value, p2->value) > 0) {
list_ele_t* tmp = p1;
p1 = p2;
p2 = tmp;
}
list_ele_t* ret_head = p1;
list_ele_t* p3 = p1->next;
/* p1 is the smallest among the three, p2 or p3 is p1's successor */
while (p2 && p3) {
int res = strcmp(p2->value, p3->value);
if (res < 0) {
p1->next = p2;
p1 = p2;
p2 = p2->next;
}
else {
p1->next = p3;
p1 = p3;
p3 = p3->next;
}
}
p1->next = p2 ? p2 : p3;
return ret_head;
}
```
* sort 完用 O(n) 搜 `q->tail`
* 因為整條 list 已經 sorted，故可由任一個 Node 直接往下搜即可，不必先 `q->tail = q->head` 在開始搜
```cpp
void q_sort(queue_t *q)
{
if (q_size(q) <= 1)
return;
q->head = q_sort_mergesort(q->head);
/* O(n) reconstruct q->tail */
while (q->tail->next)
{
q->tail = q->tail->next;
}
}
Sign in with Wallet
Connect another wallet