2020q3 Homework1 (quiz1)
===
contribute by `Liao712148`
* 1.從新回答[第1周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
###### tags: `進階電腦系統理論與實作`
**測驗1**
---
```cpp
typedef struct __node{
int value;
struct __node *next;
}node_t;
```
**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;
AA1;
while(*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
*add_entry* function 為在linked list 的結尾加上新的節點
AA1:要選擇 `assert(new_node)`來檢查是否有成功利用malloc()函數有向系統作業取得記憶體,
`assert()`是一個macro `assert(int exprexxion)`可以判斷expression是否為真，如果條件為False則會列印出錯資訊,並終止程式。
AA2:透過7~8行可以使得 *indirect(pointer to pointer)* 指向linked list的最後節點，再透過`*indirect=new_node`將new_node插入linked list的尾端
***如下圖所式***
`add_entry(&head,101);`
* 透過add_entry 的3~5行可新增一個節點(struct)
```graphviz
digraph head{
node[shape=box];
D[label=101];
NULL1[label=NULL,shape=plaintext]
D->NULL1;
{rank=same;D NULL1};
}
```
* add_entry 的while迴圈會將indiretct(poiter to pointer)指向linke list的尾端
所以indirect最後會指向`NULL`
```graphviz
digraph head{
node[shape=box];
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
D[label=72];
NULL1[label=NULL,shape=plaintext]
head->D;
D->NULL1;
indirect->NULL1;
{rank=same;D NULL1};
}
```
* 透過第9行將~~new_node插入~~將new_node(pointer)指定給`*indirtct`(pointer)
```graphviz
digraph add101{
node[shape=box];
head[shape=plaintext,fontcolor=red]
//indirect[shape=plaintext,fontcolor=blue]
D[label=72];
NULL1[label=NULL,shape=plaintext];
x[label=101];
head->D->x;
x->NULL1;
{rank=same;D x NULL1};
}
```
---
```cpp=
node_t *swap_pair(node_t *head)
{
for(node_t **node=&head;*node&&(*node)->next;BB1){
node_t *temp=*node;
BB2;
tmp->next=(*node)->next;
(*node)->next=tmp;
}
return head;
}
```
`swap_pair`function會兩兩交換linked list的節點
BB2:因為需要更改節點的next，但是會造成更改之後找不到原先節點所指向的下一個節點，導致==無法推進==，所以要多一個temp來彌補
```graphviz
digraph add101{
node[shape=box];
head[shape=plaintext,fontcolor=red]
node1[shape=plaintext,fontcolor=green]
temp[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
node1->head->D->F->G->H->I->J;
temp->D;
{rank=same;D F G H I J NULL1};
}
```
第5行
`*node=(*node)->next`
```graphviz
digraph add101{
node[shape=box];
head[shape=plaintext,fontcolor=red]
node1[shape=plaintext,fontcolor=green]
temp[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
D->F->G->H->I->J->NULL1;
temp->D;
node1->head->F;
{rank=same;D F G H I J NULL1};
}
```
第6行
`temp->next=(*node)->next`
```graphviz
digraph add101{
node[shape=box];
head[shape=plaintext,fontcolor=red]
node1[shape=plaintext,fontcolor=green]
temp[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
D->F->G->H->I->J->NULL1;
temp->D;
D->G[label=next,color=red]
//temp->G[label=next];
node1->head->F;
{rank=same;D F G H I J NULL1};
}
```
第7行
`(*node)->next=temp;`
```graphviz
digraph add101{
node[shape=box];
head[shape=plaintext,fontcolor=red]
node1[shape=plaintext,fontcolor=green]
temp[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
G->H->I->J->NULL1;
F->D;
temp->D;
D->G;
//temp->G[label=next];
node1->head->F;
{rank=same;D F G H I J NULL1};
}
```
BB1:
`node = &(*node)->next->next`
---
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
`reverse()`function 反轉linked list 的連接順序
CCC:`head->next=cursor;cursor=head;`
第4行
`node_t *next = head->next;`
```graphviz
digraph add101{
node[shape=box];
next[shape=plaintext,fontcolor=purple]
head[shape=plaintext,fontcolor=red]
cursor[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
cursor->NULL2
{rank=same cursor NULL2};
D->F->G->H->I->J->NULL1;
// cursor->D;
next->F;
head->D;
{rank=same;D F G H I J NULL1 NULL2};
}
```
第5行
`head->next=cursor`
```graphviz
digraph add101{
node[shape=box];
next[shape=plaintext,fontcolor=purple]
head[shape=plaintext,fontcolor=red]
cursor[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
D->cursor->NULL2;{rank=same; D cursor}
head->D;
next->F;
F->G->H->I->J->NULL1;
{rank=same;D F G H I J NULL1 NULL2};
}
```
第6行
`cursor=head`
```graphviz
digraph add101{
node[shape=box];
next[shape=plaintext,fontcolor=purple]
head[shape=plaintext,fontcolor=red]
cursor[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
D->NULL2
F->G->H->I->J->NULL1;
cursor->D;
next->F;
head->D;
{rank=same;D F G H I J NULL1 NULL2};
}
```
延伸問題
===
* 1 請用指標的指標(pointer to pointer)來改寫swap_pair
將原本的head(pointer)改為pointer to pointer 即可
```cpp=
void swap_pointer2pointer(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;
}
}
```
* 2 請用指標的指標(pointer to pointer)來改寫reverse
將原本的head(pointer)改為pointer to pointer 即可
```cpp=
void reverse_pointer2pointer(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
由觀察pointer to pointer版本的reverse可以發現透過while迴圈修改cursor和head，所以利用**re_recursive**function來取代while的工作
```cpp=
void reverse_recursive(node_t **head)
{
node_t *cursor = NULL;
rev_recursive(&cursor,head);
*head=cursor;
}
```
```cpp=
void rev_recursive(node_t **cursor,node_t **head){
if(!*head) return;
node_t *next = (*head)->next;
(*head)->next=*cursor;
*cursor=*head;
*head = next;
rev_recursive(cursor,head);//遞迴的呼叫
}
```
* 4 針對singly-linked list 實作 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
利用`add_entry()`,`remove_emtry()` function來實現將一linked list的組合打散
```cpp=
void fisher_Yates_shuffle(node_t **head){
srand(time(NULL));
int i=length(*head);
while(i){
node_t **indirect=head;
int index=rand()%i;
while(index){
indirect=&(*indirect)->next;
index--;
}
add_entry(head,(*indirect)->value);
remove_entry(head,*indirect);
i--;
}
}
```
## ***程式解說***
設計理念:因為要減少記憶體空間所以設法不要再多增設節點來表示打散過後的linked list,
透過產生亂數來隨機透過`remove_entry()`刪除節點，並將刪除過的節點透過`add_entry()`插入linked list的尾端
如下圖所示:
*假設要刪除第2個節點*
```graphviz
digraph add101{
node[shape=box];
// next[shape=plaintext,fontcolor=purple]
//head[shape=plaintext,fontcolor=red]
//cursor[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101,color=red];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
// NULL2[label=NULL,shape=plaintext];
D->F->G->H->I->J->NULL1;
{rank=same;D F G H I J NULL1 };
}
```
*刪除第2個節點並新增將其資料add進linked list*
根據`add_entry()`function 會在linked list的尾端新增節點
```graphviz
digraph add101{
node[shape=box];
// next[shape=plaintext,fontcolor=purple]
//head[shape=plaintext,fontcolor=red]
//cursor[shape=plaintext,fontcolor=blue]
D[label=72];
F[label=101,color=red];
G[label=108];
H[label=109];
I[label=110];
J[label=111];
NULL1[label=NULL,shape=plaintext];
// NULL2[label=NULL,shape=plaintext];
D->G->H->I->J->F->NULL1;
{rank=same;D F G H I J NULL1 };
}
```
可以發現舊的(黑色節點的)linked list資料個數比之前少了一個，所以可以確認利用亂數刪除點的方法不會超出舊有的資料(==不會刪除已經處理過的紅色節點==)，如此便可以得到打散過後的linked_list
Sign in with Wallet
Connect another wallet