自制可变数组
具有的功能：
- 初始化
- 判断是否为空
- 判断是否满
- 展示数组
- 在末尾追加值（若数组已满可自动增长）
- 在中间插入值
- 删除指定位置的值
- 倒置数组
- 整理数组
搭建（diy）过程
- 自定义一个结构类型 Arr，包含一个指针 pBase、数组总长度 len、数组有效长度 cnt；
typedef struct {
int *pBase;
int len;
int cnt;
} Arr;
int main(void)
{
Arr arr;
return 0;
}
- 指针 pBase 就类似普通数组中数组变量名的作用，对其进行操作就可以获得数组中的任一元素
- 有了结构类型 Arr 后，若只是单纯命名一个 Arr 变量，这个变量是不包含任何有效信息的，这时其中的pBase 没有指向任何有效区域，而且数组总长度 len 也没有给出，所以需要对其进行初始化，编写初始化函数 init_arr();
void init_arr(Arr * pArr, int length);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
return 0;
}
void init_arr(Arr * pArr, int length)
{
pArr->pBase = (int *)malloc(sizeof(int) * length);
//使 pBase 指向一片长度为 length * sizeof(int)的空间，即此时 arr 中可以装 length 个 int
if ( pArr->pBase == NULL ) // 若 malloc 函数返回 NULL 值，说明内存不足，此时终止程序
{
printf("动态内存分配失败！！！n");
exit(-1); //终止整个程序
}
else
{
pArr->len = length; //将数组总长度保存在 Arr 类型的 len 中
pArr->cnt = 0; //将数组有效长度保存在 Arr 类型的 cnt 中，初始为 0
}
return;
}
- 有了初始化的功能后，如果要查看该数组，采用循环的方式就很不方便了，此时可以定义一个 show_arr() 函数，使其直接能够展示给用户看，需要注意的是，如果数组为空，需要告诉用户，这时可以用一个返回bool 值的 is_empty() 函数来完成判断；
bool is_empty(Arr * pArr);
void show_arr(Arr * pArr);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
show_arr(&arr);
return 0;
}
bool is_empty(Arr * pArr)
{
if ( pArr->cnt == 0 ) // 对数组当前的有效数字进行判断，若为 0，则数组为空
{
return true;
}
else
{
return false;
}
}
void show_arr(Arr * pArr)
{
if ( is_empty(pArr) )
{
printf("还没有向数组添加任何元素！！！n");
}
else
{
for ( int i=0;icnt;i++ )
{
printf("%d ", pArr->pBase[i]);
// pArr->pBase[i] <<==>> *pArr->pBase
}
printf("n");
}
}
- 到现在为止，还没有办法向数组添加任何元素，先定义一个简单的 append_arr() 函数，其作用是在数组的末尾添加一个元素，这时需要注意，如果数组的空间已满，就无法简单的在最后插入一个元素了，而需要增大数组空间，这里使用的是申请另一块大内存的方式来实现”自动扩容“功能，还需要一个判断数组是否已满的函数；
bool is_full(Arr * pArr);
void append_arr(Arr * pArr, int val);
const int unit = 4; //定义一个常量 unit，代表数组空间不够时增长的大小
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
append_arr(&arr, 2);
append_arr(&arr, 7);
show_arr(&arr);
return 0;
}
bool is_full(Arr * pArr)
{
if ( pArr->cnt < pArr->len )
// 将当前数组有效长度与总长度进行比较，若 cnt>=len 已满
{
return false;
}
else
{
return true;
}
}
void append_arr(Arr * pArr, int val)
{
// val 代表添加元素的值
if ( is_full(pArr) )
{
int * p;
int length = pArr->len + unit;
p = (int *)malloc(sizeof(int) * length);
// 申请另一块比原数组空间大 1 个的 unit 的数组
if ( p == NULL ) // 若 malloc 函数返回 NULL 值，
// 说明内存不足，此时终止程序
{
printf("动态内存分配失败！！！n");
exit(-1); //终止整个程序
}
else
{
for ( int i=0;icnt;i++ )
{
p[i] = pArr->pBase[i];
// 将原数组空间中的值赋值给新数组空间
}
free(pArr->pBase);
// 完成赋值后，将原数组空间释放，避免占用系统空间
pArr->pBase = p;
// 将新申请到的数组空间赋值给原数组的指针，即使得原数组的指针指向新的一片大空间
pArr->pBase[pArr->cnt++] = val;
// 将新添加的元素放到数组最后位置，并将有效长度 cnt++
pArr->len = length;
// 更新数组长度
}
}
else
{
pArr->pBase[pArr->cnt++] = val;
// 将新添加的元素放到数组最后位置，并将有效长度 cnt++
}
return;
}
- 有了在末尾添加元素的功能后，感觉还需要一个在数组中间插入元素的功能，不然感觉缺了一块，于是来定义一个 insert_arr() 函数实现此功能，与 append_arr() 函数相似，需要在数组已满时”自动扩容“；
void insert_arr(Arr * pArr, int pos, int val);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
append_arr(&arr, 2);
append_arr(&arr, 7);
insert_arr(&arr, 2, 3);
show_arr(&arr);
return 0;
}
void insert_arr(Arr * pArr, int pos, int val)
{
// pos 代表插入元素的位置，从 1 开始
// val 代表插入元素的值
if ( is_full(pArr) )
// 如果数组已满，需要申请另一片大空间，对数组”扩容“，并分两次（插入位置前后）将原数组元素 // 写入新的数组空间
{
int * p;
int length = pArr->len + unit;
p = (int *)malloc(sizeof(int) * length);
if ( p == NULL ) // 若 malloc 函数返回 NULL 值，
// 说明内存不足，此时终止程序
{
printf("动态内存分配失败！！！n");
exit(-1); //终止整个程序
}
else
{
for ( int i=0;ipBase[i];
// 将原数组元素位于插入位置之前的元素赋值到新的数组内存中
}
p[pos-1] = val;
// 将 val 的值赋给对应位置
pArr->cnt++;
// 原数组 cnt 的值加 1，即有效数字加一
for ( int i=pos;icnt;i++ )
{
p[i] = pArr->pBase[i-1];
// 将原数组元素位于插入位置之后的元素赋值到新的数组内存中
}
free(pArr->pBase);
// 完成赋值后，将原数组空间释放，避免占用系统空间
pArr->pBase = p;
// 将新申请到的数组空间赋值给原数组的指针，即使得原数组的指针指向新的一片大空间
pArr->len = length;
// 更新数组有效长度
}
}
else
// 若函数还有空间，只需要将数组中位于插入位置之后的值向后移一个内存，给对应位置留空即可
{
for ( int i=pArr->cnt;i>pos-1;i-- )
{
pArr->pBase[i] = pArr->pBase[i-1];
// 将原数组元素位于插入位置之后的元素往后移位
}
pArr->pBase[pos-1] = val;
// 将 val 的值赋给对应位置
pArr->cnt++;
// 原数组 cnt 的值加 1，即有效数字加一
}
return;
}
- 此时数组已经可以随意添加任意的元素了，这就足够了吗？当然不够，光增不减可不行，还需要一个删除元素的功能，delete_arr() 可以删除指定位置的元素，并告诉用户删除掉的值是多少以及数组剩下多少个有效值；
void delete_arr(Arr * pArr, int pos);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
append_arr(&arr, 2);
append_arr(&arr, 7);
insert_arr(&arr, 2, 3);
show_arr(&arr);
delete_arr(&arr, 3);
show_arr(&arr);
return 0;
}
void delete_arr(Arr * pArr, int pos)
{
int val;
if ( is_empty(pArr) )
// 删除前先判断数组里面有没有值，没有值可没办法删
{
printf("数组为空！！！删除失败n");
}
else
{
if ( pos <= pArr->cnt)
// 如果有值还需要判断删除的位置有没有大于数组有效长度，如果这个位置比数组有效长度还长 // 也没法删除
{
val = pArr->pBase[pos-1];
// 先将这个值保存到变量 val 中，之后要告诉用户
for ( int i=pos-1;icnt-1;i++ )
{
pArr->pBase[i] = pArr->pBase[i+1];
// 直接将位于这个值之后的值向前移动一位，以此覆盖掉那个位置的值
}
pArr->cnt--;
// 删除掉了一个值，所以有效长度减一
printf("删除掉的数字是 %d, 数组还剩下 %d 个有效值n",val,pArr->cnt);
// 告知用户
}
else
{
printf("删除位置大于当前数组有效长度！！！删除失败n");
}
}
return;
}
- 有了基本的增减元素功能之后，还需要一些进阶功能才能使得数组变得易用，先来个倒置的功能吧，inverse_arr() 函数可以将当前数组的有效值顺序取反，由”正序变为反序“；
void inverse_arr(Arr * pArr);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
append_arr(&arr, 2);
append_arr(&arr, 7);
insert_arr(&arr, 2, 3);
show_arr(&arr);
delete_arr(&arr, 3);
inverse_arr(&arr);
show_arr(&arr);
return 0;
}
void inverse_arr(Arr * pArr)
{
// 倒置函数将由一个倒置算法实现：
// 其中 i 为数组初始序列，即为 0， j 为数组最后序列，为 cnt-1
// t 用来保存值，理解成 temp
int t;
int i = 0;
int j = (pArr->cnt)-1;
while ( i < j )
// 用 while 循环来进行这个过程，整个过程如下：
// 将数组头部的值赋给 t ，将数组尾部的值赋给数组头部，将 t 的值赋给数组尾部
// 实现一次交换，随后将头部指针向后移一位，尾部指针向前移一位，重复上述过程，直到前面的指针大于后面的指针就停止整个过程
{
t = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = t;
i++;
j--;
}
return;
}
- 有了各种花里胡哨的功能之后，数组成功的被用户给弄乱了，这时候又需要整理整个数组，sort_arr() 函数可以将数组按照从小到大的顺序排列，排序算法后面学了再来补充
void sort_arr(Arr * pArr);
int main(void)
{
Arr arr;
int length = 2;
init_arr(&arr, length);
append_arr(&arr, 2);
append_arr(&arr, 7);
insert_arr(&arr, 2, 3);
show_arr(&arr);
delete_arr(&arr, 3);
inverse_arr(&arr);
show_arr(&arr);
sort_arr(&arr);
return 0;
}
void sort_arr(Arr * pArr)
{
// ”首值比小“算法
int t;
for ( int i=0;icnt;i++ )
{
for ( int j=i+1;jcnt;j++ )
{
if ( pArr->pBase[j] < pArr->pBase[i] )
{
t = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = t;
}
}
}
}
- 到这里我自己 diy 的一个简单的数组就完成了，期待链表的学习，因为这个可变数组的缺陷很明显，如果数组太大的话，申请一块内存再重写的方式很鸡肋，甚至在释放掉原数组之前还可能造成内存占用过大！
