数据结构与算法7 — 动态数组

本文主要是介绍数据结构与算法7 — 动态数组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

尊重作者劳动成果，转载请注明出处，谢谢！

1. array.h

#ifndef array_H
#define array_H

#include <stddef.h>
#include <sys/types.h>
#include "delegate.h"

//动态数组，能够动态的进行扩容，支持多种数据类型，包括：int、struct等
typedef struct
{
    void *data;      //实际数组
    size_t itemSize; //数组元素大小（字节）
    size_t capacity; //数组容量
    size_t size;     //数组长度
} Array;

//定义该宏可以直观的看出数组元素的数据类型，比如：Array(int)
#define Array(type) Array

#ifdef __cplusplus
extern "C"
{
#endif
    int array_init(Array *array, size_t itemSize, size_t capacity);
    void array_free(Array *array);
    void array_clear(Array *array);
    int array_expand(Array *array, size_t increment);
    int array_shrink(Array *array);
    size_t array_length(const Array *array);
    int array_full(const Array *array);
    void *array_getItem(const Array *array, size_t index);
    void array_setItem(Array *array, size_t index, const void *item);
    void array_add(Array *array, const void *item);
    void array_insert(Array *array, const void *item, size_t index);
    void array_remove(Array *array, const void *item, Comparison comparison);
    void array_removeAll(Array *array, const void *item, Comparison comparison);
    void array_removeAt(Array *array, size_t index);
    void array_removeRange(Array *array, size_t fromIndex, size_t toIndex);
    ssize_t array_firstIndexOf(const Array *array, const void *item, Comparison comparison);
    ssize_t array_lastIndexOf(const Array *array, const void *item, Comparison comparison);
    int array_contains(const Array *array, const void *item, Comparison comparison);
    void array_sort(Array *array, Comparison comparison);
    void array_sortDesc(Array *array, Comparison comparison);
    int array_compare(const Array *arr1, const Array *arr2, Comparison comparison);
    void array_copy(Array *dest, const Array *src);
    void array_merge(Array *dest, const Array *src);
    void array_reverse(Array *array);
#ifdef __cplusplus
}
#endif

#endif

2. array.c

#include "array.h"
#include <string.h>
#include <stdlib.h>

//初始化
int array_init(Array *array, size_t itemSize, size_t capacity)
{
    if (array == NULL || itemSize <= 0)
        return -1;

    array->data = malloc(capacity * itemSize);
    if (array->data == NULL)
        return -1;

    memset(array->data, 0, capacity * itemSize);
    array->capacity = capacity;
    array->size = 0;
    array->itemSize = itemSize;
    return 0;
}

//释放内存
void array_free(Array *array)
{
    if (array == NULL)
        return;

    if (array->data != NULL)
    {
        free(array->data);
        array->data = NULL;
    }

    array->size = 0;
    array->capacity = 0;
    array->itemSize = 0;
}

//清空数组
void array_clear(Array *array)
{
    if (array == NULL)
        return;

    if (array->data != NULL)
        memset(array->data, 0, array->capacity * array->itemSize);

    array->size = 0;
    array_shrink(array); //收缩数组
}

//扩充数组
int array_expand(Array *array, size_t increment)
{
    if (array == NULL || increment <= 0)
        return -1;

    void *data = realloc(array->data, (increment + array->capacity) * array->itemSize);
    if (data == NULL)
        return -1;

    array->data = data;
    array->capacity += increment;
    return 0;
}

//收缩数组
int array_shrink(Array *array)
{
    if (array == NULL)
        return -1;

    if (array_full(array))
        return -1;

    size_t capacity;
    if (array->size == 0)
        capacity = 1;
    else
        capacity = array->size;

    void *data = realloc(array->data, capacity * array->itemSize);
    if (data == NULL)
        return -1;

    array->data = data;
    array->capacity = capacity;
    return 0;
}

//获取数组长度
size_t array_length(const Array *array)
{
    if (array == NULL || array->data == NULL)
        return 0;

    return array->size;
}

//判断数据是否已满
int array_full(const Array *array)
{
    if (array == NULL)
        return -1;

    return array->size == array->capacity;
}

//获取指定索引的元素，类似数组的下标访问
void *array_getItem(const Array *array, size_t index)
{
    if (array == NULL || index >= array->size)
        return NULL;

    return (char *)array->data + index * array->itemSize;
}

//修改指定索引位置的元素
void array_setItem(Array *array, size_t index, const void *item)
{
    if (array == NULL || index >= array->size)
        return;

    memcpy((char *)array->data + index * array->itemSize, item, array->itemSize);
}

