动态线性表的操作
//ARRAY.H
# ifndef ARRAY
# define ARRAY
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
/*
线性表是零个或者多个数据元素的有限序列
特性:
数据原始之间是有顺序的；
数据元素的个数是有限的；
数据元素的类型必须相同
过程如下：
1.当插入一个新的元素的时候,这个时候发现空间不足。
2.将原空间的数据拷贝到新的空间。
3.释放掉旧的空间。
4.把元素放入新的空间。
*/
//动态增长内存，策略 将存放数据的内存放到?堆上
//动态数组 如果5个元素
//容量capacity表示我的这块内存空间一共可以存放多少元素
//sizeof概念记录当前数组中具体的元素个数
//动态数组的结构体定义完了
typedef struct ARRAY
{
int* pAddr;//存放数据的地址
int size;//当前有多少个元素
int capacity;//容量,我容器当前最大能容纳多少元素
}_ARRAY;
//写一系列的相关对ARRAY结构体操作的函数
//初始化
_ARRAY* _ARRAY_Init();
//插入
void Push_Back__ARRAY(_ARRAY* arr, int value);
//根据位置删除
void Remove__ARRAY(_ARRAY* arr, int pos);
//根据值删除
void Remove_ByValue__ARRAY(_ARRAY* arr, int value);
//查找
int Find_ARRAY(_ARRAY* arr, int value);
//打印
void Print_ARRAY(_ARRAY* arr);
//释放动态数组的内存
void FreeSpace_ARRAY(_ARRAY* arr);
//清空数组
void Clear_ARRAY(_ARRAY* arr);
//获得动态数组容量
int Capacity_ARRAY(_ARRAY* arr);
//获得动态数据当前元素个数
int Size_ARRAY(_ARRAY* arr);
//根据位置获得某个位置元素
//ARRAY.CPP
# include "ARRAY.h"
//动态数组初始化
_ARRAY* _ARRAY_Init()
{
_ARRAY* MyArray = (_ARRAY*)malloc(sizeof(_ARRAY));
MyArray->size = 0;
MyArray->capacity = 20;
MyArray->pAddr = (int*)malloc(sizeof(int) *MyArray->capacity);
return MyArray;
}
//插入
void Push_Back__ARRAY(_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 *= 2;
arr->pAddr = newSpace;
}
//插入新元素
arr->pAddr[arr->size] = value;
arr->size++;
}
//根据位置删除
void Remove__ARRAY(_ARRAY* arr, int pos)
{
if(arr == NULL)
{
return ;
}
//判断位置是否有效
if(pos < 0 || pos >= arr->size)
{
return ;
}
//删除元素
for(int i = pos; i < arr->size - 1; i++)
{
arr->pAddr[i] = arr->pAddr[i + 1];
}
arr->size--;
}
//根据值删除
void Remove_ByValue__ARRAY(_ARRAY* arr, int value)
{
if(arr == NULL)
{
return ;
}
//找到值得位置
int pos = Find_ARRAY(arr, value);
//根据位置删除
Remove__ARRAY(arr, pos);
}
//查找
int Find_ARRAY(_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;
}
//打印
void Print_ARRAY(_ARRAY* arr)
{
if(arr == NULL)
{
return ;
}
int p = 0;
for(int i = 0; i < arr->size; i++)
{
if(p)
{
printf(" ");
}
p = 1;
printf("%d", arr->pAddr[i]);
}
printf("\n");
}
//释放动态数组的内存
void FreeSpace_ARRAY(_ARRAY* arr)
{
if(arr == NULL)
{
return ;
}
if(arr->pAddr != NULL)
{
free(arr->pAddr);
}
free(arr);
}
//清空数组
void Clear_ARRAY(_ARRAY* arr)
{
if(arr == NULL)
{
return ;
}
//pAddr->空
arr->size = 0;
}
//获得动态数组容量
int Capacity_ARRAY(_ARRAY* arr)
{
if(arr == NULL)
{
return -1;
}
return arr->capacity;
}
//获得动态数据当前元素个数
int Size_ARRAY(_ARRAY* arr)
{
if(arr == NULL)
{
return -1;
}
return arr->size;
}
//根据位置获得某个位置元素
int At_ARRAY(_ARRAY* arr, int pos)
{
return arr->pAddr[pos];
}
# endif
//main()
# include "ARRAY.h"
void test01()
{
//初始化动态数组
_ARRAY* MyARRAY = _ARRAY_Init();
//打印容量
printf("数组容量 %d\n", Capacity_ARRAY(MyARRAY));
printf("元素数量 %d\n", Size_ARRAY(MyARRAY));
//插入元素
for(int i = 0; i < 30; i++)
{
Push_Back__ARRAY(MyARRAY,i);
}
//打印容量
printf("数组容量 %d\n", Capacity_ARRAY(MyARRAY));
printf("元素数量 %d\n", Size_ARRAY(MyARRAY));
//打印
Print_ARRAY(MyARRAY);
//删除
Remove__ARRAY(MyARRAY, 0);
Remove_ByValue__ARRAY(MyARRAY,27);
//打印
Print_ARRAY(MyARRAY);
//查找5个位置
int pos = Find_ARRAY(MyARRAY, 5);
printf("5查找到:pos: %d %d\n", pos, At_ARRAY(MyARRAY, pos));
//销毁
FreeSpace_ARRAY(MyARRAY);
}
int main()
{
test01();
return 0;
}