前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
使用C语言实现一个简单的ArrayList，能够具备动态扩容的功能，为后面的C语言实现的算法奠定基础数据结构
解决方案
基本数据结构又两部分实现：
1、ArrayList.h 头文件用来定义结构和操作结构的所有方法签名
2、ArrayList.c 源文件用来实现操作结构的所有方法
详情看代码
代码编写
java语言版本
1、ArrayList.h
#ifndef MYCPROJECT_ARRAYLIST_H
#define MYCPROJECT_ARRAYLIST_H
#endif //MYCPROJECT_ARRAYLIST_H
/*****************************************************************************************************
* 由于C++编译器支持重载，函数名称会做一些处理，而在c中仅是简单函数名，这里定义为了告诉c++编译器按照C语言的方式编译即可*
*****************************************************************************************************/
#ifdef __cplusplus
extern "C"
{
#endif
/**
* 类似于java ArrayList功能
* 1、元素地址连续，支持随机访问
* 2、支持增删改查
* 3、支持动态扩容
*/
/**
* 列表初始化配置
*/
// 列表的初始化大小
#define INIT_SIZE 15
// 扩容倍数
#define INCREASE_PERC 1.5
/**
* 列表的结构名称定义
*/
// 定义
typedef struct Data Data;
typedef struct ArrayList ArrayList;
/**
* 列表的结构定义(相当于对象,但是方法定义不在对象中)
*/
// 列表元素，内部统一封装了一个指向内存的指针，可以不确定类型
struct Data {
void *data;
};
// 列表，维护一个指向任何地方的指针，并且维护整个列表的长度和所占内存的大小，此处的内存指的是指针占的内存
struct ArrayList {
// 存储数据的开头，随机访问直接游标即可
Data* datas;
// 当前列表有效元素长度
int len;
// 列表所占内存大小
int size;
};
/*****************************************************************************
* 定义操作结构的方法，相当于对象中的方法，c语言面向过程编程，也就是面向函数编程，主体是函数*
* ***************************************************************************/
/**
* 初始化列表
* 1、给list数组分配内存
* 2、初始化各变量长度
* @return 成功时返回ArrayList结构地址
*/
ArrayList* init_array_list();
/**
* 插入一个元素
* @param list
* @param p_data
* @param index 如果为0，则从头插入，如果为-1,则从尾部插入
* @return
*/
int array_list_insert(ArrayList *list, void* p_data, long index);
/**
* 获取一个元素
* @param list
* @param index
* @return 直接返回数据指针
*/
void* array_list_get(ArrayList* list, long index);
/**
* 删除元素
* @param list
* @param index
*/
void array_list_remove_at(ArrayList* list, long index);
/**
* 清空数组元素，不释放内存
* @param list
*/
void array_list_clear(ArrayList* list);
/**
* 释放数组内存
* @param list
*/
void array_list_free(ArrayList* list);
/**
* 判空
* @param list
* @return
*/
int array_list_is_empty(ArrayList* list);
#ifdef __cplusplus
};
#endif
ArrayList.c
#include <string.h>
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include "arraylist.h"
/********************************************
* 该文件为头文件的方法实现 *
********************************************/
/**
* 初始化列表:申请一块内存并初始化完成后，将内存的地址返回
* 1、Arraylist结构分配一波内存
* 2、给ArrayList结构中的data指针分配一波内存用来存储data结构列表
* @return 成功时返回ArrayList结构地址
*/
ArrayList* init_array_list(){
int i = 0;
// 先给列表分配内存
ArrayList* list = calloc(1, sizeof(ArrayList));
if (NULL == list) {
return NULL;
}
// 在给列表中的data分配内存
list->datas = calloc(INIT_SIZE, sizeof(Data));
if (NULL == list->datas) {
return NULL;
}
for (i = 0; i < INIT_SIZE; ++i)
{
// 地址给0相当于null
// datas[i] 当指针通过数组访问返回的引用，不是地址，该引用直接表示了data，所以这里使用"."来访问data
// 但是list是指针，表示的是地址，通过地址直接访问datas成员时，就需要使用"->"来访问
// datas[i].data等价与 (&datas[i]) -> data，先取到引用的地址再访问data
list->datas[i].data = 0;
}
// 元素长度
list->len = 0;
// data内存长度
list->size = INIT_SIZE;
return list;
}
/**
* 插入一个元素
* @param list
* @param p_data
* @param index 如果为0，则从头插入，如果为-1, 则从尾部插入
* @return
*/
int array_list_insert(ArrayList *list, void* p_data, long index){
// 如果要扩容，则扩容后的内存量
int relloc_size = 0;
// 参数校验.list不为null，index不可以越界
if (NULL == list || index < -1 || index >= list->len) {
return -1;
}
// 判断扩容,未插入前如果长度还剩一个位置，则开始扩容
if (list->len == list -> size - 1) {
// 判断1.5倍是否越界
int newCapacity = list->size * INCREASE_PERC;
if (newCapacity - INT_MAX > 0) {
// 如果新的数组越界了则为负数,则线性增加
newCapacity = list->size+1;
}
if (newCapacity - INT_MAX > 0) {
// 还是大于最大值，则返回-1
return -1;
}
// 重新分配内存
list->datas = realloc(list->datas, sizeof(Data) * newCapacity);
if (NULL == list->datas) {
// 分配内存失败
return -1;
}
// 新分配的内存需要初始化
for (int i = list->len; i < list->size; ++i) {
list->datas[i].data = 0;
}
list->size = newCapacity;
}
// 放入新的data
if (-1 == index) {
// 插入尾部
list->datas[list->len].data = p_data;
}else {
// 插入指定位置
void* tem = p_data;
void* tem2 = NULL;
for (int i = index; i <= list->len; ++i) {
tem2 = list->datas[i].data;
list->datas[i].data = tem;
tem = tem2;
}
}
list->len++;
return 1;
}
/**
* 获取一个元素
* @param list
* @param index
* @return 直接返回数据指针
*/
void* array_list_get(ArrayList* list, long index) {
// 参数校验
if (NULL == list || index < -1 || index >= list->len) {
return NULL;
}
// index = -1 返回最后一个元素
return index == -1 ? list->datas[list->len-1].data : list->datas[index].data;
}
/**
* 删除元素
* @param list
* @param index
*/
void array_list_remove_at(ArrayList* list, long index) {
// 参数校验
if (NULL == list || index < -1 || index >= list->len) {
return;
}
if (index == -1) {
// 删除最后一个元素
list->datas[list->len-1].data = NULL;
list->len--;
return;
}
// 删除元素，将元素覆盖过来即可
int next = index+1;
for (; next < list->len; ++next) {
list->datas[next-1].data = list->datas[next].data;
}
// 将最后一个元素变成null
list->datas[next].data = NULL;
list->len--;
return;
}
/**
* 清空数组元素，不释放内存
* @param list
*/
void array_list_clear(ArrayList* list) {
if (NULL == list) {
return;
}
// 将每一个data都指向NULL
int i = 0;
for (i = 0; i < list->len; ++i) {
list->datas[i].data = NULL;
}
// 长度改变
list->len = 0;
return;
}
/**
* 释放数组内存
* @param list
*/
void array_list_free(ArrayList* list) {
if (NULL == list) {
return;
}
// 先释放list中的datas
if (list->datas != NULL) {
free(list->datas);
}
free(list);
return;
}
/**
* 判空
* @param list
* @return
*/
int array_list_is_empty(ArrayList* list) {
if (NULL == list) {
return 0;
}
if (list->len == 0) {
return 1;
}else {
return 0;
}
}
/**
* 测试用例
* @return
*/
int main(void) {
setbuf(stdout, NULL);
ArrayList* list = init_array_list();
int ints[] = {5,4,6,3,4,5,6};
int len = 7;
for (int i = 0; i < len; ++i) {
array_list_insert(list, &ints[i], -1);
}
// array_list_insert(list, &i,-1);
if (array_list_is_empty(list) == -1) {
printf("the list is empty \n");
}
for (int j = 0; j < len; ++j) {
printf("the %d num is %d \n", j,*(int*)array_list_get(list, j));
}
// array_list_clear(list);
// i=200;
// array_list_insert(list, &i,-1);
// printf("the first num is %d \n", *(int*)array_list_get(list, 0));
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
Arraylist 是我们最经常使用的数据结构，c语言和java语言的设计思想存在很大的差异，对于面向过程的开发语言，我深刻的能够感觉到c语言任何一个函数的定义都是一个过程，执行的过程中需要将操作的结构指针传入，这里对于面向对象开发的我来说其实很不适应。
第一次发布c语言哈，拙劣写法看看就好，哈哈。