算法：C语言实现一个动态数组

ゝ一纸荒年。 2022-12-27 11:16 155阅读 0赞

# 实现 #

## 空间自增长 ##

前提： 确保array已经初始化了

1、调用时机：

*  当array要容纳的元素个数超过了数组的容量

2、需要什么条件：

*  array的首地址
 *  array要存放的元素个数（原来的个数+期望的个数）

3、怎么做

(1)、判断array的容量是否超过了要存放的元素个数

*  是：返回
 *  不是：到(3)

(2)、计算新要申请的容量（规定为16的倍数）

*  初始化为要存放的元素个数
 *  要之变成16的倍数
 *  如果计算出的容量为0，直接返回

(3)、更新本次增长之后数组要达到的容量 = 原来的容量 + 本次要申请的容量

(4)、开始向内核申请空间，空间大小为`array.capacity*sizeof(void *)`。 因为item为二级指针，指向一个指向void连续的空间的指针

*  如果原来array中没有存放元素，使用malloc申请
 *  如果原来array中存放了元素，使用realloc申请
    
     *  如果array之后的堆空间组以增长到需要的空间，申请这段空间，然后将原来的地址返回
     *  否则内核从内存空间中找一块足够大的空间，将原来的内容复制过去，然后将新内存首地址返回，最后释放老的空间

(5)、使用memset初始化刚刚申请的空间为NULL

// 功能： 令array的空间足以容纳min_capacity个元素
    void private_array_grow(ACL_ARRAY *a, int min_capacity){
        
        int min_delta = 16;
        int delta;
        // 如果数组本身的容量就足够了，就直接返回
        if(a->capacity > min_capacity){
        
            return;
        }
    
        // 计算出需要新申请多少空间（强制为16的倍数）
        /*        0       0
         *        1-16    16
         *        17-32   32
         * */
        delta = min_capacity;
        delta += min_delta-1;
        delta /= min_delta;
        delta *= min_delta;
        if(delta < 0){
        
            return;
        }
        a->capacity += delta;
        if (a->items) {
        
            a->items = (void **) realloc(a->items, a->capacity * sizeof(void *));
        } else {
        
            a->items = (void **) malloc(a->capacity * sizeof(void *));
        }
    
        /*
         * 使用0初始化刚刚申请到的内存:
         * [从items起，后移动count个元素]作为起始位置，使用0初始化'没有存放元素[数组总容量-已经存放了元素的内存]'的内存
         * */
        memset(a->items + a->count, 0, (a->capacity - a->count) * sizeof(void *));
    }

## 向动态数组尾部添加动态成员变量 ##

前提： 确保array已经初始化了

1、功能：向动态数组尾部添加动态成员变量

2、参数：

*  array的首地址
 *  要存放的元素obj： 这个元素是一个指针，指向任意类型的空间

3、返回值：返回当前存放位置的索引

4、怎么做

(1)、 确认是不是有足够的空间来存放这个元素

*  判断条件：如果数组当前索引count等于数组的容量，向内核申请新的空间，新空间大小是count + 1

(2)、放置元素

*  array\[count++\] = obj

(3)、返回当前存放元素的索引 count - 1

//  令array当前元素索引指向一个任意类型的指针
    int private_array_push(ACL_ARRAY *a, void *obj)
    {
        
        if (a->count >= a->capacity)
            private_array_grow(a, a->count + 16);
        a->items[a->count++] = obj;
        return(a->count - 1);
    }

## 从动态数组弹出最后一个元素 ##

前提： 确保array已经初始化了

1、功能：从动态数组弹出最后一个元素

ps：count为下一个元素要存放的索引，也是整个数组存放的元素个数

2、需要些什么

*  array元素的首地址
 *  需要返回最后存放的元素

3、返回值：

*  返回弹出的元素

4、怎么做：  
(1)、判断当前数组是否存放了元素， 判断条件：`count == 0`

*  如果没有，返回NULL
 *  存放了，跳到（2）

(2)、找到要弹出的索引：count不仅是元素个数，还是元素下一个要存放的索引，所以想要找到上次的索引，直接减少1就好，count–不仅找到了上次存放位置的索引，也让元素个数减少了1

(3)、用一个临时值将这个索引指向的空间存储起来，以便最终返回

(4)、 令`array[count] = NULL`

