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

2024-11-21 技术教程

在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;//创建并且返回一个空的ArrayListMyArrayList* ArrayList_Create(int cap);//销毁一个线性表ArrayListvoid ArrayList_Destroy(MyArrayList* list);//将一个线性表ArrayList中的所有元素清空void ArrayList_Clear(MyArrayList* list);//返回一个线性表ArrayList中的所有元素个数int ArrayList_Length(MyArrayList* list);//向一个线性表ArrayList的pos位置处插入新元素nodeint 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;}