練習(xí)32：雙向鏈表

原文：Exercise 32: Double Linked Lists

譯者：飛龍

這本書的目的是教給你計算機實際上如何工作，這也包括多種數(shù)據(jù)結(jié)構(gòu)和算法函數(shù)。計算機自己其實并沒有太大用處。為了讓它們做一些有用的事情，你需要構(gòu)建數(shù)據(jù)，之后在這些結(jié)構(gòu)上組織處理。其它編程語言帶有實現(xiàn)所有這些結(jié)構(gòu)的庫，或者帶有直接的語法來創(chuàng)建它們。C需要你手動實現(xiàn)所有數(shù)據(jù)結(jié)構(gòu)，這使它成為最“完美”的語言，讓你知道它們的工作原理。

我的目標是交給你這些數(shù)據(jù)結(jié)構(gòu)，以及相關(guān)算法的知識，來幫助你完成下面這三件事：

• 理解Python、Ruby或JavaScript的data = {"name": "Zed"}到底做了什么。
• 使用數(shù)據(jù)結(jié)構(gòu)來解決問題，使你成為更好的C程序員。
• 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的核心部分，讓你知道在特定條件下哪個最好。

數(shù)據(jù)結(jié)構(gòu)是什么。

“數(shù)據(jù)結(jié)構(gòu)”這個名稱自己就能夠解釋。它是具有特性模型的數(shù)據(jù)組織方法。這一模型可能設(shè)計用于以新的方法處理數(shù)據(jù)，也可能只是用于將它們更高效地儲存在磁盤上。這本書中我會遵循一些簡單的模式來構(gòu)建可用的數(shù)據(jù)結(jié)構(gòu)：

• 定義一個結(jié)構(gòu)的主要“外部結(jié)構(gòu)”。
• 定義一個結(jié)構(gòu)的內(nèi)容，通常是帶有鏈接的節(jié)點。
• 創(chuàng)建函數(shù)操作它們的函數(shù)。

C中還有其它樣式的數(shù)據(jù)結(jié)構(gòu)，但是這個模式效果很好，并且對于你創(chuàng)建的大部分數(shù)據(jù)結(jié)構(gòu)都適用。

構(gòu)建庫

對于這本書的剩余部分，當(dāng)你完成這本書之后，你將會創(chuàng)建一個可用的庫。這個庫會包含下列元素：

• 為每個數(shù)據(jù)結(jié)構(gòu)編寫的頭文件.h。
• 為算法編寫的實現(xiàn)文件.c。
• 用于測試它們確保有效的單元測試。
• 從頭文件自動生成的文檔。

你已經(jīng)實現(xiàn)了c-skeleton（項目框架目錄），使用它來創(chuàng)建一個liblcthw項目：

$ 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
$

這個會話中我執(zhí)行了下列事情：

• 復(fù)制了c-skeleton。
• 編輯Makefile，將libYOUR_LIBRARY.a改為liblcthw.a作為新的TARGET。
• 創(chuàng)建src/lcthw目錄，我們會在里面放入代碼。
• 移動src/dbg.h文件到新的目錄中。
• 編輯tests/minunit.h，使它使用所包含的#include <lcthw/dbg.h>。
• 移除libex29.*中我們不需要的源文件和測試文件。
• 清理所有遺留的東西。

執(zhí)行完之后你就準備好開始構(gòu)建庫了，我打算構(gòu)建第一個數(shù)據(jù)結(jié)構(gòu)是雙向鏈表。

雙向鏈表

我們將要向liblcthw添加的第一個數(shù)據(jù)結(jié)構(gòu)是雙向鏈表。這是你能夠構(gòu)建的最簡單的數(shù)據(jù)結(jié)構(gòu)，并且它擁有針對特定操作的實用屬性。單向鏈表通過指向下一個或上一個元素的節(jié)點來工作?！半p向”鏈表持有全部這兩個指針，而“單向”鏈表只持有下一個元素的指針。

由于每個節(jié)點都有下一個和上一個元素的指針，并且你可以跟蹤聯(lián)保的第一個和最后的元素，你就可以快速地執(zhí)行一些操作。任何涉及到插入和刪除元素的操作會非常快。它對大多數(shù)人來說也易于實現(xiàn)。

鏈表的主要缺點是，遍歷它涉及到處理沿途每個單個的指針。這意味著搜索、多數(shù)排序以及迭代元素會表較慢。這也意味著你不能直接跳過鏈表的隨機一部分。如果換成數(shù)組，你就可以直接索引到它的中央，但是鏈表不行。也就是說如果你想要訪問第十個元素，你必須經(jīng)過1~9。

定義

正如在這個練習(xí)的介紹部分所說，整個過程的第一步，是編程一個頭文件，帶有正確的C結(jié)構(gòu)定義。

#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

我所做的第一件事就是創(chuàng)建兩個結(jié)構(gòu)，ListNode和包含這些節(jié)點的List。這創(chuàng)建了是將在函數(shù)中使用的數(shù)據(jù)結(jié)構(gòu)，以及隨后定義的宏。如果你瀏覽這些函數(shù)，它們看起來非常簡單。當(dāng)我講到實現(xiàn)時，我會解釋他們，但我更希望你能猜出它們的作用。

這些數(shù)據(jù)結(jié)構(gòu)的工作方式，就是每個ListNode都有三個成員。

