C动态数组

时间：2023-01-09 00:54:04

在实际项目中，我们经常与各式各样的数据打交道。 例如：我们处理的是学生的数据。

struct student {
	int id; // 学号
	char name[20]; // 姓名
	int gender; // 性别
	int mark; // 成绩
};

学生数据使用一个结构体表示，该结构体拥有4个成员。分别为：

  • 学号
  • 姓名
  • 性别
  • 成绩

大多数情况下，数据的数量是不确定的，可能随着时间流逝而增加或减少。 例如：一开始有5个学生，后来增加到8个，再后来增加到15个。最后，减少到3个学生。 我们可以使用数组来盛放这些学生的数据，但是，声明数组时，声明一个长度为多少的数组，是一个需要考虑的问题。 如果我们能预知学生数量最多为15个，我们可以声明一个元素数量为15的结构体数组。

struct student arrStudent[15];

但是，大多数情况下，我们是不能预知数据到底有多少的。因此，最好是能够让数组的长度根据数据的多少自动增长。一种常用的数组增长策略是：当数组已经装满时，将数组长度增长到原来的两倍。 例如，数组的初始长度为5，当数组需要继续添加数据时，数组的长度增长为原来的两倍，即10个元素。若数组再次被装满，将数组的长度再次增加为原来的两倍，即20个元素。 为了实现上述的特性，我们可以借助于malloc与realloc函数。

void* malloc(size_t size);
void* realloc(void* ptr, size_t new_size);

malloc函数可以向系统申请size字节大小的内存空间。若申请成功，则返回这段内存空间的首地址。 relloc函数可以用于增长或缩短之前申请的内存空间。relloc函数的第一个参数是之前申请的内存空间的首地址，它会根据第二个参数，长度new_size增长或缩短之前申请的内存空间，并返回调整长度后的内存空间的首地址。

实现动态数组

下面我们来实现这个动态数组对象，我们将这个对象命名为vector。

struct vector {
	bool (*append)(struct vector* pVec, struct student data);
	struct student(*get)(struct vector* pVec, int index);
	void (*clear)(struct vector* pVec);
	void (*remove)(struct vector* pVec, int index);
	struct student* pData;
	int size;
	int capacity;
};

成员

这个对象有3个成员，它们分别是：

  • struct student* pData
  • int size
  • int capacity

pData用于记录数组的首元素指针。 size为数组中盛放的数据的长度。 capacity为整个数组拥有的元素个数，即数组的容量。

初始化

我们定义一个符号常量VECTOR_INIT_CAPACITY用来表示初始情况下，数组拥有的元素个数。为了方便测试，我们把这个数值定的小一点，暂时将数值设定为1。

#define VECTOR_INIT_CAPACITY 1

定义一个vectorInit函数，用于vector对象的初始化。初始情况下，使用malloc函数申请一个元素类型为struct student的数组，数组的元素数量为VECTOR_INIT_CAPACITY。保存这个数组的首元素指针到pData中。此时，数组拥有的元素个数为VECTOR_INIT_CAPACITY，盛放的数据长度为0。

void vectorInit(struct vector* pVec)
{
	pVec->pData = (struct student*)malloc(sizeof(struct student) * VECTOR_INIT_CAPACITY);
	pVec->size = 0;
	pVec->capacity = VECTOR_INIT_CAPACITY;
}

方法

接下来我们再来看vector对象的4个方法。

bool (*append)(struct vector* pVec, struct student data);
struct student(*get)(struct vector* pVec, int index);
void (*clear)(struct vector* pVec);
void (*remove)(struct vector* pVec, int index);

append方法用于向数组中添加一个struct student数据。如果添加成功返回true，否则返回false。 get方法用于从数组中获取一个struct student数据，index参数为需要获取的数组元素下标。 clear方法用于清除所有数组中盛放的数据，并将size复位为0，capacity复位为VECTOR_INIT_CAPACITY。 remove方法用于删除数组中下标为index的元素，并将size减1。

append方法

我们首先来实现append方法。

bool vectorAppend(struct vector* pVec, struct student data)
{
	// 是否超长
	if (pVec->size >= pVec->capacity)
	{
		// 加长到两倍
		struct student* newData = (struct student*)
			realloc(pVec->pData, pVec->capacity * sizeof(struct student) * 2);
		if (newData == NULL)
		{
			return false;
		}
		pVec->pData = newData;
		pVec->capacity = 2 * pVec->capacity;
	}
	pVec->pData[pVec->size] = data;
	pVec->size++;
	return true;
}

