在实际项目中,我们经常与各式各样的数据打交道。
例如:我们处理的是学生的数据。
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;
}