--- tags: linyunwen, raygoah --- # 2018q1 Homework (quiz4) ###### tags: `linyunwen` `raygoah` contributed by <`LinYunWen`, `raygoah`> - [2018q1 Homework3 (作業區)](https://hackmd.io/Ex6mTFOvS3K6NizRwX-HVQ) - [第四周練習題](https://hackmd.io/s/SyK-WApKM) - [Youtube](https://www.youtube.com/watch?v=zaA9jzWvMlg&list=PLFSyL7YoFilT_HugG5YUnSqslvFrwuIEp) ### Q1. 分析以下程式碼,推敲 FuncA, FuncB, FuncC 的作用,並且推測程式執行結果。 ![](https://i.imgur.com/I4mcQ7d.png) - 首先看到 struct node 為節點的結構,有一個 int 儲存資料,及一個 next pointer, prev pointer,因此可以推測其為一個雙向的 linked list ```clike= struct node { int data; struct node *next, *prev; }; ``` #### 1. FuncA 的作用是? ```clike= 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 都指向自己,就如下所示 :::warning `null` 和 `NULL` 不同,後者是 C 語言規格書提及的巨集,請調整用語 :notes: jserv ::: :::info - 感謝老師提醒,已更改,之後注意用詞 - 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. Use null when discussing the null character. By null character I am referring to '\0'. ``` - Reference: [C11 spec (ISO/IEC 9899:201x)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf)、[null and NULL: is there any difference?](https://bytes.com/topic/c/answers/213240-null-null-there-any-difference) ::: ```graphviz digraph structs { node[shape=record] struct0 [label= "<start>start"] struct1 [label="<prev> prev|<data> data|<next> next"]; struct0:start -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1]; struct1:prev -> struct1[arrowhead=vee, tailclip=true, arrowsize=1]; struct1:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1]; } ``` - 這是為了避免 *start 一開始的輸入為 ``NULL`` ,所以拿掉的話就會出錯 ```程式記憶體區段錯誤 (core dumped)``` :::warning 如何解釋 segmentation fault 的發生呢?這和課堂提及的 page fault 又有何關聯? :notes: jserv ::: - 再來接下看,跟 if 裡做得很像,不同點唯有 \#12~\#15 ,其是將 new_node 的 next 指向 *start ,而將 *start 的 prev 指向 new_node 最後在將 last 的 next 指向 new_node,過程就有點像是 ```graphviz digraph structs { rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; } ``` ``` #12 new_node->next = *start; ``` ```graphviz digraph structs { node[shape=record]; struct5 [label="<prev>prev|<data>new node|<next>next",color=purple] rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct5:next -> struct2 [color=red]; } ``` ``` #13 (*start)->prev = new_node; ``` ```graphviz digraph structs { node[shape=record]; struct5 [label="<prev>prev|<data>new node|<next>next"] rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct2[arrowhead=vee, tailclip=true, arrowsize=1]; struct5:next -> struct2; struct2->struct5:data[color=red] } ``` ``` #14 new_node->prev = last; ``` ```graphviz digraph structs { node[shape=record]; struct5 [label="<prev>prev|<data>new node|<next>next"] rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct2[arrowhead=vee, tailclip=true, arrowsize=1]; struct5:next -> struct2; struct2->struct5:data struct5:prev -> struct4[color=red] } ``` ``` #15 last->next = new_node; ``` ```graphviz digraph structs { node[shape=record]; struct5 [label="<prev>prev|<data>new \n node|<next>next"] rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct5:data[arrowhead=vee, tailclip=true, arrowsize=1,color=red]; struct5:next -> struct2; struct2 -> struct5:data struct5:prev -> struct4 } ``` 將上圖最後的順序整理一下,變成如下所示: ```graphviz digraph structs { rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; struct5 [label="new node"] { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct5[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct5 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; } ``` * 在這裡 last 指標並未更新,仍舊指向未增加新節點時的最後一個 node,而加入了新節點後,可以看到新節點會加在 linked list 尾端,也就是 last 指標指到的節點的下一個 - 因此可以得知這是個環狀雙向 linked list ,而且可以看到是從後端新增一個 node 插入, FuncA 中所做的事為 (e) 建立新節點,內容是 value,並安插在結尾 ```clike= // 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 的作用是? ```clike= 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 ```graphviz digraph structs { node[shape=record]; struct5 [label="<prev>prev|<data>new \n node|<next>next"] rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct2 } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct5:data[arrowhead=vee, tailclip=true, arrowsize=1]; struct5:next -> struct2; struct2 -> struct5:data struct5:prev -> struct4 } ``` ``` #8 *start = new_node; ``` ```graphviz digraph structs { rankdir=LR; node[shape=box]; struct5 [label="new node"] struct0 [label= "start", color=blue]; struct1 [label= "last"]; struct2 [label= "node1"]; struct3 [label= "node2"]; struct4 [label= "node3"]; { rank="same"; struct0 -> struct5 [color=blue] } { rank="same"; struct1 -> struct4 } struct2 -> struct3[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct3 -> struct4[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct4 -> struct5[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct5 -> struct2[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; } ``` - 因此可以知道 FuncB 是建立一個新的 node 並且將其插入到開頭 ```clike= // 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 的作用是? ```clike= 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 後面 ```clike= // 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 後依序印出哪幾個數字呢? ```clike= // 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); ``` ```graphviz digraph structs { rankdir=LR; node[shape=box]; struct0 [label= "start"]; struct1 [label= "48"]; struct2 [label= "51"]; struct3 [label= "63"]; struct4 [label= "72"]; struct5 [label= "86"]; { rank="same"; struct0 -> struct1 } struct1 -> struct2 -> struct3->struct4 -> struct5[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; struct5 -> struct1[arrowhead=vee, dir=both, tailclip=true, arrowsize=1]; } ``` - 依序為 48 -> 51 -> 63 -> 72 -> 86 :::info 延伸題目: 在上述 doubly-linked list 實作氣泡排序和合併排序,並提出需要額外實作哪些函示才足以達成目標 引入統計模型,隨機新增和刪除節點,然後評估上述合併排序程式的時間複雜度和效能分佈 (需要製圖和數學分析) ::: :::info [merge sort](https://github.com/LinYunWen/c-review/blob/master/week4/merge_sort.c)、[bubble sort](https://github.com/LinYunWen/c-review/blob/master/week4/bubble_sort.c) ::: ### Q2 考慮以下程式碼,推敲程式作用並分析輸出。 ![](https://i.imgur.com/vIk5eO9.png) ```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 :::warning 列出演算法的名稱與對應參考資料,儘量提及第一手材料 :notes: jserv ::: #### 2. K1 >> 後面接的輸出為何 #### 3. K2 >> 後面接的輸出為何 #### 4. K3 >> 後面接的輸出為何 #### 5. K4 >> 後面接的輸出為何 #### 6. K5 >> 後面接的輸出為何 #### 7. count >> 後面接的輸出為何 #### 依照順序建立 linked list I. ``` #25 struct node *head = node_new(0); ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` II. ``` #26 head->next = node_new(1); ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` III. ``` #27 head->next->next = node_new(2); ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` IV. ``` #28 head->next->next->next = node_new(3); ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <data> 3 | <ref> }"]; f [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` V. ``` #29 head->next->next->next->next = node_new(4); ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <data> 3 | <ref> }"]; f [label="{ <data> 4 | <ref> }"]; g [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` VI. - K1 因為此 linked list 不為環狀,所以 FuncX 回傳 非 0 值,故輸出 ```Yes``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <data> 3 | <ref> }"]; f [label="{ <data> 4 | <ref> }"]; g [label="{ <data> NULL}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` VII. ``` #31 head->next->next->next->next = head; ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <ref>|<data> 3 }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` VIII. - K2 因為變成環狀了,所以輸出會是 ```No``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <ref>|<data> 3 }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` IX. ``` #33 head->next->next->next->next->next = head->next; ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <ref>|<data> 3 }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` X. - K3 還是環狀的,所以輸出會是 ```No``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; e [label="{ <ref>|<data> 3 }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; 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]; d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; e:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` XI. ``` #35 head->next = head->next->next->next->next->next->next->next->next; ``` ```graphviz digraph linkedlist { rankdir=LR; node [shape=record]; a [label="{ <data> head | <ref> }", width=1.2] b [label="{ <data> 0 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` XII. - K4 還是環狀的,所以輸出會是 ```No``` - 這邊要注意到,因為 FuncX(head, &count) 傳入 count 的記憶體位址,但是在 FuncX 中,做的是 ```data++``` 而不是 ```* data++``` ,因此並不會實際計算走訪的 node,所以最後離開 FuncX 後 count 值仍為 0 :::warning 從 C 語言規格書解釋 `data++` 和 `*data++` 行為的差異,應附上 C99/C11 對應描述 :notes: jserv ::: :::info - 根據定義,suffix increment 的 precedence 是 1 ,而 dereference 的 precedence 是 2 - 所以可以發現的是 data++ 是將一個指向 int 的位址加一,預期應該要是 int 的值加一,因此加上 * , 但是因為優先度的關係, *data++ 其實是 *(data++) ,還是去增加他的位址而已,故如果要增加其值,應該寫為 (*data)++ ![](https://i.imgur.com/sW9Pg7S.png) - 同時以 code 實際操作,果然跟推測結果一樣,如下所示: ```clike= #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 的同學共筆 * [rex662624](https://hackmd.io/s/Byreb4fif#) * [afcidk](https://hackmd.io/s/SkS7PeXsf) * [raygoah](https://hackmd.io/s/BJ294eIsG) * [bauuuu1021](https://hackmd.io/s/Hk7jVN7if) * [BroLeaf](https://hackmd.io/s/Sk2fD9Pjz) * [LinYunWen](https://hackmd.io/s/HJtyXmAof) * [e94046165](https://hackmd.io/6WXM0FXOR3C8T_E3f501Ww?view) * [blake11235](https://hackmd.io/s/Hy9pIxk2M#%E7%AC%AC-4-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C) * [workat60474](https://hackmd.io/zxijbJ1LRZ-XYWA8IGFMNw?view#%E7%AC%AC-3-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C2%EF%BC%88%E9%81%B8%E6%93%87%E4%B8%8D%E7%86%9F%E6%82%89%E7%9A%84%E9%83%A8%E5%88%86%E9%87%8D%E6%96%B0%E4%BD%9C%E7%AD%94%E4%B9%8B%E4%BA%8C%EF%BC%89)