Динамические массивы

Массив это упорядоченная последовательность однотипных элементов. Динамический массив это массив переменной длины, то есть массив, который может изменять свой размер в зависимости от количества элементов в нем.

Динамические массивы обладают рядом преимуществ по сравнению со статическими массивами:

• время жизни массива не ограничено той областью видимости, в которой он был создан (только, если мы не потеряем указатель на него);
• при необходимости мы можем увеличить или уменьшить размер динамического массива.

Представим динамический массив следующей структурой:

typedef int EType;

typedef struct 
{
    EType *elements;
    size_t bufferSize;
    size_t currentSize;
} ArrayType;

typedef ArrayType* Array;

Где bufferSize это текущий размер буффера elements, то есть сколько элементов можно поместить в массив elements до его увеличения, а currentSize - текущее количество элементов в массиве. При заполнении массива, то есть, когда bufferSize == currentSize, его размер будем увеличивать вдвое.

Операции над динамическими массивами

Вот список некоторых операций, которые можно выполнять над динамическими массивами:

• get(A, index) - получить значение элемента из массива A по индексу index;
• set(A, index, e) - в ячейку массива A с индексом index записать значение e;
• add(A, e) - добавить элемент e в массив A;
• remove(A) - удалить последний добавленный элемент из массива A;
• size(A) - получить размер массива A.

Реализация

Создание динамического массива A с начальным размером size:

#define INITIAL_SIZE 10
#define init_array(A) __init_array(&A, INITIAL_SIZE)

void __init_array(Array *A, size_t size)
{
    *A = malloc(sizeof(ArrayType));
    if (*A == NULL)
    {
        fprintf(stderr, "Can't allocate memory\n");
        exit(1);
    }

    EType *elements = calloc(size, sizeof(EType));
    if (elements == NULL)
    {
        fprintf(stderr, "Can't allocate memory\n");
        exit(1);
    }

    (*A)->elements = elements;
    (*A)->bufferSize = size;
    (*A)->currentSize = 0;
}

При добавлении нового элемента в массив нам необходимо проверить есть ли в нем свободное место, если есть, то добавляем элемент в массив, если нет, то увеличиваем размер массива вдвое и лишь затем добавляем новый элемент:

void add(Array A, EType e)
{
    if (A->currentSize >= A->bufferSize)
        resize(A);
    A->elements[A->currentSize++] = e;
}

void resize(Array A)
{
    size_t newSize = A->bufferSize * 2;
    EType *newElements = (EType *)realloc(A->elements, newSize * sizeof(EType));

    if (newElements == NULL)
    {
        fprintf(stderr, "Can't reallocate memory\n");
        exit(1);
    }

    A->elements = newElements;
    A->bufferSize = newSize;
}

Получить элемент массива A по индексу index (если проводить аналогию с обычными массивами, то запись вида get(A, 1) эквивалента записи A[1]):

EType get(Array A, int index)
{
    if (index >= A->currentSize || index < 0)
    {
        fprintf(stderr, "Index out of bounds\n");
        exit(1);
    }
    return A->elements[index];
}

Присвоить элементу массива A по индексу index значение e (и снова, если проводить аналогию с обычными массивами, то запись вида set(A, 1, 5) эквивалента записи A[1] = 5):

void set(Array A, int index, EType e)
{
    if (index >= A->currentSize || index < 0)
    {
        fprintf(stderr, "Index out of bounds\n");
        exit(1);
    }
    A->elements[index] = e;
}

Получить размер динамического массива A:

size_t size(Array A)
{
    return A->currentSize;
}

Для простоты работы с массивом напишем функцию multiset(A, num, ...), которая позволит заполнить массив несколькими значениями одновременно. Параметры A и num - заполняемый массив и количество элементов, которыми он будет заполнен, соответственно:

#define multiset(A, num, ...) __multiset(A, num, __VA_ARGS__)

void __multiset(Array A, size_t num, ...)
{
    va_list valist;
    va_start(valist, num);

    for (int i = 0; i < num; i++) {
        add(A, va_arg(valist, EType));
    }

    va_end(valist);
}

Пример работы с динамическим массивом:

void print_array(Array A)
{
    for (int i = 0; i < size(A); i++)
        printf("%d ", get(A, i));
    printf("\n");
}

int main(int argc, char **argv)
{
    Array A;
    init_array(A);
    multiset(A,5, 1,2,3,4,5);

    print_array(A); // 1 2 3 4 5

    add(A, 5, 7);
    print_array(A); // 1 2 3 4 5 5 7

    set(A, 5, 6);
    print_array(A); // 1 2 3 4 5 6 7

    return 0;
}

В качестве еще одного примера использования нашей структуры напишем функцию readInts, которая считывает массив целых чисел из указанного файла:

void readInts(Array A, const char *filename)
{
    FILE *fp;

    if (filename == NULL || (fp = fopen(filename, "r")) == NULL)
    {
        fprintf(stderr, "readInts: Error: Can't open file %s\n", filename);
        exit(1);
    }

    int value;
    while (fscanf(fp, "%d", &value) == 1)
        add(A, value);

    fclose(fp);
}

Задания

Задание 1: Напишите функцию remove для удаления элементов массива. Если количество элементов в массиве в C раз меньше его длины, то происходит сжатие в B раз (C,B — константы).

Задание 2: У функции readInts есть одна неприятная особенность: по окончанию ее работы буфер будет содержать больше памяти, чем это требуется. Исправьте это.

Задание 3: Напишите функцию dyn2arr(A, B), которая преобразует динамический массив A в массив фиксированного размера B.

Задание 4: Напишите функцию arr2dyn(B, A, N), которая преобразует массив B фиксированного размера N в динамический массив A.

Задание 5: Напишите функцию swap(A, i, j), которая переставляет i и j элементы динамического массива местами.

Задание 6: Напишите функцию destroy_array(A), которая освобождает память из под массива A.