Хранение ключей в списке символьных массивов

Организация этой структуры является комбинацией двух предшест-

вующих. Память для ключей в этом случае выделяется динамически в виде

достаточно длинного массива. Если выделенный массив заполнен до конца и

требуется занесение нового ключа, динамически выделяется память для еще

одного массива и т.д. Выделяемые массивы организуются в виде списка.

Элемент таблицы содержит указатель на место хранения ключа в одном

из таких массивов (рис. 1.4). Программная реализация данного метода опира-

ется на задание сложного указателя ключа, так как, наряду с указанием ме-

стоположения в символьном массиве, необходимо еще задать и сам массив.

При этом также возможно использование вариантов доступа как по индексу,

так и по указателю. В последнем случае обращение к ключу может быть

осуществлено за один раз, а структура элемента будет соответствовать той,

которая приведена для второго варианта.

Элемент

ptr

next

Указатель на

ключ

…

Данные

Символьный массив

…

…

ptr

next

...

…

Ключ данного элемента

… …

...

ptr

*

…

…

…

Рис. 1.4. Элемент таблицы с хранением ключей в списке символьных массивов

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

#define nameArraySize 1000 // размер массива ключей

#define stringNumber 10 // количество строковых массивов

// список указателей на строки

char* stringArray[stringNumber];

Int firstFree; // начало незанятой области массива ключей

// организация элемента таблицы имен при

// хранении ключа в специальном массиве

struct element {

Int stringIndex; // индекс символьного массива

Int nameIndex; // индекс ключа