函数一开始检查数组中盛放的数据长度size是否已经大于或等于数组的容量capacity。如果数组已装满，那么把数组使用relloc增长为原来长度的两倍。若relloc函数成功将数组增长，那么它将返回增长后的数组首地址。若失败，那么它将返回NULL。如果失败，让函数返回fasle。成功之后，使用新的数组首元素指针newData更新pData。现在数组长度增加到了原来的2倍，capacity赋值 为2 * capacity。下面，可以将data放入数组了。并且，将数组中已盛放的数据长度size增加1。

get方法

我们再来实现get方法。

struct student vectorGet(struct vector* pVec, int index)
{
	return pVec->pData[index];
}

get方法很简单，就是返回下标为index的数组元素的数据。

remove方法

remove方法，用于删除数组中下标为index的元素。

void vectorRemove(struct vector* pVec, int index)
{
	for (int i = index; i < pVec->size - 1; i++)
		pVec->pData[i] = pVec->pData[i + 1];
	pVec->size -= 1;
}

删除数组元素是一个老生常谈的话题了，从index开始，依次使用后续元素覆盖前驱元素，直到覆盖完倒数第二个元素为止。若index已经是最后一个元素，那么不进行处理。最后，将数组已盛放的数据长度size减1。

clear方法

clear方法用于将所有数组中盛放的数据清空，并将数组的容量缩短为初始容量。

void vectorClear(struct vector* pVec)
{
	if (pVec->pData != NULL)
		free(pVec->pData);
	pVec->pData = (struct student*)malloc(sizeof(struct student) * VECTOR_INIT_CAPACITY);
	pVec->size = 0;
	pVec->capacity = VECTOR_INIT_CAPACITY;
}

若pData不为NULL就释放pData，并重新申请容量为VECTOR_INIT_CAPACITY的数组，并将首元素指针保存到pData。size重置为0，capacity重置为VECTOR_INIT_CAPACITY。

销毁数组

void vectorDestroy(struct vector* pVec)
{
	if (pVec->pData == NULL)
		return;
	free(pVec->pData);
	pVec->pData = NULL;
	pVec->size = 0;
	pVec->capacity = 0;
}

如果我们不再使用vector可以调用vectorDestroy将数组销毁。若pData不为空，则释放pData，并且把pData赋值为NULL。size与capacity设置为0。

初始化方法

别忘了初始化时，我们仅仅初始化了对象的成员，没有初始化对象的方法。现在，把初始化对象的方法的语句加入到函数vectorInit当中。

void vectorInit(struct vector* pVec)
{
	pVec->get = vectorGet;
	pVec->append = vectorAppend;
	pVec->remove = vectorRemove;
	pVec->clear = vectorClear;
	pVec->pData = (struct student*)malloc(sizeof(struct student) * VECTOR_INIT_CAPACITY);
	pVec->size = 0;
	pVec->capacity = VECTOR_INIT_CAPACITY;
}

使用数组

初始化及append方法

