# 2020q3 Homework1 (quiz1)
###### tags: `sysprog2020`
* [add entry](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#add-entry)
* [AA1](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#AA1)
* [AA2](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#AA2)
* [swap pair](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#swap_pair)
* [BB1](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#BB1)
* [BB2](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#BB2)
# node structure
```c
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
```graphviz
digraph {
label="node_t";
node[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">value</td>
<td port="next" border="1" bgcolor='#AAAAAA'>next</td>
</tr>
</table>
>];
node1, node2
node1:next->node2:value
{rank=same; node1 node2}
}
```
# add entry
### Target : Append a new element to list
```c
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
### analysis
Create a new element
```graphviz
digraph B {
node[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">value</td>
<td port="next" border="1" bgcolor='#AAAAAA'>next</td>
</tr>
</table>
>];
n_0,n_1,n_2,n_new
n_0:next->n_1:value
n_1:next->n_2:value
{rank=same; n_0 n_1, n_2, n_new}
}
```
find last element
```graphviz
digraph B {
node[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">value</td>
<td port="next" border="1" bgcolor='#AAAAAA'>next</td>
</tr>
</table>
>];
n_0,n_1,n_2,n_new
n_0:next->n_1:value
n_1:next->n_2:value
n_headpp[fontsize=12,shape=rect,label="indirect (node_t**)"]
n_headp[fontsize=12,shape=rect,label="*indirect (node_t*)"]
n_headpp->n_headp
n_headp->n_0:value[label="start"]
n_headp->n_0:next[label="after loop 0"]
n_headp->n_1:next[label="after loop 1"]
n_headp->n_2:next[label="after loop 2, *indirect==null"]
{rank=same; n_0 n_1, n_2, n_new}
}
```
### AA1
AA1 is not easy, I found answer by looking options
```c
assert(new_node); // check memory is allocated
```
### AA2
Since original code has create a new node and loop through list to find last node, AA2 should be insert the new node.
```c
*indirect = new_node;
```
# swap_pair
### Target : swap every two node
```c
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
### breakdown
```c
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; // initialize
*node && (*node)->next; // check there are two nodes to swap
BB1) { // next
```
#### before:
```graphviz
digraph{
n_first[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">first</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*second</td>
</tr>
</table>
>]
n_second[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">second</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*third</td>
</tr>
</table>
>]
n_third[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">third</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*next</td>
</tr>
</table>
>]
n_node[shape=rect,fontsize=12,label="*node"];
n_node->n_first:value;
n_first:next->n_second:value;
n_second:next->n_third:value;
{rank=same;n_node n_first n_second, n_third}
}
```
```c
node_t *tmp = *node; // cache the first node
BB2;
tmp->next = (*node)->next;/* ∵ the next of fisrt node shouble be
* the next of seconde node
* ∴ (*node) is a pointer to seconde node
*/
(*node)->next = tmp; // assign pointer to first node to second.next
```
#### after:
```graphviz
digraph{
n_first[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">first</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*third</td>
</tr>
</table>
>]
n_second[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">second</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*first</td>
</tr>
</table>
>]
n_third[shape=none label=<
<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">third</td>
<td port="next" border="1" bgcolor='#AAAAAA'>*next</td>
</tr>
</table>
>]
n_first:next->n_third:value;
n_second:next->n_first:value;
n_node[shape=rect,fontsize=12,label="*node"];
n_node->n_second:value;
{rank=same;n_node n_first n_second, n_third}
}
```
### BB2
The missing part should be changing \*node (node_t\*) from 'pointer to first node' to 'pointer to second node'
```c
*node=(*node)->next
```
### BB1
And it need to go through next pair, which is set \*node (node_t\*) to 'pointer to third node', and \*node is a 'pointer to second node' after above operation.
```c
node=&(*node)->next->next
```
```c
}
return head;
}
```
### without return
simply change type of head from node_t* to node_t**
```c
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;
}
}
```
### test
<iframe width="800px" height="800px" src="https://godbolt.org/e#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAM1QDsCBlZAQwBtMQBGAFlICsupVs1qhkAUgBMAISnTSAZ0ztkBPHUqZa6AMKpWAVwC2tLgHZSW9ABk8tTADljAI0zEQ3ABykADqgWE6rR6hibmvv6BdLb2Tkau7l6KypiqQQwEzMQEIcamnBZKKmp0GVkEMY4ubh7eCpnZuWEFig0VdlXxNV4AlIqoBsTIHADkUgDMdsiGWADU4uM69fioAHQIC9jiAAwAgju7BACePphYVLP1xAaqswD6d7QYmPNmsnuzn7N2BLMAbmwDJgFu9dl9LgRrrcHk85gAqewADwIIIO4jMABFZrDMHcUeNQQccXjZnCFAB3Zg%2BO4%2BZh4YgQYm/OEITDMdA9NFvA7gmjEWaM54kuEI57zcZYqQANlZ7JBpJx80kUulAtFWB6AFpNkj8dJsc8FhjpRB1ZgtTrMMjteNsLqeq9QeDwUzSQQjD5xVizaiPs7PmavWqcRbbbrfWD/bN3T4bXarb8jcHnqH48iI1Hkxq47qgzGM190ca/Z9iJgCINaLNZegI0W0XsDn9UHh0JdKdTafTJIKsMKWWyOVynV8%2BQLXSLFUma/LA9LVaaQzmE/KcUaTWbU7rl8iHeiR/6JzGgz6CTyo3OJVnzTu9ef/THb0HFynbwX/S/s5bkXmPe/XsW%2ByYk2LZtj4xA/Kw9S9riBBwsQnLciWszkggeDsBACH7vezrgT8VAQFIkhSAArD44gkbIkgkegpCkeRJHGiROi0ERpBkMQcYAoYmDsbenJnsh4LEEanHfneyH1o2wF7D8sxGHStAQIhB4Gn2vy0CR%2B6cJI4wkaQ2IGKwrA%2BJC9aCZGnyurQ3DabpvBKlKmnmap1njHZ4zjAZ0o2S5OHWcRbw6eMkjecqtDucBFkukKGmcB5nBhU5gXGtFXzWdsHnbEltDxVFhLIRO/JJhSVI0nSDI%2BdsAmqXh9BQQQmE1Q2lmzMVV6lZ2FVNXWyGdeV3aEcqWFpZ8dUEA1PUWUWIx9KwIAjCRIykKYIzbMtqALTochyJcAxDC8EycMtBALetPR9AA1iAJHZfNIzcMtq3raQm0jMtCggNlp1rbNpBwLAMCICgqAeuhbjkJQaBg%2Bw7jAJw2yhVQ6EEG4n0QM4Z3Lc4dhZEcC3HaQ0NGFoBAAPK0Kw%2BO/aQWAKaI7BY7T9KpGofyYJ9NNWqkBio0zPzKEzrB4M4xB43oWAEydEFGFLfQ0PQTBsBwPD8IIwiiCgO0yEIIufZAfSoKZQSc5qZPjB9KRpBoEBWE0%2BSWNolRxAkgh%2BAEJTBPoeRu5EnvO9U7iJUUrPpG09uCCH1u0GU2QB10QetOUEfB208eu5wfQKPtwxcHNC1LStTNvYinhSpqUrcLMwDIMgswI6skgCrghAkEq4yJbMegw247eZ132vSCdWMXaQ123UIC2PaQstSuMqxmB3BTbJ5Uor2Y2zeM9G0LR9X2kD953/UDEBIAMBA%2BLzkMQNDPjg4nZyt4nCuMCwjOq%2BSYs%2BHLk%2BLU9xcLSOihQgCBZil3LpXautd67bEbsPX6o8aw1GUr/aestxhSkblKTwnhJAAE4pRzwIfg0K29Xq70UPvQ%2Bs0ro3TugtC2RcaZvXgedfOIxJD/2YRQ6ho92bEACBobgQA%3D"></iframe>
# reverse
### Target : reverse link all node
```c
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next; // cache next
CCC; // link head to cursor and re assign cursor
head = next; // process next
}
return cursor;
}
```
### CCC
```c
head->next = cursor;
cursor = head;
```
### without return
```c
void reverse(node_t **headp)
{
node_t **cursor = headp;
node_t *head = *headp;
*cursor=NULL;
while (head) {
node_t *next = head->next; // cache next
head->next = *cursor;
*cursor = head;
head = next; // process next
}
}
```
# Fisher–Yates shuffle
The algorithm it self is not hard,
but it turns out pretty tricky to do with linked list.
```c
void FisherYatesShuffle(node_t **head)
{
int n = 0;
for (node_t *c = *head; c; ++n, c = c->next)
;
for (int i = n; i > 1; --i, head = &(*head)->next) {
node_t **target = head;
for (int s = rand() % i; s; --s, target = &(*target)->next)
;
swapNodes(head, target);
}
}
```
The swap node is much more complex than I thought, it take about 2 hours to do this, it is easier to think step by step in paper.
```c
void swapNodes(node_t **head, node_t **target)
{
if (head == target)
return;
```
swap pointer to node(next pointer of previous node)
```c
node_t *k = *head;
*head = *target;
*target = k;
```
swap next pointer of node
```c
k = (*target)->next;
(*target)->next = (*head)->next;
(*head)->next = k;
}
```
Sign in with Wallet
Connect another wallet