2018q1 Homework (quiz4)

tags: `linyunwen` `raygoah`

contributed by <LinYunWen, raygoah>

Q1. 分析以下程式碼，推敲 FuncA, FuncB, FuncC 的作用，並且推測程式執行結果。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

首先看到 struct node 為節點的結構，有一個 int 儲存資料，及一個 next pointer, prev pointer，因此可以推測其為一個雙向的 linked list

struct node {
    int data;
    struct node *next, *prev;
};

1. FuncA 的作用是?
















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 都指向自己，就如下所示

The macro NULL is defined in <stddef.h> (and other headers) as a null pointer constant [7.19]

Use NULL to indicate the macro defined in <stdlib.h> and when discussing pointers.

Reference: C11 spec (ISO/IEC 9899:201x)、null and NULL: is there any difference?

這是為了避免 *start 一開始的輸入為 NULL ，所以拿掉的話就會出錯 程式記憶體區段錯誤 (core dumped)
再來接下看，跟 if 裡做得很像，不同點唯有 #12~#15 ，其是將 new_node 的 next 指向 *start，而將 *start 的 prev 指向 new_node 最後在將 last 的 next 指向 new_node，過程就有點像是

#12 new_node->next = *start;

#13 (*start)->prev = new_node;

#14 new_node->prev = last;

#15 last->next = new_node;

將上圖最後的順序整理一下，變成如下所示：

在這裡 last 指標並未更新，仍舊指向未增加新節點時的最後一個 node，而加入了新節點後，可以看到新節點會加在 linked list 尾端，也就是 last 指標指到的節點的下一個

因此可以得知這是個環狀雙向 linked list ，而且可以看到是從後端新增一個 node 插入， FuncA 中所做的事為 (e) 建立新節點，內容是 value，並安插在結尾











// 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 的作用是?









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

#8 *start = new_node;

因此可以知道 FuncB 是建立一個新的 node 並且將其插入到開頭











// 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

FuncC 的作用是?












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
因此可以知道，在 FuncC 中所做的，是將值為 value1 的 node，插入在值為 value2 的 node 後面












// 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

在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？








// 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);

依序為 48 -> 51 -> 63 -> 72 -> 86

延伸題目：

在上述 doubly-linked list 實作氣泡排序和合併排序，並提出需要額外實作哪些函示才足以達成目標

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

參考實作

Q2 考慮以下程式碼，推敲程式作用並分析輸出。








































#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 的作用是 (涵蓋程式執行行為的正確描述最多者)?






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 >> 後面接的輸出為何

依照順序建立 linked list

#25 struct node *head = node_new(0);

II.

#26 head->next = node_new(1);

III.

#27 head->next->next = node_new(2);

IV.

#28 head->next->next->next = node_new(3);

#29 head->next->next->next->next = node_new(4);

VI.

K1 因為此 linked list 不為環狀，所以 FuncX 回傳非 0 值，故輸出 Yes

VII.

#31 head->next->next->next->next = head;

VIII.

K2 因為變成環狀，所以輸出會是 No

IX.

#33 head->next->next->next->next->next = head->next;

K3 還是環狀的，所以輸出會是 No

XI.

#35 head->next = head->next->next->next->next->next->next->next->next;

XII.

K4 還是環狀的，所以輸出會是 No
這邊要注意到，因為 FuncX(head, &count) 傳入 count 的記憶體位址，但是在 FuncX 中，做的是 data++ 而不是 * data++ ，因此並不會實際計算走訪的 node，所以最後離開 FuncX 後 count 值仍為 0

根據定義，suffix increment 的 precedence 是 1 ，而 dereference 的 precedence 是 2
所以可以發現的是 data++ 是將一個指向 int 的位址加一，預期應該要是 int 的值加一，因此加上 * ，但是因為優先度的關係， *data++ 其實是 *(data++) ，還是去增加他的位址而已，故如果要增加其值，應該寫為 (*data)++
同時以 code 實際操作，果然跟推測結果一樣，如下所示:



















#include <stdio.h>
#include <stdlib.h>

int main(){
        int count = 100;
        int count_2 = 100;
        int count_3 = 100;
        int *data = &count;
        int *data_2 = &count_2;
        int *data_3 = &count_3;
    
        data++;
        printf("data++ >> %d\n",count);
        *data_2++;
        printf("*data_2++ >> %d\n",count_2);
        (*data_3)++;
        printf("(*data_3)++ >> %d\n",count_3);
        return 0;
}

輸出結果:

$ gcc -o test test.c
$ ./test

data++ >> 100
*data_2++ >> 100
(*data_3)++ >> 101

有寫 C REVIEW 的同學共筆

2018q1 Homework3 (作業區)