# 2023q1 Homework1 (lab0)
contributed by < `irenesu2000` >
## 開發環境
```shell
$ 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-10710U CPU @ 1.10GHz
CPU family: 6
Model: 166
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 3199.92
```
## 開發過程
### q_new
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
使用 **INIT_LIST_HEAD()** 這個巨集來初始化頭節點
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *curr, *tmp;
list_for_each_entry_safe (curr, tmp, l, list) {
list_del(&curr->list);
q_release_element(curr);
}
free(l);
}
```
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
使用 `list_for_each_safe()` 相較於使用 `list_for_each()` 可以避免刪除節點之後將下一個節點的狀態也刪除導致無法進行下去,這邊運用temp來儲存current之下一個節點
:::danger
改進漢語表達。
:notes: jserv
:::
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newnode = malloc(sizeof(element_t));
if (!newnode)
return false;
newnode->value = strdup(s);
if (!newnode->value) {
free(newnode);
return false;
}
list_add(&newnode->list, head);
return true;
}
```
使用 `list_add()` 來實作插入至head前面
### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newnode = malloc(sizeof(element_t));
if (!newnode)
return false;
newnode->value = strdup(s);
if (!newnode->value) {
free(newnode);
return false;
}
list_add_tail(&newnode->list, head);
return true;
}
```
基本概念與前者相同,僅替換 **list_add()** 成 **list_add_tail()**
### q_size
```cpp=
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;
}
```
使用 **list_for_each()** 來訪問所有節點來計算長度
### q_remove_head
```cpp=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_first_entry(head, element_t, list);
list_del_init(&target->list);
if (sp) {
memcpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return target;
}
```
使用 **list_first_entry()** 來取得欲刪除之節點,刪除連結之後將其複製字串至sp中
### q_remove_tail
```cpp=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_last_entry(head, element_t, list);
list_del_init(&target->list);
if (sp) {
memcpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return target;
}
```
基本概念與前者相同,使用 **list_last_entry()** 來取得欲刪除之節點,刪除連結之後將其複製字串至sp中
### q_delete_mid
```cpp=
bool q_delete_mid(struct list_head *head)
{
if (!head)
return NULL;
int size = q_size(head);
int index;
if (size % 2 == 1) {
index = size / 2 + 1;
} else {
index = size / 2;
}
struct list_head *tmp = head;
for (int i = 0; i <= index; i++) {
if (i == index) {
list_del(tmp);
q_release_element(list_entry(tmp, element_t, list));
}
tmp = tmp->next;
}
return true;
}
```
先判斷節點總數為基數或偶數,再使用 **list_del()** 將節點連結斷開
### q_delete_dup
```cpp=
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return NULL;
struct list_head *node = head->next;
struct list_head *dup;
while (node->next != head) {
if (strcmp(list_entry(node, element_t, list)->value,
list_entry(node->next, element_t, list)->value) == 0) {
dup = node->next;
list_del(dup);
q_release_element(list_entry(dup, element_t, list));
} else {
node = node->next;
}
}
return true;
}
```
先判斷目前節點與其下一節點是否相同,若相同將其刪除,並移至下一點直至訪問完所有節點
### q_swap
```cpp=
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *first = head->next;
struct list_head *second = first->next;
while (first != head && second != head) {
first->prev->next = second;
second->prev = first->prev;
first->prev = second;
first->next = second->next;
second->next->prev = first;
second->next = first;
first = first->next;
second = first->next;
}
}
```
:::warning
使用 Graphviz 重新製圖。
:notes: jserv
:::
根據上圖概念來進行swap,可以看到需要進行修改的地方為圖片是單向而我們為雙向linked list,因此須考慮first節點之prev的next須指向second,除了添加節點之間prev指標,其餘概念與圖片一致
### q_reserve
```cpp=
void q_reverse(struct list_head *head)
{
if (!head)
return;
for (struct list_head *i = head; i->next != head->prev; i = i->next) {
list_move(head->prev, i);
}
}
```
不斷將其tail節點拉至head,使用 **list_move** 來實作
### q_descend
```cpp=
int q_descend(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return q_size(head);
}
char *max = list_entry(head->next, element_t, list)->value;
for (struct list_head *i = head; i->next != head->prev; i = i->next) {
if (strcmp(list_entry(i, element_t, list)->value, max) > 0) {
max = list_entry(i, element_t, list)->value;
}
}
struct list_head *check = head->prev;
struct list_head *del;
bool flag = 0;
while (check != head) {
if (check == head->prev) {
if (strcmp(list_entry(check, element_t, list)->value, max) < 0) {
check = check->prev;
} else {
del = check;
check = check->prev;
list_del(del);
}
} else {
if (strcmp(list_entry(check, element_t, list)->value, max) == 0) {
flag = 1;
check = check->prev;
}
if (strcmp(list_entry(check, element_t, list)->value,
list_entry(check->next, element_t, list)->value) < 0 ||
flag == 1) {
del = check;
check = check->prev;
list_del(del);
} else {
check = check->prev;
}
}
}
return q_size(head);
}
```
* 首先先找出數值最大之節點,接下來**由右至左**訪問每個節點,若為tail則不須判斷其右邊節點數值大小,僅須判斷是否比最大值小（正常狀況不會發生）
* 同時並設置了**flag**目的為判斷是否到達最大值之節點,因最大值節點左邊之節點皆需要被刪除,因此若通過最大值節點後**flag**值便會為**1**
* 接下來的其餘節點皆需要判斷**其右邊節點數值是否比目前節點數值大**以及**flag值**,若成立則須將此點刪除並移至其前一點,繼續檢查直至訪問完成
Sign in with Wallet
Connect another wallet