# 2021q1 Homework1 (quiz1)
contributed by < `gyes00205` >
###### tags: `linux2021`
>[作業要求](https://hackmd.io/@sysprog/SJlXFVMzMu)
## 程式碼原理
考慮一個單向 linked list，其結構定義為:
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### list_add_node_t
將新的節點插在串列的最前面
```cpp
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
I. `node_t->next = *list;`
```graphviz
digraph linkedlist {
node [shape=box];
list [label="*list",shape=plaintext, fontcolor=red];
rankdir=LR
{
rankdir=LR
a [label="node_t"];
b [label="0"];
c [label="1"];
d [label="NULL"];
}
{
rank="same";
list [label="*list",shape=plaintext, fontcolor=red];
list->b
}
a->b->c->d
}
```
II. `*list = node_t;`
```graphviz
digraph linkedlist {
node [shape=box];
list [label="*list",shape=plaintext, fontcolor=red];
rankdir=LR
{
rankdir=LR
a [label="node_t"];
b [label="0"];
c [label="1"];
d [label="NULL"];
}
{
rank="same";
list [label="*list",shape=plaintext, fontcolor=red];
list->a
}
a->b->c->d
}
```
### list_concat
將兩個 list 連接起來。
```cpp
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next)
*left = right;
}
```
I. 用 while 迴圈讓 left 指向 left 的尾端
```cpp
while (*left)
left = &((*left)->next)
```
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
rankdir=LR
{
rankdir=LR
a [label="L1"];
b [label="L2"];
c [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
left->a
}
a->b->c
}
```
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
rankdir=LR
{
rankdir=LR
a [label="L1"];
b [label="L2"];
c [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
left->c
}
a->b->c
}
```
II. 將指到的 NULL 節點替換成 right 節點
`*left = right;`
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="L1"];
b [label="L2"];
c [label="NULL"];
d [label="R1"];
e [label="R2"];
f [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
left->c
right->d
}
a->b->c
d->e->f
}
```
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="L1"];
b [label="L2"];
d [label="R1"];
e [label="R2"];
f [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
left->right
right->d
}
a->b->d->e->f
}
```
### quicksort
將 list 分成兩個部分, 比 pivot 小的在 left, 比 pivot 大的在 right
```cpp
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right)
*list = result;
}
```
I. 挑選 list 第一個節點當作 pivot
`node_t *pivot = *list;`
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
l1 [label="NULL"];
r1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->l1
right->r1
pivot->a
}
a->b->d->e->f->g
}
```
II.將 pivot 從 list 中拿出， p 指向剩下的 list
```cpp
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
```
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
l1 [label="NULL"];
r1 [label="NULL"];
n1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
p [label="p",shape=plaintext, fontcolor=orange];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->l1
right->r1
p->b
pivot->a
}
a->n1
b->d->e->f->g
}
```
III. 從 p 拿出節點與 pivot 比較，比 pivot 小的在 left，比 pivot 大的在 right
```cpp
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
n2 [label="NULL"];
n3 [label="NULL"];
n1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
p [label="p",shape=plaintext, fontcolor=orange];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->b
right->n3
p->d
pivot->a
}
a->n1
b->n2
d->e->f->g
}
```
IIII. 繼續比較 pivot 和 p 節點的大小
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
n2 [label="NULL"];
n3 [label="NULL"];
n1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
p [label="p",shape=plaintext, fontcolor=orange];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->b
right->d
p->e
pivot->a
}
a->n1
b->n2
d->n3
e->f->g
}
```
V. 繼續比較 pivot 和 p 節點的大小
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
n2 [label="NULL"];
n3 [label="NULL"];
n1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
p [label="p",shape=plaintext, fontcolor=orange];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->b
right->e
p->f
pivot->a
}
a->n1
b->n2
e->d->n3
f->g
}
```
VI. 繼續比較 pivot 和 p 節點的大小
```graphviz
digraph linkedlist {
node [shape=box];
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
n2 [label="NULL"];
n3 [label="NULL"];
n1 [label="NULL"];
}
{
rank="same";
left [label="left",shape=plaintext, fontcolor=red];
right [label="right",shape=plaintext, fontcolor=blue];
p [label="p",shape=plaintext, fontcolor=orange];
pivot [label="pivot",shape=plaintext, fontcolor=purple];
left->b
right->f
p->g
pivot->a
}
a->n1
b->n2
f->e->d->n3
g
}
```
VII. 假設做完所有遞迴後
```cpp
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right)
```
* 結果
```graphviz
digraph linkedlist {
node [shape=box];
result [label="result",shape=plaintext, fontcolor=red];
rankdir=LR
{
rankdir=LR
a [label="2"];
b [label="1"];
d [label="3"];
e [label="4"];
f [label="5"];
g [label="NULL"];
}
{
rank="same";
result [label="result",shape=plaintext, fontcolor=red];
result->b
}
b->a->d->e->f->g
}
```
### list_make_node
第 4 ～ 9 行先判斷 list 是否為 NULL，只有在第一次才會有 NULL 的情況。
```cpp=
node_t *list_make_node_t(node_t *list, int value) {
node_t *head = list;
node_t *tmp;
if (!list) {
list = (node_t*)malloc(sizeof(node_t));
list->next = NULL;
list->value = value;
return list;
}
while (list->next)
list = list->next;
tmp = (node_t*)malloc(sizeof(node_t));
tmp->next = NULL;
tmp->value = value;
list->next = tmp;
return head;
}
```
* while 迴圈將 list 指到串列最末端
```graphviz
digraph linkedlist {
node [shape=box];
list [label="list",shape=plaintext, fontcolor=red];
head [label="head",shape=plaintext, fontcolor=blue];
NULL [label="NULL",shape=plaintext];
rankdir=LR
{
rank="same";
head->list->1
}
1->2->NULL
}
```
```graphviz
digraph linkedlist {
node [shape=box];
list [label="list",shape=plaintext, fontcolor=red];
head [label="head",shape=plaintext, fontcolor=blue];
NULL [label="NULL",shape=plaintext];
rankdir=LR
{
rank="same";
list->2
}
{
rank="same"
head->1
}
1->2->NULL
}
```
* `list->next` 接到 `tmp`
```graphviz
digraph linkedlist {
node [shape=box];
list [label="list",shape=plaintext, fontcolor=red];
head [label="head",shape=plaintext, fontcolor=blue];
tmp [label="tmp",shape=plaintext, fontcolor=blue];
NULL [label="NULL",shape=plaintext];
rankdir=LR
{
rank="same";
list->b
}
{
rank="same"
tmp->c
}
{
rank="same"
head->a
}
a->b->c->NULL
}
```
### list_free
在寫 list_free 時有遇到以下問題
* 錯誤版： 一開始寫的方式如下
```cpp
static void list_free(node_t **list) {
while (*list) {
node_t *tmp = *list;
printf("*list %p\n", *list);
list = &((*list)->next);
printf("(*list)->next %p\n", *list);
printf("free tmp %p\n", tmp);
free(tmp);
printf("(*list)->next %p\n", *list);
printf("-----------------------------\n");
}
}
```
:::warning
錯誤訊息：
free(): double free detected in tcache 2
Aborted (core dumped)
:::
> 後來試著將 *list 與 (*list)->next 印出， 發現釋放完 tmp 的記憶體後， (*list)->next 的記憶體竟然與釋放前不同。
*list 0x561b16144360
(*list)->next 0x561b16144320
free tmp 0x561b16144360
(*list)->next 0x561b16144010
---------------------------------------->
*list 0x561b16144010
(*list)->next (nil)
free tmp 0x561b16144010
(*list)->next 0x561b16144010
---------------------------------------->
*list 0x561b16144010
(*list)->next 0x561b16144010
free tmp 0x561b16144010
* 正確版
```cpp
static void list_free(node_t **list) {
while (*list) {
node_t *tmp = *list;
*list = (*list)->next;
free(tmp);
}
}
```
## random 輸出結果相仿?
參考 [random](https://linux.die.net/man/3/random) 得知可以設定 `void srandom(unsigned int seed)` 讓 random 的結果不同, 如果沒有設定 seed value, random 會預設 seed value 為 1。其中 `time(NULL)` 透過 time 函式來獲得系統時間, 它的返回值為從 00:00:00 GMT, January 1, 1970 到現在所持續的秒數。
```cpp
int main(int argc, char **argv) {
size_t count = 20;
node_t *list = NULL;
srandom(time(NULL));
while (count--)
list = list_make_node_t(list, random() % 1024);
list_display(list);
quicksort(&list);
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
## iterative 版本
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 和 [hankluo6](https://hackmd.io/@hankluo6/2021q1quiz1#Optimized-QuickSort)
，參考連結的資料結構為陣列，我們的資料結構為 linked list ，所以我新增兩個 function 。
### find_value
找到 list 中第 index+1 個節點的 value
```cpp
int find_value(node_t *list, int index) {
while (index--)
list = list->next;
return list->value;
}
```
### assign_value
更改 list 中第 index+1 個節點的 value
```cpp
void assign_value(node_t *list, int index, int value) {
while (index--)
list = list->next;
list->value = value;
}
```
### quicksort_iterative
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並將資料結構改為 linked list。
```cpp
bool quicksort_iterative(node_t **list, int elements) {
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
beg[0]=0; end[0]=elements;
while (i >= 0) {
L=beg[i]; R=end[i]-1;
if (L < R) {
piv = find_value(*list, L);
if (i == MAX_LEVELS-1)
return false;
while (L < R) {
while (find_value(*list, R) >= piv && L < R)
R--;
if (L < R)
assign_value(*list, L++, find_value(*list, R));
while (find_value(*list, L) <= piv && L < R)
L++;
if (L < R)
assign_value(*list, R--, find_value(*list, L));
}
assign_value(*list, L, piv); beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;
}
else
i--;
}
return true;
}
```
### main
新增變數 `success` 判斷 quick sort 是否成功
```cpp
int main(int argc, char **argv) {
size_t count = 20;
bool success;
node_t *list = NULL;
srandom(time(NULL));
for (int i = 0; i < count; i++)
list = list_make_node_t(list, random() % 1024);
list_display(list);
success = quicksort_iterative(&list, count);
if(!success)
return EXIT_FAILURE;
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
Sign in with Wallet
Connect another wallet