練習33：鏈表算法 · 笨辦法學C

# 練習33：鏈表算法 > 原文：[Exercise 33: Linked List Algorithms](http://c.learncodethehardway.org/book/ex33.html) > 譯者：[飛龍](https://github.com/wizardforcel) 我將想你介紹涉及到排序的兩個算法，你可以用它們操作鏈表。我首先要警告你，如果你打算對數據排序，不要使用鏈表，它們對于排序十分麻煩，并且有更好的數據結構作為替代。我向你介紹這兩種算法只是因為它們難以在鏈表上完成，并且讓你思考如何高效操作它們。為了編寫這本書，我打算將算法放在兩個不同的文件中，`list_algos.h`和`list_algos.c`，之后在`list_algos_test.c`中編寫測試。現在你要按照我的結構，因為它足以把事情做好，但是如果你使用其它的庫要記住這并不是通用的結構。這個練習中我打算給你一些額外的挑戰，并且希望你不要作弊。我打算先給你單元測試，并且讓你打下來。之后讓你基于它們在維基百科中的描述，嘗試實現這個兩個算法，之后看看你的代碼是否和我的類似。 ## 冒泡排序和歸并排序互聯網的強大之處，就是我可以僅僅給你[冒泡排序](http://en.wikipedia.org/wiki/Bubble_sort)和[歸并排序](http://en.wikipedia.org/wiki/Merge_sort)的鏈接，來讓你學習它們。是的，這省了我很多字。現在我要告訴你如何使用它們的偽代碼來實現它們。你可以像這樣來實現算法： + 閱讀描述，并且觀察任何可視化的圖表。 + 使用方框和線條在紙上畫出算法，或者使用一些帶有數字的卡片（比如撲克牌），嘗試手動執行算法。這會向你形象地展示算法的執行過程。 + 在`list_algos.c`文案總創建函數的主干，并且創建`list_algos.h`文件，之后創建測試代碼。 + 編寫第一個測試并且編譯所有東西。 + 回到維基百科頁面，復制粘貼偽代碼到你創建的函數中（不是C代碼）。 + 將偽代碼翻譯成良好的C代碼，就像我教你的那樣，使用你的單元測試來保證它有效。 + 為邊界情況補充一些測試，例如空鏈表，排序號的鏈表，以及其它。 + 對下一個算法重復這些過程并測試。我只是告訴你理解大多數算法的秘密，直到你碰到一些更加麻煩的算法。這里你只是按照維基百科來實現冒泡排序和歸并排序，它們是一個好的起始。 ## 單元測試下面是你應該通過的單元測試： ```c #include "minunit.h" #include <lcthw/list_algos.h> #include <assert.h> #include <string.h> char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"}; #define NUM_VALUES 5 List *create_words() { int i = 0; List *words = List_create(); for(i = 0; i < NUM_VALUES; i++) { List_push(words, values[i]); } return words; } int is_sorted(List *words) { LIST_FOREACH(words, first, next, cur) { if(cur->next && strcmp(cur->value, cur->next->value) > 0) { debug("%s %s", (char *)cur->value, (char *)cur->next->value); return 0; } } return 1; } char *test_bubble_sort() { List *words = create_words(); // should work on a list that needs sorting int rc = List_bubble_sort(words, (List_compare)strcmp); mu_assert(rc == 0, "Bubble sort failed."); mu_assert(is_sorted(words), "Words are not sorted after bubble sort."); // should work on an already sorted list rc = List_bubble_sort(words, (List_compare)strcmp); mu_assert(rc == 0, "Bubble sort of already sorted failed."); mu_assert(is_sorted(words), "Words should be sort if already bubble sorted."); List_destroy(words); // should work on an empty list words = List_create(words); rc = List_bubble_sort(words, (List_compare)strcmp); mu_assert(rc == 0, "Bubble sort failed on empty list."); mu_assert(is_sorted(words), "Words should be sorted if empty."); List_destroy(words); return NULL; } char *test_merge_sort() { List *words = create_words(); // should work on a list that needs sorting List *res = List_merge_sort(words, (List_compare)strcmp); mu_assert(is_sorted(res), "Words are not sorted after merge sort."); List *res2 = List_merge_sort(res, (List_compare)strcmp); mu_assert(is_sorted(res), "Should still be sorted after merge sort."); List_destroy(res2); List_destroy(res); List_destroy(words); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_bubble_sort); mu_run_test(test_merge_sort); return NULL; } RUN_TESTS(all_tests); ``` 建議你從冒泡排序開始，使它正確，之后再測試歸并。我所做的就是編寫函數原型和主干，讓這三個文件能夠編譯，但不能通過測試。之后你將實現填充進入之后才能夠工作。 ## 實現你作弊了嗎？之后的練習中，我只會給你單元測試，并且讓自己實現它。對于你來說，不看這段代碼知道你自己實現它是一種很好的練習。下面是`list_algos.c`和`list_algos.h`的代碼： ```c #ifndef lcthw_List_algos_h #define lcthw_List_algos_h #include <lcthw/list.h> typedef int (*List_compare)(const void *a, const void *b); int List_bubble_sort(List *list, List_compare cmp); List *List_merge_sort(List *list, List_compare cmp); #endif ``` ```c #include <lcthw/list_algos.h> #include <lcthw/dbg.h> inline void ListNode_swap(ListNode *a, ListNode *b) { void *temp = a->value; a->value = b->value; b->value = temp; } int List_bubble_sort(List *list, List_compare cmp) { int sorted = 1; if(List_count(list) <= 1) { return 0; // already sorted } do { sorted = 1; LIST_FOREACH(list, first, next, cur) { if(cur->next) { if(cmp(cur->value, cur->next->value) > 0) { ListNode_swap(cur, cur->next); sorted = 0; } } } } while(!sorted); return 0; } inline List *List_merge(List *left, List *right, List_compare cmp) { List *result = List_create(); void *val = NULL; while(List_count(left) > 0 || List_count(right) > 0) { if(List_count(left) > 0 && List_count(right) > 0) { if(cmp(List_first(left), List_first(right)) <= 0) { val = List_shift(left); } else { val = List_shift(right); } List_push(result, val); } else if(List_count(left) > 0) { val = List_shift(left); List_push(result, val); } else if(List_count(right) > 0) { val = List_shift(right); List_push(result, val); } } return result; } List *List_merge_sort(List *list, List_compare cmp) { if(List_count(list) <= 1) { return list; } List *left = List_create(); List *right = List_create(); int middle = List_count(list) / 2; LIST_FOREACH(list, first, next, cur) { if(middle > 0) { List_push(left, cur->value); } else { List_push(right, cur->value); } middle--; } List *sort_left = List_merge_sort(left, cmp); List *sort_right = List_merge_sort(right, cmp); if(sort_left != left) List_destroy(left); if(sort_right != right) List_destroy(right); return List_merge(sort_left, sort_right, cmp); } ``` 冒泡排序并不難以理解，雖然它非常慢。歸并排序更為復雜，實話講如果我想要犧牲可讀性的話，我會花一點時間來優化代碼。歸并排序有另一種“自底向上”的實現方式，但是它太難了，我就沒有選擇它。就像我剛才說的那樣，在鏈表上編寫排序算法沒有什么意思。你可以把時間都花在使它更快，它比起其他可排序的數據結構會相當版。鏈表的本質決定了如果你需要對數據進行排序，你就不要使用它們（尤其是單向的）。 ## 你會看到什么如果一切都正常工作，你會看到這些： ```sh $ make clean all rm -rf build src/lcthw/list.o src/lcthw/list_algos.o tests/list_algos_tests tests/list_tests rm -f tests/tests.log find . -name "*.gc*" -exec rm {} \; rm -rf `find . -name "*.dSYM" -print` cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list_algos.o src/lcthw/list_algos.c ar rcs build/liblcthw.a src/lcthw/list.o src/lcthw/list_algos.o ranlib build/liblcthw.a cc -shared -o build/liblcthw.so src/lcthw/list.o src/lcthw/list_algos.o cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_algos_tests.c -o tests/list_algos_tests cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_tests.c -o tests/list_tests sh ./tests/runtests.sh Running unit tests: ---- RUNNING: ./tests/list_algos_tests ALL TESTS PASSED Tests run: 2 tests/list_algos_tests PASS ---- RUNNING: ./tests/list_tests ALL TESTS PASSED Tests run: 6 tests/list_tests PASS $ ``` 這個練習之后我就不會向你展示這樣的輸出了，除非有必要向你展示它的工作原理。你應該能知道我運行了測試，并且通過了所有測試。 ## 如何改進退回去查看算法描述，有一些方法可用于改進這些實現，其中一些是很顯然的： + 歸并排序做了大量的鏈表復制和創建操作，尋找減少它們的辦法。 + 歸并排序的維基百科描述提到了一些優化，實現它們。 + 你能使用`List_split`和`List_join`（如果你實現了的話）來改進歸并排序嘛？ + 瀏覽所有防御性編程原則，檢查并提升這一實現的健壯性，避免`NULL`指針，并且創建一個可選的調試級別的不變量，在排序后實現`is_sorted`的功能。 ## 附加題 + 創建單元測試來比較這兩個算法的性能。你需要`man 3 time`來查詢基本的時間函數，并且需要運行足夠的迭代次數，至少以幾秒鐘作為樣本。 + 改變需要排序的鏈表中的數據總量，看看耗時如何變化。 + 尋找方法來創建不同長度的隨機鏈表，并且測量需要多少時間，之后將它可視化并與算法的描述對比。 + 嘗試解釋為什么對鏈表排序十分麻煩。 + 實現`List_insert_sorted`（有序鏈表），它使用`List_compare`，接收一個值，將其插入到正確的位置，使鏈表有序。它與創建鏈表后再進行排序相比怎么樣？ + 嘗試實現維基百科上“自底向上”的歸并排序。上面的代碼已經是C寫的了，所以很容易重新創建，但是要試著理解它的工作原理，并與這里的低效版本對比。