# 2024q1 Homework1 (lab0)
contributed by < [YeeeLiang](https://github.com/YeeeLiang) >
### Reviewed by `yenslife`
- [ ] GitHub
:::danger
command 是「命令」，而非「指令」(instruction)。
不用假裝有禮貌說「建議」，就是因為同學沒做好，你要求他改進。
:::
<s>建議</s> 將程式碼上傳到 Github 上，方便追蹤。你可以使用 `git push origin [分支名稱]` <s>指令</s>來上傳 (origin 表示你的 remote repo 的 url，可以透過 `git remote -v` 來查看)
:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::
### Reviewed by `yeh-sudo`
開發過程沒有描述你的想法與作法，只有貼上程式碼，在你的 Github 上也沒有你上傳的程式碼，請將程式碼上傳至你的 Github ，並且有完整的 git commit message 來闡述你做了什麼以及你的實作方法，可以參考〈[How to Write a Git Commit Message](https://cbea.ms/git-commit/)〉。
# 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 126
Model name: Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
Stepping: 5
CPU MHz: 1200.000
CPU max MHz: 3600.0000
CPU min MHz: 400.0000
BogoMIPS: 2380.80
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 128 KiB
L2 cache: 2 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 針對佇列操作的程式碼實作
:::danger
改進你的漢語表達。
:::
這個函式將在佇列的頭部插入一個新節點，資料為傳遞給函式的 data。如果佇列是空的，新節點將同時成為尾端節點。
:::danger
說好的進度呢？
:::
:::info
抱歉，之前Git遇上傳輸困難，目前正努力補齊中
> 你唯一需要跟我道歉的理由是，你不夠強。 :notes: jserv
:::
<s>
## q_new
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head != NULL) {
INIT_LIST_HEAD(head);
}
return head;
}
```
## q_free
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
struct list_head *pos, *temp;
element_t *entry;
list_for_each_safe(pos, temp, head) {
entry = list_entry(pos, element_t, list);
free(entry->data);
list_del(pos);
free(entry);
}
free(head);
}
```
## q_insert_head
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL) {
return false;
}
new_element->data = strdup(s);
if (new_element->data == NULL) {
free(new_element);
return false;
}
list_add(&new_element->list, head);
return true;
}
```
## q_insert_tail
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL) {
return false;
}
new_element->data = strdup(s);
if (new_element->data == NULL) {
free(new_element);
return false;
}
list_add_tail(&new_element->list, head);
return true;
}
```
## q_remove_head
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (list_empty(head)) {
return NULL;
}
element_t *entry = list_first_entry(head, element_t, list);
strncpy(sp, entry->data, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(&entry->list);
free(entry->data);
free(entry);
return entry;
}
```
## q_remove_tail
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (list_empty(head)) {
return NULL;
}
element_t *entry = list_last_entry(head, element_t, list);
strncpy(sp, entry->data, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(&entry->list);
free(entry->data);
free(entry);
return entry;
}
```
## q_size
:::danger
留意用語。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
光看<s>函數</s> 名字，不容易想起功用為何(筆記一下)
主要功能：計算目前佇列的節點總量
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
return list_empty(head) ? 0 : list_size(head);
}
```
## q_delete_mid
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
if (list_empty(head)) {
return false;
}
struct list_head *slow = head;
struct list_head *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head *temp = slow->prev->next;
list_del(temp);
free(list_entry(temp, element_t, list)->data);
free(list_entry(temp, element_t, list));
return true;
}
```
## q_delete_dup
```c
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
if (list_empty(head)) {
return false;
}
struct list_head *current, *temp;
element_t *current_entry, *temp_entry;
list_for_each_safe(current, temp, head) {
current_entry = list_entry(current, element_t, list);
struct list_head *compare, *temp_compare;
element_t *compare_entry, *temp_compare_entry;
list_for_each_safe(compare, temp_compare, head) {
if (compare != current) {
compare_entry = list_entry(compare, element_t, list);
if (strcmp(current_entry->data, compare_entry->data) == 0) {
temp_compare_entry = list_entry(temp_compare, element_t, list);
list_del(temp_compare);
free(temp_compare_entry->data);
free(temp_compare_entry);
}
}
}
}
return true;
}
```
## q_swap
兩個鄰近的node進行交換，[如圖](https://leetcode.com/problems/swap-nodes-in-pairs/description/)
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
if (list_size(head) < 2) {
return;
}
struct list_head *pos;
element_t *current, *next;
list_for_each(pos, head) {
current = list_entry(pos, element_t, list);
if (pos->next != head) {
next = list_entry(pos->next, element_t, list);
char *temp = current->data;
current->data = next->data;
next->data = temp;
}
pos = pos->next;
}
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
## q_reverse
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)。
:::
注意：q_reverse 只能重排已經存在的節點，因此不該配置或釋放任何鏈結串列節點
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (list_empty(head) || list_size(head) == 1) {
return;
}
struct list_head *current, *temp;
element_t *current_entry, *temp_entry;
list_for_each_safe(current, temp, head) {
current_entry = list_entry(current, element_t, list);
// Move the current element to the front
list_move(¤t_entry->list, head);
}
}
```
## q_reverseK
也是反向順序排列，與q_reverse不同在於，q_reverseK指定每 k 個節點為一組
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
if (list_size(head) < k) {
return;
}
struct list_head *pos, *temp;
element_t *current, *next;
int count = 0;
list_for_each_safe(pos, temp, head) {
if (count == k) {
count = 0;
continue;
}
current = list_entry(pos, element_t, list);
if (count < k) {
next = list_entry(pos->next, element_t, list);
char *temp_data = current->data;
current->data = next->data;
next->data = temp_data;
}
count++;
}
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
## q_sort
以遞增順序來排序
```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (list_empty(head) || list_size(head) == 1) {
return;
}
}
```
## q_descend
可參閱[2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)的圖，有助於程式碼的理解
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
if (list_empty(head) || list_size(head) == 1) {
return 0;
}
int removed_nodes = 0;
struct list_head *current, *temp;
element_t *current_entry, *temp_entry;
list_for_each_safe(current, temp, head) {
current_entry = list_entry(current, element_t, list);
struct list_head *compare, *temp_compare;
element_t *compare_entry, *temp_compare_entry;
list_for_each_safe(compare, temp_compare, head) {
if (compare != current) {
compare_entry = list_entry(compare, element_t, list);
if (strcmp(current_entry->data, compare_entry->data) < 0) {
temp_compare_entry = list_entry(temp_compare, element_t, list);
list_del(temp_compare);
free(temp_compare_entry->data);
free(temp_compare_entry);
removed_nodes++;
}
}
}
}
return removed_nodes;
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
## q_merge
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
return 0;
}
int main() {
return 0;
}
```
</s>
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
Sign in with Wallet
Connect another wallet