数据结构-数组代码实现(C语言)
#include <>
#include <>
#define DEFAULT_SIZE 1024 // 一个page是4k
typedef struct array
{
int *pData; //指针变量，存放数组第一个元素地址。
int length; //数组当前长度(有几个元素)。
int size; //数组空间大小
}Array;
void init(Array &arr)
{
//初始化，给数组申请空间。
arr.length = 0;
arr.size = DEFAULT_SIZE;
arr.pData = new int[arr.size];
// 数组分配在栈上，内存的释放由程序自己执行
// new出来的数据，分配在堆上，大小可以是运行时确定，释放由程序员负责。
}
void destroy(Array &arr)
{
delete[] arr.pData;
arr.length = 0;
arr.size = 0;
}
void expand(Array &arr)
{
// 扩容原理：申请一段比原来更大的新空间，把数据拷贝过去。再清空旧空间的数据。
int osize = arr.size;
int *opData = arr.pData;
arr.size *= 2;
arr.pData = new int[arr.size];
// 方法一：memcpy
// memcpy拷贝的效率要比手动拷贝高
// memcpy支持任意一段内存拷贝到另外一段内存
// memcpy(, opData, osize*sizeof(int));
// 方法二：手动自己拷贝
for(int i = 0; i < osize; i++)
{
*(arr.pData + i) = *(opData + i);// 从头到尾，取指针对应的地址的值，放到新空间中。
}
delete[] opData;// 因为是new出来的空间，需要程序员释放
}
// 根据下标返回值。index有效，返回值；无效，返回0
int get(Array &arr, int index)
{
if(index >= 0 && index < arr.length)
{
return *(arr.pData + index);
}
else
{
return 0;
}
}
void set(Array &arr, int index, int value)
{
if(index >= 0 && index < arr.length)
{
*(arr.pData + index) = value;
}
}
int getLength(Array &arr)
{
return arr.length;
}
int find(Array &arr, int value)
{
int pos = -1;
for(int i = 0; i < arr.length; i++)
{
if(*(arr.pData + i) == value)
{
pos = i;
break;
}
}
return pos;
}
int prev(Array &arr, int index)
{
return get(arr, index-1);
}
int next(Array &arr, int index)
{
return get(arr, index+1);
}
void insert(Array &arr, int index, int value)
{
// 有可能数组已经满了
if(arr.length >= arr.size)
{
expand(arr);
}
if(index == -1 || index == arr.length || (index >= 0 && index < arr.length))
{
if(index >= 0 && index < arr.length)
{
// memcpy
memcpy(arr.pData + index + 1, arr.pData + index, (arr.length - index)*sizeof(int));
// 手动拷贝
}
else
{
if(index == -1)
{
index = arr.length;
}
}
*(arr.pData + index) = value;
arr.length++;
}
}
void remove(Array &arr, int index)
{
// index 存在
if(index >= 0 && index < arr.length)
{
// memcpy
memcpy(arr.pData + index, arr.pData + index + 1, (arr.length - index - 1)*sizeof(int));
// 手工拷贝
arr.length--;
}
}
void traverse(Array &arr)
{
for(int i = 0; i < arr.length; i++)
{
printf("%d ", *(arr.pData+i));
}
printf("\n");
}
int main()
{
// 会写测试用例 正常case+边界case
Array a;
init(a);
printf("%d,%d\n", a.size, a.length);
insert(a, 0, 1);
insert(a, 0, 2);
insert(a, 0, 3);
insert(a, 1, -1);
traverse(a);
printf("%d, %d\n", find(a, 3), find(a, 10));
remove(a, 2);
traverse(a);
destroy(a);
printf("%d,%d\n", a.size, a.length);
return 0;
}