2020q3 Homework1 (lab0)
===
contribute by `Liao712148`
###### tags: `進階電腦系統理論與實作`
#### Queue structure
因為在之後的`q_size`,`q_insert_head`,`q_insert_tail`都有要求，要在$O(1)$時間完成，所以在`queue_t`中新增了`tail`,`size`這兩個成員
```cpp=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
---
#### q_new
將陣列初始化
```cpp=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
---
#### q_free
將陣列中使用到的空間都釋出
```cpp=
void q_free(queue_t *q)
{
if (q == NULL)
return ;
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
要特別注意第`8`行，因為我們在`insert node`階段，有分配一個空間給它，所以要記得將那一段空間給釋放出來。
---
#### q_insert_head
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
size_t length = strlen(s);
char *tmp = malloc(sizeof(char)*(length+1));
if (tmp == NULL) {
free(newh);
return false;
}
newh->value = tmp;
strcnpy(tmp, s, length);
tmp[length] = '\0';
newh->next = q->head;
q->head = newh;
if (q->tail == NULL)
q->tail = q->head;
q->size++;
return true;
}
```
插入`node`，要注意的是在第`10`行有配置記憶體空間給字串`s`，當配置失敗時，在回傳錯`false`之前要先將`newh`給釋放掉。此外用`strcnpy`複製字串並不保證會複製到最後面的`null terminator`
[C語言中函數strcpy ,strncpy ,strlcpy的用法](http://www.unixlinux.online/unixlinux/linuxbc/bclinux/201703/61067.html)
所以我們會在字串的尾端主動加上`null terminator`。
在第`20,21`處理當第一次插入`node`時，`tail`會是指向初始化的`NULL`，所以將`tail`改成指向第一個`node`。
---
#### q_insert_tail
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
size_t length = strlen(s);
char *tmp = malloc(sizeof(char)*(length+1));
if (tmp == NULL) {
free(newh);
return false;
}
newh->value = tmp;
strcnpy(tmp, s, length);
tmp[length] = '\0';
newh->next = NULL;
if (q->size == 0)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
同理`bool q_insert_head(queue_t *q, char *s)`
---
#### q_remove_head
將陣列中的`head`中的字串複製到`sp`，倘若字串比`bufsize`長，則只能複製`bufzise-1`個字元，之後再將`head node`所配置的空間整個釋出
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL || sp == NULL)
return false;
size_t length = strlen(q->head->value);
if (length > bufsize)
length = bufsize - 1;
strcnpy(sp, q->head->value, length);
sp[length] = '\0';
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
if (q->size == 0)
q->tail = NULL;
return true;
}
```
---
#### q_size
在$O(1)$時間內，回傳陣列的大小
```cpp=
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
else
return q->size;
}
```
---
#### q_reverse
將陣列順序對調
```cpp=
void q_reverse(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
list_ele_t *tmp = NULL;
q->tail = q->head;
while (q->head->next != NULL) {
list_ele_t *next = q->head->next;
q->head->next = tmp;
tmp = q->head;
q->head = next;
}
q->head->next = tmp;
q->tail->next = NULL;
}
```
利用[quiz1](https://hackmd.io/@sysprog/sysprog2020-quiz1)，即可完成，要特別留意的是，要記得更新`tail`指向的地方。
---
#### q_sort
依據每個`node`中的字串長度，由短的排到大的
```cpp=
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
int length = q->size;
if (length < 8)
insertion_sort(&q->head); // refer https://www.geeksforgeeks.org/insertion-sort-for-singly-linked-list/
else
merge_sort(&q->head); // refer https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
list_ele_t *tmp = q->head;
while (tmp->next != NULL)
tmp = tmp->next;
q->tail = tmp;
}
```
當問題的資料量較小時(欲排序的元素之數目較小)，使用Insertion Sort會很有效率，這是因為和Quick Sort、Merge Sort、Heap Sort相比，Insertion Sort不具有「遞迴」形式，因此不需要系統的stack。
[Stackoverflow：Is recursion ever faster than looping?](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)
附上結果圖
Sign in with Wallet
Connect another wallet