void * private_array_pop(ACL_ARRAY *a){
        
        void *ptr;
    
        if(a->count == 0){
        
            return (NULL);
        }
    
        a->count--;
        ptr = a->items[a->count];
        a->items[a->count] = NULL;
        return ptr;
    }

## 返回array元素的个数 ##

1.  需要什么：

*  array的首地址

2、返回什么？

*  元素个数

3、怎么做？

*  如果array==`NULL`，返回-1
 *  否则，返回`a.count`

int private_array_size(const ACL_ARRAY *a)
    {
        
    	if(a == NULL)
    		return(-1);
    	return(a->count);
    }

## 返回索引idx的值 ##

前提： 确保array已经初始化了

1、功能： 如果我们想要取出索引idx处的元素怎么做？

2、需要什么？

*  array的首地址
 *  要寻值的索引

3、返回值：

*  返回找到的值

4、怎么做：

(1)、确保索引有效： 如果索引无效返回NULL

*  idx必须大于-1 & index 小于count\[下一个元素的索引\]

(2)、从items中找到存储的值

void *private_array_index(const ACL_ARRAY *a, int idx)
    {
        
        if(idx < 0 || idx > a->count - 1)
            return(NULL);
    
        return(a->items[idx]);
    }

## 删除索引idx处的元素 ##

1、需要什么？

*  array首地址
 *  待删除元素的索引
 *  是否需要释放索引指向的空间，如果需要，那么如何释放索引指向的那个元素

2、返回值

*  \-1表示删除失败
 *  0表示删除成功

3、怎么做？

(1)、判断array是否初始化

*  没有初始化，返回-1
 *  初始化了，跳到(2)  
    (2)、判断索引是否越界
 *  越界，返回-1
 *  没有越界，跳到(3)

(3)、判断索引指向的空间是否需要释放

*  如果需要，而且索引指向的空间不为NULL，那么释放，释放之后跳到(4)
 *  如果不需要，跳到(4)

(4)、元素个数减少1

(5)、判断释放元素之后，array是否还存在元素

*  存放，将最末尾的那个元素移动到刚刚释放的空间的位置，然后跳到(6)
 *  不存放，跳到(6)

(6) 到了这一步，该干的事情已经干完了，返回0

int private_array_delete(ACL_ARRAY *a, int idx, void (*free_fn)(void*))
    {
        
        if (a == NULL)
            return (-1);
        if (idx < 0 || idx >= a->count)
            return (-1);
        if (free_fn != NULL && a->items[idx] != NULL)
            free_fn(a->items[idx]);
        a->count--;
        if (a->count > 0)
            a->items[idx] = a->items[a->count];
        return (0);
    }

## 删除array中的内存obj ##

1、参数：

*  array的首地址
 *  要删除的内存obj的地址

2、返回值：需要知道是否返回成功

*  \-1表示不成功
 *  0表示成功

3、怎么做：  
（1）如果数组没有初始化(`array == NULL`)或者`obj==NULL`，直接返回0，否则跳到（2）  
（2）循环array，如果发现item与obj相等，调用`private_array_delete`，否则跳到（3）  
（3） 直接返回-1

int private_array_delete_obj(ACL_ARRAY *a, void *obj, void (*free_fn)(void*))
    {
        
        int   i;
    
        if (a == NULL || obj == NULL)
            return (-1);
        for (i = 0; i < a->count; i++) {
        
            if (a->items[i] == obj) {
        
                return (private_array_delete(a, i, free_fn));
            }
        }
        return (-1);
    }

## 释放掉动态数组内的成员变量但并不释放动态数组对象 ##

1、需要什么

*  array的首地址
 *  释放数组项的的函数指针free\_fn

2、无需返回值

3、怎么做  
(1) 如果array 为NULL，直接返回；否则跳到(2)  
(2) 循环array，如果free\_fn不为NULL & 数组项不为NULL，调用free\_fn(数组项)，然后将a->items\[idx\] = NULL  
(3) 最后令`a.count = 0`

void private_array_clean(ACL_ARRAY *a, void (*free_fn)(void *)){
        
        for(int i = 0; i < a->count; i++){
        
            if(free_fn != NULL && a->items[i] != NULL){
        
                free_fn(a->items);
            }
            a->items[idx] = NULL;	/* sanity set to be null */
        }
        a->count = 0;
    }

