C实现的vector动态数组
2009 年 3 月 20 日
动态数组vector是日常业务代码最常用的数据结构,大多数高级语言都提供了动态数组的实现, 如c++中的std::vector, python和golang中的[]。然而在c中没有提供这一重要的轮子,我们在这里一步一步构建一个c中的vector,可能不能在正式场景中使用,但是可以作为一个研习数据结构和内存分配的工具。
- 创建文件vector.h, vector.c,定义vector数据结构和init函数
//vector.h #ifndef VECTOR_H_ #define VECTOR_H_ #define INIT_CAP 10 typedef struct vector{ int cap; int len; void **items; }vector; void init_vec(vector *v, int cap); #endif
//vector.c #include "vector.h" #include "comm.h" void init_vec(vector *v, int cap){ v->cap = cap; v->len = 0; v->items = calloc(v->cap, sizeof(void *)); if(!v->items) err_exit(MEM_ERR); }
- (1)设置动态数组的容量为INIT_CAP,使用长度为0。
- (2)调用calloc() 为数组分配内存,同时初始化为0,在c中对于指针而言是NULL
- (3)若创建失败,调用err_exit,打印错误信息,同时终止进程。
2. 向动态数组添加元素
//vector.c void push_back_vec(vector *v, void *item){ if(v->len == v->cap) resize_vec(v, v->cap*2); v->items[v->len++] = item; } void push_front_vec(vector *v, void *item){ if(v->len == v->cap) resize_vec(v, v->cap*2); memmove(v->items + 1, v->items, v->len*sizeof(void *)); v->items[0] = item; v->len++; } void insert_vec(vector *v, void *item, int ix){ if(ix <= 0){ push_front_vec(v, item); }else if(ix >= v->len){ push_back_vec(v, item); }else{ if(v->len == v->cap) resize_vec(v, v->cap*2); memmove(v->items + ix + 1, v->items + ix, (v->len - ix)*sizeof(void *)); v->len++; v->items[ix] = item; } }
- (1)增加元素前检查数组容量,并进行调整
- (2)使用memmove减少元素移动的次数
3. 调整动态数组容量
//vector.c static void resize_vec(vector *v, int new_cap){ v->cap = new_cap; v->items = realloc(v->items, sizeof(void *)*v->cap); if(!v->items) err_exit(MEM_ERR); }
- (1)调用realloc()重新分配内存,转移元素,从而调整数组容量
4. 从动态数组删除元素
//vector.c void *pop_back_vec(vector *v){ if(v->len < 1) return NULL; int last = v->len-1; void *ret = v->items[last]; v->items[last] = NULL; --v->len; if(v->len < v->cap/3) resize_vec(v, v->cap/2); return ret; } void *pop_front_vec(vector *v){ if(v->len < 1) return NULL; void *ret = v->items[0]; v->len--; memmove(v->items, v->items + 1, v->len*sizeof(void *)); if(v->len < v->cap/3) resize_vec(v, v->cap/2); return ret; } void *del_at_vec(vector *v, int ix){ if(v->len == 0 || v->len <= ix || ix < 0) return NULL; else if(v->len - 1 == ix){ return pop_back_vec(v); }else if(ix == 0){ return pop_front_vec(v); } void *ret = v->items[ix]; memmove(v->items + ix, v->items + ix + 1, (v->len - ix - 1)*sizeof(void *)); v->len--; if(v->len < v->cap/3) resize_vec(v, v->cap/2); return ret; }
- (1)为了实现队列和栈,需要实现两端插入和推出
- (2)为了实现随机存取,需要实现按索引插入和推出
5.添加测试用例
//vector.h #define INIT_VEC(vec) vector vec; init_vec(&vec, INIT_CAP) #define FREE_VEC(vec) reset_vec(&(vec)) #define REINIT_VEC(vec) reset_vec(&(vec)); init_vec(&vec, INIT_CAP)
//vector.c void test_vec(){ vector v; init_vec(&v, INIT_CAP); for(long i = 0; i < 20; i++){ push_back_vec(&v, (void *)(i)); } for(int i = 0; i < 3; i++){ pop_front_vec(&v); pop_back_vec(&v); } insert_vec(&v, (void *)3, 3); del_at_vec(&v, 3); print_vec(&v); reset_vec(&v); }
- (1)为了方便调用,添加了宏定义INIT, REINIT 和FREE
代码清单 ( https://github.com/KevinACoder/Learning/tree/master/ds
)