【附C源码】C语言实现动态数组从原理到实践在C语言开发中数组的长度在编译期就必须确定这种静态特性在面对数据规模不确定的场景时显得力不从心。为了解决这个问题我实现了一个动态数组Dynamic Array数据结构类似于C STL中的std::vector能够在运行时自动扩容同时保持O(1)的随机访问效率。设计思路动态数组的核心思想是分离逻辑大小与物理容量。逻辑上的size表示当前存储的元素数量而物理上的capacity表示底层数组的实际长度。当size达到capacity时触发扩容机制通常将容量翻倍以摊还O(1)的插入复杂度。结构体定义如下typedefintData;typedefstruct{Data*data;// 指向堆内存的指针intsize;// 当前元素个数intcapacity;// 当前容量}Vector;使用typedef将int定义为Data类型是为了后续扩展。如果需要存储其他类型如double或结构体指针只需修改这一行即可。内存管理创建与销毁动态数组的创建涉及两次内存分配一次为结构体本身一次为数据存储区。这种设计允许数组在堆上动态存在生命周期由程序员控制。Vector*vectorCreateWithCapacity(intinitialCapacity){Vector*vec(Vector*)malloc(sizeof(Vector));if(!vec)returnNULL;vec-data(Data*)malloc(sizeof(Data)*initialCapacity);if(!vec-data){free(vec);returnNULL;}vec-size0;vec-capacityinitialCapacity;returnvec;}销毁时需要先释放内部数据数组再释放结构体本身。顺序不能颠倒否则会造成内存泄漏。voidvectorDestroy(Vector*vec){if(!vec)return;free(vec-data);free(vec);}扩容策略扩容是动态数组的核心操作。当size capacity时触发vectorGrow函数staticvoidvectorGrow(Vector*vec){if(vec-sizevec-capacity){intnewCapacityvec-capacity*2;Data*newData(Data*)realloc(vec-data,sizeof(Data)*newCapacity);if(!newData)return;vec-datanewData;vec-capacitynewCapacity;}}这里采用翻倍扩容策略。数学分析表明这种策略能够将插入操作的均摊时间复杂度控制在O(1)。如果每次只增加固定容量时间复杂度将退化为O(n)。核心操作实现尾部操作尾部插入Push和删除Pop是最高效的操作时间复杂度均为O(1)。voidvectorPush(Vector*vec,Data val){if(!vec)return;vectorGrow(vec);vec-data[vec-size]val;}voidvectorPop(Vector*vec){if(!vec||vec-size0)return;vec-size--;}注意Pop操作并不真正释放内存只是减小size。这种设计符合惰性释放原则避免频繁的内存操作。随机访问动态数组支持O(1)的随机访问这是其相对于链表的核心优势。DatavectorGet(Vector*vec,intindex){if(!vec||index0||indexvec-size)return0;returnvec-data[index];}voidvectorSet(Vector*vec,intindex,Data val){if(!vec||index0||indexvec-size)return;vec-data[index]val;}边界检查是必要的防御性编程实践。虽然会影响少许性能但能有效防止缓冲区溢出。插入与删除在指定位置插入或删除元素需要移动后续所有元素时间复杂度为O(n)。voidvectorInsert(Vector*vec,intindex,Data val){if(!vec||index0||indexvec-size)return;vectorGrow(vec);for(intivec-size;iindex;i--){vec-data[i]vec-data[i-1];}vec-data[index]val;vec-size;}voidvectorErase(Vector*vec,intindex){if(!vec||index0||indexvec-size)return;for(intiindex;ivec-size-1;i){vec-data[i]vec-data[i1];}vec-size--;}插入时采用从后向前移动的策略避免覆盖未处理的数据。删除时则从前向后移动。容量控制除了自动扩容动态数组还应提供手动容量控制接口voidvectorReserve(Vector*vec,intnewCapacity){if(!vec||newCapacityvec-capacity)return;Data*newData(Data*)realloc(vec-data,sizeof(Data)*newCapacity);if(!newData)return;vec-datanewData;vec-capacitynewCapacity;}voidvectorShrinkToFit(Vector*vec){if(!vec||vec-capacityvec-size)return;Data*newData(Data*)realloc(vec-data,sizeof(Data)*vec-size);if(!newData)return;vec-datanewData;vec-capacityvec-size;}Reserve用于预分配空间避免多次扩容的开销。ShrinkToFit则在内存敏感的场景下释放多余容量使capacity等于size。批量操作与算法动态数组不仅是一个容器还应支持常见的数组操作voidvectorReverse(Vector*vec){if(!vec||vec-size1)return;intleft0,rightvec-size-1;while(leftright){Data tempvec-data[left];vec-data[left]vec-data[right];vec-data[right]temp;left;right--;}}voidvectorSort(Vector*vec){if(!vec||vec-size1)return;for(inti0;ivec-size-1;i){for(intj0;jvec-size-i-1;j){if(vec-data[j]vec-data[j1]){Data tempvec-data[j];vec-data[j]vec-data[j1];vec-data[j1]temp;}}}}这里实现了双指针反转和冒泡排序。虽然冒泡排序的时间复杂度为O(n²)但对于小规模数据已经足够。在实际项目中可以替换为qsort或自定义的快速排序实现。测试验证main函数中编写了完整的测试用例覆盖了创建、插入、删除、查找、排序、复制、清空等所有操作。通过打印数组状态可以直观地观察每一步操作的结果。Vector*vecvectorCreate();vectorPush(vec,1);vectorPush(vec,2);vectorPush(vec,3);vectorPrint(vec);// [1, 2, 3] (size3, capacity4)总结这个动态数组实现涵盖了数据结构设计的几个关键点内存管理合理的分配与释放策略避免泄漏容量策略翻倍扩容保证均摊O(1)插入边界检查防御性编程提高健壮性接口完整提供容器应有的全部基本操作代码总计约380行无外部依赖可直接嵌入到任何C项目中使用。对于需要存储复杂类型的场景只需将Data定义为相应指针类型即可。⚠️源码地址https://github.com/anjuxi/C-dynamic_array
【附C源码】C语言实现动态数组：从原理到实践
【附C源码】C语言实现动态数组从原理到实践在C语言开发中数组的长度在编译期就必须确定这种静态特性在面对数据规模不确定的场景时显得力不从心。为了解决这个问题我实现了一个动态数组Dynamic Array数据结构类似于C STL中的std::vector能够在运行时自动扩容同时保持O(1)的随机访问效率。设计思路动态数组的核心思想是分离逻辑大小与物理容量。逻辑上的size表示当前存储的元素数量而物理上的capacity表示底层数组的实际长度。当size达到capacity时触发扩容机制通常将容量翻倍以摊还O(1)的插入复杂度。结构体定义如下typedefintData;typedefstruct{Data*data;// 指向堆内存的指针intsize;// 当前元素个数intcapacity;// 当前容量}Vector;使用typedef将int定义为Data类型是为了后续扩展。如果需要存储其他类型如double或结构体指针只需修改这一行即可。内存管理创建与销毁动态数组的创建涉及两次内存分配一次为结构体本身一次为数据存储区。这种设计允许数组在堆上动态存在生命周期由程序员控制。Vector*vectorCreateWithCapacity(intinitialCapacity){Vector*vec(Vector*)malloc(sizeof(Vector));if(!vec)returnNULL;vec-data(Data*)malloc(sizeof(Data)*initialCapacity);if(!vec-data){free(vec);returnNULL;}vec-size0;vec-capacityinitialCapacity;returnvec;}销毁时需要先释放内部数据数组再释放结构体本身。顺序不能颠倒否则会造成内存泄漏。voidvectorDestroy(Vector*vec){if(!vec)return;free(vec-data);free(vec);}扩容策略扩容是动态数组的核心操作。当size capacity时触发vectorGrow函数staticvoidvectorGrow(Vector*vec){if(vec-sizevec-capacity){intnewCapacityvec-capacity*2;Data*newData(Data*)realloc(vec-data,sizeof(Data)*newCapacity);if(!newData)return;vec-datanewData;vec-capacitynewCapacity;}}这里采用翻倍扩容策略。数学分析表明这种策略能够将插入操作的均摊时间复杂度控制在O(1)。如果每次只增加固定容量时间复杂度将退化为O(n)。核心操作实现尾部操作尾部插入Push和删除Pop是最高效的操作时间复杂度均为O(1)。voidvectorPush(Vector*vec,Data val){if(!vec)return;vectorGrow(vec);vec-data[vec-size]val;}voidvectorPop(Vector*vec){if(!vec||vec-size0)return;vec-size--;}注意Pop操作并不真正释放内存只是减小size。这种设计符合惰性释放原则避免频繁的内存操作。随机访问动态数组支持O(1)的随机访问这是其相对于链表的核心优势。DatavectorGet(Vector*vec,intindex){if(!vec||index0||indexvec-size)return0;returnvec-data[index];}voidvectorSet(Vector*vec,intindex,Data val){if(!vec||index0||indexvec-size)return;vec-data[index]val;}边界检查是必要的防御性编程实践。虽然会影响少许性能但能有效防止缓冲区溢出。插入与删除在指定位置插入或删除元素需要移动后续所有元素时间复杂度为O(n)。voidvectorInsert(Vector*vec,intindex,Data val){if(!vec||index0||indexvec-size)return;vectorGrow(vec);for(intivec-size;iindex;i--){vec-data[i]vec-data[i-1];}vec-data[index]val;vec-size;}voidvectorErase(Vector*vec,intindex){if(!vec||index0||indexvec-size)return;for(intiindex;ivec-size-1;i){vec-data[i]vec-data[i1];}vec-size--;}插入时采用从后向前移动的策略避免覆盖未处理的数据。删除时则从前向后移动。容量控制除了自动扩容动态数组还应提供手动容量控制接口voidvectorReserve(Vector*vec,intnewCapacity){if(!vec||newCapacityvec-capacity)return;Data*newData(Data*)realloc(vec-data,sizeof(Data)*newCapacity);if(!newData)return;vec-datanewData;vec-capacitynewCapacity;}voidvectorShrinkToFit(Vector*vec){if(!vec||vec-capacityvec-size)return;Data*newData(Data*)realloc(vec-data,sizeof(Data)*vec-size);if(!newData)return;vec-datanewData;vec-capacityvec-size;}Reserve用于预分配空间避免多次扩容的开销。ShrinkToFit则在内存敏感的场景下释放多余容量使capacity等于size。批量操作与算法动态数组不仅是一个容器还应支持常见的数组操作voidvectorReverse(Vector*vec){if(!vec||vec-size1)return;intleft0,rightvec-size-1;while(leftright){Data tempvec-data[left];vec-data[left]vec-data[right];vec-data[right]temp;left;right--;}}voidvectorSort(Vector*vec){if(!vec||vec-size1)return;for(inti0;ivec-size-1;i){for(intj0;jvec-size-i-1;j){if(vec-data[j]vec-data[j1]){Data tempvec-data[j];vec-data[j]vec-data[j1];vec-data[j1]temp;}}}}这里实现了双指针反转和冒泡排序。虽然冒泡排序的时间复杂度为O(n²)但对于小规模数据已经足够。在实际项目中可以替换为qsort或自定义的快速排序实现。测试验证main函数中编写了完整的测试用例覆盖了创建、插入、删除、查找、排序、复制、清空等所有操作。通过打印数组状态可以直观地观察每一步操作的结果。Vector*vecvectorCreate();vectorPush(vec,1);vectorPush(vec,2);vectorPush(vec,3);vectorPrint(vec);// [1, 2, 3] (size3, capacity4)总结这个动态数组实现涵盖了数据结构设计的几个关键点内存管理合理的分配与释放策略避免泄漏容量策略翻倍扩容保证均摊O(1)插入边界检查防御性编程提高健壮性接口完整提供容器应有的全部基本操作代码总计约380行无外部依赖可直接嵌入到任何C项目中使用。对于需要存储复杂类型的场景只需将Data定义为相应指针类型即可。⚠️源码地址https://github.com/anjuxi/C-dynamic_array
