# 练习34：动态数组
> 原文：[Exercise 34: Dynamic Array](http://c.learncodethehardway.org/book/ex34.html)
> 译者：[飞龙](https://github.com/wizardforcel)
动态数组是自增长的数组，它与链表有很多相同的特性。它通常占据更少的空间，跑得更快，还有一些其它的优势属性。这个练习会涉及到它的一些缺点，比如从开头移除元素会很慢，并给出解决方案（只从末尾移除）。
动态数组简单地实现为`void **`指针的数组，它是预分配内存的，并且指向数据。在链表中你创建了完整的结构体来储存`void *value`指针，但是动态数组中你只需要一个储存它们的单个数组。也就是说，你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。
我会给你头文件作为起始，你需要为实现打下它们：
```c
#ifndef _DArray_h
#define _DArray_h
#include <stdlib.h>
#include <assert.h>
#include <lcthw/dbg.h>
typedef struct DArray {
int end;
int max;
size_t element_size;
size_t expand_rate;
void **contents;
} DArray;
DArray *DArray_create(size_t element_size, size_t initial_max);
void DArray_destroy(DArray *array);
void DArray_clear(DArray *array);
int DArray_expand(DArray *array);
int DArray_contract(DArray *array);
int DArray_push(DArray *array, void *el);
void *DArray_pop(DArray *array);
void DArray_clear_destroy(DArray *array);
#define DArray_last(A) ((A)->contents[(A)->end - 1])
#define DArray_first(A) ((A)->contents[0])
#define DArray_end(A) ((A)->end)
#define DArray_count(A) DArray_end(A)
#define DArray_max(A) ((A)->max)
#define DEFAULT_EXPAND_RATE 300
static inline void DArray_set(DArray *array, int i, void *el)
{
check(i < array->max, "darray attempt to set past max");
if(i > array->end) array->end = i;
array->contents[i] = el;
error:
return;
}
static inline void *DArray_get(DArray *array, int i)
{
check(i < array->max, "darray attempt to get past max");
return array->contents[i];
error:
return NULL;
}
static inline void *DArray_remove(DArray *array, int i)
{
void *el = array->contents[i];
array->contents[i] = NULL;
return el;
}
static inline void *DArray_new(DArray *array)
{
check(array->element_size > 0, "Can't use DArray_new on 0 size darrays.");
return calloc(1, array->element_size);
error:
return NULL;
}
#define DArray_free(E) free((E))
#endif
```
这个头文件向你展示了`static inline`的新技巧，它就类似`#define`宏的工作方式，但是它们更清楚，并且易于编写。如果你需要创建一块代码作为宏，并且不需要代码生成，可以使用`static inline`函数。
为链表生成`for`循环的`LIST_FOREACH`不可能写为`static inline`函数，因为它需要生成循环的内部代码块。实现它的唯一方式是灰调函数，但是这不够块，并且难以使用。
之后我会修改代码，并且让你创建`DArray`的单元测试。
```c
#include "minunit.h"
#include <lcthw/darray.h>
static DArray *array = NULL;
static int *val1 = NULL;
static int *val2 = NULL;
char *test_create()
{
array = DArray_create(sizeof(int), 100);
mu_assert(array != NULL, "DArray_create failed.");
mu_assert(array->contents != NULL, "contents are wrong in darray");
mu_assert(array->end == 0, "end isn't at the right spot");
mu_assert(array->element_size == sizeof(int), "element size is wrong.");
mu_assert(array->max == 100, "wrong max length on initial size");
return NULL;
}
char *test_destroy()
{
DArray_destroy(array);
return NULL;
}
char *test_new()
{
val1 = DArray_new(array);
mu_assert(val1 != NULL, "failed to make a new element");
val2 = DArray_new(array);
mu_assert(val2 != NULL, "failed to make a new element");
return NULL;
}
char *test_set()
{
DArray_set(array, 0, val1);
DArray_set(array, 1, val2);
return NULL;
}
char *test_get()
{
mu_assert(DArray_get(array, 0) == val1, "Wrong first value.");
mu_assert(DArray_get(array, 1) == val2, "Wrong second value.");
return NULL;
}
char *test_remove()
{
int *val_check = DArray_remove(array, 0);
mu_assert(val_check != NULL, "Should not get NULL.");
mu_assert(*val_check == *val1, "Should get the first value.");
mu_assert(DArray_get(array, 0) == NULL, "Should be gone.");
DArray_free(val_check);
val_check = DArray_remove(array, 1);
mu_assert(val_check != NULL, "Should not get NULL.");
mu_assert(*val_check == *val2, "Should get the first value.");
mu_assert(DArray_get(array, 1) == NULL, "Should be gone.");
DArray_free(val_check);
return NULL;
}
char *test_expand_contract()
{
int old_max = array->max;
DArray_expand(array);
mu_assert((unsigned int)array->max == old_max + array->expand_rate, "Wrong size after expand.");
DArray_contract(array);
mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");
DArray_contract(array);
mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");
return NULL;
}
char *test_push_pop()
{
int i = 0;
for(i = 0; i < 1000; i++) {
int *val = DArray_new(array);
*val = i * 333;
DArray_push(array, val);
}
mu_assert(array->max == 1201, "Wrong max size.");
for(i = 999; i >= 0; i--) {
int *val = DArray_pop(array);
mu_assert(val != NULL, "Shouldn't get a NULL.");
mu_assert(*val == i * 333, "Wrong value.");
DArray_free(val);
}
return NULL;
}
char * all_tests() {
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_new);
mu_run_test(test_set);
mu_run_test(test_get);
mu_run_test(test_remove);
mu_run_test(test_expand_contract);
mu_run_test(test_push_pop);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
这向你展示了所有操作都如何使用，它会使`DArray`的实现变得容易：
```c
#include <lcthw/darray.h>
#include <assert.h>
DArray *DArray_create(size_t element_size, size_t initial_max)
{
DArray *array = malloc(sizeof(DArray));
check_mem(array);
array->max = initial_max;
check(array->max > 0, "You must set an initial_max > 0.");
array->contents = calloc(initial_max, sizeof(void *));
check_mem(array->contents);
array->end = 0;
array->element_size = element_size;
array->expand_rate = DEFAULT_EXPAND_RATE;
return array;
error:
if(array) free(array);
return NULL;
}
void DArray_clear(DArray *array)
{
int i = 0;
if(array->element_size > 0) {
for(i = 0; i < array->max; i++) {
if(array->contents[i] != NULL) {
free(array->contents[i]);
}
}
}
}
static inline int DArray_resize(DArray *array, size_t newsize)
{
array->max = newsize;
check(array->max > 0, "The newsize must be > 0.");
void *contents = realloc(array->contents, array->max * sizeof(void *));
// check contents and assume realloc doesn't harm the original on error
check_mem(contents);
array->contents = contents;
return 0;
error:
return -1;
}
int DArray_expand(DArray *array)
{
size_t old_max = array->max;
check(DArray_resize(array, array->max + array->expand_rate) == 0,
"Failed to expand array to new size: %d",
array->max + (int)array->expand_rate);
memset(array->contents + old_max, 0, array->expand_rate + 1);
return 0;
error:
return -1;
}
int DArray_contract(DArray *array)
{
int new_size = array->end < (int)array->expand_rate ? (int)array->expand_rate : array->end;
return DArray_resize(array, new_size + 1);
}
void DArray_destroy(DArray *array)
{
if(array) {
if(array->contents) free(array->contents);
free(array);
}
}
void DArray_clear_destroy(DArray *array)
{
DArray_clear(array);
DArray_destroy(array);
}
int DArray_push(DArray *array, void *el)
{
array->contents[array->end] = el;
array->end++;
if(DArray_end(array) >= DArray_max(array)) {
return DArray_expand(array);
} else {
return 0;
}
}
void *DArray_pop(DArray *array)
{
check(array->end - 1 >= 0, "Attempt to pop from empty array.");
void *el = DArray_remove(array, array->end - 1);
array->end--;
if(DArray_end(array) > (int)array->expand_rate && DArray_end(array) % array->expand_rate) {
DArray_contract(array);
}
return el;
error:
return NULL;
}
```
这占你展示了另一种处理复杂代码的方法，观察头文件并阅读单元测试，而不是一头扎进`.c`实现中。这种“具体的抽象”让你理解代码如何一起工作，并且更容易记住。
## 优点和缺点
`DArray`在你需要这些操作时占优势。
+ 迭代。你可以仅仅使用基本的`for`循环，使用`DArray_count`和`DArray_get`来完成任务。不需要任何特殊的宏。并且由于不处理指针，它非常快。
+ 索引。你可以使用`DArray_get`和`DArray_set`来随机访问任何元素，但是`List`上你就必须经过第N个元素来访问第N+1个元素。
+ 销毁。你只需要以两个操作销毁结构体和`content`。但是`List`需要一些列的`free`调用同时遍历每个元素。
+ 克隆。你只需要复制结构体和`content`，用两步复制整个结构。`List`需要遍历所有元素并且复制每个`ListNode`和值。
+ 排序。你已经见过了，如果你需要对数据排序，`List`非常麻烦。`DArray`上可以实现所有高效的排序算法，因为你可以随机访问任何元素。
+ 大量数据。如果你需要储存大量数据，`DArray`由于基于`content`，比起相同数量的`ListNode`占用更少空间而占优。
然而`List`在这些操作上占优势。
+ 在开头插入和移除元素。`DArray`需要特殊的优化来高效地完成它，并且通常还需要一些复制操作。
+ 分割和连接。`List`只需要复制一些指针就能完成，但是`DArray`需要复制涉及到的所有数组。
+ 少量数据。如果你只需要存储几个元素，通常使用`List`所需的空间要少于`DArray`，因为`DArray`需要考虑到日后的添加而扩展背后的空间，但是`List`只需要元素所需的空间。
考虑到这些，我更倾向使用`DArray`来完成其它人使用`List`所做的大部分事情。对于任何需要少量节点并且在两端插入删除的，我会使用`List`。我会想你展示两个相似的数据结构，叫做`Stack`和`Queue`，它们也很重要。
## 如何改进
像往常一样，浏览每个函数和操作，并且执行防御性编程检查，以及添加先决条件、不变量等任何可以使实现更健壮的东西。
## 附加题
+ 改进单元测试来覆盖耕作操作，并使用`for`循环来测试迭代。
+ 研究`DArray`上如何实现冒泡排序和归并排序，但是不要马上实现它们。我会在下一张实现`DArray`的算法，之后你可以完成它。
+ 为一些常用的操作编写一些性能测试，并与`List`中的相同操作比较。你已经做过很多次了，但是这次需要编写重复执行所涉及操作的单元测试，之后在主运行器中计时。
+ 观察`DArray_expand`如何使用固定增长（`size + 300`）来实现。通常动态数组都以倍数增长（`size * 2`）的方式实现，但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言，并且看看什么情况下需要倍数增长而不是固定增长。
- 笨办法学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” 已死