## 释放整个数组 ##

1、需要什么

*  array的首地址
 *  释放数组项的的函数指针free\_fn

2、无需返回值

void private_array_destroy(ACL_ARRAY *a, void (*free_fn)(void *)){
        
        private_array_clean(a, free_fn);
        if(a->items){
        
            free(a->items);
        }
        free(a->items);
    }

# 总结 #

1、private\_array.c

#include "private_array.h"
    #include <stdlib.h>
    #include <memory.h>
    #include <assert.h>
    
    
    //指向数组的首元素
    static void *array_iter_head(ACL_ITER *iter, struct ACL_ARRAY *a){
        
        assert(a != NULL);
        iter->size = a->count;  // 当前容器中元素总个数
        iter->i = 0;   // 当前迭代器在容器中的位置索引
        if(a->items == NULL){
        
            iter->ptr = iter->data = NULL;
        }else{
        
            iter->ptr = iter->data = a->items[0];
        }
        return (iter->ptr);
    }
    
    // 指向迭代器指针的下一个元素
    static void *array_iter_next(ACL_ITER *iter, struct ACL_ARRAY *a){
        
        assert(a != NULL);
        // 索引自增1
        iter->i++;
        if (iter->i >= a->count)
            iter->data = iter->ptr = 0;
        else
            iter->data = iter->ptr = a->items[iter->i];
        return (iter->ptr);
    }
    static void *array_iter_tail(ACL_ITER *iter, struct ACL_ARRAY *a){
        
        iter->i = a->count - 1;
        iter->size = a->count;
        if (a->items == NULL || iter->i < 0)
            iter->ptr = iter->data = 0;
        else
            iter->ptr = iter->data = a->items[iter->i];
        return (iter->ptr);
    }
    static void *array_iter_prev(ACL_ITER *iter, struct ACL_ARRAY *a){
        
        iter->i--;
        if (iter->i < 0)
            iter->data = iter->ptr = 0;
        else
            iter->data = iter->ptr = a->items[iter->i];
        return (iter->ptr);
    }
    
    
    
    // min_capacity    至少需要容纳min_capacity个元素
    void private_array_grow(ACL_ARRAY *a, int min_capacity){
        
        int min_delta = 16;
        int delta;
        // 如果数组本身的容量就足够了，就直接返回
        if(a->capacity > min_capacity){
        
            return;
        }
    
        // 计算出需要新申请多少空间（强制为16的倍数）
        /*        0       0
         *        1-16    16
         *        17-32   32
         * */
        delta = min_capacity;
        delta += min_delta-1;
        delta /= min_delta;
        delta *= min_delta;
        if(delta < 0){
        
            return;
        }
        a->capacity += delta;
        if (a->items) {
        
            a->items = (void **) realloc(a->items, a->capacity * sizeof(void *));
        } else {
        
            a->items = (void **) malloc(a->capacity * sizeof(void *));
        }
    
        /*
         * 使用0初始化刚刚申请到的内存:
         * [从items起，后移动count个元素]作为起始位置，使用0初始化'没有存放元素[数组总容量-已经存放了元素的内存]'的内存
         * */
        memset(a->items + a->count, 0, (a->capacity - a->count) * sizeof(void *));
    }
    
    int private_array_push(ACL_ARRAY *a, void *obj)
    {
        
        if (a->count >= a->capacity)
            private_array_grow(a, a->count + 16);
        a->items[a->count++] = obj;
        return(a->count - 1);
    }
    
    
    static void array_prepare_append(ACL_ARRAY *a, int app_count){
        
        assert(app_count > 0);
    
        //（ 数组元素个数 + 待存储的元素个数 ）  > 数组容量
        if (a->count + app_count > a->capacity){
        
            private_array_grow(a, a->count + app_count);
        }
    }
    
    ACL_ARRAY *private_array_create(int init_size){
        
        ACL_ARRAY  *a;
    
        a = (ACL_ARRAY *) calloc(1, sizeof(ACL_ARRAY));
        assert(a);
    
        a->iter_head = array_iter_head;
        a->iter_next = array_iter_next;
        a->iter_tail = array_iter_tail;
        a->iter_prev = array_iter_prev;
    
        if(init_size > 0)
            array_prepare_append(a, init_size);
    
        return (a);
    }
    
    void * private_array_pop(ACL_ARRAY *a){
        
        void *ptr;
    
        if(a->count == 0){
        
            return (NULL);
        }
    
        a->count--;
        ptr = a->items[a->count];
        a->items[a->count] = NULL;
        return ptr;
    }
    
    void *private_array_index(const ACL_ARRAY *a, int idx)
    {
        
        if(idx < 0 || idx > a->count - 1)
            return(NULL);
    
        return(a->items[idx]);
    }
    int private_array_size(const ACL_ARRAY *a)
    {
        
        if(a == NULL)
            return(-1);
        return(a->count);
    }
    
    int private_array_delete(ACL_ARRAY *a, int idx, void (*free_fn)(void*))
    {
        
        if (a == NULL)
            return (-1);
        if (idx < 0 || idx >= a->count)
            return (-1);
        if (free_fn != NULL && a->items[idx] != NULL)
            free_fn(a->items[idx]);
        a->count--;
        if (a->count > 0)
            a->items[idx] = a->items[a->count];
        return (0);
    }
    
    
    int private_array_delete_obj(ACL_ARRAY *a, void *obj, void (*free_fn)(void*))
    {
        
        int   i;
    
        if (a == NULL || obj == NULL)
            return (-1);
        for (i = 0; i < a->count; i++) {
        
            if (a->items[i] == obj) {
        
                return (private_array_delete(a, i, free_fn));
            }
        }
        return (-1);
    }
    
    void private_array_clean(ACL_ARRAY *a, void (*free_fn)(void *)){
        
        for(int i = 0; i < a->count; i++){
        
            if(free_fn != NULL && a->items[i] != NULL){
        
                free_fn(a->items[i]);
            }
        }
        a->count = 0;
    }
    
    void private_array_destroy(ACL_ARRAY *a, void (*free_fn)(void *)){
        
        private_array_clean(a, free_fn);
        if(a->items){
        
            free(a->items);
        }
        free(a);
    }

