練習33：鏈表算法

原文：Exercise 33: Linked List Algorithms

譯者：飛龍

我將想你介紹涉及到排序的兩個算法，你可以用它們操作鏈表促王。我首先要警告你混驰，如果你打算對數(shù)據(jù)排序系草，不要使用鏈表撕贞，它們對于排序十分麻煩，并且有更好的數(shù)據(jù)結(jié)構(gòu)作為替代朋蔫。我向你介紹這兩種算法只是因為它們難以在鏈表上完成罚渐，并且讓你思考如何高效操作它們。

為了編寫這本書驯妄，我打算將算法放在兩個不同的文件中荷并，list_algos.h和list_algos.c，之后在list_algos_test.c中編寫測試∏嗳樱現(xiàn)在你要按照我的結(jié)構(gòu)源织，因為它足以把事情做好，但是如果你使用其它的庫要記住這并不是通用的結(jié)構(gòu)微猖。

這個練習中我打算給你一些額外的挑戰(zhàn)谈息，并且希望你不要作弊。我打算先給你單元測試励两，并且讓你打下來黎茎。之后讓你基于它們在維基百科中的描述，嘗試實現(xiàn)這個兩個算法当悔，之后看看你的代碼是否和我的類似傅瞻。

冒泡排序和歸并排序

互聯(lián)網(wǎng)的強大之處，就是我可以僅僅給你冒泡排序和歸并排序的鏈接盲憎，來讓你學習它們嗅骄。是的，這省了我很多字”恚現(xiàn)在我要告訴你如何使用它們的偽代碼來實現(xiàn)它們溺森。你可以像這樣來實現(xiàn)算法：

• 閱讀描述，并且觀察任何可視化的圖表窑眯。
• 使用方框和線條在紙上畫出算法屏积，或者使用一些帶有數(shù)字的卡片（比如撲克牌），嘗試手動執(zhí)行算法磅甩。這會向你形象地展示算法的執(zhí)行過程炊林。
• 在list_algos.c文案總創(chuàng)建函數(shù)的主干，并且創(chuàng)建list_algos.h文件卷要，之后創(chuàng)建測試代碼渣聚。
• 編寫第一個測試并且編譯所有東西。
• 回到維基百科頁面僧叉，復制粘貼偽代碼到你創(chuàng)建的函數(shù)中（不是C代碼）奕枝。
• 將偽代碼翻譯成良好的C代碼，就像我教你的那樣瓶堕，使用你的單元測試來保證它有效隘道。
• 為邊界情況補充一些測試，例如空鏈表郎笆，排序號的鏈表谭梗，以及其它。
• 對下一個算法重復這些過程并測試题画。

我只是告訴你理解大多數(shù)算法的秘密默辨，直到你碰到一些更加麻煩的算法。這里你只是按照維基百科來實現(xiàn)冒泡排序和歸并排序苍息，它們是一個好的起始缩幸。

單元測試

下面是你應該通過的單元測試：

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

建議你從冒泡排序開始，使它正確竞思，之后再測試歸并表谊。我所做的就是編寫函數(shù)原型和主干，讓這三個文件能夠編譯盖喷，但不能通過測試爆办。之后你將實現(xiàn)填充進入之后才能夠工作。

實現(xiàn)

你作弊了嗎课梳？之后的練習中距辆，我只會給你單元測試余佃，并且讓自己實現(xiàn)它。對于你來說跨算，不看這段代碼知道你自己實現(xiàn)它是一種很好的練習爆土。下面是list_algos.c和list_algos.h的代碼：

#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

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

冒泡排序并不難以理解，雖然它非常慢诸蚕。歸并排序更為復雜步势，實話講如果我想要犧牲可讀性的話，我會花一點時間來優(yōu)化代碼背犯。

歸并排序有另一種“自底向上”的實現(xiàn)方式坏瘩，但是它太難了，我就沒有選擇它漠魏。就像我剛才說的那樣倔矾，在鏈表上編寫排序算法沒有什么意思。你可以把時間都花在使它更快蛉幸，它比起其他可排序的數(shù)據(jù)結(jié)構(gòu)會相當版破讨。鏈表的本質(zhì)決定了如果你需要對數(shù)據(jù)進行排序，你就不要使用它們（尤其是單向的）奕纫。

你會看到什么

如果一切都正常工作提陶，你會看到這些：

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

這個練習之后我就不會向你展示這樣的輸出了，除非有必要向你展示它的工作原理匹层。你應該能知道我運行了測試隙笆，并且通過了所有測試。

如何改進

退回去查看算法描述升筏，有一些方法可用于改進這些實現(xiàn)撑柔，其中一些是很顯然的：

• 歸并排序做了大量的鏈表復制和創(chuàng)建操作，尋找減少它們的辦法您访。
• 歸并排序的維基百科描述提到了一些優(yōu)化铅忿，實現(xiàn)它們。
• 你能使用List_split和List_join（如果你實現(xiàn)了的話）來改進歸并排序嘛灵汪？
• 瀏覽所有防御性編程原則檀训，檢查并提升這一實現(xiàn)的健壯性，避免NULL指針享言，并且創(chuàng)建一個可選的調(diào)試級別的不變量峻凫，在排序后實現(xiàn)is_sorted的功能。

附加題

• 創(chuàng)建單元測試來比較這兩個算法的性能览露。你需要man 3 time來查詢基本的時間函數(shù)荧琼，并且需要運行足夠的迭代次數(shù)，至少以幾秒鐘作為樣本。
• 改變需要排序的鏈表中的數(shù)據(jù)總量命锄，看看耗時如何變化堰乔。
• 尋找方法來創(chuàng)建不同長度的隨機鏈表，并且測量需要多少時間累舷，之后將它可視化并與算法的描述對比浩考。
• 嘗試解釋為什么對鏈表排序十分麻煩夹孔。
• 實現(xiàn)List_insert_sorted（有序鏈表）被盈，它使用List_compare，接收一個值搭伤，將其插入到正確的位置只怎，使鏈表有序。它與創(chuàng)建鏈表后再進行排序相比怎么樣怜俐？
• 嘗試實現(xiàn)維基百科上“自底向上”的歸并排序身堡。上面的代碼已經(jīng)是C寫的了，所以很容易重新創(chuàng)建拍鲤，但是要試著理解它的工作原理贴谎，并與這里的低效版本對比。