C语言中的动态数组

动态数组与其在C语言中的实现

在C语言中，数组是一片连续的内存空间，这片内存空间被划分为大小相等的小空间。在介绍动态数组之前，让我们先简单回顾一下数组的基本特性。

数组的优点

• 访问速度快：可以通过下标索引直接访问元素，时间复杂度为O(1)。
• 内存连续：有利于局部性原理，高速缓存命中率高。

数组的缺点

• 大小固定：数组大小必须在声明时确定，之后无法改变。若数组空间不够，需要重新定义更大的数组。
• 空间静态分配：若申请了较大的数组但实际使用较少，会造成内存浪费。
• 插入和删除效率低：需要移动大量元素，时间复杂度为O(n)。

为了克服数组的上述缺点，我们引入了动态内存分配的概念。

为什么需要动态内存分配？

• 栈空间有限, 不适合存放大数据。
• 栈帧大小在编译期间确定, 栈空间不能存放动态大小的数据。
• 每个线程都有自己的栈, 不适合存放多线程共享的数据。

常见的内存分配函数有malloc, calloc, realloc, free。接下来我们将通过一个实例来展示如何在C语言中实现动态数组。

C语言实现动态数组

首先，我们需要定义一个动态数组的结构体和相关操作。这些操作包括创建数组、添加元素、删除元素、增长容量以及销毁数组。

// vector.h
#include <stdlib.h>

typedef int E;

typedef struct {
 E* elements;
 int size;
 int capacity;
} Vector;

Vector* vector_create(void);
Vector* vector_create_calloc(void);
void push_back(Vector* v, E val);
void push_front(Vector* v, E val);
E pop_back(Vector* v);
E pop_front(Vector* v);
void grow_capacity(Vector* v);
void vector_destory(Vector* v);

接下来，我们实现这些函数。

// vector.c
#include "vector.h"
#include <stdio.h>
#include <stdlib.h>
#define DEFAULT_CAPACITY 4
#define PREALLOC_MAX 1024
Vector* vector_create(void) {
 Vector* v = malloc(sizeof(Vector));
 if (!v)
 {
  printf("Error: malloc fail in vector_create\n");
  exit(1);
 }
 E* p = malloc(sizeof(E) * DEFAULT_CAPACITY);
 if (!p)
 {
  printf("Error: malloc fail in vector_create\n");
  exit(1);
 }
 v->elements = p;
 v->capacity = DEFAULT_CAPACITY;
 v->size = 0;
}

Vector* vector_create_calloc(void) {
 Vector* v = calloc(1, sizeof(Vector));
 if (v == NULL) {
  printf("Error: calloc failed\n");
  exit(1);
 }
 v->elements = calloc(DEFAULT_CAPACITY, sizeof(E));
 if (v->elements == NULL) {
  printf("Error: calloc failed\n");
  exit(1);
 }
 v->capacity = DEFAULT_CAPACITY;
 v->size = 0;
 return v;
}

void grow_capacity(Vector* v) {
 int new_capacity = v->capacity < PREALLOC_MAX ?
  v->capacity << 1 : v->capacity + PREALLOC_MAX;
 E* p = realloc(v->elements, new_capacity * sizeof(E));
 if (!p)
 {
  printf("ERROR: grow_capacity");
  exit(1);
 }
 v->elements = p;
 v->capacity = new_capacity;
}
void push_back(Vector* v, E val) {
 if (v->capacity == v->size)
 {
  grow_capacity(v);
 }
 v->elements[v->size++] = val;
}
// 在数组最前面添加元素，所有元素依次后移
void push_front(Vector* v, E val) {
 if (v->capacity == v->size)
 {
  grow_capacity(v);
 }
 v->size++;
 for (int i = v->size - 2; i > 0; i--)
 {
  v->elements[i + 1] = v->elements[i];
 }
 v->elements[0] = val;
}
// 删除最后一个元素, 并把最后一个元素返回
E pop_back(Vector* v) {
 return v->elements[v->size--];
}
// 删除第一个元素，并把第一个元素返回
E pop_front(Vector* v) {
 int t = v->elements[0];
 for (int i = 0; i < v->size - 1; i++)
 {
  v->elements[i] = v->elements[i + 1];
 }
 v->size--;
 return t;
}

void vector_destory(Vector* v) {
 free(v->elements);
 free(v);
}

现在，我们可以在主函数中测试我们的动态数组了。

// main.c
#include <stdio.h>
#include "vector.h"

void print_vector(Vector* v) {
    printf("向量大小: %d, 容量: %d\n", v->size, v->capacity);
    printf("元素: ");
    for (int i = 0; i < v->size; i++) {
        printf("%d ", v->elements[i]);
    }
    printf("\n");
}

int main(void) {
    printf("使用malloc创建向量:\n");
    Vector* v1 = vector_create();
    push_back(v1, 1);
    push_back(v1, 2);
    push_back(v1, 3);
    print_vector(v1);

    printf("使用realloc扩容向量:\n");
    for (int i = 4; i <= 10; i++) {
        push_back(v1, i);
    }
    print_vector(v1);

    printf("使用calloc创建向量:\n");
    Vector* v2 = vector_create_calloc();
    push_back(v2, 1);
    push_back(v2, 2);
    push_back(v2, 3);
    push_back(v2, 4);
    push_back(v2, 5);
    print_vector(v2);

    printf("使用free销毁向量\n");
    vector_destory(v1);
    vector_destory(v2);

    return 0;
}

运行上述代码，我们得到以下输出结果：

下面我们来一个简单的总结，并讲两点注意事项：

1. malloc函数分配的内存块包含未初始化的垃圁数据，而calloc函数分配的内存块会被自动初始化为0。
2. malloc函数只接受一个参数，即要分配的字节数。而calloc函数接受两个参数，一个是要分配的元素的数量，另一个是每个元素的大小。这使得calloc更适合用于数组的分配。
3. 由于calloc会初始化分配的内存，所以它可能比malloc稍微慢一些，尤其是在分配大量内存时。

注意事项

1. use after free
2. double free