当前位置： 首页 > news >正文

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

news 来源：原创 2024/4/24 5:25:29

练习34：动态数组

原文：Exercise 34: Dynamic Array

译者：飞龙

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

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

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

#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的单元测试。

#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的实现变得容易：

#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）的方式实现，但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言，并且看看什么情况下需要倍数增长而不是固定增长。

相关文章：

  • https://www.jianshu.com/p/dbffae16ba0b
  • Python利用正则抓取网页内容保存到本地
  • 管理员页面
  • Spring Boot整合MyBatis
  • 1100名达摩院“扫地僧”加持，阿里云的下一个十年
  • 深入学习JVM了解JVM内存模型
  • I.MX6 AW-NB177NF p2p support
  • Vue Router
  • 【转】FPGA内部小数计算
  • LeetCode算法题-Non-decreasing Array（Java实现）
  • 我的IT转行之路
  • 读书笔记之《实战Java虚拟机》（6）：性能监控工具
  • B-树(B+树) 学习总结
  • 【DAY24】内省，NIO的学习笔记
  • 双亲委派模型与Tomcat类加载架构
  • 【402天】跃迁之路——程序员高效学习方法论探索系列（实验阶段159-2018.03.14）...
  • Codepen 每日精选（2018-3-25）
  • DataBase in Android
  • es6
  • Fabric架构演变之路
  • FineReport中如何实现自动滚屏效果
  • Git同步原始仓库到Fork仓库中
  • JDK 6和JDK 7中的substring（）方法
  • nodejs调试方法
  • node入门
  • opencv python Meanshift 和 Camshift
  • OpenStack安装流程（juno版）- 添加网络服务（neutron）- controller节点
  • rabbitmq延迟消息示例
  • SQLServer之创建显式事务
  • vuex 笔记整理
  • 百度贴吧爬虫node+vue baidu_tieba_crawler
  • 工作踩坑系列——https访问遇到“已阻止载入混合活动内容”
  • 关于使用markdown的方法（引自CSDN教程）
  • 前端代码风格自动化系列（二）之Commitlint
  • 如何打造100亿SDK累计覆盖量的大数据系统
  • 如何在 Tornado 中实现 Middleware
  • 什么软件可以剪辑音乐？
  • 数据仓库的几种建模方法
  • 项目实战-Api的解决方案
  • 赢得Docker挑战最佳实践
  • 《天龙八部3D》Unity技术方案揭秘
  • ionic异常记录
  • shell使用lftp连接ftp和sftp,并可以指定私钥
  • ​草莓熊python turtle绘图代码（玫瑰花版）附源代码
  • # 手柄编程_北通阿修罗3动手评：一款兼具功能、操控性的电竞手柄
  • （4）Elastix图像配准：3D图像
  • （ｃ语言）strcpy函数用法
  • （DFS + 剪枝）【洛谷P1731】 [NOI1999] 生日蛋糕
  • (html转换)StringEscapeUtils类的转义与反转义方法
  • (搬运以学习)flask 上下文的实现
  • （笔记）Kotlin——Android封装ViewBinding之二 优化
  • （附源码）计算机毕业设计SSM基于java的云顶博客系统
  • （九十四）函数和二维数组
  • （已更新）关于Visual Studio 2019安装时VS installer无法下载文件，进度条为0，显示网络有问题的解决办法
  • (转)Android中使用ormlite实现持久化(一)--HelloOrmLite