笨办法学C 练习33:链表算法

练习33:链表算法

原文:Exercise 33: Linked List Algorithms

译者:飞龙

我将想你介绍涉及到排序的两个算法,你可以用它们操作链表。我首先要警告你,如果你打算对数据排序,不要使用链表,它们对于排序十分麻烦,并且有更好的数据结构作为替代。我向你介绍这两种算法只是因为它们难以在链表上完成,并且让你思考如何高效操作它们。

为了编写这本书,我打算将算法放在两个不同的文件中,list_algos.h和list_algos.c,之后在list_algos_test.c中编写测试。现在你要按照我的结构,因为它足以把事情做好,但是如果你使用其它的库要记住这并不是通用的结构。

这个练习中我打算给你一些额外的挑战,并且希望你不要作弊。我打算先给你单元测试,并且让你打下来。之后让你基于它们在维基百科中的描述,尝试实现这个两个算法,之后看看你的代码是否和我的类似。

冒泡排序和归并排序

互联网的强大之处,就是我可以仅仅给你冒泡排序和归并排序的链接,来让你学习它们。是的,这省了我很多字。现在我要告诉你如何使用它们的伪代码来实现它们。你可以像这样来实现算法:

  1. 阅读描述,并且观察任何可视化的图表。

  2. 使用方框和线条在纸上画出算法,或者使用一些带有数字的卡片(比如扑克牌),尝试手动执行算法。这会向你形象地展示算法的执行过程。

  3. 在list_algos.c文案总创建函数的主干,并且创建list_algos.h文件,之后创建测试代码。

  4. 编写第一个测试并且编译所有东西。

  5. 回到维基百科页面,复制粘贴伪代码到你创建的函数中(不是C代码)。

  6. 将伪代码翻译成良好的C代码,就像我教你的那样,使用你的单元测试来保证它有效。

  7. 为边界情况补充一些测试,例如空链表,排序号的链表,以及其它。

  8. 对下一个算法重复这些过程并测试。

我只是告诉你理解大多数算法的秘密,直到你碰到一些更加麻烦的算法。这里你只是按照维基百科来实现冒泡排序和归并排序,它们是一个好的起始。

单元测试

下面是你应该通过的单元测试:

# include "minunit.h"# include # include # include char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"};# define NUM_VALUES 5List *create_words(){    int i = 0;    List *words = List_create();    for(i = 0; i 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的代码:

# ifndef lcthw_List_algos_h# define lcthw_List_algos_h# include 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 # include 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) 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);            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)  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);}

冒泡排序并不难以理解,虽然它非常慢。归并排序更为复杂,实话讲如果我想要牺牲可读性的话,我会花一点时间来优化代码。

归并排序有另一种“自底向上”的实现方式,但是它太难了,我就没有选择它。就像我刚才说的那样,在链表上编写排序算法没有什么意思。你可以把时间都花在使它更快,它比起其他可排序的数据结构会相当版。链表的本质决定了如果你需要对数据进行排序,你就不要使用它们(尤其是单向的)。

你会看到什么

如果一切都正常工作,你会看到这些:

$ make clean allrm -rf build src/lcthw/list.o src/lcthw/list_algos.o tests/list_algos_tests tests/list_testsrm -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.ccc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list_algos.o src/lcthw/list_algos.car rcs build/liblcthw.a src/lcthw/list.o src/lcthw/list_algos.oranlib build/liblcthw.acc -shared -o build/liblcthw.so src/lcthw/list.o src/lcthw/list_algos.occ -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list_algos_tests.c   -o tests/list_algos_testscc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list_tests.c   -o tests/list_testssh ./tests/runtests.shRunning unit tests:----RUNNING: ./tests/list_algos_testsALL TESTS PASSEDTests run: 2tests/list_algos_tests PASS----RUNNING: ./tests/list_testsALL TESTS PASSEDTests run: 6tests/list_tests PASS$

这个练习之后我就不会向你展示这样的输出了,除非有必要向你展示它的工作原理。你应该能知道我运行了测试,并且通过了所有测试。

如何改进

退回去查看算法描述,有一些方法可用于改进这些实现,其中一些是很显然的:

  1. 归并排序做了大量的链表复制和创建操作,寻找减少它们的办法。

  2. 归并排序的维基百科描述提到了一些优化,实现它们。

  3. 你能使用List_split和List_join(如果你实现了的话)来改进归并排序嘛?

  4. 浏览所有防御性编程原则,检查并提升这一实现的健壮性,避免NULL指针,并且创建一个可选的调试级别的不变量,在排序后实现is_sorted的功能。

附加题

  1. 创建单元测试来比较这两个算法的性能。你需要man 3 time来查询基本的时间函数,并且需要运行足够的迭代次数,至少以几秒钟作为样本。

  2. 改变需要排序的链表中的数据总量,看看耗时如何变化。

  3. 寻找方法来创建不同长度的随机链表,并且测量需要多少时间,之后将它可视化并与算法的描述对比。

  4. 尝试解释为什么对链表排序十分麻烦。

  5. 实现List_insert_sorted(有序链表),它使用List_compare,接收一个值,将其插入到正确的位置,使链表有序。它与创建链表后再进行排序相比怎么样?

  6. 尝试实现维基百科上“自底向上”的归并排序。上面的代码已经是C写的了,所以很容易重新创建,但是要试着理解它的工作原理,并与这里的低效版本对比。

关键字:c, lxthw

版权声明

本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部