Строка символов, определяющая значение ключа содержится в самом
элементе (рис. 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. Раз-
мер выделяемой памяти зависит от длины ключа и определяется в ходе рабо-
ты программы.
Преимущества. Легкость управления доступной оперативной памя-
тью. Динамическое выделение памяти позволяет организовать эффективное
хранение ключей произвольных размеров.
Недостатки. Дополнительные затраты памяти на хранение указате-
лей, замедление работы с ключами за счет введения дополнительных опера-
ций работы со ссылками (указателями), дополнительные временные затраты
на динамическое выделение и освобождение памяти малыми порциями.