struct vector vec;
vectorInit(&vec);
struct student s1 = { 1, "小明", 1, 90 };
vec.append(&vec, s1);
for (int i = 0; i < vec.size; i++)
{
	struct student s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

首先声明一个vector对象，调用函数vectorInit将其初始化。声明一个struct student结构体s1，将s1初始化为小明的数据。调用vector的append方法将小明的数据s1添加到数组当中。之后，使用循环遍历整个vector，循环的次数为vec.size。循环内部，调用vector的get方法，可以得到数组中的各个数据，并将其打印在控制台上。 打印vector的size与capacity，它们都为1。

测试append追加

接下来，向vector中再追加一个元素，小红的数据s2。遍历整个vector，可以得到小明和小红的数据。 打印vector的size与capacity，现在它们都增加为2了。

struct student s2 = { 2, "小红", 0, 95 };
vec.append(&vec, s2);
for (int i = 0; i < vec.size; i++)
{
	struct student s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

测试remove

vec.remove(&vec, 0);
for (int i = 0; i < vec.size; i++)
{
	struct student s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

调用remove方法，将下标为0的小明的数据删除。遍历整个vector，只能得到小红的数据。 打印vector的size与capacity，size为1，capacity为2。

测试clear

调用clear方法，清空所有数据，将size复位为0，将capacity复位为VECTOR_INIT_CAPACITY。遍历整个vector，已经没有数据了。

vec.clear(&vec);
for (int i = 0; i < vec.size; i++)
{
	struct student s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

打印vector的size与capacity，size为1，capacity为1。

销毁数组

最后，别忘记调用vectorDestroy将vector销毁。

vectorDestroy(&vec);

现阶段代码

#include <stdlib.h>
#include <stdio.h>
struct student {
	int id; // 学号
	char name[20]; // 姓名
	int gender; // 性别
	int mark; // 成绩
};
#define VECTOR_INIT_CAPACITY 1
struct vector {
	bool (*append)(struct vector* pVec, struct student data);
	struct student(*get)(struct vector* pVec, int index);
	void (*clear)(struct vector* pVec);
	void (*remove)(struct vector* pVec, int index);
	struct student* pData;
	int size;
	int capacity;
};
bool vectorAppend(struct vector* pVec, struct student data)
{
	// 是否超长
	if (pVec->size >= pVec->capacity)
	{
		// 加长到两倍
		struct student* newData = (struct student*)
			realloc(pVec->pData, pVec->capacity * sizeof(struct student) * 2);
		if (newData == NULL)
		{
			return false;
		}
		pVec->pData = newData;
		pVec->capacity = 2 * pVec->capacity;
	}
	pVec->pData[pVec->size] = data;
	pVec->size++;
	return true;
}
struct student vectorGet(struct vector* pVec, int index)
{
	return pVec->pData[index];
}
void vectorRemove(struct vector* pVec, int index)
{
	for (int i = index; i < pVec->size - 1; i++)
		pVec->pData[i] = pVec->pData[i + 1];
	pVec->size -= 1;
}
void vectorClear(struct vector* pVec)
{
	if (pVec->pData != NULL)
		free(pVec->pData);
	pVec->pData = (struct student*)malloc(sizeof(struct student) * VECTOR_INIT_CAPACITY);
	pVec->size = 0;
	pVec->capacity = VECTOR_INIT_CAPACITY;
}
void vectorInit(struct vector* pVec)
{
	pVec->get = vectorGet;
	pVec->append = vectorAppend;
	pVec->remove = vectorRemove;
	pVec->clear = vectorClear;
	pVec->pData = (struct student*)malloc(sizeof(struct student) * VECTOR_INIT_CAPACITY);
	pVec->size = 0;
	pVec->capacity = VECTOR_INIT_CAPACITY;
}
void vectorDestroy(struct vector* pVec)
{
	if (pVec->pData == NULL)
		return;
	free(pVec->pData);
	pVec->pData = NULL;
	pVec->size = 0;
	pVec->capacity = 0;
}
int main()
{
	struct vector vec;
	vectorInit(&vec);
	struct student s1 = { 1, "小明", 1, 90 };
	vec.append(&vec, s1);
	for (int i = 0; i < vec.size; i++)
	{
		struct student s = vec.get(&vec, i);
		printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
	}
	printf("size:%d\n", vec.size);
	printf("capacity:%d\n", vec.capacity);
	getchar();
	struct student s2 = { 2, "小红", 0, 95 };
	vec.append(&vec, s2);
	for (int i = 0; i < vec.size; i++)
	{
		struct student s = vec.get(&vec, i);
		printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
	}
	printf("size:%d\n", vec.size);
	printf("capacity:%d\n", vec.capacity);
	getchar();
	vec.remove(&vec, 0);
	for (int i = 0; i < vec.size; i++)
	{
		struct student s = vec.get(&vec, i);
		printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
	}
	printf("size:%d\n", vec.size);
	printf("capacity:%d\n", vec.capacity);
	getchar();
	vec.clear(&vec);
	for (int i = 0; i < vec.size; i++)
	{
		struct student s = vec.get(&vec, i);
		printf("%d %s %d %d\n", s.id, s.name, s.gender, s.mark);
	}
	printf("size:%d\n", vec.size);
	printf("capacity:%d\n", vec.capacity);
	getchar();
	vectorDestroy(&vec);
	return 0;
}

通用数组元素

目前，vector对象只能用于盛放struct student类型的数据。我们可以将所有的struct student改为void *，让其可以盛放任意数据类型的指针。 此外，我们在函数中，再多做一些参数检查。 在append方法内，对参数指针进行判空检查。 在get方法内，检查index是否超出已盛放的数据size的大小。若超出大小，则返回NULL。 接下来，我们把vector对象的代码拆分成vector.h与vector.cpp两个文件。 vector.h中，有符号常量VECTOR_INIT_CAPACITY的定义，vector对象的声明。以及初始化函数和销毁函数的声明。

vector.h文件如下：

#pragma once
#define VECTOR_INIT_CAPACITY 10
struct vector {
	bool (*append)(vector* pVec, void* data);
	void* (*get)(vector* pVec, int index);
	void (*clear)(vector* pVec);
	void (*remove)(vector* pVec, int index);
	void** pData;
	int size;
	int capacity;
};
void vectorInit(vector*);
void vectorDestroy(vector* pVec);

vector.cpp文件如下：

#include "vector.h"
#include <stdlib.h>
bool vectorAppend(vector* pVec, void* data)
{
	if (pVec == NULL || data == NULL)
		return false;
	// 是否超长
	if (pVec->size >= pVec->capacity)
	{
		// 加长到两倍
		void** newData = (void**)realloc(pVec->pData, pVec->capacity * sizeof(void*) * 2);
		if (newData == NULL)
		{
			return false;
		}
		pVec->pData = newData;
		pVec->capacity = 2 * pVec->capacity;
	}
	pVec->pData[pVec->size] = data;
	pVec->size++;
	return true;
}
void* vectorGet(vector* pVec, int index)
{
	if (index >= pVec->size)
		return NULL;
	return pVec->pData[index];
}
void vectorRemove(vector* pVec, int index)
{
	for (int i = index; i < pVec->size - 1; i++)
		pVec->pData[i] = pVec->pData[i + 1];
	pVec->size -= 1;
}
void vectorClear(vector* pVec)
{
	if (pVec->pData != NULL)
		free(pVec->pData);
	pVec->pData = (void**)malloc(sizeof(void*) * VECTOR_INIT_CAPACITY);
	pVec->capacity = VECTOR_INIT_CAPACITY;
	pVec->size = 0;
}
void vectorInit(vector* pVec)
{
	pVec->get = vectorGet;
	pVec->append = vectorAppend;
	pVec->remove = vectorRemove;
	pVec->clear = vectorClear;
	// 初始情况下申请VECTOR_INIT_CAPACITY个element
	pVec->pData = (void**)malloc(sizeof(void*) * VECTOR_INIT_CAPACITY);
	pVec->capacity = VECTOR_INIT_CAPACITY;
	pVec->size = 0;
}
void vectorDestroy(vector* pVec)
{
	if (pVec->pData == NULL)
		return;
	free(pVec->pData);
	pVec->pData = NULL;
	pVec->size = 0;
	pVec->capacity = 0;
}

测试通用数组

现在，vector数组可以用于盛放任意类型数据对象的指针。让我们使用它，用于盛放struct student *。

初始化与append

struct vector vec;
vectorInit(&vec);
struct student* s1 = (struct student*)malloc(sizeof(struct student));
s1->id = 1;
strcpy(s1->name, "小明");
s1->gender = 1;
s1->mark = 90;
vec.append(&vec, s1);
for (int i = 0; i < vec.size; i++)
{
	struct student* s = (struct student*)vec.get(&vec, i);
	printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

这里我们使用malloc申请一个struct student结构体，申请成功后，将其赋值为小明的数据。之后，将结构体struct student的指针s1，添加进入vector。遍历vector可以拿到我们之前放置进去的数据的指针，但是它是void*类型的，我们将其转换为struct student*类型，并赋值到s，使用这个指针，可以打印出小明数据的各项详情。

测试append追加

struct student* s2 = (struct student*)malloc(sizeof(struct student));
s2->id = 2;
strcpy(s2->name, "小红");
s2->gender = 0;
s2->mark = 95;
vec.append(&vec, s2);
for (int i = 0; i < vec.size; i++)
{
	struct student* s = (struct student*)vec.get(&vec, i);
	printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

再次使用malloc申请一个struct student结构体，申请成功后，将其赋值为小红的数据。之后，将结构体struct student的指针，追加进入vector。遍历vector可以拿到小明、小红数据的指针。

测试remove

// 别忘记销毁小明的数据
free(vec.get(&vec, 0));
vec.remove(&vec, 0);
for (int i = 0; i < vec.size; i++)
{
	struct student* s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

现在，我们将小明的数据删除，注意一定要free掉小明的数据。仅仅remove小明数据的指针是不行的，小明的数据是由malloc申请的，必须调用free销毁。

测试clear

for (int i = 0; i < vec.size; i++)
{
	struct student* s = vec.get(&vec, i);
	free(s);
}
vec.clear(&vec);
for (int i = 0; i < vec.size; i++)
{
	struct student* s = vec.get(&vec, i);
	printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
}
printf("size:%d\n", vec.size);
printf("capacity:%d\n", vec.capacity);

使用循环，获取所有数据的指针，调用free将这些数据都销毁。其后，我们就可以安全地清空vector数组了。

销毁数组

最后别忘记销毁vector本身。

vectorDestroy(&vec);

刚刚我们为了测试把数组初始长度设置得很短，实际中，可以设置稍微长一点，比如初始数组长度为10。

#define VECTOR_INIT_CAPACITY 10

最后代码

vector.h

#pragma once

#include <stdbool.h>

#define VECTOR_INIT_CAPACITY 10

struct vector {
    bool (*append)(struct vector* pVec, void* data);
    void* (*get)(struct vector* pVec, int index);
    void (*clear)(struct vector* pVec);
    void (*remove)(struct vector* pVec, int index);

    void** pData;
    int size;
    int capacity;
};

void vectorInit(struct vector*);
void vectorDestroy(struct vector* pVec);

main.c

#define _CRT_SECURE_NO_WARNINGS

#include "vector.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct student {
    int id;         //  学号
    char name[20];  //  姓名
    int gender;     //  性别
    int mark;       //  成绩
};

int main()
{
    struct vector vec;
    vectorInit(&vec);

    //  append
    struct student* s1 = (struct student*)malloc(sizeof(struct student));
    s1->id = 1;
    strcpy(s1->name, "小明");
    s1->gender = 1;
    s1->mark = 90;
    vec.append(&vec, s1);

    for (int i = 0; i < vec.size; i++)
    {
        struct student* s = (struct student*)vec.get(&vec, i);
        printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
    }

    printf("size:%d\n", vec.size);
    printf("capacity:%d\n", vec.capacity);
    getchar();

    //  append追加
    struct student* s2 = (struct student*)malloc(sizeof(struct student));
    s2->id = 2;
    strcpy(s2->name, "小红");
    s2->gender = 0;
    s2->mark = 95;
    vec.append(&vec, s2);

    for (int i = 0; i < vec.size; i++)
    {
        struct student* s = (struct student*)vec.get(&vec, i);
        printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
    }

    printf("size:%d\n", vec.size);
    printf("capacity:%d\n", vec.capacity);
    getchar();

    //  remove
    //  别忘记销毁小明的数据
    free(vec.get(&vec, 0));
    vec.remove(&vec, 0);

    for (int i = 0; i < vec.size; i++)
    {
        struct student* s = vec.get(&vec, i);
        printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
    }
    printf("size:%d\n", vec.size);
    printf("capacity:%d\n", vec.capacity);

    for (int i = 0; i < vec.size; i++)
    {
        struct student* s = vec.get(&vec, i);
        free(s);
    }
    getchar();

    //  clear
    vec.clear(&vec);

    for (int i = 0; i < vec.size; i++)
    {
        struct student* s = vec.get(&vec, i);
        printf("%d %s %d %d\n", s->id, s->name, s->gender, s->mark);
    }
    printf("size:%d\n", vec.size);
    printf("capacity:%d\n", vec.capacity);
    getchar();

    //  销毁数组
    vectorDestroy(&vec);
    
    return 0;
}

vector.c

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

bool vectorAppend(struct vector* pVec, void* data)
{
	if (pVec == NULL || data == NULL)
		return false;

	//  是否超长
	if (pVec->size >= pVec->capacity)
	{
		//  加长到两倍
		void** newData = (void**)realloc(pVec->pData, pVec->capacity * sizeof(void*) * 2);
		if (newData == NULL)
		{
			return false;
		}
		pVec->pData = newData;
		pVec->capacity = 2 * pVec->capacity;
	}

	pVec->pData[pVec->size] = data;
	pVec->size++;
	return true;
}

void* vectorGet(struct vector* pVec, int index)
{
	if (index >= pVec->size)
		return NULL;
	return pVec->pData[index];
}

void vectorRemove(struct vector* pVec, int index)
{
	for (int i = index; i < pVec->size - 1; i++)
		pVec->pData[i] = pVec->pData[i + 1];
	pVec->size -= 1;
}

void vectorClear(struct vector* pVec)
{
	if (pVec->pData != NULL)
		free(pVec->pData);

	pVec->pData = (void**)malloc(sizeof(void*) * VECTOR_INIT_CAPACITY);
	pVec->capacity = VECTOR_INIT_CAPACITY;
	pVec->size = 0;
}

void vectorInit(struct vector* pVec)
{
	pVec->get = vectorGet;
	pVec->append = vectorAppend;
	pVec->remove = vectorRemove;
	pVec->clear = vectorClear;

	//  初始情况下申请VECTOR_INIT_CAPACITY个element
	pVec->pData = (void**)malloc(sizeof(void*) * VECTOR_INIT_CAPACITY);
	pVec->capacity = VECTOR_INIT_CAPACITY;
	pVec->size = 0;
}

void vectorDestroy(struct vector* pVec)
{
	if (pVec->pData == NULL)
		return;
	free(pVec->pData);
	pVec->pData = NULL;
	pVec->size = 0;
	pVec->capacity = 0;
}
标签：

相关文章