# 2021q1 Homework1 (lab0-c)
contributed by < `JimmyZhan070100` >

###### tags: `linux2021`

## Queue 實做

[github](https://github.com/JimmyZhan070100/lab0-c)

### Queue structure

題目要求必須在 $O(1)$ 的時間內得到 qeue 的尾端和大小，所以在結構裡增加 `tail` 和 `size`

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Insert tail in O(1) time */
    int size;    /* Get count of elements in O(1) time */
} queue_t;

### New
產生一個新的 queue，同時初始化相關的資料結構

### Free
釋放 queue 前需要檢查是否 queue 為 NULL。
再來釋放 queue 上的每個 node 使用空間，此外必須先將字串的空間先釋放後，再來釋放 node

### Insert head/tail
新增一個 node 並且將字串放入 value，然後將 node 放入頭/尾

- 注意
- 如果 queue 是空的，則必須改動 head/tail
- 不論是新增一個 node 或為 value 要一塊空間都必須確認是否 `malloc` 有成功，若沒有成功則必須 `return false`
- 為字串新增一塊空間時必須 ==+1== 負責存放 `\0`
`malloc(sizeof(char) * (strlen(s) + 1))`

### Remove head
移除之前必須檢查是否 queue 為空的，以及 sp 是否有指向一塊記憶體位置。
依據題目要求，必須先將 value 指向的字串複製到 sp。接著改變 q->head 方向後，再釋放原本 q->head 的空間

> 題目說 `up to a maximum of bufsize-1 characters, plus a null terminator`，要注意字串的正確長度

if (bufsize > strlen(q->head->value)) {
    strncpy(sp, q->head->value, strlen(q->head->value));
    sp[strlen(q->head->value)] = '\0';
} else {
    strncpy(sp, q->head->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}

### Size
因為在結構上有紀錄節點的長度，所以只需要回傳 `q->size` 即可，不過要注意若 q 是空的，則要回傳 0

### Reverse

宣告三個指標 `curr`, `next`, `tmp`。利用 `curr` 紀錄當下的節點，`next`紀錄下一個節點，`tmp`負責當作中介

list_ele_t *curr = q->head, *next = q->head->next, *tmp;

digraph struct {
    node [shape=record];
    curr[label= "curr" shape= plaintext, fontcolor=red]
    next[label= "next" shape= plaintext, fontcolor=red]
    n1[label="<f0> head|<f1> size|<f2> tail"];
    {
        rankdir=LR;
        n2[label="<f0> 1-value|<f1> next"];
        n3[label="<f0> 2-value|<f1> next"];
        nn[label="<f0> ...|<f1> next"];
        n2:f1 -> n3;
        n3:f1 -> nn;
    }
    n1:f0 -> n2; n1:f2 -> nn;
    curr-> n2:f0; next-> n3;
}

接著將 `tail` 改為 `head` 的位置，並進入迴圈改變節點的順序

while (next) {
    tmp = next->next;
    next->next = curr;
    curr = next;
    next = tmp;
}

最後將 `tail->next` 改為 NULL，以及 `head` 指向 `curr` 所在的節點。

q->tail->next = NULL;
q->head = curr;

### Sort

## 如何測試

測試所有測資

針對單一個測資可以用：

以得到更詳細的程式運行狀況，方便檢查程式的錯誤