HackMD
2025q1 Homework1 (lab0)
contributed by < TING0419 >
開發環境
$ uname -a
Linux ting-ASUS-TUF-Gaming-A15-FA506IU-FA506IU 6.8.0-52-generic #53~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Wed Jan 15 19:18:46 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.9) 2.35
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800H with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5789.20
開發指定的佇列操作
q_new
原版本：
使用記憶體分配來創建一個新的雙向鏈結的head。
該函數分配記憶體並初始化鏈表，將 head->next 和 head->prev 設置為指向自身。
如果記憶體分配失敗，返回 NULL 以防止空指標存取。
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
head->next = head;
head->prev = head;
return head;
}
改進：
使用 list.h中提供的API改寫，使程式更為簡潔。
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
q_free
在佇列的實現中，鏈結串列是通過在 element_t 中定義的 list_head 結構來連接的。因此，可以使用在 list.h中定義的 list_for_each_entry_safe 遍歷佇列中的所有 element_t，並獲取每個 element_t 的位址以釋放其記憶體。此外，由於 element_t 中的字串所指向的記憶體區塊也需要釋放，最後，還需要釋放 head 的 list_head 所指向的記憶體區塊。
void q_free(struct list_head *head)
{
if (!head)
return;
if (list_empty(head)) {
free(head);
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
element_t *current = list_entry(node, element_t, list);
q_release_element(current);
}
free(head);
}
q_insert_head
原版本：
使用 list_add 實現 q_insert_head()，將新節點插入佇列的 head 。確保當 element_t 的值指向字串時，使用 strdup() 來分配並複製字串，以避免在測試過程中發生錯誤。
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node) {
return false;
}
new_node->value = strdup(s);
list_add(&new_node->list, head);
return true;
}
改進：
這段改進優化了記憶體管理和錯誤處理。首先，新增了對 head 和 s 是否為空指標的檢查，防止空指標錯誤。接著，將字串的記憶體分配方式改為手動分配並使用 strncpy 進行字串複製，以避免緩衝區溢出。最後，對記憶體分配失敗的情況做了處理，確保在失敗時釋放已分配的記憶體，防止記憶體洩漏。
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
int s_len = strlen(s);
element->value = (char *) malloc((s_len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, (s_len + 1));
list_add(&element->list, head);
return true;
}
q_insert_tail
原版本：
實現 q_insert_tail 函數，將元素插入佇列的尾部。
為新節點分配記憶體並使用 strdup 函數複製字串。
使用 list.h 的API list_add_tail() 將新節點插入佇列的末尾。
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node) {
return false;
}
list_add_tail(&new_node->list, head);
new_node->value = strdup(s);
return true;
}
改進：
通過利用雙向鏈結串列的特性使用 q_insert_head。將新節點插入到 head->prev 位置，等同於將節點添加至尾部。
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s) {
return false;
}
return q_insert_head(head->prev, s);
}
q_remove_head
q_remove_tail
q_size
使用 list.h 中的 list_for_each 來計算佇列的長度。
如果佇列為空，返回 0；否則，返回元素的數量。
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
q_delete_mid
q_delete_dup
q_swap
q_reverse
q_reverseK
q_sort
q_ascend
q_descend
q_merge
make test
原版本：
改進：
