笨办法学C 练习34:动态数组

练习34:动态数组

原文:Exercise 34: Dynamic Array

译者:飞龙

动态数组是自增长的数组,它与链表有很多相同的特性。它通常占据更少的空间,跑得更快,还有一些其它的优势属性。这个练习会涉及到它的一些缺点,比如从开头移除元素会很慢,并给出解决方案(只从末尾移除)。

动态数组简单地实现为void 指针的数组,它是预分配内存的,并且指向数据。在链表中你创建了完整的结构体来储存void *value指针,但是动态数组中你只需要一个储存它们的单个数组。也就是说,你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。

我会给你头文件作为起始,你需要为实现打下它们:

# ifndef _DArray_h# define _DArray_h# include # include # include 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 300static inline void DArray_set(DArray *array, int i, void *el){    check(i 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 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的单元测试。

# include "minunit.h"# include 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 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的实现变得容易:

# include # include 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 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 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在你需要这些操作时占优势。

  1. 迭代。你可以仅仅使用基本的for循环,使用DArray_count和DArray_get来完成任务。不需要任何特殊的宏。并且由于不处理指针,它非常快。

  2. 索引。你可以使用DArray_get和DArray_set来随机访问任何元素,但是List上你就必须经过第N个元素来访问第N+1个元素。

  3. 销毁。你只需要以两个操作销毁结构体和content。但是List需要一些列的free调用同时遍历每个元素。

  4. 克隆。你只需要复制结构体和content,用两步复制整个结构。List需要遍历所有元素并且复制每个ListNode和值。

  5. 排序。你已经见过了,如果你需要对数据排序,List非常麻烦。DArray上可以实现所有高效的排序算法,因为你可以随机访问任何元素。

  6. 大量数据。如果你需要储存大量数据,DArray由于基于content,比起相同数量的ListNode占用更少空间而占优。

然而List在这些操作上占优势。

  1. 在开头插入和移除元素。DArray需要特殊的优化来高效地完成它,并且通常还需要一些复制操作。

  2. 分割和连接。List只需要复制一些指针就能完成,但是DArray需要复制涉及到的所有数组。

  3. 少量数据。如果你只需要存储几个元素,通常使用List所需的空间要少于DArray,因为DArray需要考虑到日后的添加而扩展背后的空间,但是List只需要元素所需的空间。

考虑到这些,我更倾向使用DArray来完成其它人使用List所做的大部分事情。对于任何需要少量节点并且在两端插入删除的,我会使用List。我会想你展示两个相似的数据结构,叫做Stack和Queue,它们也很重要。

如何改进

像往常一样,浏览每个函数和操作,并且执行防御性编程检查,以及添加先决条件、不变量等任何可以使实现更健壮的东西。

附加题

  1. 改进单元测试来覆盖耕作操作,并使用for循环来测试迭代。

  2. 研究DArray上如何实现冒泡排序和归并排序,但是不要马上实现它们。我会在下一张实现DArray的算法,之后你可以完成它。

  3. 为一些常用的操作编写一些性能测试,并与List中的相同操作比较。你已经做过很多次了,但是这次需要编写重复执行所涉及操作的单元测试,之后在主运行器中计时。

  4. 观察DArray_expand如何使用固定增长(size + 300)来实现。通常动态数组都以倍数增长(size * 2)的方式实现,但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言,并且看看什么情况下需要倍数增长而不是固定增长。

关键字:c, lxthw

版权声明

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

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部