Массивы, использованные в нескольких предыдущих разделах, были статическими, их размер и содержимое задавались во время компиляции. Если потребовать, чтобы некоторую таблицу слов или символов HTML можно было изменять во время выполнения, то хэш-таблица была бы для этой цели более подходящей структурой. Вставка в отсортированный массив п элементов по одному занимает О(n2), чего стоит избегать при больших n.
Однако часто нам нужно работать с переменным, но небольшим числом значений, и тогда массивы по-прежнему могут применяться. Для уменьшения потерь при перераспределении памяти изменение размера должно происходить блоками, и для простоты массив должен храниться вместе с информацией, необходимой для управления им^ В C++ и Java это делается с помощью классов из стандартных библиотек, а в С мы можем добиться похожего результата с помощью структур.
Следующий код определяет расширяемый массив с элементами типа Nameval: новые элементы добавляются в хвост массива, который удлиняется при необходимости. Доступ к каждому элементу по его индексу происходит за константное время. Эта конструкция аналогична векторным классам из библиотек C++ и Java.
typedef struct Nameval Nameval;
struct Nameval {
char *name;
int value; };
struct NVtab {
int nval; /* текущее количество
элементов */
int max; /* под сколько элементов
выделена память */
Nameval *nameval; /* массив пар */
} nvtab;
enum { NVINIT = 1, NVGROW = 2 };
/* addname: добавить новое имя
и значение в nvtab */
int addname(Nameval newname)
{
Nameval *nvp;
if (nvtab.nameval == NULL) { /* первый вызов
*/ nvtab.nameval =
(Nameval *) malloc(NVINIT * sizeof(Nameval));
if (nvtab.nameval == NULL)
return -1; nvtab.max = NVINIT; nvtab.nval = 0;
} else if (nvtab.nval >= nvtab.max) { /* расширить
*/ nvp = (Nameval *) realloc(nvtab.nameval,
(NVGROW*nvtab.max) * sizeof(Nameval));
if (nvp == NULL)
return -1;
nvtab.max *= NVGROW;
nvtab.nameval = nvp; }
nvtab.nameval[nvtab.nval]
= newname; return nvtab.
Функция addname возвращает индекс только что добавленного элемента или -1 в случае возникновения ошибки.
Вызов reallос увеличивает массив до новых размеров, сохраняя существующие элементы, и возвращает указатель на него или NULL при недостатке памяти. Удвоение размера массива при каждом вызове realloc сохраняет средние "ожидаемые" затраты на копирование элемента постоянными; если бы массив увеличивался каждый раз только на один элемент, то производительность была бы порядка 0(п2). Поскольку при перераспределении памяти адрес массива может измениться, то программа должна обращаться к элементам массива по индексам, а не через указатели. Заметьте, что код не таков:
потому что при такой форме если вызов realloc не сработает, то исход-ный-массив будет утерян.
Мы задаем очень маленький начальный размер массива (NVINIT = 1). Это заставляет программу увеличивать массив почти сразу, что гарантирует проверку данной части программы. Начальное значение может быть и увеличено, когда программа начнет реально использоваться, однако затраты на стартовое расширение массива ничтожны.
Значение, возвращаемое realloc, не обязательно должно приводиться к его настоящему типу, поскольку в С нетипизированные указатели (void *) приводятся к любому типу указателя автоматически. Однако в C++ это не так; здесь преобразование обязательно. Можно поспорить, что безопаснее: преобразовывать типы (это честнее и понятнее) или не преобразовывать (поскольку в преобразовании легко может закрасться ошибка). Мы выбрали преобразование, потому что тогда программа корректна как в С, так и в C++. Цена такого решения — уменьшение количества проверок на ошибки компилятором С, но это неважно, когда мы производим дополнительные проверки с помощью двух компиляторов.
Удаление элемента может быть более сложной операцией, поскольку нам нужно решить, что же делать с образовавшейся "дыркой" в массиве. Если порядок элементов не имеет значения, то проще всего переставить последний элемент на место удаленного. Однако, если порядок должен быть сохранен, нам нужно сдвинуть элементы после "дырки" на одну позицию:
/* delname: удалить первое
совпавшее имя в массиве nvtab */
int delname(char *name)
{
int i;
for (i = 0; i < nvtab.nval; i++)
if (strcmp(nvtab.nameval[i].name,
name)
== 0) { meminove(nvtab. nameval+i, nvtab.
nameval'+i+1, (nvtab.nval-(i+1)
) * sizeof(Nameval));
nvtab.nval--; return 1;
}
return 0:
}
Вызов memmove сдвигает массив, перемещая элементы вниз на одну позицию; memmove — стандартная библиотечная функция для копирования блоков памяти любого размера.
В стандарте ANSI определены две функции: memcpy, которая работает быстрее, но может затереть память, если источник и приемник данных пересекаются, и memmove, которая может работать медленнее, но зато всегда корректна. Бремя выбора между скоростью и корректностью не должно взваливаться на программиста; должна была бы быть только одна функция. Считайте, что это так и есть, и всегда используйте memmove.
Мы могли бы заменить вызов memmove следующим циклом:
nt j;
for (j = i; j
< nvtab.nval-1; j++)
nvtab.namevalfj]
= nvtab.nameval[j+1];i
Однако мы предпочитаем использовать memmove, чтобы обезопасить себя от легко возникающей ошибки копирования элементов в неправильном порядке. Если бы мы вставляли элемент, а не удаляли, то цикл должен был бы идти вверх, чтобы не затереть элементы. Вызывая memmove, мы ограждаем себя от необходимости постоянно задумываться об этом.
Альтернатива перемещению элементов — помечать удаленные элементы как неиспользуемые. Тогда для добавления элемента нам надо сначала найти неиспользуемую ячейку и увеличивать массив, только если свободного места не найдено. В данном примере элемент можно пометить как неиспользуемый, установив значения поля name в NULL.
Массивы — простейший способ группировки данных; вовсе не случайно большинство языков имеют эффективные и удобные индексируемые массивы и даже представляют строки в виде массивов символов. Массивы просты в использовании, обладают константным доступом к любому элементу, хорошо работают с двоичным поиском и быстрой сортировкой, а также почти совсем не тратят лишних ресурсов. Для наборов данных фиксированного размера, которые могут быть созданы даже во время компиляции, или же для гарантированно небольших объемов данных массивы подходят идеально. Однако хранение меняющегося набора значений в массиве может быть весьма ресурсоемким, поэтому, если количество элементов непредсказуемо и потенциально неограниченно, может оказаться удобнее использовать другую структуру данных.
Упражнение 2-5
В приведенном выше коде функция delname не вызывает realloc для возврата системе памяти, освобожденной удалением элемента. Имеет ли смысл это делать? Как решить, стоит это делать или нет?
Упражнение 2-6
Внесите необходимые изменения в функции delname и addname, чтобы удаленные элементы помечались как неиспользуемые. Насколько остальная программа не зависит от этого изменения?
