# 2021q1 Homework1 (quiz1) contributed by <`fwfly`> # 測驗一 ## EXIT_FAILURE, EXIT_SUCCESS 跟 NULL 這三個變數都定義在 stddef 中 ``` #include<stddef.h> ``` 就可以消除關於這三個變數的 compile error ## 用 valgrind 檢測 memory leak 在補完 list_free 跟 list_make_node_t ，為了確認自己是否真的 free 掉 memory, 所以用 valgrind 跑一下． 卻發現出現 leak 的狀況 ``` :~/project/quiz1$ valgrind --leak-check=full ./q1-1 ... 省略 ... ==33224== Command: ./q1-1 ==33224== NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016 ==33224== ==33224== HEAP SUMMARY: ==33224== in use at exit: 320 bytes in 20 blocks ==33224== total heap usage: 21 allocs, 1 frees, 1,344 bytes allocated ==33224== ==33224== 320 (16 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2 ==33224== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==33224== by 0x1093F9: list_make_node_t (in /home/fwfly/project/quiz1/q1-1) ==33224== by 0x1094EB: main (in /home/fwfly/project/quiz1/q1-1) ==33224== ==33224== LEAK SUMMARY: ==33224== definitely lost: 16 bytes in 1 blocks ==33224== indirectly lost: 304 bytes in 19 blocks ==33224== possibly lost: 0 bytes in 0 blocks ==33224== still reachable: 0 bytes in 0 blocks ==33224== suppressed: 0 bytes in 0 blocks ==33224== ==33224== For lists of detected and suppressed errors, rerun with: -s ==33224== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) ``` 看來似乎 alloc 的全部都沒有 free 掉． 後來才發現，如果 sort 結果不對的話會直接離開程式而沒有做 free ```c= if (!list_is_ordered(list)) return EXIT_FAILURE; # memory leak! 直接離開程式 list_free(&list); return EXIT_SUCCESS; ``` 所以需要在 EXIT_FAILURE 之前再補上 free 來避免 memory leak ## LLL 根據 [Algorithms 4th edition](https://algs4.cs.princeton.edu/23quicksort/) 裡面提到 :::info Quicksort is a divide-and-conquer method for sorting. ::: 因此在做 quicksort 的時候，最後會把 sort 好的兩個 list 再接回成一個 sort list_concat 的功能~~是把算好的兩個結果做結合，~~ 則是在做個工作，從 quicksort 裡的程式碼可以看出， list_concat 會把 sort 好的 left, right 跟 pivot 接成一個 list ```c= quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); // CCC list_concat(&result, pivot); list_concat(&result, right); ``` 一開始認為是 ``` *left=(*left)->next; ``` 但是上面的答案是錯誤的，而且實際跑出來的結果也有問題 首先這個 concat 的 function 傳遞參數是這個樣子 ```c= static inline void list_concat(node_t **left, node_t *right) ``` *right 的部分沒有問題，指的是要接起來的右半邊 那 **left 傳進來的到底是什麼？ 假設傳進來的 list 有 3 個 node, 那用 **left 傳進 function 則會出現下圖 ![](https://i.imgur.com/YuVhVic.jpg) ppleft 代表的是 **left original left 代表的是原本 list 的 left 由於 ppleft 是指標的指標，所以他所記錄的位置會是 original left 的位置 那 LLL 執行過後的結果是 ? ```c= left = &((*left)->next) ``` 答案如下 ![](https://i.imgur.com/6pulaI9.jpg) ppleft 會指向 node1 的 next 而不是 node2 然後如果繼續跑迴圈則會是以下虛線的走法 ![](https://i.imgur.com/ZQrekPz.jpg) 全部都會指向 next 的部分． 那 LLL 的答案到底表示什麼 ? 首先是 ```c= (*left) ``` 取出 left 所指的地方的值，假設是在 list 的頭 而 left 指的地方的值則是 original left 的值 則會得到 node1，因此 ```c= (*left)->next ``` 則是指 node1 的 next． 那 & 呢? ```c= &((*left)->next) ``` 則是取出 next 的位址( 不是 node2 的位址 ) 最後再把位址 assign 給 ppleft 來完成 ppleft 的移動 ```c= left = &((*left)->next) ``` ## AAA 跟 BBB quick sort 換選出一個 pivot ，比 pivot 小的會放左邊，比 pivot 大的會放右邊． 然後再分開排序，排序方法一樣先選出一個 pivot 然後以此類推直到排序完為止． 所以 AAA = list 大於 pivot = right BBB = list 小於 pivot = left ### CCC 最後再把整個 list 全部接回去( 包含 pivot ) ``` list_concat(&result, pivot); list_concat(&result, right); ```