首页 > 代码库 > 通用型动态数组的总结
通用型动态数组的总结
基本数据结构之-通用型动态数组
动态数组的应用主要是对于长度未知的数组，先开辟一段空间来存储数据，当空间不够时，在开辟两倍的空间来存储数据
和普通数组的区别就是，我们可以不用关心数组的长度的问题，唯一需要关注的就是数据的类型是自定义数据类型还是基本数据类型，但是不论是基本数据类型还是自定义的数据类型，都需要自定义两个函数，这两个函数时遍历（打印）函数和比较函数，因为，在传递的是地址，没法再里面判断是什么类型，只能交给使用者去定义它的想关的函数，
先说基本的结构:
为了适应更多的数据类型，我们存储的只是数据的的地址（void *），其实我们更关注的是数据存储的那块首地址，因此我们使用void ** 来存储数据存储区域的首地址；
为了更好的操作数组，我们需要维护两个变量，一个是容量，一个是长度，当数组的长度和容量相同时，我们就需要重新开辟一段空间来存储现在的数据和即将放入数组的数据。
直接上代码：
typedef struct _DYNAMICARRAY
{
// 数据存储
void **Array;
// 数组的容量
int Capacity;
// 数组现有数据的长度
int ArrayLen;
}DynamicArray;
自定义的数据类型，我们就必须定义自己的初始化函数
int Init_DynamicArray(void **DArray)
{
if (DArray == NULL)
{
exit(-1);
}
DynamicArray *dynamicarray = (DynamicArray *)malloc(sizeof(DynamicArray));
dynamicarray->Array = (void **)malloc(sizeof(void *)*MAXCAPACITY);
if (dynamicarray->Array == NULL)
{
exit(-2);
}
for (int i = 0; i < MAXCAPACITY; ++i)
{
// 将开辟void * 指针指向NULL
//dynamicarray->Array[i] = NULL;
*((dynamicarray->Array) + i) = NULL;
}
// 将数组的变化写入想关数据
dynamicarray->ArrayLen = 0;
dynamicarray->Capacity = MAXCAPACITY;
*DArray = dynamicarray;
return 0;
}
数组有顺序插入的特性，当然你也可以在数组内随机插入，但是插入一般是不允许的，因为你插入的数据对数组来说可能无法访问，因此虽然提供了随机插入函数，但是，并不会对数据的长度和容量带来改变，因为我不确定，你插入数据的意图，如果你插入的数据的位置刚好在数组可以允许范围类，那么你就修改了当前的值，如果你插入的不在允许的范围内，那么对数组的原有数据是没有影响的e
// 在数组末尾插入数据
int pushBack_DynamicArray(void *DArray, void *Data)
{
if (DArray == NULL)
{
return -1;
}
if (Data =http://www.mamicode.com/= NULL)
{
return -2;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
if (dynamicarray->ArrayLen == dynamicarray->Capacity)
{
void ** tempCapaticy = (void **)malloc(sizeof(void *)*dynamicarray->Capacity * 2);
if (tempCapaticy == NULL)
{
return -3;
}
memcpy(tempCapaticy, dynamicarray->Array, sizeof(void *)*dynamicarray->Capacity);
free(dynamicarray->Array);
dynamicarray->Array = tempCapaticy;
for (int i = dynamicarray->Capacity; i < dynamicarray->Capacity * 2; ++i)
{
dynamicarray->Array[i] = NULL;
}
dynamicarray->Capacity *= 2;
}
dynamicarray->Array[dynamicarray->ArrayLen] = Data;
++dynamicarray->ArrayLen;
return 0;
}
// 指定位置插入函数，如果在数组允许的范围内，则起到修改该位置的元素的作用，如果在不允许的范围类，可能导致程崩溃，当然你也可修改源码，来使插入合法
// 指定位置插入
void InsertByPos(void *DArray, int Pos, void *Val)
{
if (DArray == NULL)
{
return;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
dynamicarray->Array[Pos] = Val;
}
删除某个位置的数据，这个可能和原生数组有些差别，因为原生数据没有删除单个数据的功能，我做了如下的处理，当删除某个数据时，我把后面的数据向前移动一个位置，覆盖原来的数据
// 指定位置删除
int eraseByPos_DynamicArray(void *DArray, int Pos)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
if (Pos < 0 || Pos >= dynamicarray->ArrayLen)
{
return -2;
}
for (int i = Pos; i < dynamicarray->ArrayLen - 1; ++i)
{
dynamicarray->Array[i] = dynamicarray->Array[i + 1];
}
dynamicarray->Array[dynamicarray->ArrayLen - 1] = NULL;
--dynamicarray->ArrayLen;
return 0;
}
// 头删 （这个基本数据类型的数组也是没有的，但是作为自己定义的数据类型，为了操作的方便，自己加上的）
int eraseFront_DynamicArray(void *DArray)
{
int ret = eraseByPos_DynamicArray(DArray, 0);
return ret;
}
// 尾删（同头删）
int eraseBack_DynamicArray(void *DArray)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
int ret = eraseByPos_DynamicArray(DArray, dynamicarray->ArrayLen - 1);
return ret;
}
// 查看某个位置的值
void * GetByPos_DynamicArray(void *DArray, int Pos)
{
// 这儿没有做安全检查的原因是，因为在实际的数组中，我们访问一个不存在的值时可能导致程序崩溃，这儿也是这样的
DynamicArray *dynamicarray = (DynamicArray *)DArray;
return dynamicarray->Array[Pos];
}
查看某个数据在当前的数组中是否存在
int GetByVal_DynamicArray(void *DArray, void *Val, COMPARE compare)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
for (int i = 0; i < dynamicarray->ArrayLen; ++i)
{
if (!compare(dynamicarray->Array[i], Val))
{
return i;
}
}
return -1;
}
// 遍历（打印当前的数组）
void Traversal_DynamicArray(void *DArray, TRAVERSAL traversal)
{
if (DArray == NULL)
{
return;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
printf("<……………………………………………………>\n");
for (int i = 0; i < dynamicarray->ArrayLen; ++i)
{
traversal(dynamicarray->Array[i]);
}
}
// 对当前的数组的释放
int Destroy__DynamicArray(void *DArray)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
if (dynamicarray->Array != NULL)
{
free(dynamicarray->Array);
dynamicarray->Array = NULL;
}
free(dynamicarray);
dynamicarray = NULL;
return 0;
}
一些其他功能:
// 得到数组的长度
int Size_DynamicArray(void *DArray)
{
if (DArray == NULL)
{
return 0;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
return dynamicarray->ArrayLen;
}
// 得到数组的容量
int Capacity_DynamicArray(void *DArray)
{
if (DArray == NULL)
{
return 0;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
return dynamicarray->Capacity;
}
数组的逆置
int Inverted_DynamicArray(void *DArray)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
for (int i = 0; i < dynamicarray->ArrayLen / 2; ++i)
{
void *temp = dynamicarray->Array[i];
dynamicarray->Array[i] = dynamicarray->Array[dynamicarray->ArrayLen - 1 - i];
dynamicarray->Array[dynamicarray->ArrayLen - 1 - i] = temp;
}
return 0;
}
// 数组的排序
int Sort__DynamicArray(void *DArray, COMPARE compare)
{
if (DArray == NULL)
{
return -1;
}
DynamicArray *dynamicarray = (DynamicArray *)DArray;
if (dynamicarray->ArrayLen == 1)
{
return 0;
}
Quick_Sort(dynamicarray->Array, 0, dynamicarray->ArrayLen - 1, compare);
return 0;
}
这个没有给出Quick_Sort(dynamicarray->Array, 0, dynamicarray->ArrayLen - 1, compare)函数，主要是因为这个值修改来自于快排，要相信自己也是可以的。
源码可能会被放到github上面。最近在培训时间学习怎么使用github，如果你有想关的操作的视频教程欢迎你分享给我！
谢谢！！
通用型动态数组的总结