owned this note
owned this note
Published
Linked with GitHub
# 2020q3 Homework1 (quiz1)
contributed by <`fdsa654hg`>
###### tags: `sysprog2020`
## 分析以下程式碼
### 回答問題並用 Graphviz 解釋程式碼
#### 1.資料結構定義如下
```graphviz
digraph G{
rankdir=LR;
node [shape=record];
a [label="{ <data> value | <ref> }"]
b [label="{ <data> value | <ref> }"];
c [label="{ <data> value | <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];
}
```
```cpp=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
#### 2. Q1:AA1=? & Q2:AA2=?
- `(a) assert(new_node)`
- `(b) *indirect = new_node`
```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;
AA1; //assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
AA2 //*indirect = new_node;
}
```
- AA1之前的程式碼為建立一個 `node_t` 的新實例`new_node`，將參數 `new_value` 賦值給它並讓 `new_value->next` 指向 `NULL`
- 只看之前的程式碼仍無法判斷 AA1 為何，先考慮以下程式碼
```cpp=
while (*indirect)
indirect = &(*indirect)->next;
```
- `add_entry` 會將新增的節點放在最後，`indirect` 剛開始為list之 `head` 經此迴圈迭代會指向最後一個 `node` 的 `Next` ，下一行程式碼只要將新增的節點 `new_node` 至於此記憶體位置即可，故AA2為 `*indirect = new_node`
- 由以上推論AA1為 `assert(new_node)`，`assert()` 函式在此能起到判斷 `new_node` 是否成功建立的作用
#### 3. Q3:BB1=? & Q4:BB2=?
##### 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
```cpp=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1 /*node = &(*node)->next->next)*/) {
node_t *tmp = *node;
BB2 //*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
- 此函式的目的是從list的 `head` 開始，每兩個node交換(換過的不再換)
- 即
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <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 -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:data -> b:data [arrowhead=vee, arrowtail=vee, dir=both, tailport = n, headport=n, color=red];
c:data -> d:data [arrowhead=vee, arrowtail=vee, dir=both, tailport = n, headport=n, color=red];
}
```
- 變成
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 2 | <ref> }"]
b [label="{ <data> 1 | <ref> }"];
c [label="{ <data> 4 | <ref> }"];
d [label="{ <data> 3 | <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 -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 故 `for loop` 應要每兩個 `node` 執行一次，而 `node` 為雙重指標，存取的資料應是 `node_t` 型別指標的址，所以 BB1 為 `node = &(*node)->next->next`
##### BB2 = ?
- (a) node = (*node)->next
- (b) node = &(*node)->next
- (c\) *node = (*node)->next
- (d) *node = &(*node)->next
- (e) *node = &((*node)->next)
```cpp=
node_t *tmp = *node;
BB2; //*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
```
- 此段程式碼的目的是要交換兩個 `node`
- 由於 `node` 為雙重指標，真正能操作Linked List的是其指向的指標，為了改變其結構要使用`*`號，並將 `*node` 指向的節點改為下一個節點，故答案為 `*node = (*node)->next`
- 3、4行重新調整兩個節點的`next`所指的對象
#### 4.Q5:CCC=?
- (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
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC //head->next = cursor; cursor = head;
head = next;
}
return cursor;
}
```
- 此函式目的是反轉原本的 list 順序，即
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <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 -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 變成
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 4 | <ref> }"]
b [label="{ <data> 3 | <ref> }"];
c [label="{ <data> 2 | <ref> }"];
d [label="{ <data> 1 | <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 -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
##### 此函式的執行邏輯為
- 用 `head` 作為媒介並使用 `while` 迴圈跑完整個 Linked List
- 迴圈內先宣告一個空指標 `cursor`
- `head` 為 list 的開頭，先宣告一個指標 `next` 指向 `head->next` 即第二個節點
- 為了反轉整個 list 的順序勢必得從開頭下手，因為 Singly Linked List 只能從開頭開始存取，且變數 `next` 已經存取 `head` 的下一個位置故下一行即可反轉，即
```cpp=
head->next = cursor
```
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <ref> }"];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 下一步為
```cpp=
cursor = head
```
- 這樣下一個 `head` 能指向當前的 `head`
- 全部選項僅(b)符合邏輯
- 最後的 `head ＝ next` 讓下次迭代有正確的 `head`
- 照上述的邏輯運作，第二次迭代應為
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 第三次迭代
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 第四次迭代
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 1 | <ref> }"]
b [label="{ <data> 2 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 4 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
- 完成，結果正確
### 修改程式碼以避免回傳指標
#### `swap_pair` 原程式碼
```cpp=
node_t *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;
}
return head;
}
```
- 為避免回傳指標，使用指標的指標來改寫原函式
```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;
}
}
```
- 原函式需要回傳 `head` 指標的原因是因為 `head` 指向的東西是會改變的，但若使用指標的指標當參數傳入，改變的東西是其儲存的值所指向的東西，本身並不會改變，所以不需要回傳新的 `head`
- 如圖所示(`head` 為指標的指標，`head_value` 為`head` 所存的指標)
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 4 | <ref> }"]
b [label="{ <data> 3 | <ref> }"];
c [label="{ <data> 2 | <ref> }"];
d [label="{ <data> 1 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head[shape=plaintext,fontcolor=darkgreen];
head_value[shape=plaintext,fontcolor=darkgreen];
head -> head_value;
head_value -> d:data
}
```
- `swap_pair(head)` 作用後
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 3 | <ref> }"]
b [label="{ <data> 4 | <ref> }"];
c [label="{ <data> 1 | <ref> }"];
d [label="{ <data> 2 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head[shape=plaintext,fontcolor=darkgreen];
head_value[shape=plaintext,fontcolor=darkgreen];
head -> head_value;
head_value -> d:data
}
```
- 可知 `head` 所指向的東西不會改變，會改變的只有 `head_value`
#### `reverse()` 原程式碼
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; cursor = head;
head = next;
}
return cursor;
}
```
- 修改後
```cpp=
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;
}
```
- 原理如 `swap_pair()` 那段所述，不過此段程式碼要將 `head` 以 `*head` 取代，並在最後加上 `*head = cursor` ，因為 `head` 後會指向 `NULL`
### 以遞迴呼叫 `reverse()`
```cpp=
void reverse(node_t **head){
*head = rev_reverse(head);
}
node_t *rev_recursive(node_t **head){
if(*head!=NULL){
node_t cursor = NULL;
(*head) -> next = cursor;
cursor = rev_recursive((*head) -> next);
cursor -> next = *head;
return *head;
}
}
```
- 修改後
```cpp=
node_t *rev_recursive(node_t **head){
if((*head)->next){
node_t *next = rev_recursive(&(*head)->next);
(*head)->next->next = *head;
(*head)->next = NULL;
return next;
}
else{
return *head;
}
}
void reverse(node_t **head){
*head = rev_recursive(head);
}
```
- 此資料結構為單向的 Linked List，且若要使用遞迴的方法反轉原始順序，必須先走到最後一個節點用 `if` 條件句判斷到達尾端並回傳 `head` (即原始list的末端)
- 此處只會走到倒數第二個 `node`
```cpp=
if((*head)->next)
```
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 4 | <ref> }"]
b [label="{ <data> 3 | <ref> }"];
c [label="{ <data> 2 | <ref> }"];
d [label="{ <data> 1 | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head[shape=plaintext,fontcolor=darkgreen];
head -> b:ref;
}
```
```cpp=
(*head)->next->next = *head;
(*head)->next = NULL;
```
- 此段程式碼的目的是將自己的 `next` 指向自己(即調轉方向)，並將自己的 `next` 清空
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
a [label="{ <data> 4 | <ref> }"]
b [label="{ <data> 3 | <ref> }"];
c [label="{ <data> 2 | <ref> }"];
d [label="{ <data> 1 | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head[shape=plaintext,fontcolor=darkgreen];
head -> b:ref;
}
```
- 由於 `stack` 的特性，其執行順序會從倒數第二個節點開始執行上述兩行程式碼，下一個執行的是倒數第三個...，直到第一個節點也執行過了整個就完成了
- 由於除了在最後一個節點有回傳 `head` 之外其他的節點皆回傳上次回傳的結果，所以整個遞迴的過程回傳的值是最後一個節點的 `head` ，即新 list 的開頭
### Fisher–Yates shuffle
```cpp=
for(int i = n; i>=1; --i)
{
int j=rand(i);//生成1-i之間的隨機數
exchange(A[i],A[j]);//交換A[i]，A[j]
}
```
- 這是 `Fisher–Yates shuffle` 的演算法(不額外新增空間儲存的版本)，不過這是用`array`實作的，我將把它改成 Linked List 的版本
- 演算法的實作其實蠻簡單的，不過由於 Linked List 沒有隨機存取性，所以交換兩個元素很可能必須 traverse 整個list，因此是最麻煩的部份，以下簡述程式碼運作原理
```cpp=
int list_length(node_t *head){
int count = 0;
while(head){
++count;
head = head->next;
}
return count;
}
```
- 此函式的作用為計算 list 的個數
```cpp=
void exchange_nodes(node_t **head, int first_node, int second_node){
int count = second_node - first_node;
if(!count)return;
node_t **indirection = head;
node_t *first_cursor = NULL;
node_t *second_cursor = NULL;
while(first_node-1){
first_cursor = *indirection;
indirection = &(*indirection)->next;
--first_node;
}
node_t *first_node_des = *indirection;
while(count){
second_cursor = *indirection;
indirection = &(*indirection)->next;
--count;
}
node_t *second_node_des = *indirection;
if(first_cursor)first_cursor->next = second_node_des;
second_cursor->next = first_node_des;
node_t *tmp = second_node_des->next;
second_node_des->next = first_node_des->next;
first_node_des->next = tmp;
if(!first_cursor)*head = second_node_des;
}
```
- 第3行 -- 若隨機抽取的節點與未排序的節點為同一個就不用交換
- 第9～13行及17～21行 -- 取得隨機取得跟未排序的兩個節點的位置
- 第25～30行 -- 交換兩個節點並將其所指向的及被指向的節點調整好
- 第32行 -- 若交換到第1個節點更新新的 `head`
```cpp=
void Fisher_Yates_shuffle(node_t **head){
for(int i = list_length(*head); i>=1; --i){
int j = rand() % i + 1;
exchange_nodes(head,j,i);
}
}
```
- 這個函式為演算法的實例
Google Drive
Gist
Clipboard
Sign in with Wallet