//在数组末尾添加元素
void array_add(Array *array, const void *item)
{
    if (array == NULL)
        return;

    if (array_full(array))
        array_expand(array, array->capacity / 2);

    memcpy((char *)array->data + array->size * array->itemSize, item, array->itemSize);
    array->size++;
}

//在指定索引的位置上插入元素
void array_insert(Array *array, const void *item, size_t index)
{
    if (array == NULL || index > array->size)
        return;

    if (array_full(array))
        array_expand(array, array->capacity / 2);

    if (index >= array->size) //add
    {
        memcpy((char *)array->data + array->size * array->itemSize, item, array->itemSize);
    }
    else //insert
    {
        void *src = (char *)array->data + index * array->itemSize;
        void *dest = (char *)src + array->itemSize;
        memmove(dest, src, (array->size - index) * array->itemSize);
        memcpy(src, item, array->itemSize);
    }
    array->size++;
}

//删除满足指定条件的第一个元素
void array_remove(Array *array, const void *item, Comparison comparison)
{
    if (array == NULL)
        return;

    size_t i;
    for (i = 0; i < array->size; i++)
    {
        if (comparison((char *)array->data + i * array->itemSize, item, array->itemSize) == 0)
        {
            if (i != array->size - 1) //不是最后一个元素
            {
                void *src = (char *)array->data + (i + 1) * array->itemSize;
                void *dest = (char *)array->data + i * array->itemSize;
                memmove(dest, src, (array->size - i) * array->itemSize);
            }

            //最后一个元素，赋值为0
            array->size -= 1;
            memset((char *)array->data + array->size * array->itemSize, 0, array->itemSize);
            break;
        }
    }
}

//删除所有满足指定条件的元素
void array_removeAll(Array *array, const void *item, Comparison comparison)
{
    if (array == NULL)
        return;

    size_t i;
    for (i = 0; i < array->size; i++)
    {
        if (comparison((char *)array->data + i * array->itemSize, item, array->itemSize) == 0)
        {
            if (i != array->size - 1) //不是最后一个元素
            {
                void *src = (char *)array->data + (i + 1) * array->itemSize;
                void *dest = (char *)array->data + i * array->itemSize;
                memmove(dest, src, (array->size - i) * array->itemSize);
            }

            //最后一个元素，赋值为0
            array->size -= 1;
            memset((char *)array->data + array->size * array->itemSize, 0, array->itemSize);
            i--; //勿漏
        }
    }
}

//删除指定索引位置的元素
void array_removeAt(Array *array, size_t index)
{
    array_removeRange(array, index, index);
}

//删除指定索引范围的元素
void array_removeRange(Array *array, size_t fromIndex, size_t toIndex)
{
    if (array == NULL)
        return;

    if (fromIndex > toIndex)
        return;

    if (fromIndex >= array->size || toIndex >= array->size)
        return;

    size_t num = toIndex - fromIndex + 1;
    size_t endIndex = array->size - 1;
    if (toIndex != endIndex)
    {
        void *src = (char *)array->data + (toIndex + 1) * array->itemSize;
        void *dest = (char *)array->data + fromIndex * array->itemSize;
        memmove(dest, src, (endIndex - toIndex) * array->itemSize);
    }

    array->size -= num;
    memset((char *)array->data + array->size * array->itemSize, 0, num * array->itemSize);
}

//获取满足指定条件的第一个索引，不存在时返回-1
ssize_t array_firstIndexOf(const Array *array, const void *item, Comparison comparison)
{
    if (array == NULL)
        return -1;

    size_t i;
    for (i = 0; i < array->size; i++)
    {
        if (comparison((char *)array->data + i * array->itemSize, item, array->itemSize) == 0)
            return i;
    }

    return -1;
}

//获取满足指定条件的最后一个索引，不存在时返回-1
ssize_t array_lastIndexOf(const Array *array, const void *item, Comparison comparison)
{
    if (array == NULL)
        return -1;

    ssize_t i;
    for (i = array->size - 1; i >= 0; i--)
    {
        if (comparison((char *)array->data + i * array->itemSize, item, array->itemSize) == 0)
            return i;
    }

    return -1;
}

//判读数组是否包含指定元素，存在返回大于0，不存在返回-1
int array_contains(const Array *array, const void *item, Comparison comparison)
{
    return array_firstIndexOf(array, item, comparison);
}

