动态数组的代码实现

1.总述

1.DynamicArray.h 2.DynamicArray.c 3.test-main.c

2.代码实现

/* 文件名：DynamicArray.h 作者：Muten 编码时间：20201020 编码目的：动态数组及其相关操作的声明 代码功能：声明动态数组及其相关操作 测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3 版本信息：VER1.0 */ #pragma once #ifndef DYNAMIC_ARRAY_H #define DYNAMIC_ARRAY_H #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct DYNAMICARRAY{ int *pAddr; int size; int capacity; }Dynamic_Array; // 初始化 Dynamic_Array* Init_Dynamic_Array(); // 插入 void Push_Back_Array(Dynamic_Array* arr, int value); // 根据位置删除 void RemoveByPos_Array(Dynamic_Array* arr, int pos); // 根据值删除 void RemoveByValue_Array(Dynamic_Array* arr, int pos); // 查找 int Find_Array(Dynamic_Array* arr,int value); // 打印 int Print_Array(Dynamic_Array* arr); // 释放动态数组的内存 void FreeSpace_Array(Dynamic_Array* arr); // 清空数组 void Clear_Array(Dynamic_Array* arr); // 获得动态数组当前元素 int Capacity_Array(Dynamic_Array* arr); // 获得动态数组的长度 int Size_Array(Dynamic_Array* arr); // 获得动态数组的位置 int At_Array(Dynamic_Array*arr, int pos); #endif /* 文件名：DynamicArray.c 作者：Muten 编码时间：20201020 编码目的：动态数组及其相关操作的定义实现 代码功能：实现动态数组及其相关操作 测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3 版本信息：VER1.0 */ #include "DynamicArray.h" Dynamic_Array * Init_Dynamic_Array() { printf("Init_Dynamic_Array\n"); // 初始化动态数组 Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array)); // 初始化 myArray->size = 0; myArray->capacity = 20; myArray->pAddr = (int*)malloc(sizeof(int)*myArray->capacity); return myArray; } void Push_Back_Array(Dynamic_Array * arr, int value) { if (arr == NULL) return; if (arr->size == arr->capacity) { int* newSpace = (int *)malloc(sizeof(int)*arr->capacity * 2); memcpy(newSpace,arr->pAddr,arr->capacity*sizeof(int)); free(arr->pAddr); arr->capacity = arr->capacity * 2; arr->pAddr = newSpace; } arr->pAddr[arr->size] = value; arr->size++; } void RemoveByPos_Array(Dynamic_Array * arr, int pos) { if (arr == NULL) return; // 判断位置是否有效 if (pos < 0 || pos >= arr->size) { return; } for (int i = pos; i < arr->size; i++) { arr->pAddr[i] = arr->pAddr[i + 1]; } arr->size--; } void RemoveByValue_Array(Dynamic_Array * arr, int value) { if (arr == NULL) return; // 找到值的位置 int pos = -1; for (int i = 0; i < arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } RemoveByPos_Array(arr,pos); } int Find_Array(Dynamic_Array * arr, int value) { if (arr == NULL) { return -1; } // 找到值的位置 int pos = -1; for (int i = 0; i < arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } return pos; } int Print_Array(Dynamic_Array * arr) { for (int i = 0; i < arr->size; i++) printf("%d ",arr->pAddr[i]); printf("\n"); return 0; } void FreeSpace_Array(Dynamic_Array * arr) { if (arr == NULL) return; if (arr->pAddr != NULL) free(arr->pAddr); free(arr); } void Clear_Array(Dynamic_Array * arr) { if (arr == NULL) return; arr->size = 0; } int Capacity_Array(Dynamic_Array * arr) { if (arr == NULL) return -1; return arr->capacity; } int Size_Array(Dynamic_Array * arr) { if (arr == NULL) return -1; return arr->size; } int At_Array(Dynamic_Array * arr, int pos) { return arr->pAddr[pos]; }

 

/* 文件名：test-main.c 作者：Muten 编码时间：20201020 编码目的：测试测试动态数组的相关实现 代码功能：测试动态数组的相关实现 测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3 版本信息：VER1.0 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "DynamicArray.h" void test01() { Dynamic_Array* myArray = Init_Dynamic_Array(); printf("array_capacity is [%d],array_size is[%d]\n", Capacity_Array(myArray), Size_Array(myArray)); for (int i = 0; i < 30; i++) { Push_Back_Array(myArray,i); } printf("array_capacity is [%d],array_size is[%d]\n", Capacity_Array(myArray), Size_Array(myArray)); Print_Array(myArray); // 删除 RemoveByPos_Array(myArray,0); RemoveByValue_Array(myArray,27); // 删除之后再打印数组 Print_Array(myArray); // 查找 int pos = Find_Array(myArray,5); printf("value %d's pos = %d\n",pos,At_Array(myArray,pos)); // 销毁 FreeSpace_Array(myArray); } int main(void) { test01(); system("pause"); return 0; }

4.说明

这里的动态数组实现的思想其实就是STL中vector实现的思想，vector的实现要另外加上模板来实现对各种数据结构的支持，另外当内存不 够动态增长时，vector会自动扩容，其增长倍数和平台是有关系的，曾经测试过在window下是按照1.5倍的方式来扩容的，Linux下是按照2 倍的方式来扩容的.