# 2020q3 Homework1 (quiz1)
contributed by < `Rsysz` >
###### tags: `sysprog`
## Outline
[TOC]
## 1. 解釋程式運作原理
由`add_entry`, `find_entry`, `remove_entry`, `swap_pair`, `reverse`, `print_list`構成
* **`add_entry`**
```cpp=
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;
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
透過`node_t **indirect`存取`head`內保存的記憶體位址，接著建立新節點`new_node`分配記憶體空間與賦值，另外由此可知`node_t **head`是多餘的，程式碼可修改為`void add_entry(node_t **indirect, int new_value)`
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
indirect [label = "{addr|indirect|<ref>}"];
entry_head [label="{addr|head|<ref>}"];
head [label = "{addr|(main)head|<ref>}"];
new_node [label = "{addr|new_node|<ref>}"];
memory [label = "{addr|value|<ref>next}"];
memory_head [label = "{addr|value|<ref>next}"];
indirect:ref -> head;
entry_head:ref -> head;
head:ref -> memory_head;
new_node:ref -> memory;
memory:ref -> NULL;
}
```
利用`assert(new_node)`確保正確分配記憶體，透過`*indirect`遍歷Link list找到末端節點
並接上新節點
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
indirect [label = "{addr|indirect|<ref>}"];
head [label = "{addr|*indirect|<ref>}"];
new_node [label = "{addr|new_node|<ref>}"];
memory [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_1|<ref>next}"];
memory_tail [label = "{addr|value_2|<ref>next}"];
memory_mid:ref -> memory_tail;
memory_tail:ref -> memory;
indirect:ref -> head;
head:ref -> memory_tail:ref;
new_node:ref -> memory;
memory:ref -> NULL;
}
```
* **`find_entry`**
```cpp=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next);
/* interate */
return current;
}
```
透過`head`遍歷Link list尋找value對應的節點
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
head [label="{addr|head|<ref>}"];
memory_head [label = "{addr|value_1|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
head:ref -> memory_mid;
memory_head:ref -> memory_mid;
memory_mid:ref -> memory_tail;
}
```
* **`remove_entry`**
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
透過`find_entry`找到對應的節點後將其放入`entry`，再使用`remove_entry`刪除指定的節點
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
indirect [label = "{addr|indirect|<ref>}"];
entry_head [label="{addr|head|<ref>}"];
head [label = "{addr|(main)head|<ref>}"];
entry [label = "{addr|entry|<ref>}"];
memory [label = "{addr|value|<ref>next}"];
memory_head [label = "{addr|value|<ref>next}"];
indirect:ref -> head;
entry_head:ref -> head;
head:ref -> memory_head;
entry:ref -> memory;
memory:ref -> NULL;
}
```
而`remove_entry`使用`*indrect`遍歷Link list找尋指定的節點並予以刪除
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
indirect [label = "{addr|indirect|<ref>}"];
head [label = "{addr|*indirect|<ref>}"];
entry [label = "{addr|entry|<ref>}"];
memory [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_1|<ref>next}"];
memory_tail [label = "{addr|value_2|<ref>next}"];
memory_mid:ref -> memory_tail;
memory_tail:ref -> memory;
indirect:ref -> head;
head:ref -> memory_mid:ref;
entry:ref -> memory_tail;
memory:ref -> NULL;
}
```
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
indirect [label = "{addr|indirect|<ref>}"];
head [label = "{addr|*indirect|<ref>}"];
memory [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_1|<ref>next}"];
memory_mid:ref -> memory;
indirect:ref -> head;
head:ref -> memory_mid:ref;
memory:ref -> NULL;
}
```
* **`swap_pair`**
```cpp=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) //BB1
{
node_t *tmp = *node;
*node = (*node)->next; //BB2
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
透過`*node`遍歷Link list 每兩個節點交換一次
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
tmp_node [label = "{addr|*node|<ref>}"];
tmp [label = "{addr|tmp|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
memory_head:ref -> memory_mid;
memory_mid:ref -> memory_tail;
tmp:ref -> memory_head;
tmp_node:ref -> memory_mid;
}
```
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
tmp_node [label = "{addr|*node|<ref>}"];
tmp [label = "{addr|tmp|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
memory_head:ref -> memory_tail;
memory_mid:ref -> memory_head;
tmp:ref -> memory_head;
tmp_node:ref -> memory_mid;
}
```
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
top_node [label = "{addr|node|<ref>}"];
tmp_node [label = "{addr|*node|<ref>}"];
tmp [label = "{addr|tmp|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
memory_head:ref -> memory_tail;
memory_mid:ref -> memory_head;
tmp:ref -> memory_head;
top_node:ref -> tmp_node;
tmp_node:ref -> memory_tail;
}
```
* **`reverse`**
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; //CCC
cursor = head;
head = next;
}
return cursor;
}
```
透過`next`保留後續Link list
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
cursor [label = "{addr|cursor|<ref>}"];
next [label = "{addr|next|<ref>}"];
head [label = "{addr|head|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
next:ref -> memory_mid;
head:ref -> memory_head;
memory_head:ref -> memory_mid;
memory_mid:ref -> memory_tail;
cursor:ref -> NULL;
}
```
透過`cursor`反轉Link list
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
cursor [label = "{addr|cursor|<ref>}"];
next [label = "{addr|next|<ref>}"];
head [label = "{addr|head|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
next:ref -> memory_mid;
head:ref -> memory_mid;
memory_head:ref -> NULL;
memory_mid:ref -> memory_tail;
cursor:ref -> memory_head;
}
```
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
cursor [label = "{addr|cursor|<ref>}"];
next [label = "{addr|next|<ref>}"];
head [label = "{addr|head|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
next:ref -> memory_tail;
head:ref -> memory_mid;
memory_head:ref -> NULL;
memory_mid:ref -> memory_head;
cursor:ref -> memory_head;
}
```
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
cursor [label = "{addr|cursor|<ref>}"];
next [label = "{addr|next|<ref>}"];
head [label = "{addr|head|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
next:ref -> memory_tail;
head:ref -> memory_tail;
memory_head:ref -> NULL;
memory_mid:ref -> memory_head;
cursor:ref -> memory_mid;
}
```
* **`print_list`**
```cpp=
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
```
透過`head`遍歷Link list印出所有`value`
```graphviz
digraph add_entry{
node [shape=record];
rankdir=LR;
head [label = "{addr|head|<ref>}"];
memory_tail [label = "{addr|value_3|<ref>next}"];
memory_mid [label = "{addr|value_2|<ref>next}"];
memory_head [label = "{addr|value_1|<ref>next}"];
head:ref -> memory_mid;
memory_head:ref -> memory_mid;
memory_mid:ref -> memory_tail;
memory_tail:ref -> NULL;
}
```
## 2. 修改函式 swap_pair 和 reverse，以pointer to pointer避免回傳
```cpp=
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 **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
## 3. 改寫 reverse，新增rev_recursive遞迴反轉Link list
```cpp=
node_t *rev_recursive(node_t *cursor, node_t *head)
{
if(!head)
return cursor;
node_t *next = head->next;
head->next = cursor;
return rev_recursive(head, next);
}
void reverse(node_t **head)
{
if(!(*head))
return;
*head = rev_recursive(NULL, *head);
}
```
## 4. 實作 Fisher–Yates shuffle，使用swap減少記憶體使用量
```cpp=
void shuffle(node_t **head)
{
srand(time(NULL));
int size = 0;
node_t *tmp = *head;
while(tmp){
size++;
tmp = tmp->next;
}
while(size != 0)
{
node_t *tail, *prev_tmp = NULL, *prev_tail = NULL;
int rad = rand() % size;
tmp = tail = *head;
for(int i = 0; i < rad; i++){
prev_tmp = tmp;
tmp = tmp->next;
}
for(int j = 0; j < size - 1; j++){
prev_tail = tail;
tail = tail->next;
}
/*prev_swap & head*/
if(prev_tmp != NULL)
prev_tmp->next = tail;
else
*head = tail;
if(prev_tail != NULL)
prev_tail->next = tmp;
else
*head = tmp;
/*swap*/
node_t *next = tmp->next;
tmp->next = tail->next;
tail->next = next;
size--;
}
}
```
Sign in with Wallet
Connect another wallet