//数组升序排序（直接插入排序法，使用自定义比较器）
void array_sort(Array *array, Comparison comparison)
{
    if (array == NULL || array->size == 0)
        return;

    void *tmp = malloc(array->itemSize);
    size_t i;
    ssize_t j;

    for (i = 1; i < array->size; i++) //默认第一个元素有序，需n-1次插入
    {
        if (comparison((char *)array->data + i * array->itemSize, (char *)array->data + (i - 1) * array->itemSize, array->itemSize) < 0)
        {
            memcpy(tmp, (char *)array->data + i * array->itemSize, array->itemSize);
            j = i - 1;

            //查找插入位置
            while (j >= 0 && comparison((char *)array->data + j * array->itemSize, tmp, array->itemSize) > 0)
            {
                //元素后移
                //memcpy((char *)array->data + (j + 1) * array->itemSize, (char *)array->data + j * array->itemSize, array->itemSize);
                j--;
            }

            //元素后移
            void *src = (char *)array->data + (j + 1) * array->itemSize;
            void *dest = (char *)src + 1 * array->itemSize;
            memmove(dest, src, array->itemSize * (i - j - 1));

            //插入元素
            memcpy((char *)array->data + (j + 1) * array->itemSize, tmp, array->itemSize);
        }
    }

    free(tmp);
}

//数组降序排序（直接插入排序法，使用自定义比较器）
void array_sortDesc(Array *array, Comparison comparison)
{
    if (array == NULL || array->size == 0)
        return;

    void *tmp = malloc(array->itemSize);
    size_t i;
    ssize_t j;

    for (i = 1; i < array->size; i++) //默认第一个元素有序，需n-1次插入
    {
        if (comparison((char *)array->data + i * array->itemSize, (char *)array->data + (i - 1) * array->itemSize, array->itemSize) > 0)
        {
            memcpy(tmp, (char *)array->data + i * array->itemSize, array->itemSize);
            j = i - 1;

            //查找插入位置
            while (j >= 0 && comparison((char *)array->data + j * array->itemSize, tmp, array->itemSize) < 0)
            {
                //元素后移
                //memcpy((char *)array->data + (j + 1) * array->itemSize, (char *)array->data + j * array->itemSize, array->itemSize);
                j--;
            }

            //元素后移
            void *src = (char *)array->data + (j + 1) * array->itemSize;
            void *dest = (char *)src + 1 * array->itemSize;
            memmove(dest, src, array->itemSize * (i - j - 1));

            //插入元素
            memcpy((char *)array->data + (j + 1) * array->itemSize, tmp, array->itemSize);
        }
    }

    free(tmp);
}

//数组比较（使用自定义比较器），相同返回0，大于返回大于0，小于返回小于0
int array_compare(const Array *arr1, const Array *arr2, Comparison comparison)
{
    if (arr1 == arr2)
        return 0;

    if (arr1 == NULL || arr2 == NULL)
        return -1;

    if (arr1->size != arr2->size)
        return -1;

    int res;
    size_t i;
    for (i = 0; i < arr1->size; i++)
    {
        res = comparison((char *)arr1->data + i * arr1->itemSize, (char *)arr2->data + i * arr2->itemSize, arr1->itemSize);
        if (res != 0)
            break;
    }

    return res;
}

//复制数组
void array_copy(Array *dest, const Array *src)
{
    if (dest == NULL || src == NULL)
        return;

    //src的大小比dest的容量还要大，需要扩容
    if (src->size > dest->capacity)
        array_expand(dest, src->size - dest->capacity);

    memcpy(dest->data, src->data, src->size * src->itemSize);
    dest->size = src->size;
}

//数组合并
void array_merge(Array *dest, const Array *src)
{
    if (dest == NULL || src == NULL)
        return;

    if (dest->size + src->size > dest->capacity)
        array_expand(dest, (dest->size + src->size - dest->capacity) * 2);

    memcpy((char *)dest->data + dest->size * dest->itemSize, src->data, src->size * src->itemSize);
    dest->size += src->size;
}

//数组反转
void array_reverse(Array *array)
{
    if (array == NULL || array->size <= 1)
        return;

    void *tmp = malloc(array->itemSize);
    size_t i;

    for (i = 0; i < array->size / 2; i++)
    {
        memcpy(tmp, (char *)array->data + i * array->itemSize, array->itemSize);
        memcpy((char *)array->data + i * array->itemSize, (char *)array->data + (array->size - i - 1) * array->itemSize, array->itemSize);
        memcpy((char *)array->data + (array->size - i - 1) * array->itemSize, tmp, array->itemSize);
    }

    free(tmp);
}

这篇关于数据结构与算法7 — 动态数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

数据结构与算法7 — 动态数组

1. array.h

2. array.c

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