Использование динамического массива мало чем отличается от использования связного списка.Основным отличием является то, что вы несете ответственность за отслеживание size и realloc вашего data массива, когда size == capacity (или когда capacity == 0 для нового элемента).
Кроме того, что вылибо выделение для каждого узла со связанным списком, тогда как с динамическим массивом вы можете распределить более эффективным способом, выделяя несколько крат текущего capacity при size == capacity.Для массивов совершенно неизвестного размера вы можете начать с capacity = 2 или 8, а затем либо увеличивать на несколько кратных (например, 3/2 или 2 и т. Д.), Либо на некоторое фиксированное количество (8, 16, etc..) каждый разперераспределение необходимо.Обычно я просто удваиваю текущую емкость, например, начиная 2, перераспределяя хранилище в data для 4, 8, 16, 32, ... целых чисел, когда к data добавляется больше чисел.Вы можете делать это так, как вам нравится - , пока вы отслеживаете свои size и capacity.
Может помочь небольшой пример.Давайте начнем с простой структуры, где data - единственный динамический член, который нас интересует.Например:
#define CAP 2 /* initial capacity for new struct */
typedef struct {
size_t size,
capacity;
int *data;
} blkhd_node;
Где size - ваш "slots used so far", а capacity - ваш "total available slots" и data ваш "array of integers we're storing".
Функция addдовольно тривиально.Все, что вам нужно сделать, это проверить, нужно ли вам realloc (например, эта структура еще не используется, где используются capacity == 0 или все слоты и size == capacity).Поскольку realloc можно использовать как для нового, так и для изменения размера размещения, это все, что вам нужно.Схема проста: если это новая структура, мы выделим CAP число int, в противном случае size == capacity будет выделено 2 * capacity число int.
Всякий раз, когда мы realloc, мы делаем это с временным указателем! Почему?При сбое realloc возвращается NULL.Если вы вернули realloc с исходным указателем (например, data = realloc (data, newsize); и NULL), вы перезапишете свой исходный адрес указателя на data с помощью NULL и свою способность достичь (или free) исходного блокапотеря памяти - создание утечки памяти. Используя временный указатель, мы можем проверить, будет ли realloc успешнее до , мы присвоим новый адрес data. Важно, что если realloc не удастся -- тогда наши существующие целые числа, на которые указывает data, все еще в порядке, поэтому мы можем свободно использовать наше первоначальное распределение в случае сбоя realloc. Важно помнить.
Нам также нужен способ указатьуспех / сбой или функция add. Здесь вы не добавляете новый узел, поэтому возвращение указателя на новый узел не вариант. В этом случае простой int возврат 0 для сбоя1 для успеха так же хорош, как и все остальное.
При этом функция add может быть такой простой:
int add (blkhd_node *b, int v)
{
/* realloc if (1) new struct or (2) size == capacity */
if (!b->capacity || b->size == b->capacity) {
size_t newsize;
if (!b->capacity) /* new stuct, set size = CAP */
newsize = CAP;
else if (b->size == b->capacity) /* otherwise double size */
newsize = b->capacity * 2;
/* alway realloc with a temporary pointer */
void *tmp = realloc (b->data, newsize * sizeof *b->data);
if (!tmp) { /* validate reallocation */
perror ("realloc_b->data");
return 0; /* return failure */
}
b->data = tmp; /* assign new block of mem to data */
b->capacity = newsize; /* set capacity to newsize */
}
b->data[b->size++] = v; /* set data value to v */
return 1; /* return success */
}
Примечание: так как вы инициализируете свою структуруи size и capacity будут 0, вы можете обойтись без отдельных проверок для capacity == 0 и size == capacity и использовать троичный для установки newsize.Возможно, это менее читаемый способ, и хороший компилятор будет оптимизировать оба идентичных кода, но для полноты вы можете заменить настройку кода newsize на:
/* realloc if (1) new struct or (2) size == capacity */
if (b->size == b->capacity) {
/* set newsize */
size_t newsize = b->capacity ? b->capacity * 2 : CAP;
Учитывая эту опцию, вашВыбор всегда должен быть за более читаемый и поддерживаемый код.Вы выполняете свою работу и позволяете компилятору беспокоиться об остальном.
(вы можете сделать динамический массив struct blockhead_node в точно таким же образом - просто учтите количествоструктуры, которые у вас есть в массиве в дополнение к size, capacity для data в каждом - что вам остается)
Итак, давайте посмотрим, позволит ли наша схема первоначального выделения для 2-intв add 100-int в наш массив data с кратким примером, в котором он приведен в целом:
#include <stdio.h>
#include <stdlib.h>
#define CAP 2 /* initial capacity for new struct */
typedef struct {
size_t size,
capacity;
int *data;
} blkhd_node;
int add (blkhd_node *b, int v)
{
/* realloc if (1) new struct or (2) size == capacity */
if (!b->capacity || b->size == b->capacity) {
size_t newsize;
if (!b->capacity) /* new stuct, set size = CAP */
newsize = CAP;
else if (b->size == b->capacity) /* otherwise double size */
newsize = b->capacity * 2;
/* alway realloc with a temporary pointer */
void *tmp = realloc (b->data, newsize * sizeof *b->data);
if (!tmp) { /* validate reallocation */
perror ("realloc_b->data");
return 0; /* return failure */
}
b->data = tmp; /* assign new block of mem to data */
b->capacity = newsize; /* set capacity to newsize */
}
b->data[b->size++] = v; /* set data value to v */
return 1; /* return success */
}
void prndata (blkhd_node *b)
{
for (size_t i = 0; i < b->size; i++) {
if (i && i % 10 == 0)
putchar ('\n');
printf (" %3d", b->data[i]);
}
putchar ('\n');
}
int main (void) {
blkhd_node b = { .size = 0 }; /* declare/initialize struct */
for (int i = 0; i < 100; i++) /* add 100 data values */
if (!add (&b, i + 1))
break; /* don't exit, all prior data still good */
/* output results */
printf ("\nsize : %zu\ncapacity : %zu\n\n", b.size, b.capacity);
prndata (&b);
free (b.data); /* don't forget to free what you allocate */
return 0;
}
Пример использования / Вывод
$ ./bin/dynarrayint
size : 100
capacity : 128
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Использование памяти / проверка ошибок
В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей в отношении любого выделенного блока памяти: (1) всегда сохраняет указатель на начальный адрес для блокапамяти, таким образом, (2) он может быть освобожден , когда он больше не нужен.
Обязательно, чтобы вы использовали программу проверки ошибок памяти, чтобы гарантировать, что вы не пытаетесь получить доступ к памятиили написать за пределами / за пределами выделенного блока, попытаться прочитать или основать условный переход на неинициализированном значении и, наконец, подтвердить, что вы освобождаете всю выделенную память.
Для Linux valgrind - нормальный выбор.Для каждой платформы есть похожие проверки памяти.Все они просты в использовании, просто запустите вашу программу через нее.
$ valgrind ./bin/dynarrayint
==12589== Memcheck, a memory error detector
==12589== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==12589== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==12589== Command: ./bin/dynarrayint
==12589==
size : 100
capacity : 128
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
==12589==
==12589== HEAP SUMMARY:
==12589== in use at exit: 0 bytes in 0 blocks
==12589== total heap usage: 7 allocs, 7 frees, 1,016 bytes allocated
==12589==
==12589== All heap blocks were freed -- no leaks are possible
==12589==
==12589== For counts of detected and suppressed errors, rerun with: -v
==12589== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.
Посмотрите вещии дайте мне знать, если у вас есть дополнительные вопросы.