contributed by < Thegoatistasty
>
注意書寫規範:中英文間用一個半形空白字元區隔。
:notes: jserv
謝謝老師,有進行修改了
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 13
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
struct list_head *q_new()
{
struct list_head *head = (struct list_head*) malloc(sizeof(*head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
void q_free(struct list_head *l) {
if(!l)
return;
element_t *save, *temp;
list_for_each_entry_safe(temp, save, l, list)
q_release_element(temp);
free(l);
}
這邊曾經遇到的問題是沒有預留 '/0'
位置給 value,導致出現
ERROR: Corruption detected in block with address 0x55a707abb980 when attempting to free it
目前還沒找到是哪裡產生這樣的訊息,不過解決方法就是在 malloc 時多加一個 byte 的空間
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = (element_t*) malloc(sizeof(element_t));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);//+1 for '/0'
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add(&new->list, head);
return true;
}
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new = (element_t*) malloc(sizeof(*new));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add_tail(&new->list, head);
return true;
}
遇到的問題類似,以q_remove_head為例
查詢教育部辭典「蠻」,改進你的漢語書寫。
:notes: jserv
收到!
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head)
return NULL;
sp = (char*) malloc(bufsize * sizeof(char*));
if(!sp)
return NULL;
element_t* first_entry = list_first_entry(head, element_t, list);
strncpy(sp, first_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return first_entry;
}
原本這麼寫,但會跑出
ERROR: Failed to store removed value
後來發現sp已經malloc過了(q_test.c裡do_remove的remove),再malloc一次會在測試時找不到原本的位置,所以將malloc刪掉就好了
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head)
return NULL;
if(!sp)
return NULL;
element_t* last_entry = list_last_entry(head, element_t, list);
strncpy(sp, last_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return last_entry;
}
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new = (element_t*) malloc(sizeof(*new));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add_tail(&new->list, head);
return true;
}
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
for(struct list_head* node = head->next; node->next != head; node = node->next){
list_del(node);
list_add(node, node->next);
}
}
利用老師上課提到的『指標一快一慢』的方法(Hare & Tortoise Algorithm)
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
// Hare & Tortoise Algorithm
struct list_head *fast, *slow;
fast = slow = head->next;
do{
fast = fast->next;
if(fast == head)
break;
slow = slow->next;
fast = fast->next;
}while(fast != head);
list_del(slow);
return true;
}
參考 npes87184's blog的作法,再以自己的方法實作
為了實作 merge sort,我加入了兩個函式:
struct list_head *merge_two_lists
: 用來合併二個鏈結串列struct list_head *merge_sort
: merge sort 的遞迴式merge_two_lists 原本是這麼做的
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
struct list_head *temp = (struct list_head *)malloc(sizeof(temp));
if(!temp)
return list1;
struct list_head *save = temp;
while(list1 && list2){
element_t *v1 = list_entry(list1, element_t, list);
element_t *v2 = list_entry(list2, element_t, list);
if(strcmp(v1->value, v2->value) >= 0){
temp->next = list1;
list1->prev = temp;
temp = list1 = list1->next;
}
else{
temp->next = list2;
list2->prev = temp;
temp = list2 = list2->next;
}
}
if(!list1){
temp->next = list2;
list2->prev = temp;
}
if(!list2){
temp->next = list1;
list1->prev = temp;
}
free(temp);
return save->next;
但當我 make test 時會顯示
FATAL ERROR: Calls to malloc disallowed
發現它不讓我使用 malloc,思來想去找不到好方法,於是尋找是否有人用類似的方法。結果找到 @seasonwang 和我參考的是同一個部落格,而且是用 indirect pointer 的方式,於是我將他的基礎上改進程式碼(減少一個 indirect pointer ),並改為
請查詢英文字典,理解 "optimize" 和 "improve" 的差異。
注意 資訊科技詞彙翻譯
:notes: jserv
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
{
struct list_head *temp = NULL;
struct list_head **indirect = &temp;
struct list_head *last = NULL;
while (list1 && list2) {
element_t *v1 = list_entry(list1, element_t, list);
element_t *v2 = list_entry(list2, element_t, list);
if (strcmp(v1->value, v2->value) <= 0) {
list1->prev = *indirect;
*indirect = list1;
list1 = list1->next;
} else {
list2->prev = *indirect;
*indirect = list2;
list2 = list2->next;
}
last = *indirect;
indirect = &((*indirect)->next);
}
if (!list1) {
last->next = list2;
list2->prev = last;
}
if (!list2) {
last->next = list1;
list1->prev = last;
}
return temp;
}
然後是遞迴的 merge sort
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast, *slow;
fast = slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->prev->next = NULL;
slow->prev = NULL;
struct list_head *list1 = merge_sort(head);
struct list_head *list2 = merge_sort(slow);
return merge_two_lists(list1, list2);
}
再來是作業的 q_sort,當時忘記重新連結頭跟尾,debug 了很久
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if(list_empty(head))
return;
// break the list circle
head->prev->next = NULL;
head->prev = NULL;
// merge sort
head->next = merge_sort(head->next);
// reconnect
head->next->prev = head;
struct list_head *t = head;
while (t->next != NULL) {
t->next->prev = t;
t = t->next;
}
head->prev = t;
t->next = head;
}
我第一眼看到這個函式時,蠻疑惑為什麼會需要 merge多個 list,因為之前操作都是只有一個 list 的情形。於是閱讀了 qtest.c
的 do_merge
和 do_new
才發現一直以來操作的其實是 current->q
。
而在 do_merge
呼叫 q_merge
時會傳入 &chain.head
,並接收 merge 完後 list 的長度。所以要存取所有的 list 的話,需要用到 queue_context_t
這個 struct。
int q_merge(struct list_head *head)
{
if(!head || list_empty(head))
return 0;
queue_contex_t *headchain = list_entry(head->next, queue_contex_t, chain);
if(list_is_singular(headchain->q))
return headchain->size;
for(struct list_head *h = head->next->next; h != head; h = h->next){
queue_contex_t *qctx = list_entry(h, queue_contex_t, chain);
headchain->size += qctx->size;
list_splice_tail_init(qctx->q, headchain->q);
}
q_sort(headchain->q);
return headchain->size;
// https://leetcode.com/problems/merge-k-sorted-lists/
}
2487. Remove Nodes From Linked List
改以 Graphviz 製圖
:notes: jserv
最直觀的解法應該是從頭開始逐一節點檢查,但是這樣時間複雜度會是
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return 1;
int len = 1;
element_t *t = list_entry(head->prev, element_t, list);
char *v = t->value;
struct list_head *h, *safe;
for(h = head->prev->prev, safe = h->prev; h != head; h = safe, safe = h->prev){
t = list_entry(h, element_t, list);
if(strcmp(v, t->value) > 0){
list_del(h);
q_release_element(list_entry(h, element_t, list));
}
else{
v = t->value;
len++;
}
}
return len;
}
二者非常類似,我都是將 traverse 到的點用 list_move
移到head後面,比較不同的是 q_reverseK 需要額外用一個 counter 計數以及 head 的位置要調整而已
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_is_singular(head))
return;
struct list_head *node, *safe, *start;
start = head;
int counter = 0;
list_for_each_safe(node, safe, head){
counter++;
if(counter == k){
struct list_head *temp, *temp_safe;
for(temp = start->next, temp_safe = temp->next; temp != safe; temp = temp_safe, temp_safe = temp->next)
list_move(temp, start);
counter = 0;
start = safe->prev;
}
}
}
目前95/100
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up