# 2020q3 Homework1 (quiz1)
contributed by < `carlhutant` >
```c=1
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
example [label="{<value> value| <next> next}"]
}
```
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
藍色為 main 中的 head
```c=8
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
```
傳入的是 main 中 head 的 address
因此 :
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> head:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
藍色為 head
紅色為 indirect
```c=11
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
```
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
new_node [label="{<value> new_value| <next>NULL }"][color=darkgreen];
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> head:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
綠色為 new_node
```c=14
AA1;
```
==(a) assert(new_node) 大概有確認 malloc 是否完成的功能==
==(b) *indirect = new_node==
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
new_node [label="{<value> new_value| <next>NULL }"][color=darkgreen];
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnew_node}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> head:value;
head:next -> 72:value[style="dashed"][color=grey];
head:next -> new_node:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
改動了 head 紀錄的 address
因此 (a) 較恰當
```c=15
while (*indirect)
indirect = &(*indirect)->next;
```
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> head:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
step1:
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nnext of 72}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> 72:next;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
step2:
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nnext of 101}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> 101:next;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
step3:
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nnext of 108}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> 108:next;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
```c=17
AA2;
```
==(a) assert(new_node) 確認 malloc 是否完成==
==(b) *indirect = new_node==
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nnext of 108}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> 108:next;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
NULL 換成 address of new_node
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nnext of 108}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next> address of new_node }"];
new_node [label="{<value> new_value| <next>NULL }"][color=darkgreen];
indirect -> 108:next;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
108:next -> new_node:value;
}
```
因此選 (b)
```c=18
}
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
```
建立 tmp 綠色
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
tmp [label="{<next> address of\nnode 72}"][color=darkgreen]
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
tmp -> 72:value
indirect -> head:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
```c=43
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
```
要完成共三項 :
1.藍色 head 指向 101
2.72 的 next 指向 108
3.101 的 next 指向 72
2. 與 3. 分別在 44 與 45 完成了 (從 tmp 可看出)
因此 BB2 要將
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
tmp [label="{<next> address of\nnode 72}"][color=darkgreen]
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
tmp -> 72:value
indirect -> head:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
轉成
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
tmp [label="{<next> address of\nnode 72}"][color=darkgreen]
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 101}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
tmp -> 72:value
indirect -> head:value;
head:next -> 101:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
==( a ) node = (*node)->next==
==( b ) node = &(*node)->next==
==( c ) *node = (*node)->next==
==( d ) *node = &(*node)->next==
==( e ) *node = &((*node)->next)==
選 ( c ) *node = (*node)->next
可知交換完後會是 :
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
tmp [label="{<next> address of\nnode 72}"][color=darkgreen]
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 101}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 108}"];
101 [label="{<value> 101| <next> address of\nnode 72}"];
108 [label="{<value> 108| <next>NULL }"];
tmp -> 72:value
indirect -> head:value;
head:next -> 101:value;
72:next -> 108:value;
101:next -> 72:value;
}
```
下一輪開始前必須轉成 :
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
indirect [label="{<next> address of\nhead}"][color=red];
head [label="{<next> address of\nnode 101}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 108}"];
101 [label="{<value> 101| <next> address of\nnode 72}"];
108 [label="{<value> 108| <next>NULL }"];
indirect -> 72:next;
head:next -> 101:value;
72:next -> 108:value;
101:next -> 72:value;
}
```
因此 BB1
==( a ) node = (*node)->next->next==
==( b ) *node = (*node)->next->next==
==( c ) *node = ((*node)->next)->next==
==( d ) *node = &((*node)->next)->next==
==( e ) node = &(*node)->next->next==
==( f ) *node = &(*node)->next->next==
選(e)
```c=47
return head;
}
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
```
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
cursor [label="{<next> NULL}"][color=darkgreen]
next [label="{<next> address of\nnode 101}"][color=red];
head [label="{<next> address of\nnode 72}"][color=blue];
72 [label="{<value> 72| <next> address of\nnode 101}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
next -> 101:value;
head:next -> 72:value;
72:next -> 101:value;
101:next -> 108:value;
}
```
藍色為 head
紅色為 next
綠色為 cursor
因為 72 的 next 必須改為 NULL 所以才發現 cursor 應該是指向每個 next 要改成的目標
而 head 為要修改的 node
最後變成 :
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
cursor [label="{<next> address of\nnode 72}"][color=darkgreen]
next [label="{<next> address of\nnode 108}"][color=red];
head [label="{<next> address of\nnode 101}"][color=blue];
72 [label="{<value> 72| <next> NULL}"];
101 [label="{<value> 101| <next> address of\nnode 108}"];
108 [label="{<value> 108| <next>NULL }"];
cursor -> 72:value;
next -> 108:value;
head:next -> 101:value;
72:next -> 101:value[color=grey][style="dashed"];
101:next -> 108:value;
}
```
==( a ) cursor = head; head->next = cursor==
==( b ) head->next = cursor; cursor = head==
==( c ) cursor = head==
==( d ) head->next = cursor==
==( e ) head->next->next = cursor; cursor->next = head==
==( f ) cursor->next = head; head->next->next = cursor==
因此選 (b)
```c=55
CCC;
head = next;
}
return cursor;
}
```
改變指標操作方式的 swap_pair 和 reverse :
```c=1
void swap_pair(node_t **head)
{
for (node_t **node = head; *node && (*node)->next; node=&(*node)->next->next) {
node_t *tmp = *node;
*node=(*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
}
void reverse(node_t **node)
{
node_t *cursor = NULL;
while (*node) {
node_t *next = (*node)->next;
(*node)->next = cursor;
cursor = *node;
*node = next;
}
*node=cursor;
}
```
以遞迴改寫的 reverse :
```c=1
void rev_recursive(node_t **node, node_t *cursor)
{
if(*node){
node_t *next = (*node)->next;
(*node)->next = cursor;
cursor = *node;
*node = next;
rev_recursive(node,cursor);
}
else{
*node = cursor;
}
}
void reverse(node_t **node)
{
node_t *cursor = NULL;
rev_recursive(node,cursor);
}
```
```c=60
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
/* swap pair.
* See https://leetcode.com/problems/swap-nodes-in-pairs/
*/
head = swap_pair(head);
print_list(head);
head = reverse(head);
print_list(head);
return 0;
}
```
實作 Fisher–Yates shuffle:
```c=1
void FYShuffle(node_t **head){
srand(time(NULL));
node_t **node=head;
int num=0;
while(*node){
num++;
node=&(*node)->next;
}
for(int i=num;i>0;i--){
int pos=rand()%i+num-i;
node=head;
for(int j=0;j<pos;j++){
node=&(*node)->next;
}
node_t *tmp=*node;
*node=(*node)->next;
tmp->next=*head;
*head=tmp;
}
}
```
Sign in with Wallet
Connect another wallet