Непосредственное хранение ключа в элементе таблицы

Строка символов, определяющая значение ключа содержится в самом

элементе (рис. 1. 1).

Элемент

…

Ключ

Данные

Рис_.1.1. Элемент таблицы с непосредственным хранением ключа

На языке Си элемент можно описать следующей структурой:

#define nameSize

Размер ключа

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

// хранении ключа в элементе.

struct element {

char name[nameSize]; // ключ

int count;

};

// счетчик частоты встречаемости

Такой метод хранения удобен для ключей, имеющих одинаковую дли-

ну и небольшой размер (6-14 символов). Он часто используется в языках Ас-

семблера, Фортране, макропроцессорах.

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

работки.

Недостатки. Неэффективное использование памяти при различной

длине ключей и большом максимальном размере. Существование ограничи-

теля длины имени может быть неприемлемо в ряде приложений.

Динамическое выделение памяти для ключа

Память для хранения строки символов выделяется динамически с ис-

пользованием стандартных функций ОС и языков программирования (рис.

1.2).

Элемент

Указатель на

Ключ

Данные

…

Ключ

Рис_.1.2. Элемент таблицы с динамическим выделением памяти для ключа

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

нения данного имени. В любой момент занимаемая память может быть легко

освобождена. Описание структуры элемента на языке Си мало чем отлича-

ется от первого варианта.

// Организация элемента таблицы имен при хранении ключа

// в динамически выделяемой памяти.

struct element {

char* name; // указатель на ключ

Int count; // счетчик частоты встречаемости

};

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

new. Кроме того, возможно использование функций malloc или calloc. Раз-

мер выделяемой памяти зависит от длины ключа и определяется в ходе рабо-

ты программы.

Преимущества. Легкость управления доступной оперативной памя-

тью. Динамическое выделение памяти позволяет организовать эффективное

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

Недостатки. Дополнительные затраты памяти на хранение указате-

лей, замедление работы с ключами за счет введения дополнительных опера-

ций работы со ссылками (указателями), дополнительные временные затраты

на динамическое выделение и освобождение памяти малыми порциями.