# 2023q1 Homework1 (lab0)
contributed by < [cin-cout](https://github.com/cin-cout) >
:::danger
未見 [cin-cout/lab0-c](https://github.com/cin-cout/lab0-c) 程式碼更新。
:notes: jserv
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping: 10
CPU MHz: 1201.821
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 開發過程
### q_new
#### version 1
<s>很多人會</s> 宣告 element 再傳其中的 head 給 qtest，但其實 qtest 是<s>餵給</s> q_context_t 內的 q ，所以 malloc element 的大小只會浪費空間，free 也會需要多 free head 所在的 element。
:::danger
避免說「餵給」這樣不精準的話。「很多人」如何如何，到底跟你的開發進度何關？
:notes: jserv
:::
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if(!q){
return NULL;
}
INIT_LIST_HEAD(q);
return q;
}
```
### q_insert_head
#### version 1
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *q = malloc(sizeof(element_t));
if (!q)
return false;
strcpy(q->value, s);
q->list.prev = NULL;
q->list.next = head;
head->prev = &q->list;
}
```
#### version 2
<s>一開始耍白痴</s>，忘記剛創立時 q->value 是 NULL ，不能 copy 。
加了空間宣告。
:::warning
避免帶有個人色彩的發言，改進你的漢語表達。
:notes: jserv
:::
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
q->value = malloc(sizeof(s));
strcpy(q->value, s);
list_add(&q->list, head);
return true;
}
```
#### version 3
評分時發現11 12怎麼過不了明明已經做完了 insert 了，後來發現是動態宣告 value 的時候沒有檢查是否有足夠空間。
養成良好 coding 習慣，要檢查任何：
1. 傳入值是否有意義
2. 動態宣告是否有成功
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head || !s){
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
q->value = malloc(sizeof(s));
if (!(q->value)) {
free(q);
return false;
}
strcpy(q->value, s);
list_add(&q->list, head);
return true;
}
```
#### version 4
之前的方式是切跟 char s 一樣的 size ，但其實只要切跟字串一樣剛剛好大小就好了。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head){
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
int s_len = strlen(s);
q->value = malloc(s_len+1);
if (!(q->value)) {
test_free(q);
return false;
}
strncpy(q->value, s, s_len);
q->value[s_len] = '\0';
list_add(&q->list, head);
return true;
}
```
### q_insert_tail
#### version 1
這是跟 insert head 一起做的，前者成功， insert tail <s>照本宣科</s>。
:::warning
查閱教育部辭典「[照本宣科](https://dict.revised.moe.edu.tw/dictView.jsp?ID=115527)」的寓意，再回來看這裡程式碼的撰寫，看用語是否恰當。
:notes: jserv
:::
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if(!head){
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
int s_len = strlen(s);
q->value = malloc(s_len+1);
if (!(q->value)) {
test_free(q);
return false;
}
strncpy(q->value, s, s_len);
q->value[s_len] = '\0';
list_add_tail(&q->list, head);
return true;
}
}
```
:::warning
思考如何精簡程式碼。
:notes: jserv
:::
### q_remove_head
#### version 1
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || !sp){
return NULL;
}
element_t * cur_r = list_entry(head->next, element_t, list);
list_del_init(head->next);
strncpy(sp, cur_r->value, bufsize);
return cur_r;
}
```
#### version 2
加了 sp[bufsize-1] = '\0'; ，其實不影響成績，但是這是考慮若 value size > bufsize 時在最底端會沒有 '\0' 結束符號，所以加了這行。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || !sp){
return NULL;
}
element_t* cur_r = list_entry(head->next, element_t, list);
list_del_init(head->next);
strncpy(sp, cur_r->value, bufsize);
sp[bufsize-1] = '\0';
return cur_r;
}
```
#### version 3
參考之前範例，在 empty 下不會把 head 刪掉。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || !sp || list_empty(head)){
return NULL;
}
element_t* cur_r = list_entry(head->next, element_t, list);
list_del_init(head->next);
strncpy(sp, cur_r->value, bufsize);
sp[bufsize-1] = '\0';
return cur_r;
}
```
#### version 4
參考 [chun61205](https://hackmd.io/@roger61205/lab0-2023) ，原作法對 sp 的處理有問題，若 sp 傳 NULL 只代表 test 不需要用到 sp 來做一些輸出，還是要 remove node ，原作法是將 sp == NULL 視為無效。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head)){
return NULL;
}
element_t* cur_r = list_entry(head->next, element_t, list);
list_del_init(head->next);
if(sp){
strncpy(sp, cur_r->value, bufsize-1);
sp[bufsize-1] = '\0';
}
return cur_r;
}
```
### q_remove_tail
#### version 1
同上，<s>照本宣科</s>
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head)){
return NULL;
}
element_t* cur_r = list_entry(head->prev, element_t, list);
list_del_init(head->prev);
if(sp){
strncpy(sp, cur_r->value, bufsize-1);
sp[bufsize-1] = '\0';
}
return cur_r;
}
```
### q_delete_mid
#### version 1
最後 error，time limit exceeded。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if(!head || list_empty(head)){
return false;
}
struct list_head* slow = head->next;
struct list_head* fast = head->next;
while(fast != head || fast != head->prev){
slow = slow->next;
fast = fast->next->next;
}
//del slow
list_del_init(slow);
q_free(slow);
return true;
}
```
#### version 2
while 條件打錯了，應該是&&不是||
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if(!head || list_empty(head)){
return false;
}
struct list_head* slow = head->next;
struct list_head* fast = head->next;
while(fast != head && fast != head->prev){
slow = slow->next;
fast = fast->next->next;
}
//del slow
list_del_init(slow);
q_free(slow);
return true;
}
```
### q_size
#### version 1
這很簡單，原本想試看看可不可以類似 container_of 的作法直接去找 queue_context_t 的 size ，但以失敗告終。
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if(!head){
return 0;
}
int len = 0;
struct list_head *node;
list_for_each(node, head)
len++;
return len;
}
```
### q_free
#### version 1
```c
void q_free(struct list_head *l) {
struct list_head *node;
struct list_head *safe;
element_t* cur_f;
list_for_each_safe(node, safe, l){
cur_f = list_entry(node, element_t, list);
free(cur_f);
}
INIT_LIST_HEAD(l);
}
```
#### version 2
加了防呆，目前認為以前有些人的 queue free 做的有問題。
在 qtest 內 head 是放在 queue_context_t 裡面，而 qtest 再 q_free 後也會把 queue_context_t 給 free 掉，所以 qfree 應該是不需要處理 head 的。
:::warning
改進漢語表達。
:notes: jserv
:::
```c
void q_free(struct list_head *l)
{
if(!l){
return;
}
struct list_head *node;
struct list_head *safe;
element_t* cur_f;
list_for_each_safe(node, safe, l){
cur_f = list_entry(node, element_t, list);
free(cur_f);
}
}
```
#### version 3
用 q_release_element 會比較快，而且舊方法沒有刪掉 value 值。
```c
void q_free(struct list_head *l)
{
if(!l){
return;
}
struct list_head *node;
struct list_head *safe;
element_t* cur_f;
list_for_each_safe(node, safe, l){
cur_f = list_entry(node, element_t, list);
q_release_element(cur_f);
}
}
```
#### version 4
清掉 head 。
```c
void q_free(struct list_head *l)
{
if(!l){
return;
}
struct list_head *node;
struct list_head *safe;
element_t* cur_f;
list_for_each_safe(node, safe, l){
cur_f = list_entry(node, element_t, list);
q_release_element(cur_f);
}
//cur_f = list_entry(l, element_t, list);
test_free(l);
}
```
### q_reverse
#### version 1
用 for_each_safe 不用擔心更改以後 next 會不照原本方向，所以就是把每個點都 prev next 交換。
```c
void q_reverse(struct list_head *head)
{
struct list_head *node;
struct list_head *safe;
struct list_head *tmp;
list_for_each_safe(node, safe, head){
tmp = node->prev;
node->prev = node->next;
node->next = tmp;
}
}
```
#### version 2
原方法沒有處理到 head。
```c
void q_reverse(struct list_head *head)
{
if(!head){
return;
}
struct list_head *node;
struct list_head *safe;
struct list_head *tmp;
list_for_each_safe(node, safe, head){
tmp = node->prev;
node->prev = node->next;
node->next = tmp;
}
tmp = head->prev;
head->prev = head->next;
head->next = tmp;
}
```
### q_sort
#### version 1
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 對原本雙向的 list 為了配合上課所學單向 merge sort 所作的修改，以及[上課講義](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)對 sort list 的講解，在加上自己的一些<s>優化</s> 改進。
```c
struct list_head* merge_two_queue(struct list_head *L1, struct list_head *L2)
{
struct list_head* head, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (strcmp(list_entry(L1, element_t, list)->value, list_entry(L2, element_t, list)->value) >= 0) ? &L2: &L1;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *)(void *)((uintptr_t)(void *) L1 | (uintptr_t)(void *) L2);
return head;
}
static struct list_head *merge_sort(struct list_head *head)
{
if(!head || !head->next){
return head;
}
struct list_head *slow = head, *fast = head->next;
for (; fast && fast->next; fast = fast->next->next, slow = slow->next)
;
fast = slow->next;
slow->next = NULL;
return merge_two_queue(merge_sort(head), merge_sort(fast));
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if(!head || list_empty(head)){
return;
}
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head* tmp;
for(tmp=head; tmp->next; tmp=tmp->next){
tmp->next->prev = tmp;
}
tmp->next = head;
head->prev = tmp;
}
```
### q_merge
#### version 1
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 對 queue context 資料結構的理解，以及[上課講義](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)對 merge k sorted list 的講解，改進原本 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C)改為每看一個 queue 就 merge sort 一次，並非先全部<s>串街</s> ??? 再 merge sort。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *f_q = list_entry(head->next, queue_contex_t, chain);
if (list_is_singular(head))
return f_q->size;
queue_contex_t *cur_q;
list_for_each_entry(cur_q, head, chain) {
if (cur_q != f_q) {
q_merge_two_sorted(f_q->q, cur_q->q);
f_q->size += cur_q->size;
cur_q->size = 0;
}
}
return f_q->size;
}
````
:::danger
程式碼的縮排和風格，務必依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 規範。
:notes: jserv
:::
#### version 2
前一版沒有考慮使用 merge_two_queue 時 queue 必須先做前後處理。
```diff
@@ -7,12 +7,21 @@ int q_merge(struct list_head *head)
if (list_is_singular(head))
return f_q->size;
queue_contex_t *cur_q;
+ f_q->q->prev->next = NULL;
list_for_each_entry(cur_q, head, chain) {
if (cur_q != f_q) {
- q_merge_two_sorted(f_q->q, cur_q->q);
+ cur_q->q->prev->next = NULL;
+ f_q->q->next = merge_two_queue(f_q->q->next, cur_q->q->next);
+ INIT_LIST_HEAD(cur_q->q);
f_q->size += cur_q->size;
cur_q->size = 0;
}
}
+ struct list_head* tmp;
+ for(tmp=f_q->q; tmp->next; tmp=tmp->next){
+ tmp->next->prev = tmp;
+ }
+ tmp->next = f_q->q;
+ f_q->q->prev = tmp;
return f_q->size;
}
```
:::info
提示: 使用 `diff -up` 命令可產生二個檔案間的變更處列表
:notes: jserv
:::
### q_reverseK
#### version 1
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if(!head || list_empty(head)){
return;
}
struct list_head *node, *safe, *tmp_head, *tmp;
int cur_k = 1;
list_for_each_safe(node, safe, head){
if(k==1){
for (int i = 1; i < k; i++) {
tmp = node->next;
if(tmp == head){
return;
}
}
tmp_head = node;
}
else{
if(cur_k == k){
cur_k=0;
}
else{
cur_k++;
}
list_move(node, tmp_head);
}
}
```
#### version 2
cur_k 條件判斷有誤，然後 move 邏輯修正。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if(!head || list_empty(head)){
return;
}
struct list_head *node, *safe, *tmp_head = head->next, *tmp;
int cur_k = 1;
list_for_each_safe(node, safe, head){
if(cur_k==1){
tmp = node;
for (int i = 1; i < k; i++) {
tmp = tmp->next;
if(tmp == head){
return;
}
}
tmp_head = node;
}
else{
list_move_tail(node, tmp_head);
tmp_head = node;
}
if(cur_k == k){
cur_k=1;
}
else{
cur_k++;
}
}
}
```
### q_delete_dup
#### version 1
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if(!head){
return false;
}
struct list_head *node;
bool last_del = 0;
list_for_each(node, head){
if(strcmp(list_entry(node, element_t, list)->value, list_entry(node->next, element_t, list)->value)){
if(last_del){
last_del = 0;
node = node->prev;
list_del(node->next);
q_release_element(list_entry(node->next, element_t, list));
}
}
else{//same
list_del(node->next);
q_release_element(list_entry(node->next, element_t, list));
node = node->prev;
last_del = 1;
}
}
return true;
}
```
#### version 2
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if(!head){
return false;
}
struct list_head *cur = head;
while(cur->next != head && cur->next->next != head){
element_t *c = list_entry(cur->next, element_t, list),
*n = list_entry(cur->next->next, element_t, list);
if(!strcmp(c->value, n->value)){
while(cur->next->next != head && !strcmp(c->value, n->value)){
struct list_head *next = n->list.next;
list_del(cur->next->next);
q_release_element(n);
n = list_entry(next, element_t, list);
}
list_del(cur->next);
q_release_element(c);
}
cur = cur->next;
}
return true;
}
```
Sign in with Wallet
Connect another wallet