# 2020q3 Homework1 (quiz1)
contributed by< `JimmyLiu0530` >
###### tags: `進階電腦系統理論與實作`
- [Linked list 測驗題目](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## 測驗1: singly linked list
題目給定 linked list 結構定義為:
```c=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
且已知不存在 circular (環狀結構) 情況下，對單向 linked list 進行操作
圖例:
```graphviz
digraph foo{
rankdir=LR;
node [shape=record];
a [label="{ <data> 12 | <ref> }"]
b [label="{ <data> 54 | <ref> }"];
c [label="{ <data> 37 | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
### 原始測驗題的思考及理解
- `add_entry`
> 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
程式碼如下:
```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;
}
```
#### 核心觀念: 找到整串 linked list 的尾巴，將它指向新增的節點
運作原理如下:
1. **第3行** 建立一個指向 head 的指標 indirect ( pointer to pointer )
```mermaid
graph LR
subgraph linked list
head==>node1==>node2
end
subgraph pointer to pointer
indirect==>head
end
```
2. **第5-7行** 配置一個 node_t 的空間，並初始化
3. **第9行** 應選 `assert(new_node)`，用來檢查new_node是否合法
4. **第10-11行** 用來找到 linked list 的最後一個 node。下圖展示第一圈 while 後的結果，以此類推
```mermaid
graph LR
subgraph linked list
head==>node1==>node2
end
subgraph pointer to pointer
indirect==>node1
end
```
5. **第12行** 應選***indirect = new_node**，把最後一個 node 的 next 指向 new_node，增加節點完成
:::warning
**Note**
- `->` 的執行順位大於 `&` ，所以要先進行 `->` 運算再運算 `&`
:::
- `remove_entry`
> 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
程式碼如下:
```c=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
#### 核心觀念: 繞過欲刪除的節點
運作原理如下:
1. **第3行** 建立一個指向 head 的指標 indirect ( pointer to pointer )
```mermaid
graph LR
subgraph linked list
head==>node1==>entry==>node3
end
subgraph pointer to pointer
indirect==>head
end
```
2. **第5-6行** 找到欲刪除的節點 entry
```mermaid
graph LR
subgraph linked list
head==>node1==>entry==>node3
end
subgraph pointer to pointer
indirect==>node1
end
```
3. **第8行** 繞過 entry，也就是說把 entry 的上一個節點改指向 entry 的下一個節點
```mermaid
graph LR
subgraph linked list
head==>node1==>node3
entry==>node3
end
subgraph pointer to pointer
indirect==>node1
end
```
4. **第9行** 釋放 entry 的記憶體資源
```mermaid
graph LR
subgraph linked list
head==>node1==>node3
end
subgraph pointer to pointer
indirect==>node1
end
```
- `swap_pair`
> 交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 `1->2->3->4`，則該回傳 `2->1->4->3`
程式碼如下:
```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;
}
```
#### 核心觀念: 倆倆一組，相關指標做改變
運作原理如下:
1. **第3行 for 條件** 應選 `node = &(*node)->next->next`，因為此 function 為兩兩交換，因此下一輪 node pointer 應指向目前這對的尾，如下所示:
```mermaid
graph LR
subgraph linked list
head==>node1==>node2==>node3==>node4
end
subgraph pointer to pointer
node==>node2
end
```
2. **第4行** 建立一個 tmp 指向該對的頭，如下所示:
```mermaid
graph LR
subgraph linked list
head==>node1==>node2==>node3==>node4
end
subgraph pointer to pointer
node==>head
end
subgraph temp
tmp==>node1
end
```
3. **第5行** 應選 `*node = (*node)->next`，使 head 改指向該對的尾(e.g. node2)，如下所示:
```mermaid
graph LR
subgraph linked list
head==>node2
node1==>node2==>node3==>node4
end
subgraph pointer to pointer
node==>head
end
subgraph temp
tmp==>node1
end
```
4. **第6行** 該對的頭 (e.g. node1) 的 next 改指向下一對的頭 (e.g. node3)，如下所示:
```mermaid
graph LR
subgraph linked list
head==>node2
node1==>node3
node2==>node3==>node4
end
subgraph pointer to pointer
node==>head
end
subgraph temp
tmp==>node1
end
```
5. **第7行** 該對的尾 (e.g. node2) 的 next 改指向頭 (e.g. node1)，如下所示:
```mermaid
graph LR
subgraph linked list
head==>node2
node1==>node3
node2==>node1
node3==>node4
end
subgraph pointer to pointer
node==>head
end
subgraph temp
tmp==>node1
end
```
6. 之後依此類推...直到交換結束，或是只剩沒成對的node。最後 return 交換後整個 linked list 的頭
- `reverse`
> 將給定的 linked list 其內節點予以反向，即 `1->2->3->4`，則該回傳 `4->3->2->1`
程式碼如下:
```c=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
#### 核心觀念: 將 cursor 視為指向 head 的前一個節點，next 視為指向 head 的後一個節點。不斷更新(往後挪)三個指標 cursor、head、next直到 linked list 的尾巴
運作原理如下:
1. **第5行** 創建一個指標 next 指向目前 head 所指的節點的下一個節點。如圖 next 指向 node2
```mermaid
graph LR
subgraph linked list
head==>node1==>node2==>node3==>node4
next==>node2
cursor==>NULL
end
```
2. **第6行** 應選 `head->next = cursor; cursor = head` ，如圖先將 head->next (i.e. node1) 指向 cursor 指的 NULL，再將 cursor 指向 head
```mermaid
graph LR
subgraph linked list
head==>node1
cursor==>node1
next==>node2==>node3==>node4
node1==>NULL
end
```
3. **第7行** 將 head 指標往後挪一個節點，如圖 head 從指向 node1 變成 node2
```mermaid
graph LR
subgraph linked list
head==>node2
cursor==>node1
next==>node2==>node3==>node4
node1==>NULL
end
```
### 延伸問題
#### 1.避免回傳指標的函式 `swap_pair_revised` & `reverse_revised`
說明: 利用指標的指標對 `swap_pair` 及 `reverse` 兩函式做改寫，來達到不需回傳整串 linked list 的 head
- `swap_pair_revised`
程式碼如下:
```c=
void swap_pair_revised(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;
}
}
```
主程式呼叫:
`swap_pair_revised(&head);`
運作原理如下:
1. 與函式 `swap_pair` 只有傳入 parameter 的方式不同，差別在於 `swap_pair` 採 **pass by value** 的方法；而 `swap_pair_revised` 則是採 **pass by reference** 的方法。有關 pass by value 跟 reference 的詳細解說，可到 [Pass by value vs Pass by reference](https://medium.com/@racktar7743/c-c-%E6%8C%87%E6%A8%99%E6%95%99%E5%AD%B8-%E5%9B%9B-pass-by-value-vs-pass-by-reference-ed5882802789) 觀看
- `reverse_revised`
程式碼如下:
```c=
void reverse_revised(node_t **indirect)
{
node_t *cursor = NULL;
while (*indirect) {
node_t *next = (*indirect)->next;
(*indirect)->next = cursor;
cursor = *indirect;
*indirect = next;
}
*indirect = cursor;
}
```
主程式呼叫:
`reverse_revised(&head);`
運作原理如下:
1. 與原函式概念一樣，只是改採用 pass by reference 的方法，因此一些相對應的變數(e.g. while 的條件從 `head` 改成 `*indirect`)也須做修改
2. **第10行** 最後再把新的 linked list 頭的位置 assign 到 head (i.e. *indirect) 去
#### 2. 以遞迴改寫 `reverse` 函式
首先，建立**遞迴**演算法有幾個重點: (a) **終止條件** (b) **將原問題變成與其相似且規模較小的問題**
程式碼如下:
```c=
node_t *rev_recursive(node_t *p)
{
if(p->next == NULL)
{
return p;
}
node_t *head = rev_recursive(p->next);
node_t *q = p->next;
q->next = p;
p->next = NULL;
return head;
}
```
主程式呼叫:
`head = rev_recursive(head);`
運作原理如下:
1. **第3-6行** 即為終止條件。if 條件若成立，代表 p 為此 linked list 的最後一個節點，也就是新的 head，因此回傳該位址
2. **第7行** 遞迴呼叫 rev_recursive()，並將新的 head 記錄下來
3. **第8-10行** 舉例來說，假設 p 指向 node2，則 q 指向 node3。經過這幾行的處理後，第一張圖會變成第二張圖，也就是 node3->next 指向 node2，且 node2->next 指向 NULL
```mermaid
graph LR
subgraph linked list
head==>node1==>node2==>node3==>NULL
end
```
```mermaid
graph LR
subgraph linked list
head==>node1==>node2==>NULL
node3==>node2
end
```
#### 3. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，儘量降低記憶體的使用量
什麼是 `Fisher–Yates shuffle`?
> 用來將一個有限集合生成一個隨機排列的方法，簡單來說，該算法可以洗牌序列。該算法產生無偏頗的排列，代表每種排列的可能性均等。
程式碼如下
```c=
// this swap function is under the premise that
// 1 <= p <= q <= total number of node in the linked list
// and is used to swap pth and qth node in the linked list
void swap(node_t **head, int p, int q)
{
// nothing to do if p,q are the same
if(p == q)
return;
// search for pth node in the linked list
node_t *prevP = NULL, *currP = *head;
for(int i = p-1; i>0; i--)
{
prevP = currP;
currP = currP->next;
}
// search for qth node in the linked list
node_t *prevQ = NULL, *currQ = *head;
for(int i = q-1; i>0; i--)
{
prevQ = currQ;
currQ = currQ->next;
}
// if pth node is head of linked list, i.e. p==1, make qth node a new head
if (p==1)
*head = currQ;
else
prevP->next = currQ;
// if q is 1, p must be 1 either, the process will return due to line7
prevQ->next = currP;
// swap next pointers
node_t *tmp = currQ->next;
currQ->next = currP->next;
currP->next = tmp;
}
void Fisher_Yates_shuffle(node_t **indirect)
{
// count how many nodes are in linked list
int totalNum = 0;
node_t *tmp = *indirect;
while(tmp)
{
totalNum += 1;
tmp = tmp->next;
}
srand(time(NULL));
// start from the first node and randomly choose a number q s.t. p<=q<=totalNum
for(int p = 1; p <= totalNum-1; p++)
{
int q = (rand() % (totalNum-p+1))+p;
swap(indirect, p, q);
}
}
```
主程式呼叫:
`Fisher_Yates_shuffle(&head);`
運作原理如下:
1. 先說明 `swap` 函式，主要將第 p 跟第 q 個節點交換
**第11-24行** 先找到第 p 跟第 q 個節點的位置，並記錄在 currP 及 currQ， prevP 跟 prevQ 則分別記錄 currP 及 currQ 的前一個節點
**第26-27行** 需考慮 p==1 的情況，也就是第 p 個節點是 head
**第33行** 之所以這裡不用 if-else 是因為在給定的前提中，1 <= p <= q。當 q=1 時，
p 勢必也是 1 ，因此會在 `line 8` retrun 掉了
**第36-38行** 做一些 `next` pointer 的交換
2. 此 `swap` 函式因為是 linked list，所以不像 array 在給定第 p 跟第 q 個元素做交換下可在O(1)完成，需 $O(n)$。
3. 接著看 `Fisher_Yates_shuffle` 函式，此函式精神在於在第 p 輪中，會隨機找一個介於 p 跟總節點數的數字 q，並將第 p 跟第 q 個交換
**第44-50行** 計算 linked list 的總節點數
**第55-60行** 從 linked list 的第一個節點開始，在之間隨機找一個節點做交換，再來換第二個節點...以此類推，一直重複做到倒數第二個節點
4. 此`Fisher_Yates_shuffle` 函式的時間複雜度為 $O(n^2)$，但空間複雜度只需 $O(1)$。
Sign in with Wallet
Connect another wallet