練習32：雙向鏈表 · 笨辦法學C

# 練習32：雙向鏈表 > 原文：[Exercise 32: Double Linked Lists](http://c.learncodethehardway.org/book/ex32.html) > 譯者：[飛龍](https://github.com/wizardforcel) 這本書的目的是教給你計算機實際上如何工作，這也包括多種數據結構和算法函數。計算機自己其實并沒有太大用處。為了讓它們做一些有用的事情，你需要構建數據，之后在這些結構上組織處理。其它編程語言帶有實現所有這些結構的庫，或者帶有直接的語法來創建它們。C需要你手動實現所有數據結構，這使它成為最“完美”的語言，讓你知道它們的工作原理。我的目標是交給你這些數據結構，以及相關算法的知識，來幫助你完成下面這三件事： + 理解Python、Ruby或JavaScript的`data = {"name": "Zed"}`到底做了什么。 + 使用數據結構來解決問題，使你成為更好的C程序員。 + 學習數據結構和算法的核心部分，讓你知道在特定條件下哪個最好。 ## 數據結構是什么。 “數據結構”這個名稱自己就能夠解釋。它是具有特性模型的數據組織方法。這一模型可能設計用于以新的方法處理數據，也可能只是用于將它們更高效地儲存在磁盤上。這本書中我會遵循一些簡單的模式來構建可用的數據結構： + 定義一個結構的主要“外部結構”。 + 定義一個結構的內容，通常是帶有鏈接的節點。 + 創建函數操作它們的函數。 C中還有其它樣式的數據結構，但是這個模式效果很好，并且對于你創建的大部分數據結構都適用。 ## 構建庫對于這本書的剩余部分，當你完成這本書之后，你將會創建一個可用的庫。這個庫會包含下列元素： + 為每個數據結構編寫的頭文件`.h`。 + 為算法編寫的實現文件`.c`。 + 用于測試它們確保有效的單元測試。 + 從頭文件自動生成的文檔。你已經實現了`c-skeleton`（項目框架目錄），使用它來創建一個`liblcthw`項目： ```sh $ cp -r c-skeleton liblcthw $ cd liblcthw/ $ ls LICENSE Makefile README.md bin build src tests $ vim Makefile $ ls src/ dbg.h libex29.c libex29.o $ mkdir src/lcthw $ mv src/dbg.h src/lcthw $ vim tests/minunit.h $ rm src/libex29.* tests/libex29* $ make clean rm -rf build tests/libex29_tests rm -f tests/tests.log find . -name "*.gc*" -exec rm {} \; rm -rf `find . -name "*.dSYM" -print` $ ls tests/ minunit.h runtests.sh $ ``` 這個會話中我執行了下列事情： + 復制了`c-skeleton`。 + 編輯Makefile，將`libYOUR_LIBRARY.a`改為`liblcthw.a`作為新的`TARGET`。 + 創建`src/lcthw`目錄，我們會在里面放入代碼。 + 移動`src/dbg.h`文件到新的目錄中。 + 編輯` tests/minunit.h`，使它使用所包含的`#include <lcthw/dbg.h>`。 + 移除`libex29.*`中我們不需要的源文件和測試文件。 + 清理所有遺留的東西。執行完之后你就準備好開始構建庫了，我打算構建第一個數據結構是雙向鏈表。 ## 雙向鏈表我們將要向`liblcthw`添加的第一個數據結構是雙向鏈表。這是你能夠構建的最簡單的數據結構，并且它擁有針對特定操作的實用屬性。單向鏈表通過指向下一個或上一個元素的節點來工作。“雙向”鏈表持有全部這兩個指針，而“單向”鏈表只持有下一個元素的指針。由于每個節點都有下一個和上一個元素的指針，并且你可以跟蹤聯保的第一個和最后的元素，你就可以快速地執行一些操作。任何涉及到插入和刪除元素的操作會非常快。它對大多數人來說也易于實現。鏈表的主要缺點是，遍歷它涉及到處理沿途每個單個的指針。這意味著搜索、多數排序以及迭代元素會表較慢。這也意味著你不能直接跳過鏈表的隨機一部分。如果換成數組，你就可以直接索引到它的中央，但是鏈表不行。也就是說如果你想要訪問第十個元素，你必須經過1~9。 ### 定義正如在這個練習的介紹部分所說，整個過程的第一步，是編程一個頭文件，帶有正確的C結構定義。 ```c #ifndef lcthw_List_h #define lcthw_List_h #include <stdlib.h> struct ListNode; typedef struct ListNode { struct ListNode *next; struct ListNode *prev; void *value; } ListNode; typedef struct List { int count; ListNode *first; ListNode *last; } List; List *List_create(); void List_destroy(List *list); void List_clear(List *list); void List_clear_destroy(List *list); #define List_count(A) ((A)->count) #define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL) #define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL) void List_push(List *list, void *value); void *List_pop(List *list); void List_unshift(List *list, void *value); void *List_shift(List *list); void *List_remove(List *list, ListNode *node); #define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\ ListNode *V = NULL;\ for(V = _node = L->S; _node != NULL; V = _node = _node->M) #endif ``` 我所做的第一件事就是創建兩個結構，`ListNode`和包含這些節點的`List`。這創建了是將在函數中使用的數據結構，以及隨后定義的宏。如果你瀏覽這些函數，它們看起來非常簡單。當我講到實現時，我會解釋他們，但我更希望你能猜出它們的作用。這些數據結構的工作方式，就是每個`ListNode`都有三個成員。 + 值，它是無類型的指針，存儲我們想在鏈表中放置的東西。 + `ListNode *next`指針，它指向另一個儲存下一個元素的`ListNode `。 + `ListNode *prev`指針，它指向另一個儲存上一個元素的`ListNode `。 `List`結構只是這些`ListNode`結構的容器，它們互聯鏈接組成鏈型。它跟蹤鏈表的`count`，`first`和`last`元素。最后，看一看`src/lcthw/list.h:37`，其中我定義了`LIST_FOREACH`宏。這是個常見的習語，你可以創建一個宏來生成迭代代碼，使用者就不會弄亂了。正確使用這類執行過程來處理數據結構十分困難，所以可以編寫宏來幫助使用者。當我講到實現時，你可以看到我如何使用它。 ### 實現一旦你理解了它們之后，你很可能理解了雙向鏈表如何工作。它只是帶有兩個指針的節點，指向鏈表中前一個和后一個元素。接下來你可以編寫`src/lcthw/list.c`中的代碼，來理解每個操作如何實現。 ```c #include <lcthw/list.h> #include <lcthw/dbg.h> List *List_create() { return calloc(1, sizeof(List)); } void List_destroy(List *list) { LIST_FOREACH(list, first, next, cur) { if(cur->prev) { free(cur->prev); } } free(list->last); free(list); } void List_clear(List *list) { LIST_FOREACH(list, first, next, cur) { free(cur->value); } } void List_clear_destroy(List *list) { List_clear(list); List_destroy(list); } void List_push(List *list, void *value) { ListNode *node = calloc(1, sizeof(ListNode)); check_mem(node); node->value = value; if(list->last == NULL) { list->first = node; list->last = node; } else { list->last->next = node; node->prev = list->last; list->last = node; } list->count++; error: return; } void *List_pop(List *list) { ListNode *node = list->last; return node != NULL ? List_remove(list, node) : NULL; } void List_unshift(List *list, void *value) { ListNode *node = calloc(1, sizeof(ListNode)); check_mem(node); node->value = value; if(list->first == NULL) { list->first = node; list->last = node; } else { node->next = list->first; list->first->prev = node; list->first = node; } list->count++; error: return; } void *List_shift(List *list) { ListNode *node = list->first; return node != NULL ? List_remove(list, node) : NULL; } void *List_remove(List *list, ListNode *node) { void *result = NULL; check(list->first && list->last, "List is empty."); check(node, "node can't be NULL"); if(node == list->first && node == list->last) { list->first = NULL; list->last = NULL; } else if(node == list->first) { list->first = node->next; check(list->first != NULL, "Invalid list, somehow got a first that is NULL."); list->first->prev = NULL; } else if (node == list->last) { list->last = node->prev; check(list->last != NULL, "Invalid list, somehow got a next that is NULL."); list->last->next = NULL; } else { ListNode *after = node->next; ListNode *before = node->prev; after->prev = before; before->next = after; } list->count--; result = node->value; free(node); error: return result; } ``` 我實現了雙向鏈表上的所有操作，它們不能用簡單的宏來完成。比起覆蓋文件中的每一行，我打算為`list.h`和`list.c`中的每個操作提供一個高階的概覽。你需要自己閱讀代碼。 list.h:List_count 返回鏈表中元素數量，它在元素添加或移除時維護。 list.h:List_first 返回鏈表的首個元素，但是并不移除它。 list.h:List_last 返回鏈表的最后一個元素，但是不移除它。 list.h:LIST_FOREACH 遍歷鏈表中的元素。 list.c:List_create 簡單地創建主要的`List`結構。 list.c:List_destroy 銷毀`List`以及其中含有的所有元素。 list.c:List_clear 為釋放每個節點中的值（而不是節點本身）創建的輔助函數。 list.c:List_clear_destroy 清理并銷毀鏈表。它并不十分搞笑因為它對每個元素遍歷兩次。 list.c:List_push 第一個操作演示了鏈表的有點。它向鏈表尾添加新的元素，由于只是一些指針賦值，所以非常快。 list.c:List_pop `List_push`的反向版本，它去除最后一個元素并返回它。 list.c:List_unshift 亦可以輕易對鏈表執行的另一件事，就是快速地向鏈表頭部添加元素。由于找不到合適的詞，這里我把它稱為`unshift`。 list.c:List_shift 類似`List_pop`，但是它移除鏈表的首個元素并返回。 list.c:List_remove 當你執行`List_pop`或`List_shift`時，它執行實際的移除操作。在數據結構中移除數據總是看似比較困難，這個函數也不例外。它需要處理一些條件，取決于被移除的位置，在開頭、在結尾、開頭并且結尾，或者在中間。這些函數大多數都沒什么特別的，你應該能夠輕易描述出來，并且根據代碼來理解它。你應該完全專注于`List_destroy`中的`LIST_FOREACH`如何使用來理解它如何簡化通常的操作。 ## 測試在你編譯它們之前，需要創建測試來確保它們正確執行。 ```c #include "minunit.h" #include <lcthw/list.h> #include <assert.h> static List *list = NULL; char *test1 = "test1 data"; char *test2 = "test2 data"; char *test3 = "test3 data"; char *test_create() { list = List_create(); mu_assert(list != NULL, "Failed to create list."); return NULL; } char *test_destroy() { List_clear_destroy(list); return NULL; } char *test_push_pop() { List_push(list, test1); mu_assert(List_last(list) == test1, "Wrong last value."); List_push(list, test2); mu_assert(List_last(list) == test2, "Wrong last value"); List_push(list, test3); mu_assert(List_last(list) == test3, "Wrong last value."); mu_assert(List_count(list) == 3, "Wrong count on push."); char *val = List_pop(list); mu_assert(val == test3, "Wrong value on pop."); val = List_pop(list); mu_assert(val == test2, "Wrong value on pop."); val = List_pop(list); mu_assert(val == test1, "Wrong value on pop."); mu_assert(List_count(list) == 0, "Wrong count after pop."); return NULL; } char *test_unshift() { List_unshift(list, test1); mu_assert(List_first(list) == test1, "Wrong first value."); List_unshift(list, test2); mu_assert(List_first(list) == test2, "Wrong first value"); List_unshift(list, test3); mu_assert(List_first(list) == test3, "Wrong last value."); mu_assert(List_count(list) == 3, "Wrong count on unshift."); return NULL; } char *test_remove() { // we only need to test the middle remove case since push/shift // already tests the other cases char *val = List_remove(list, list->first->next); mu_assert(val == test2, "Wrong removed element."); mu_assert(List_count(list) == 2, "Wrong count after remove."); mu_assert(List_first(list) == test3, "Wrong first after remove."); mu_assert(List_last(list) == test1, "Wrong last after remove."); return NULL; } char *test_shift() { mu_assert(List_count(list) != 0, "Wrong count before shift."); char *val = List_shift(list); mu_assert(val == test3, "Wrong value on shift."); val = List_shift(list); mu_assert(val == test1, "Wrong value on shift."); mu_assert(List_count(list) == 0, "Wrong count after shift."); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_create); mu_run_test(test_push_pop); mu_run_test(test_unshift); mu_run_test(test_remove); mu_run_test(test_shift); mu_run_test(test_destroy); return NULL; } RUN_TESTS(all_tests); ``` 它簡單地遍歷了每個操作，并且確保它們有效。我在測試中做了簡化，對于整個程序我只創建了一個`List *list`，這解決了為每個測試構建一個`List`的麻煩，但它同時意味著一些測試會受到之前測試的影響。這里我試著是每個測試不改變鏈表，或實際使用上一個測試的結果。 ## 你會看到什么如果你正確完成了每件事，當你執行構建并且運行單元測試是，你會看到： ```sh $ make cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c ar rcs build/liblcthw.a src/lcthw/list.o ranlib build/liblcthw.a cc -shared -o build/liblcthw.so src/lcthw/list.o 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_tests ALL TESTS PASSED Tests run: 6 tests/list_tests PASS $ ``` 確保6個測試運行完畢，以及構建時沒有警告或錯誤，并且成功構建了`build/liblcthw.a`和`build/liblcthw.so`文件。 ## 如何改進我打算告訴你如何改進代碼，而不是使它崩潰。 + 你可以使用`LIST_FOREACH`并在循環中調用`free`來使`List_clear_destroy`更高效。 + 你可以為一些先決條件添加斷言，使其部結構`NULL`值作為`List *list`的參數。 + 你可以添加不變了，來檢查列表的內容始終正確，例如`count`永遠不會`< 0`，如果`count > 0`，`first`不為`NULL`。 + 你可以向頭文件添加文檔，在每個結構、函數和宏之前添加描述其作用的注釋。這些改進執行了防御性編程實踐，并且“加固”了代碼來避免錯誤或使用不當。馬上去做這些事情，之后找到盡可能多的辦法來改進代碼。 ## 附加題 + 研究雙向和單向鏈表，以及什么情況下其中一種優于另一種。 + 研究雙向鏈表的限制。例如，雖然它們對于插入和刪除元素很高效，但是對于變量元素比較慢。 + 還缺少什么你能想到的操作？比如復制、連接、分割等等。實現這些操作，并且為它們編寫單元測試。