# 练习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`。
+ 你可以向头文件添加文档,在每个结构、函数和宏之前添加描述其作用的注释。
这些改进执行了防御性编程实践,并且“加固”了代码来避免错误或使用不当。马上去做这些事情,之后找到尽可能多的办法来改进代码。
## 附加题
+ 研究双向和单向链表,以及什么情况下其中一种优于另一种。
+ 研究双向链表的限制。例如,虽然它们对于插入和删除元素很高效,但是对于变量元素比较慢。
+ 还缺少什么你能想到的操作?比如复制、连接、分割等等。实现这些操作,并且为它们编写单元测试。
- 笨办法学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” 已死
- 捐赠名单