# 2021q1 Homework1 (lab0)
contributed by < `mahavishnuj` >
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
## 實驗環境
這次的實驗由於必須使用 Ubuntu Linux 藉此測試針對Mac系統所出的`Multipass` 使用類似Docker的技術可以在 `MacOS` 中達到較為輕量化的 `VM`
```shell
$ uname -a
Linux moral-gator 5.4.0-66-generic #74-Ubuntu SMP Wed Jan 27 22:54:38 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
```
:::danger
multipass 使用 macOS 的 [Hypervisor.framework](https://developer.apple.com/documentation/hypervisor) 或 [VirtualBox](https://www.virtualbox.org/)，後兩者跟 Docker 行為落差較大，請注意用語。
:notes: jserv
:::
## 實驗過程與心得
### q_size()
在跟著指示在 `queue` 這個結構裡面加入 `int size` 透過這個方式能夠讓我們能夠更了解 `queue` 裡頭的各種資訊，除此之外更加入了另一個 `Pointer` `*tail` 以便於之後從尾端插入資料能在 **$O(1)$** 的時間內達成。相較於沒有 `*tail` 的狀況需要從 `head` 依序慢慢的找節省了不少時間
```c=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
我的方法是先判斷 `q` 是否為空，不是內容為空是根本沒有新增 `queue` 或是內完全不含任何數值都是回傳 `0` 若是內容有物則直接回傳 `q` 內 `size` 的內容
```c=
int q_size(queue_t *q)
{
if (!q || !q->head ) {
return 0;
}
return q->size;
}
```
### q_new()
再來實作新增 `queue` 這個程式，其實在程式碼中的 `TODO` 就有貼心小提醒，所以在一開始除了用 `malloc` 宣告出一個 `queue` 之餘，還在後面檢查是否有成功宣告並配置記憶體，若是失敗則回傳 `NULL` 值
```c=
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_insert_head
透過取的 `head` 指標的位置，作為起始位置並將插入新的元素放在左端，除了 `q` 本身若是不存在的話或是節點宣告失敗必須回傳`NULL` 需要注意若是在宣告 `value` 時失敗需要將 `newh` 釋放出來，來避免造成 `Memory Leak` 的狀況。
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
/*allocate more than 1 size of string length*/
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
if (q->size == 0) {
q->tail = newh;
}
q->head = newh;
q->size += 1;
return true;
}
```
### Insert_tail
原則上宣告新節點以及檢查記憶體的方式跟 `head` 一樣，在 `Requirement` 裡面有提到需要達到 ***O(1)*** 的時間複雜度，直觀的方法就是從 `head` 慢慢依序往下找直到最後一個 `Node` 後面接上新的點，但這樣的做法曠時廢日，透過這樣子多一個指標指向 `tail` 的方式可以大大縮短時間，需要注意的時若是佇列裡面是空的，添加完需要把 `head` 與 `tail` 都指向同一個點。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q) {
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh) {
free(newh);
return false;
}
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
strncpy(newh->value, s, strlen(s) + 1);
newh->next = NULL;
if (!q->tail) {
q->tail = newh;
q->head = newh;
}
else {
q->tail->next = newh;
q->tail = newh;
}
q->size++;
return true;
}
```
### q_free()
`free` 的過程其實挺直白的，透過 `head` 的指標慢慢往下找到下一個點，值得一提的部分是在 `free` 動作之前應該先把 `head` 移動到下一個點，避免在不小心 `free` 之後遺失 `head` 的位置，還有必須先 `free` `value` 這個 `array` 空間之後在處理整個資料結構。
```c=
void q_free(queue_t *q)
{
if (!q) {
return;
}
list_ele_t *tmp = q->head;
while (q->head) {
q->head = q->head->next;
free(tmp->value);
free(tmp);
tmp = q->head;
}
free(q);
}
```
### q_remove_head
在移出 `head` 的同時還需要回傳 `head` 節點所含的內容，除了檢查佇列是否為空之外，還要檢查是否為空佇列。之後在把需要移除的節點 `address` 存於 `tmp` 當中，並將 `head` 先移動到下一個點上面，需要注意的部分是需要在 `sp` 最後加上一個 `\0`，在 `free` 的部分也記得要把 `value` 一起釋放。
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
list_ele_t *tmp = q->head;
q->head = tmp->next;
if (sp) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_reverse
看到教材有分享利用`Pointer to Pointer`做 `Indirection` 來操作指標內容，但在實做上面還是先用三個指標的方式來操作。
```c=
void q_reverse(queue_t *q)
{
if (!q) {
return;
}
if (q->size < 2) {
return;
}
list_ele_t *cur = q->head;
list_ele_t *nxt = cur;
list_ele_t *prev = NULL;
q->tail = q->head;
while (nxt) {
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
q->head = prev;
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=red]
nxt[shape=plaintext,fontcolor=purple]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
cur->A;
nxt->A
}
A->B->C->D->NULL1
prev->NULL2
}
```
- 一開始先將 `prev` 指標指向 `NULL` ， `head`, `cur`, 與 `nxt` 指向最一開始的節點。 進入 `while loop` 之後先將 `nxt` 指向下一個節點， `cur` 指向 `prev` 所指的點，之後再分別將 `prev` 與 `cur` 往前移
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=red]
nxt[shape=plaintext,fontcolor=purple]
tail[shape=plaintext,fontcolor=orange]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
tail->A
head->A
cur->A;
nxt->B
}
B->C->D->NULL1
prev->A->NULL2
}
```
- 執行兩次後的結果，而 `head` 的部分直到執行到最後才會做修改， `tail` 的部分則是一開始便改變
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=blue]
prev[shape=plaintext,fontcolor=red]
nxt[shape=plaintext,fontcolor=purple]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
prev->A
nxt->C
head->A
cur->C
}
B->A->NULL2
C->D->NULL1
}
```
### q_sort
在實作排序的部分，參考了很多同學還有網路上的相關資料，先用一個 `function` 將 `linked-list` 分成兩個子字串。
```c=
list_ele_t *split_list(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *rabt = head->next;
list_ele_t *turt = head;
while (rabt && rabt->next) {
turt = turt->next;
rabt = rabt->next->next;
}
rabt = turt->next;
turt->next = NULL;
list_ele_t *l1 = split_list(head);
list_ele_t *l2 = split_list(rabt);
return merge_sort(l1, l2);
}
```
- 利用兩個指標，以偵查 cycle 所使用的龜兔賽跑概念，指標 `rabt` 移動距離是 `turt` 的兩倍
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
turt[shape=plaintext,fontcolor=red]
rabt[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
turt->A
}
A->B->C->D->NULL1
rabt->B
}
```
- 執行完後 `rabt` 與 `turt` 會分別在不同的點，並且將其斷開成兩截
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
rabt[shape=plaintext,fontcolor=blue]
turt[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
A->B->C->D->NULL1
turt->C
rabt->NULL1
}
```
- 斷成兩截後分別回傳兩段 `linked-list` 的 `head` 指標
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
rabt[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
rabt->C
}
A->B->NULL1
C->D->NULL2
}
```
- 然後再依照其 `value` 的大小去做排序，使用跟 `QuickSort` 一樣 `Divided and Conquer` 的策略進行
```c=
list_ele_t *merge_sort(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *tmp, *q;
if (strcmp(l1->value, l2->value) < 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
q = tmp;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
tmp->next = l1;
tmp = tmp->next;
l1 = l1->next;
} else {
tmp->next = l2;
tmp = tmp->next;
l2 = l2->next;
}
}
if (l1) {
tmp->next = l1;
}
if (l2) {
tmp->next = l2;
}
return q;
}
```
Sign in with Wallet
Connect another wallet