# 第一週測驗 q4
題目如下網址
https://hackmd.io/@jserv/SyK-WApKM?type=view#%E6%B8%AC%E9%A9%97-1
## 第一題
### 各個function作用
測驗1
作答如下
```c=1
#include <stdlib.h>
#include <stdio.h>
struct node { int data; struct node *next, *prev; };
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;
}
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;
}
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;
}
void display(struct node *start) {
struct node *temp = start;
printf("Traversal in forward direction \n");
for (; temp->next != start; temp = temp->next)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\nTraversal in reverse direction \n");
struct node *last = start->prev;
for (temp = last; temp->prev != last; temp = temp->prev)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\n");
}
int main() {
struct node *start = NULL;
FuncA(&start, 51); FuncB(&start, 48);
FuncA(&start, 72); FuncA(&start, 86);
FuncC(&start, 63, 51);
display(start);
return 0;
}
```
分別推測FuncA , FuncB , FuncC 功能
並推測程式執行結果
```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;
}
```
**1.FuncA作用**
如果 *start 不是NULL(＃2)，直接malloc一個 node 節點，將 value 丟給此節點，並將此節點的 next ，prev 都指向自己
再來（＃9）開始加入新節點，到起始節點與最後節點之間，使其維持環狀結構的 linked list
**所以答案選項(e) 建立新節點，內容是 value，並安插在結尾**
```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;
}
```
**2.FuncB作用**
將新加入的 node 節點放在 start 和 last 之間，最後再將起始節點改為 new_node
```
(#8)*start = new_node;
```
也就是將新加入的節點設為開頭
**所以答案選項(d) 建立新節點，內容是 value，並安插在開頭**
```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;
}
```
**3.FuncC作用**
(＃5 #6) traversal 用 while 搜尋 value2 如果有找到 ，將新加入的節點 node value1 ，加在 value2的後面，一樣是形成一個環狀 linked list
**所以答案選項(e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1
### 輸出結果
在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？
```c=
void display(struct node *start) {
struct node *temp = start;
printf("Traversal in forward direction \n");
for (; temp->next != start; temp = temp->next)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\nTraversal in reverse direction \n");
struct node *last = start->prev;
for (temp = last; temp->prev != last; temp = temp->prev)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\n");
}
int main() {
struct node *start = NULL;
FuncA(&start, 51); FuncB(&start, 48);
FuncA(&start, 72); FuncA(&start, 86);
FuncC(&start, 63, 51);
display(start);
return 0;
}
```
(#20)display(start)輸出結果為
Traversal in forward direction 48 51 63 72 86
Traversal in reverse direction 86 72 63 51 48
## 第二題
### 各個function作用
```c=
#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作用**
將 node 節點丟進去FuncX ， loop 內 traversal 直到 node = NULL 或 node 回到 head 為止
loop 裡面的 data++ ，每跑一次 node = node->next ，就會加一次 sizeof(int
) 的位址，但看起來原本應該是想要每個 node 內的 data 都 +1 ，所以應該寫成 （* data)++
，先 dereference 後再 ++
(#11) return node - head; 返回直如果是0 ， 表示繞回起始點 ， 是一個環狀 linked list
**2.struct node *node_new (int data)**
用來新增一個節點，並返回一個節點 struct node ， main 中將返回節點加入linked list尾端
Sign in with Wallet
Connect another wallet