C语言利用动态数组实现顺序表（不限数据类型）

实现任意数据类型的顺序表的初始化，插入，删除（按值删除；按位置删除），销毁功能。、

顺序表结构体

　　实现顺序表结构体的三个要素：（1）数组首地址；（2）数组的大小；（3）当前数组元素的个数。

11 //顺序表结构体
22 struct DynamicArray{
33     void **addr; //指向数组的首地址（指向数组的指针）
44     int capacity; //数组的大小
55     int size; //当前数组元素的个数
66 };

注意事项：void **addr为二级指针，即数组的元素也为指针，因为我们并不知道用户的输入数据是什么类型，操作数据的地址是最安全的方法。

初始化

　　对顺序表进行初始化，实际上为初始化顺序表内的各个成员，另外对输入的参数做边界处理。

1 1 //初始化数组,初始化结构体和里面的元素。初始化之后返回该数组,写为void*
2 2 void *Init(int capacity_){
3 3     if (capacity_ <= 0){
4 4         return NULL;
5 5     }
6 6     
7 7     struct DynamicArray *arr = malloc(sizeof(struct DynamicArray));//开辟一个结构体就可以了
8 8     if (NULL == arr){
9 9         return NULL;
1010     }
1111 
1212     arr->capacity = capacity_;
1313     arr->addr = malloc(sizeof(void*)*arr->capacity);//对数组开辟内存
1414     arr->size = 0;
1515 
1616     return arr;
1717 }

插入操作

　　对于顺序表的插入操作，需要在pos位置处开始的元素统一往后移动一个位置，处理方式为：从后往前挨个移动，从前往后会覆盖。

　　注意：（1）考虑顺序表的顺序插入和乱序插入，12行的代码；（2）若顺序表被填满，则需要对现有数组进行扩大空间，这里涉及到四步操作：开辟内存、拷贝数据（尽量使用memcpy）、释放原内存、修改指针指向。（3）对输入参数做边界处理。

1 1 //插入值,从后往前挨个移动一位,如果插入的值过大，则扩大数组
2 2 void Insert(void *arr_, int pos, void *data){
3 3 
4 4     struct DynamicArray *arr = (struct DynamicArray *)arr_;
5 5 
6 6     if (NULL == arr || NULL == data){
7 7         return;
8 8     }
9 9 
1010     //对于无效的pos，默认插入到现有元素的后面一个
1111     //if (pos < 0 || pos > arr->capacity)
1212     if (pos < 0 || pos > arr->size)
1313     {
1414         pos = arr->size;
1515     }
1616 
1717     //每次调用插入函数都会插入值，因此arr->size++，size一直增长，且没有限制
1818     if (arr->size >= arr->capacity)
1919     //if (arr->size > arr->capacity)
2020     {
2121 
2222         //开辟新内存
2323         int newcapacity = arr->capacity * 2;
2424         void **newaddr = malloc(sizeof(void *)*newcapacity);
2525 
2626         //拷贝数据,尽量使用内存拷贝函数
2727         memcpy(newaddr, arr->addr, sizeof(void *) * arr->capacity);
2828 
2929         //释放原空间
3030         if (arr->addr != NULL){
3131             free(arr->addr);
3232             arr->addr = NULL;
3333         }
3434 
3535         //修改指针指向
3636         arr->addr = newaddr;
3737         arr->capacity = newcapacity;
3838     }
3939 
4040     for (int i = arr->size - 1; i >= pos; --i){
4141         arr->addr[i + 1] = arr->addr[i];
4242     }
4343     arr->addr[pos] = data; //添加过后，size变化
4444     arr->size++;
4545 }

遍历操作

　　遍历一般的作用为打印数据，但这里并不知道用户的是什么数据，这里由回调函数进行打印（C语言函数指针和回调函数）。

1 1 //遍历
2 2 void Foreach(void *arr_, void(*_callback)(void *)){
3 3     struct DynamicArray * arr = (struct DynamicArray *)arr_;
4 4     if (NULL == arr || NULL == _callback){
5 5         return;
6 6     }
7 7     for (int i = 0; i < arr->size; ++i){
8 8         _callback(arr->addr[i]);
9 9     }
1010 }

删除操作

　　这里分为按值删除和按位置删除，其中按值操作调用了按位置操作的代码，因此需要注意size--的问题。另外，按值操作也使用了回调函数。

