# 练习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写的了，所以很容易重新创建，但是要试着理解它的工作原理，并与这里的低效版本对比。
- 笨办法学C 中文版
- 前言
- 导言：C的笛卡尔之梦
- 练习0：准备
- 练习1：启用编译器
- 练习2：用Make来代替Python
- 练习3：格式化输出
- 练习4：Valgrind 介绍
- 练习5：一个C程序的结构
- 练习6：变量类型
- 练习7：更多变量和一些算术
- 练习8：大小和数组
- 练习9：数组和字符串
- 练习10：字符串数组和循环
- 练习11：While循环和布尔表达式
- 练习12：If，Else If，Else
- 练习13：Switch语句
- 练习14：编写并使用函数
- 练习15：指针，可怕的指针
- 练习16：结构体和指向它们的指针
- 练习17：堆和栈的内存分配
- 练习18：函数指针
- 练习19：一个简单的对象系统
- 练习20：Zed的强大的调试宏
- 练习21：高级数据类型和控制结构
- 练习22：栈、作用域和全局
- 练习23：认识达夫设备
- 练习24：输入输出和文件
- 练习25：变参函数
- 练习26：编写第一个真正的程序
- 练习27：创造性和防御性编程
- 练习28：Makefile 进阶
- 练习29：库和链接
- 练习30：自动化测试
- 练习31：代码调试
- 练习32：双向链表
- 练习33：链表算法
- 练习34：动态数组
- 练习35：排序和搜索
- 练习36：更安全的字符串
- 练习37：哈希表
- 练习38：哈希算法
- 练习39：字符串算法
- 练习40：二叉搜索树
- 练习41：将 Cachegrind 和 Callgrind 用于性能调优
- 练习42：栈和队列
- 练习43：一个简单的统计引擎
- 练习44：环形缓冲区
- 练习45：一个简单的TCP/IP客户端
- 练习46：三叉搜索树
- 练习47：一个快速的URL路由
- 后记：“解构 K&R C” 已死