• 值，它是無類型的指針，存儲我們想在鏈表中放置的東西。
• ListNode *next指針，它指向另一個儲存下一個元素的ListNode。
• ListNode *prev指針，它指向另一個儲存上一個元素的ListNode。

List結(jié)構(gòu)只是這些ListNode結(jié)構(gòu)的容器，它們互聯(lián)鏈接組成鏈型。它跟蹤鏈表的count，first和last元素。

最后，看一看src/lcthw/list.h:37，其中我定義了LIST_FOREACH宏。這是個常見的習(xí)語，你可以創(chuàng)建一個宏來生成迭代代碼，使用者就不會弄亂了。正確使用這類執(zhí)行過程來處理數(shù)據(jù)結(jié)構(gòu)十分困難，所以可以編寫宏來幫助使用者。當(dāng)我講到實現(xiàn)時，你可以看到我如何使用它。

實現(xiàn)

一旦你理解了它們之后，你很可能理解了雙向鏈表如何工作。它只是帶有兩個指針的節(jié)點，指向鏈表中前一個和后一個元素。接下來你可以編寫src/lcthw/list.c中的代碼，來理解每個操作如何實現(xiàn)。

#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;
}

我實現(xiàn)了雙向鏈表上的所有操作，它們不能用簡單的宏來完成。比起覆蓋文件中的每一行，我打算為list.h和list.c中的每個操作提供一個高階的概覽。你需要自己閱讀代碼。

list.h:List_count

返回鏈表中元素數(shù)量，它在元素添加或移除時維護。

list.h:List_first

返回鏈表的首個元素，但是并不移除它。

list.h:List_last

返回鏈表的最后一個元素，但是不移除它。

list.h:LIST_FOREACH

遍歷鏈表中的元素。

list.c:List_create

簡單地創(chuàng)建主要的List結(jié)構(gòu)。

list.c:List_destroy

銷毀List以及其中含有的所有元素。

list.c:List_clear

為釋放每個節(jié)點中的值（而不是節(jié)點本身）創(chuàng)建的輔助函數(shù)。

list.c:List_clear_destroy

清理并銷毀鏈表。它并不十分搞笑因為它對每個元素遍歷兩次。

list.c:List_push

第一個操作演示了鏈表的有點。它向鏈表尾添加新的元素，由于只是一些指針賦值，所以非?？?。

list.c:List_pop

List_push的反向版本，它去除最后一個元素并返回它。

list.c:List_unshift

亦可以輕易對鏈表執(zhí)行的另一件事，就是快速地向鏈表頭部添加元素。由于找不到合適的詞，這里我把它稱為unshift。

list.c:List_shift

類似List_pop，但是它移除鏈表的首個元素并返回。

list.c:List_remove

當(dāng)你執(zhí)行List_pop或List_shift時，它執(zhí)行實際的移除操作。在數(shù)據(jù)結(jié)構(gòu)中移除數(shù)據(jù)總是看似比較困難，這個函數(shù)也不例外。它需要處理一些條件，取決于被移除的位置，在開頭、在結(jié)尾、開頭并且結(jié)尾，或者在中間。

這些函數(shù)大多數(shù)都沒什么特別的，你應(yīng)該能夠輕易描述出來，并且根據(jù)代碼來理解它。你應(yīng)該完全專注于List_destroy中的LIST_FOREACH如何使用來理解它如何簡化通常的操作。

測試

在你編譯它們之前，需要創(chuàng)建測試來確保它們正確執(zhí)行。

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

它簡單地遍歷了每個操作，并且確保它們有效。我在測試中做了簡化，對于整個程序我只創(chuàng)建了一個List *list，這解決了為每個測試構(gòu)建一個List的麻煩，但它同時意味著一些測試會受到之前測試的影響。這里我試著是每個測試不改變鏈表，或?qū)嶋H使用上一個測試的結(jié)果。

你會看到什么

如果你正確完成了每件事，當(dāng)你執(zhí)行構(gòu)建并且運行單元測試是，你會看到：

$ 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個測試運行完畢，以及構(gòu)建時沒有警告或錯誤，并且成功構(gòu)建了build/liblcthw.a和build/liblcthw.so文件。

如何改進

我打算告訴你如何改進代碼，而不是使它崩潰。

• 你可以使用LIST_FOREACH并在循環(huán)中調(diào)用free來使List_clear_destroy更高效。
• 你可以為一些先決條件添加斷言，使其部結(jié)構(gòu)NULL值作為List *list的參數(shù)。
• 你可以添加不變了，來檢查列表的內(nèi)容始終正確，例如count永遠不會< 0，如果count > 0，first不為NULL。
• 你可以向頭文件添加文檔，在每個結(jié)構(gòu)、函數(shù)和宏之前添加描述其作用的注釋。

這些改進執(zhí)行了防御性編程實踐，并且“加固”了代碼來避免錯誤或使用不當(dāng)。馬上去做這些事情，之后找到盡可能多的辦法來改進代碼。

附加題

• 研究雙向和單向鏈表，以及什么情況下其中一種優(yōu)于另一種。
• 研究雙向鏈表的限制。例如，雖然它們對于插入和刪除元素很高效，但是對于變量元素比較慢。
• 還缺少什么你能想到的操作？比如復(fù)制、連接、分割等等。實現(xiàn)這些操作，并且為它們編寫單元測試。