2、private\_array.h

#pragma once
    
    
    
    typedef struct ACL_ARRAY ACL_ARRAY;
    struct ACL_ARRAY{
        
        int     capacity;
        int     count;
        void    **items;
    
        void  (*push_back)(struct ACL_ARRAY*, void*);
        void  (*push_front)(struct ACL_ARRAY*, void*);
        void *(*pop_back)(struct ACL_ARRAY*);
        void *(*pop_front)(struct ACL_ARRAY*);
    
        void *(*iter_head)(ACL_ITER*, struct ACL_ARRAY*);
        void *(*iter_next)(ACL_ITER*, struct ACL_ARRAY*);
        void *(*iter_tail)(ACL_ITER*, struct ACL_ARRAY*);
        void *(*iter_prev)(ACL_ITER*, struct ACL_ARRAY*);
    };
    
    /**
     * 创建一个动态数组
     * @param init_size {int} 动态数组的初始大小
     * @return {ACL_ARRAY*} 动态数组指针
     */
    ACL_ARRAY *private_array_create(int init_size);
    
    /**
     * 释放掉动态数组内的成员变量，但并不释放动态数组对象
     * @param a {ACL_ARRAY*} 动态数组指针
     * @param free_fn {void (*)(void*)} 用于释放动态数组内成员变量的释放函数指针
     */
    void private_array_clean(ACL_ARRAY *a, void (*free_fn)(void *));
    
    /**
     * 释放掉动态数组内的成员变量，并释放动态数组对象
     * @param a {ACL_ARRAY*} 动态数组指针
     * @param free_fn {void (*)(void*)} 用于释放动态数组内成员变量的释放函数指针
     */
    void private_array_destroy(ACL_ARRAY *a, void (*free_fn)(void *));
    
    /**
     * 向动态数组尾部添加动态成员变量
     * @param a {ACL_ARRAY*} 动态数组指针
     * @param obj {void*} 动态成员变量
     * @return {int} 0: 成功；-1: 失败
     */
    int private_array_push(ACL_ARRAY *a, void *obj);
    
    /**
     * 从动态数组中弹出最尾一个对象
     * @param a {ACL_ARRAY*} 动态数组指针
     * @return {void*}, NULL 表示数组为空
     */
    void* private_array_pop(ACL_ARRAY *a);
    
    /**
     * 从动态数组中的指定位置删除某个对象，删除后数组内元素的先后顺序有可能发生了改变,
     * 因为删除后会自动将数组中最后的元素移至该位置处
     * @param a {ACL_ARRAY*} 动态数组指针
     * @param position {int} 某个位置，不得越界
     * @param free_fn {void (*)(void*)} 用于释放动态数组内成员变量的释放函数指针，如果该
     *  指针为空，则不释放，否则用此函数进行释放动态对象
     * @return {int} 0: 成功；-1: 失败
     */
    int private_array_delete(ACL_ARRAY *a, int idx, void (*free_fn)(void*));
    
    int private_array_delete_obj(ACL_ARRAY *a, void *obj, void (*free_fn)(void*));
    
    /**
     * 从动态数组中的某个下标位置取出动态对象
     * @param a {ACL_ARRAY*} 动态数组指针
     * @param idx {int} 下标位置，不能越界，否则返回-1
     * @return {void*} != NULL: 成功；== NULL: 不存在或失败
     */
    void *private_array_index(const ACL_ARRAY *a, int idx);
    
    /**
     * 获得当前动态数组中动态对象的个数
     * @param a {ACL_ARRAY*} 动态数组指针
     * @return {int} 动态数组中动态对象的个数
     */
    int private_array_size(const ACL_ARRAY *a);
    
    void private_array_grow(ACL_ARRAY *a, int min_capacity);
    
    #define	PRIVATE_ARRAY_PUSH(a, ptr) do  \
    {
            \
    	if ((a)->count >= (a)->capacity)  \
    		private_array_grow((a), (a)->count + 16);  \
    	(a)->items[(a)->count++] = (ptr);  \
    } while (0)
    
    #define	PRIVATE_ARRAY_POP(a, ptr) do  \
    {
            \
    	if ((a)->count > 0) {
            \
    		(a)->count--;  \
    		(ptr) = (a)->items[(a)->count];  \
    		(a)->items[(a)->count] = NULL;  \
    	} else {
            \
    		(ptr) = NULL;  \
    	}  \
    } while (0)

