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

    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 裡面提到

Quicksort is a divide-and-conquer method for sorting.

因此在做 quicksort 的時候，最後會把 sort 好的兩個 list 再接回成一個 sort

list_concat 的功能是把算好的兩個結果做結合， 則是在做個工作，從 quicksort 裡的程式碼可以看出， list_concat 會把 sort 好的 left, right 跟 pivot 接成一個 list

    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 傳遞參數是這個樣子

static inline void list_concat(node_t **left, node_t *right)

*right 的部分沒有問題，指的是要接起來的右半邊
那 **left 傳進來的到底是什麼？

假設傳進來的 list 有 3 個 node, 那用 **left 傳進 function 則會出現下圖

ppleft 代表的是 **left
original left 代表的是原本 list 的 left
由於 ppleft 是指標的指標，所以他所記錄的位置會是 original left 的位置

那 LLL 執行過後的結果是 ?

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

答案如下

ppleft 會指向 node1 的 next 而不是 node2
然後如果繼續跑迴圈則會是以下虛線的走法

全部都會指向 next 的部分．

那 LLL 的答案到底表示什麼 ?
首先是

(*left)

取出 left 所指的地方的值，假設是在 list 的頭
而 left 指的地方的值則是 original left 的值
則會得到 node1，因此

(*left)->next

則是指 node1 的 next．
那 & 呢?

&((*left)->next)

則是取出 next 的位址( 不是 node2 的位址 )
最後再把位址 assign 給 ppleft 來完成 ppleft 的移動

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