# 2021q1 Homework1 (quiz1)
contributed by < `Tzuying` >

###### tags: `linux2021`

> [J02: quiz1](https://hackmd.io/@sysprog/SJlXFVMzMu)

:::success

* [x] 圖形化 [Graphviz](https://graphviz.org/)
* [ ] Real [Random](https://linux.die.net/man/3/random), [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
* [ ] 避免使用遞迴呼叫 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)
* [ ] 探討 Linux 的 linked list 和上述程式碼的落差，並改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例，避免使用遞迴呼叫
* [ ] 思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
* [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf) by [冼鏡光](https://zh.wikipedia.org/zh-tw/%E5%86%BC%E9%8F%A1%E5%85%89)
:::

## Preview

* `node_t *node_t` 與 `node_t **list`
* 指標 = 值為記憶體的變數
* 設計變數為記憶體，表示未來希望改變的是該記憶體存放的數值(需要*)
* 當函式參數為指標，可能是一個 node，也可能是一串 node 的開頭 (array or llist)，需透過上下文確認
* 記憶體變數的最終目是(使用)改變記憶體存放的數值，為了達到這個目的，需要各種記憶體變數操作
* 製作記憶體不連續的多元素容器結構, linked list
* 作為瀏覽多元素容器結構的 index
* 為函式加註解以理解各自作用 [GitHub(wait)]()
* [Boolean type support library](https://en.cppreference.com/w/c/types/boolean), from C99
* [Quicksort](https://en.wikipedia.org/wiki/Quicksort)
* The shaded element is the ==pivot==. It is always chosen as the last element of the partition. 

## 解題

* ANS(Try-1) : d / e / c / b
* implment `list_make_node_t` and `list_free`
* run `gcc -o quiz ./main.c ./llist.c; ./quiz`
* result = null
* 
* 思路
* list 有建置成功，所以問題不會在 AAA 或 BBB，而 CCC 其他答案都不可能，所以錯誤應該是 LLL
* ANS(Try-2) : **c** / e / c / b
* ==盲點== `list_concat`
* 函式目的很清楚，讓 left 走到尾端，將 right 放在其 next
* 觀察 caller `quicksort`，result 要一直放置 list 的開頭，所以 list_concat 中走 Linked List 的動作不能在 `node_t *` 層級，要在 list 結構的記憶體層級 `node_t **`，否則最後 result 都會指在 list 結尾 NULL

                 list_concat(&result, left);
                 list_concat(&result, pivot);
                 list_concat(&result, right);
                 *list = result;

* 換句話說，不能透過 next `result = result->next` 移動，要透過 next 的記憶體位置 `&result = &(result->next)` 移動
* 回到選項，以圖片表示兩種作法差異，假設 list => 1016, 84, 706
* 執行前

            digraph before {
                rankdir=LR

                subgraph cluster_0 {
                    style=filled;
                    color=lightgrey;
                    node1 [shape=record, label="{ <value>1016 | <ref> A(node2) }",color=darkgreen]
                    node2 [shape=record, label="{ <value>84 | <ref> A(node3) }",color=darkgreen]
                    node3 [shape=record, label="{ <value>706 | <next>NULL }",color=darkgreen];

                    node1 -> node2 -> node3  ;
                    label = "the list";
                }

                subgraph cluster_1 {
                    color=white;
                    left [shape=box, label="A(result)", width=1.5];
                    label = "left";
                }

                subgraph cluster_2 {
                    color=white;
                    result[shape=box, label="A(node1)"];
                    label = "result";
                }

                left -> result;
                result -> node1:value ;

            }

* `d` `*left = (*left)->next`

            digraph before {
                rankdir=LR

                subgraph cluster_0 {
                    style=filled;
                    color=lightgrey;
                    node1 [shape=record, label="{ <value>1016 | <next> A(node2) }",color=darkgreen]
                    node2 [shape=record, label="{ <value>84 | <next> A(node3) }",color=darkgreen]
                    node3 [shape=record, label="{ <value>706 | <next>NULL }",color=darkgreen];

                    node1 -> node2 -> node3  ;
                    label = "the list";
                }

                subgraph cluster_1 {
                    color=white;
                    left [shape=box, label="A(result)", width=1.2];
                    label = "left";
                }

                subgraph cluster_2 {
                    color=white;
                    result[shape=box, label="A(node2)", width=1.2];
                    label = "*left(result)";
                }

                left -> result;
                result -> node2:value ;

            }

* `c` `left = &((*left)->next)`

            digraph before {
                rankdir=LR

                subgraph cluster_0 {
                    style=filled;
                    color=lightgrey;
                    node1 [shape=record, label="{ <value>1016 | <next> A(node2) }",color=darkgreen]
                    node2 [shape=record, label="{ <value>84 | <next> A(node3) }",color=darkgreen]
                    node3 [shape=record, label="{ <value>706 | <next>NULL }",color=darkgreen];

                    node1 -> node2 -> node3  ;
                    label = "the list";
                }

                subgraph cluster_1 {
                    color=white;
                    left [shape=box, label="A(node1->next))", width=1.7];
                    label = "left";
                }
                
                subgraph cluster_3 {
                    color=white;
                    pleft[shape=box, label="A(node2)", width=1.2];
                    label = "*left";
                }

                subgraph cluster_2 {
                    color=white;
                    result[shape=box, label="A(node1)", width=1.2];
                    label = "result";
                }

                left -> pleft -> node2:value ;

            }

            digraph before {
                rankdir=LR

                subgraph cluster_0 {
                    style=filled;
                    color=lightgrey;
                    node1 [shape=record, label="{ <value>1016 | <next> A(node2) }",color=darkgreen]
                    node2 [shape=record, label="{ <value>84 | <next> A(node3) }",color=darkgreen]
                    node3 [shape=record, label="{ <value>706 | <next>NULL }",color=darkgreen];

                    node1 -> node2 -> node3  ;
                    label = "the list";
                }

                subgraph cluster_1 {
                    color=white;
                    left [shape=box, label="A(node2->next))", width=1.7];
                    label = "left";
                }
                
                subgraph cluster_3 {
                    color=white;
                    pleft[shape=box, label="A(node3)", width=1.2];
                    label = "*left";
                }

                subgraph cluster_2 {
                    color=white;
                    result[shape=box, label="A(node1)", width=1.2];
                    label = "result";
                }

                left -> pleft -> node3:value ;

            }

* ==比較== `void list_add_node_t(node_t **list, node_t *node_t)` vs `node_t * list_make_node_t(node_t *list, long value)`
* 這兩個函式都是要建立一個 list ，為什麼輸入參數型態可以不同
* `void list_add_node_t(node_t **list, node_t *node_t)`
* 將 `node_t **list` 改為 `node_t *list`，發現 list 只剩下 pivot
* 其實是簡單的傳值傳址觀念，若有 list 結構改變，需要傳址(&(node_t * list))進函式，而只有透過 `*` 操作才會實際有變化
* 假設某函式輸入參數如下，在該函式裡對 a 做任意給值都不會影響函式外部。反過來說，若 a 的層級越上，能做的真實改變範圍就越大
* `node_t a`
* `node_t *a` => 對 `*a` 的改變會真的生效
* `node_t **a` => 對 `*a` / `**a` 的改變會真的生效
* `node_t * list_make_node_t(node_t *list, long value)`
* 雖然改變儘限於函式中，但因為有以回傳值接起來，所以也沒有問題

## Graphviz

* 可以在 hackmd 上直接寫 Graphviz 程式碼，就會自動產生圖片 :sparkles:
* [documentation](https://graphviz.org/documentation/)
* [node shape](https://graphviz.org/doc/info/shapes.html)
* [attribute](https://graphviz.org/doc/info/attrs.html)
* [Gallery](https://graphviz.org/gallery/) : [Hello World](https://graphviz.org/Gallery/directed/hello.html)

    digraph G { 
        Hello->World
    }

* [如何編譯與程式語言簡介](http://wiki.csie.ncku.edu.tw/Graphviz?revision=7e4c6cf2373e41d948c8fb5caffd0407b9f302d7)
* 參考範例 [2018q1 Homework (quiz4)](https://hackmd.io/2iFLLGRyT2SzIAV-Hwf1NA?both)

digraph R {
    rankdir=LR
    
    subgraph cluster_0 {
		style=filled;
		color=lightgrey;
        node1 [shape=record, label="{ <value>1016 | <ref> }",color=darkgreen]
        node2 [shape=record, label="{ <value>84 | <ref> }",color=darkgreen]
        node3 [shape=record, label="{ <value>706 | <next>NULL }",color=darkgreen];
            
        node1:ref:c -> node2  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    node2:ref:c -> node3  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
		label = "the list";
	}
    
    subgraph cluster_1 {
        color=white;
		node[shape=box, label=""];
        left;
		label = "left";
	}
    
    subgraph cluster_2 {
        color=white;
		node[shape=box, label=""];
        result;
		label = "result";
	}
        
    left -> result [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    result -> node1:value [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];

}

## 重點整理

* 變動結構的函式其 list/head 參數
* 需傳址 (除非有在 caller 做特殊處理)
* 需考慮離開函式之後，指標參數的值在哪裡，是否符合設計