owned this note
owned this note
Published
Linked with GitHub
# 2022q1 Homework1 (lab0)
contributed by < `cyrong` >
## 修改 `queue.[ch]`
### `q_new`
使用 `list.h` 中的 `INIT_LIST_HEAD` 來實作 head 初始化
```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_free`
原先 `list_for_each_entry_safe` 的部份是使用 `list_for_each_entry`
但是會發生 segmentation fault
詳細閱讀程式碼後在註解中有看到
```c
/*
* The nodes and the head of the list must be kept unmodified while
* iterating through it. Any modifications to the the list will cause undefined
* behavior.
*/
```
在 `q_release_element` 的使用後會修改到 `node`
因此應該改用 `list_for_each_entry_safe`
```c=
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *tmp, *safe;
list_for_each_entry_safe (tmp, safe, l, list)
q_release_element(tmp);
free(l);
}
```
### `q_insert_head`
在 `queue` 的 `insert` 以及 `remove` 操作中，有了 `list.h` 中的一些函式可以使得這兩個指令操作變得方便起來
```c=
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
if (!s)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
INIT_LIST_HEAD(&ele->list);
int slen = strlen(s) + 1;
ele->value = malloc(slen);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, slen);
list_add(&ele->list, head);
return true;
}
```
### `q_insert_tail`
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
if (!s)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
INIT_LIST_HEAD(&ele->list);
int slen = strlen(s) + 1;
ele->value = malloc(slen);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, slen);
list_add_tail(&ele->list, head);
return true;
}
```
### `q_remove_head`
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
list_del(head->next);
if (sp && bufsize) {
int slen = strlen(ele->value);
slen = slen > bufsize - 1 ? bufsize - 1 : slen;
strncpy(sp, ele->value, slen);
sp[slen] = '\0';
}
return ele;
}
```
### `q_remove_tail`
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
list_del(head->prev);
if (sp && bufsize) {
int slen = strlen(ele->value);
slen = slen > bufsize - 1 ? bufsize - 1 : slen;
strncpy(sp, ele->value, slen);
sp[slen] = '\0';
}
return ele;
}
```
### `q_size`
```c=
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`
在一開始要找到 `queue` 的中間 `node` 時，我使用的方法是以下透過 `q_size` 的方法，在之後觀摩其他同學的作業時發現了另一種寫法，可以減低數 `node` 的次數。
```c
int mid = q_size(head) / 2;
struct list_head *tmp = head->next;
for (int i = 0; i < mid; i++)
tmp = tmp->next;
```
```c=
bool q_delete_mid(struct list_head *head)
{
struct list_head *l1, *l2;
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
l1 = head->next;
l2 = head->prev;
while (l1 != l2 && l1->next != l2) {
l1 = l1->next;
l2 = l2->prev;
}
list_del(l1);
q_release_element(list_entry(l1, element_t, list));
return true;
}
```
### `q_delete_dup`
```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 *i = head->next, *j;
for (j = i->next; j != head; j = j->next) {
if (!strcmp(list_entry(i, element_t, list)->value,
list_entry(j, element_t, list)->value)) {
list_del(j);
q_release_element(list_entry(j, element_t, list));
j = i;
} else {
i = i->next;
}
}
return true;
}
```
### `q_swap`
這邊利用了 `list.h` 中的 `list_move_tail` 將第 2n 與 2n + 1 的 node 進行對調
```c=
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *tmp;
for (tmp = head->next; tmp != head && tmp->next != head; tmp = tmp->next)
list_move_tail(tmp->next, tmp);
}
```
### `q_reverse`
這裡用了與 swap 相似的作法，不斷移動第一個 node 並且將最尾端的 node 不斷移動到第一個 node 前，以達成 reverse 的目的
```c=
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *tmp;
for (tmp = head; tmp->next != head; tmp = tmp->next)
list_move(head->prev, tmp);
}
```
### `q_sort`
使用 merge sort，在合併時比較字串
```c=
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *l1, *l2;
l1 = head->next;
l2 = head->prev;
while (l1 != l2 && l1->next != l2) {
l1 = l1->next;
l2 = l2->prev;
}
LIST_HEAD(left);
LIST_HEAD(right);
list_cut_position(&left, head, l1);
list_cut_position(&right, head, head->prev);
q_sort(&left);
q_sort(&right);
while (!list_empty(&left) && !list_empty(&right)) {
struct list_head *l = left.next, *r = right.next;
if (strcmp(list_entry(l, element_t, list)->value,
list_entry(r, element_t, list)->value) <= 0) {
list_del(l);
list_add_tail(l, head);
} else {
list_del(r);
list_add_tail(r, head);
}
}
if (!list_empty(&left))
list_splice_tail(&left, head);
if (!list_empty(&right))
list_splice_tail(&right, head);
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