3、acl\_iterator.h

typedef struct ACL_ITER ACL_ITER;
    struct ACL_ITER {
        
        void *ptr;		/**< 迭代器指针, 与容器相关 */
        void *data;		/**< 用户数据指针 */
        int   i;		/**< 当前迭代器在容器中的位置索引 */
        int   size;		/**< 当前容器中元素总个数 */
    };
    
    /**
     * 正向遍历容器中元素
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     * @examples: samples/iterator/
     */
    #define	ACL_FOREACH(iter, container)  \
            for ((container)->iter_head(&(iter), (container));  \
                 (iter).ptr;  \
                 (container)->iter_next(&(iter), (container)))
    
    /**
     * 反向遍历容器中元素
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     * @examples: samples/iterator/
     */
    #define	ACL_FOREACH_REVERSE(iter, container)  \
            for ((container)->iter_tail(&(iter), (container));  \
                 (iter).ptr;  \
                 (container)->iter_prev(&(iter), (container)))
    
    /**
     * 获得当前迭代指针与某容器关联的成员结构类型对象
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     */
    #define	ACL_ITER_INFO(iter, container)  \
    	(container)->iter_info(&(iter), (container))
    
    #define	acl_foreach_reverse	ACL_FOREACH_REVERSE
    #define	acl_foreach		ACL_FOREACH
    #define	acl_iter_info		ACL_ITER_INFO

4、main

#include <stdio.h>
    #include "private_array.h"
    #include <stdlib.h>
    
    int main(void)
    {
        
        ACL_ARRAY *a = private_array_create(10);
        ACL_ITER iter;
        int   i;
        char *ptr;
    
        for (i = 0; i < 20; i++) {
        
            ptr = (char*) malloc(32);
            snprintf(ptr, 32, "data: %d", i);
            (void) private_array_push(a, ptr);
        }
    
        printf("\nacl_foreach for acl_array:\n");
        acl_foreach(iter, a) {
        
            printf(">> i: %d, value: %s\n", iter.i, (char*) iter.data);
        }
    
        printf("\nacl_foreach_reverse for acl_array:\n");
        acl_foreach_reverse(iter, a) {
        
            printf(">> i: %d, value: %s\n", iter.i, (char*) iter.data);
        }
    
        private_array_destroy(a, free);
    
        return 0;
    }