C语言实现ArrayList (线性表顺序存储结构)

在Java中动态数组为ArrayList, C++ STL中为Vector. JAVA,C++中均采用泛型来实现，实现了数据结构与存储类型的分离。在C语言中没有泛型。故采用void 指针来实现泛型的效果。

arraylist.h

#ifndef ARRAY_LIST_H #define ARRAY_LIST_H #include<stdio.h> #include<stdlib.h> #include<memory.h> typedef void MyArrayListNode; typedef struct _ArrayList { int length; //当前长度 int capacity; //容量 unsigned int* data;//数组指针 }MyArrayList; //创建并且返回一个空的ArrayList MyArrayList* ArrayList_Create(int cap); //销毁一个线性表ArrayList void ArrayList_Destroy(MyArrayList* list); //将一个线性表ArrayList中的所有元素清空 void ArrayList_Clear(MyArrayList* list); //返回一个线性表ArrayList中的所有元素个数 int ArrayList_Length(MyArrayList* list); //向一个线性表ArrayList的pos位置处插入新元素node int ArrayList_Insert(MyArrayList* list, MyArrayListNode* node, int pos); //获取一个线性表ArrayList的pos位置处的元素 MyArrayListNode* ArrayList_Get(MyArrayList* list, int pos); //删除一个线性表ArrayList的pos位置处的元素 返回值为被删除的元素，NULL表示删除失败 MyArrayListNode* ArrayList_Delete(MyArrayList* list, int pos); //增加ArrayList 空间大小，返回新空间大小 int grow(MyArrayList* list, int size); #endif // !ARRAY_LIST_H

arraylist.c

#include"arraylist.h" MyArrayList* ArrayList_Create(int capacity) { MyArrayList *list = NULL; list = (MyArrayList *)malloc(sizeof(MyArrayList)); if (list == NULL) { fprintf(stderr,"create ArrayList failed.\n"); return NULL; } memset(list, 0, sizeof(list)); list->data = (unsigned int*)malloc(sizeof(unsigned int*) * capacity); if (list->data == NULL) { fprintf(stderr, "malloc data space failed.\n"); return NULL; } list->capacity = capacity; list->length = 0; return list; } void ArrayList_Destroy(MyArrayList* list) { if (list == NULL) { return; } if (list->data) { free(list->data); } free(list); } void ArrayList_Clear(MyArrayList* list) { if (list == NULL) { return; } list->length = 0; } int ArrayList_Length(MyArrayList* list) { MyArrayList* arrayList = (MyArrayList* )list; return arrayList->length; } int ArrayList_Insert(MyArrayList* list, MyArrayListNode* node, int pos) { if (list == NULL) { return -1; fprintf(stderr,"the ArrayList is Null\n"); } if (pos < 0) { return -2; fprintf(stderr, "the ArrayList is Null\n"); } if (list->length == list->capacity) { fprintf(stdout, "the ArrayList is Full,Grow Capacity\n"); int ret = grow(list,list->capacity * 2); if (ret == -1) { return -3; } } for (int i = list->length; i > pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos] = (unsigned int)node; list->length += 1; return 0; } MyArrayListNode* ArrayList_Get(MyArrayList* list, int pos) { if (list == NULL || pos < 0 || pos > list->length) { fprintf(stderr,"wrong arguments\n"); return NULL; } return (MyArrayListNode*)list->data[pos]; } MyArrayListNode* ArrayList_Delete(MyArrayList* list, int pos){ if (list == NULL || pos < 0 || pos > list->length) { fprintf(stderr, "wrong arguments\n"); return NULL; } MyArrayListNode* node = (MyArrayListNode*)list->data[pos]; for (int i = pos + 1; i < list->length; i++) { list->data[i-1] = list->data[i]; } list->length--; return node; } int grow(MyArrayList* list, int size) { if (list == NULL || size < list->capacity) { fprintf(stderr, "wrong argument.\n"); return -1; } int newSize = size; if (size > 2 * list->capacity) { newSize = 2 * list->capacity; } unsigned int* oldData = list->data; unsigned int* newData = malloc(newSize * sizeof(unsigned int*)); if (newData == NULL) { fprintf(stderr,"grow capacity failed.\n"); return -1; } list->data = newData; memset(list->data,0,sizeof(list->data)); memcpy(list->data, oldData, sizeof(oldData)*list->length); list->capacity = newSize; free(oldData); return newSize; }