---
tags: linyunwen
---
# 2018q1 Homework6 (c-review)
###### tags: `linyunwen`
contributed by <`LinYunWen`>
- [D06: c-review](https://hackmd.io/s/ByDzIZzjf)
## [第四周練習題](https://hackmd.io/s/SyK-WApKM)
### Q1. 分析以下程式碼，推敲 FuncA, FuncB, FuncC 的作用，並且推測程式執行結果。
- 首先看到 struct node 為節點的結構，有一個 int 儲存資料，及一個 next pointer, prev pointer，因此可以推測其為一個雙向的 linked list
```c=
struct node {
int data;
struct node *next, *prev;
};
```
1. FuncA 的作用是?
```c=
void FuncA(struct node **start, int value) {
if (!*start) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
```
- 首先可以看到一開始的 if 為判斷 ```*start``` 存不存在是不是 null ，如果是 null 則在第 3 行 malloc 出 ```*new_node``` ，並且將其 data 放 value (#4)，然後 next, prev 都指向自己，就如下所示
```
*start
^
|---+-------------+
| | |
+--------------------+
+ prev | data | next +
+--------------------+
```
- 這是為了避免 *start 一開始的輸入為 null ，所以拿掉的話就會出錯 ```程式記憶體區段錯誤 (core dumped)```
- 再來接下看，跟 if 裡做得很像，不同點唯有 \#12~\#15 ，其是將 new_node 的 next 指向 *start ，而將 *start 的 prev 指向 new_node 最後在將 last 的 next 指向 new_node，過程就有點像是
```shell
+-> | start | <--> | last | <-+
+-----------------------------+
// new_node->next = *start;
| new | -+
+-> | start | <--> | last | <-+
+-----------------------------+
// (*start)->prev = new_node;
| new | <-+
+-> | start | <--> | last | -+
+----------------------------+
// new_node->prev = last;
+- | new | <-+
| +-> | start | <--> | last | -+ <-+
| +----------------------------+ |
+----------------------------------------------+
// last->next = new_node;
+-> | new | <--> | start | <--> | last | <-+
| |
+------------------------------------------+
```
- 因此可以得知這是個環狀雙向 linked list ，而且可以看到是從後端新增一個 node 插入
```c=
// q1.1
FuncA(&start, 1);
FuncA(&start, 2);
FuncA(&start, 3);
FuncA(&start, 4);
display(start);
// output
// Traversal in forward direction
// 1 2 3 4
// Traversal in reverse direction
// 4 3 2 1
```
2. FuncB 的作用是?
```c=
void FuncB(struct node **start, int value) {
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev = new_node;
*start = new_node;
}
```
- 而 FuncB 跟 FuncA 有點類似，都是建立一個新的 node (\#3) ， 給定 data 為 value (\#4) ， 主要差別是在 \#8 ，最後會將 *start 移到新的 node
```
+-> | new | <--> | start | <--> | last | <-+
| |
+------------------------------------------+
// *start = new_node;
+-> | start | <--> | mid | <--> | last | <-+
| |
+------------------------------------------+
```
- 因此可以知道他是建立一個新的 node 並且將其插入到開頭
```c=
// q1.2
FuncA(&start, 1);
FuncB(&start, 2);
FuncB(&start, 3);
FuncB(&start, 4);
display(start);
// output
// Traversal in forward direction
// 4 3 2 1
// Traversal in reverse direction
// 1 2 3 4
```
3. FuncC 的作用是?
```c=
void FuncC(struct node **start, int value1, int value2) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value1;
struct node *temp = *start;
while (temp->data != value2)
temp = temp->next;
struct node *next = temp->next;
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
```
- 要注意的是 \#4~\#6 有一個 while loop 要找 temp->data 如果等於 value2 時即跳出迴圈，並且以這個 temp node 向後接上 new_node
```c=
// q1.3
FuncA(&start, 1);
FuncA(&start, 2);
FuncA(&start, 3);
FuncA(&start, 4);
FuncC(&start, 5, 3);
display(start);
// output
// Traversal in forward direction
// 1 2 3 5 4
// Traversal in reverse direction
// 4 5 3 2 1
```
4. 在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？
```c=
// q1.4~10
struct node *start = NULL; // *statr -> null
FuncA(&start, 51); // *statr -> 51
FuncB(&start, 48); // *statr -> 48 -> 51
FuncA(&start, 72); // *statr -> 48 -> 51 -> 72
FuncA(&start, 86); // *statr -> 48 -> 51 -> 72 -> 86
FuncC(&start, 63, 51); // *statr -> 48 -> 51 -> 63 -> 72 -> 86
display(start);
```
### Q2 考慮以下程式碼，推敲程式作用並分析輸出。
```clike=
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct node {
int data;
struct node *next;
};
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
struct node *node_new(int data) {
struct node *temp = malloc(sizeof(struct node));
temp->data = data; temp->next = NULL;
return temp;
}
int main() {
int count = 0;
struct node *head = node_new(0);
head->next = node_new(1);
head->next->next = node_new(2);
head->next->next->next = node_new(3);
head->next->next->next->next = node_new(4);
printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next = head;
printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next->next = head->next;
printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next = head->next->next->next->next->next->next->next->next;
printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
printf("K5 >> %d\n", head->next->data);
printf("count >> %d\n", count);
return 0;
}
```
1. FuncX 的作用是 (涵蓋程式執行行為的正確描述最多者)?
```clike=
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
```
- 可以看到這裡有個 for loop 用來從 linked list 頭跑到最後，而且注意到這個 node 是宣告在外面，所以最後跑完時， for loop 的終止條件 為 ```node && node != head``` ，表示最後結束時，node 要不是為 null 就是跟 head 相同，因此最後 node - head 要視為 0 的話，就是一個環狀的 linked list
2. K1 >> 後面接的輸出為何
3. K2 >> 後面接的輸出為何
4. K3 >> 後面接的輸出為何
5. K4 >> 後面接的輸出為何
6. K5 >> 後面接的輸出為何
7. count >> 後面接的輸出為何
```
struct node *head = node_new(0);
head
|
0 -> null
-------------------------------------
head->next = node_new(1);
head
|
0 -> 1 -> null
-------------------------------------
head->next->next = node_new(2);
head
|
0 -> 1 -> 2 -> null
-------------------------------------
head->next->next->next = node_new(3);
head
|
0 -> 1 -> 2 -> 3 -> null
-------------------------------------
head->next->next->next->next = node_new(4);
head
|
0 -> 1 -> 2 -> 3 -> 4 -> null
-------------------------------------
```
- K1 因為此 linked list 不為環狀，所以 FuncX 回傳 非 0 值，故輸出 ```Yes```
```
head
|
0 -> 1 -> 2 -> 3 -> 4 -> null
------------------------------------
head->next->next->next->next = head;
head
|
0 -> 1 -> 2 -> 3
^ |
+--------------+
```
- K2 因為變成環狀了，所以輸出會是 ```No```
```
head
|
0 -> 1 -> 2 -> 3
^ |
+--------------+
------------------------------------
head->next->next->next->next->next = head->next;
head
|
0 -> 1 -> 2 -> 3
^ |
+--------------+
```
- K3 還是環狀的，所以輸出會是 ```No```
```
head
|
0 -> 1 -> 2 -> 3
^ |
+--------------+
------------------------------------
head->next = head->next->next->next->next->next->next->next->next;
head
|
0 --+
^ |
+---+
```
- K4 還是環狀的，所以輸出會是 ```No```
- K5 輸出會是 ```0```
- count 還會是 0 ， 因為 for loop 裡是對他的為製作操作不影響他的值
- // TODO: 輸出位址
## [第五週測驗 (上)](https://hackmd.io/s/SynmEVIqG)
### O1. 考慮以下程式碼，推敲其作用 (選出最符合行為的描述)
```clike
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
將 `Func32` 改寫為以下功能等價的程式碼:
```clike
uint8_t FuncI(uint32_t x)
{
if (!x) return 32;
int n = 1;
if (!(x >> 16)) { n += 16; x <<= 16; }
if (!(x >> M1)) { n += 8; x <<= 8; }
if (!(x >> M2)) { n += 4; x <<= 4; }
if (!(x >> M3)) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
1. Func32 = ?
- 首先可以明顯地看到這是一個遞迴的 function ，argument 為一個 unsigned int ，而他只做一件事，```如果 x 不為 0 就將自己向右平移一位 (除以二) ，然後自呼叫自己一次，否則回傳 32```
- 因此假設我們給定
```clike
int main() {
uint8_t result = Func32(1);
printf("result: %" PRIu8 "\n", result);
return 0;
}
```
- 執行過程：
```clike
// x = 1
Func32(1 >> 1) - 1
0 // return 32 and go back
32 - 1 // = 0
// x = 0x0000ffff
Func32(0x0000ffff >> 1) - 1
Func32(0x00007fff >> 1) - 1
Func32(0x00003fff >> 1) - 1
...
Func32(0x00000001 >> 1) - 1 // total has 16 layers
0 ? Func32(x >> 1) - 1 : 32; // return 32 and go back
32 - 1
...
19 - 1
18 - 1
17 - 1
// result = 16
```
2. M1 = ?
3. M2 = ?
4. M3 = ?
#### Reference: [uint type](https://stackoverflow.com/questions/12120426/how-to-print-uint32-t-and-uint16-t-variables-value/25984999)
### O2. 延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。
## [第五週測驗 (中)](https://hackmd.io/s/HkQjgqI5G)
### O1. 考慮以下程式碼，推敲其作用 (選出最符合行為的描述)
### O2. 延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。
Sign in with Wallet
Connect another wallet