1 1 //删除（按值删除，按位置删除）
2 2 void DeletePos(void *arr_, int pos){
3 3     struct DynamicArray *arr = arr_;
4 4     if (NULL == arr){
5 5         return;
6 6     }
7 7 
8 8     for (int i = pos; i < arr->size - 1; ++i){
9 9         arr->addr[i] = arr->addr[i + 1];
1010     }
1111 
1212     arr->size--;//size会减小
1313 }
1414 void DeleteValue(void *arr_, void * data, int(*_compare)(void *, void*)){
1515     struct DynamicArray *arr = arr_;
1616     if (NULL == arr || NULL == data || NULL == _compare){
1717         return;
1818     }
1919     for (int i = 0; i < arr->size; i++){
2020         if (_compare(arr->addr[i], data)){
2121             DeletePos(arr, i);
2222             break; 
2323         }
2424     }
2525     //arr->size--; DeletePos里面已经有size--了
2626 }

销毁操作

　　注意事项：需要先释放成员函数，再释放结构体。

1 1 //销毁
2 2 void Destory(void * arr_){
3 3     struct DynamicArray *arr = arr_;
4 4     if (NULL == arr){
5 5         return;
6 6     }
7 7     if (arr->addr != NULL){
8 8         free(arr->addr);
9 9         arr->addr = NULL;
1010     }
1111     if (arr != NULL){
1212         free(arr);
1313         arr = NULL;
1414     }
1515 }

元素个数和数组大小函数

　　之所以提供这两个函数，是因为不希望用户能直接看到我们定义的结构体内部，也不希望用户可以随便更改，因此我们各个函数的返回值都是void类型，这里提供两个函数，以便用户可以查看元素的个数和数组的大小。

11 int capaArray(void *arr_){
22     struct DynamicArray *arr = (struct DynamicArray *)arr_;
33     return arr->capacity;
44 }
55 
66 int sizeArray(void *arr_){
77     struct DynamicArray *arr = (struct DynamicArray *)arr_;
88     return arr->size;
99 }

测试

　　进行测试时，需要自定义打印和比较回调函数，不需要关心void*data是什么，仅仅实现自定义数据的比较和打印即可。另外回调函数使用时不需要任何参数，只需要函数名；另外，测试了结构体和整型顺序表，可以对顺序表结构体中的void **addr为二级指针有更好的理解。

1 1 struct Person{
2 2     char name[100];
3 3     int age;
4 4 };
5 5 
6 6 // 自定义输出函数
7 7 void print(void *data_){
8 8     if (NULL == data_){
9 9         return;
1010     }
1111     struct Person *data = (struct Person *)data_;
1212     printf("name:%s, age:%d\n", data->name, data->age);
1313 }
1414  //整型自定义输出函数，访问时需要解引用
1515 void printInt(void *data_){
1616     if (NULL == data_){
1717         return;
1818     }
1919     int *data = (int *)data_;
2020     printf("age:%d\n", *data);
2121 }
2222 
2323 //自定义比较函数
2424 int compare(void *d1, void *d2){
2525     if (NULL == d1|| NULL == d2){
2626         return 0;
2727     }
2828     struct Person *p1 = d1;
2929     struct Person *p2 = d2;
3030 
3131     return (strcmp(p1->name, p2->name) == 0 && (p1->age == p2->age));
3232 }
3333 
3434 void test(){
3535     struct Person p1 = {"aaa", 10};
3636     struct Person p2 = { "bbb", 20 };
3737     struct Person p3 = { "ccc", 30 };
3838     struct Person p4 = { "ddd", 40 };
3939     struct Person p5 = { "eee", 50 };
4040     struct Person p6 = { "fff", 60 };
4141     //int p1 = 1;
4242     //int p2 = 2;
4343     //int p3 = 3;
4444     //int p4 = 4;
4545     //int p5 = 5;
4646 
4747 
4848     void * arr = Init(4);
4949     Insert(arr, 1, &p1);
5050     Insert(arr, 2, &p2);
5151     Insert(arr, 3, &p3);
5252     Insert(arr, 4, &p4);
5353     printf("%d\n", capaArray(arr));
5454     Insert(arr, 100, &p5);
5555     printf("%d\n", capaArray(arr));
5656     Insert(arr, 1, &p6);
5757     Foreach(arr, print);
5858     printf("-----------------\n");
5959     DeleteValue(arr, &p2, compare);
6060     Foreach(arr, print);
6161     Destory(arr);
6262 
6363 }
6464 
6565 
6666 int main(){
6767 
6868     test();
6969     system("pause");
7070     return 0;
7171 }