数据结构【动态数组】

数据结构【动态数组】

在堆中申请数组空间,扩容时realloc,注意不可增删改的情况并处理即可。

以下代码不一定完全正确。

#include <stdio.h>
#include <stdlib.h>
/**
 * 声明动态数组,并提供相关的函数操作
 */
// 动态数组结构体
typedef struct Array
{
 // 动态数组
 int *elementData;
 // 容量
 size_t capacity;
 // 长度
 size_t size;
} DynamicArray;
// 初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity);
// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array);
// 调整动态数组内存大小
void resizeDynamicArray(DynamicArray *array, size_t newCapacity);
// 获取动态数组长度(元素个数)
size_t getLength(const DynamicArray *array);
// 在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element);
// 在末尾插入新元素
void insertEnd(DynamicArray *array, int element);
// 删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index);
// 删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array);
// 遍历所有的元素
void print(DynamicArray *array);
/**
 * 主函数
*/
int main(int argc, char const *argv[])
{
 DynamicArray array;
 initDynamicArray(&array, 2);
 insertAt(&array, 0, 10);
 insertAt(&array, 0, 20);
 insertAt(&array, 0, 20);
 print(&array);
 getchar();
 return 0;
}
// 初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity){
 // 分配空间
 if (initialCapacity > 0) {
 array->elementData = (int *) malloc(initialCapacity * (sizeof(int)));
 } else if (initialCapacity == 0) {
 array->elementData = NULL;
 } else {
 printf("您输入的长度不合法。");
 return;
 }
 // 初始化capacity
 array->capacity = initialCapacity;
 // todo 初始化size
 array->size = 0;
}
// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array){
 free(array->elementData);
}
// 扩容
void resizeDynamicArray(DynamicArray *array, size_t newCapacity){
 printf("1.5倍扩容启动\n");
 array->elementData = realloc(array->elementData, newCapacity*sizeof(int));
 array->capacity += array->capacity>>1;
}
// 获取动态数组长度(元素个数)
size_t getLength(const DynamicArray *array){
 return array->size;
}
// 在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element){
 // index 不符合规则的情况
 if(index < 0 || index > array->size){
 printf("无效的位置输入\n");
 return;
 }
 (array->size == array->capacity) ? resizeDynamicArray(array, array->capacity += array->capacity>>1) : 0;
 //
 for(int i = array->size; i>index; i--){
 array->elementData[i] = array->elementData[i-1];
 }
 array->elementData[index] = element;
 array->size++;
}
// 在末尾插入新元素
void insertEnd(DynamicArray *array, int element){
 insertAt(array, array->size, element);
}
// 删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index){
 if(index < 0 || index >= array->size){
 printf("无效的元素删除\n");
 return -1;
 }
 int temp = array->elementData[index];
 for(int i = index+1; i<array->size; i++){
 array->elementData[i-1] = array->elementData[i];
 }
 array->size--;
 return temp;
}
// 删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array){
 return deleteAt(array, array->size-1);
}
// 遍历所有的元素
void print(DynamicArray *array){
 for(int i = 0; i<array->size; i++){
 printf("%d\n", array->elementData[i]);
 }
 printf("\n");
}
作者:持枢丶原文地址:https://www.cnblogs.com/wangsiyaoa/p/17881944.html

%s 个评论

要回复文章请先登录注册