Массивы структур – таблицы
Обычной практикой является размещение одинаковых по содержанию экземпляров структур в одном месте, последовательно – друг за другом. В результате образуется логическая структура данных, называемая таблицей. Каждый экземпляр структуры, входящий в таблицу, называется элементом таблицы.
Как физическая структура данных таблица представляет собой линейную последовательность ячеек памяти, число которых определяется количеством и размером полей каждого элемента, а также числом элементов таблицы.
Над таблицей можно определить следующие операции:
- включение нового элемента путем расширения таблицы или его вставки на свободное место;
- поиск элемента для последующей его обработки;
- исключение элемента из таблицы.
Скорость доступа к элементам таблицы при выполнении этих операций зависит от двух факторов – способа организации поиска нужного элемента и размера таблицы.
Поиск в таблице
Перечисленные выше операции с таблицей предполагают, что для однозначного доступа к ее элементам последние должны содержать один или более признаков, отличающих их от других элементов этой таблицы. С этой целью в логическую структуру элемента включается по крайней мере одно поле – ключ, содержимое которого уникально для любого из элементов, входящих в таблицу. В общем случае работа с таблицами сводится к методам решения задачи поиска нужного элемента таблицы по заданному значению ключа. Результат решения – получение адреса искомого элемента или заключение о его отсутствии.
Для локализации элемента таблицы необходимо знать два адресных компонента – адрес таблицы и смещение нужного элемента относительно начала таблицы. Адрес таблицы получить несложно, так как он является адресом ее первого элемента. Что же касается определения второй компоненты адреса, то для этого существует ряд методов, рассмотрению которых и будет посвящено дальнейшее изложение.
В ряде случаев наряду с ключевым полем определяют еще одно служебное поле – поле текущего состояния элемента, которое может принимать три значения:
- элемент свободен – после инициализации таблицы элемент ни разу не использовался для хранения полезной информации;
- элемент используется для хранения полезной информации;
- элемент удален – после инициализации таблицы элемент хотя бы один раз использовался для хранения полезной информации, после чего был освобожден.
Целесообразность использования поля текущего состояния элемента будет видна из дальнейших рассуждений.
С точки зрения организации поиска таблицы делятся на:
- неупорядоченные;
- древовидные;
- упорядоченные;
- с вычисляемыми входами (хэш-таблицы).
Неупорядоченные таблицы
Это простейший вид организации таблиц. Элементы располагаются непосредственно друг за другом, без пропусков. Процесс поиска нужного элемента выполняется очень просто – последовательным перебором элементов таблицы начиная с первого. При этом анализируется ключевое поле и в случае удовлетворения его условию поиска нужный элемент локализуется. Такой способ поиска называется последовательным, или линейным. Для добавления нового элемента необходимо найти первое свободное место, после чего выполнить операцию добавления.
Процесс удаления можно реализовать следующим образом. После локализации нужного элемента его поле текущего состояния необходимо установить в состояние "элемент удален". Тогда процесс поиска места для добавления нового элемента будет заключаться в поиске такого элемента, у которого поле текущего состояния элемента имеет значение "элемент удален" или "элемент свободен". Можно еще более оптимизировать работу с неупорядоченной таблицей путем введения в начале таблицы (или перед ней) дескриптора, поля которого содержали бы информацию о размере таблицы, положении первого свободного элемента и т. д.
Обычно неупорядоченные таблицы используют в качестве временных для хранения небольшого количества элементов (до 20). Для таблиц большего размера такая организация поиска неэффективна, поэтому для них следует применять другие способы локализации нужного элемента.
Приемы работы с неупорядоченной таблицей продемонстрируем на примере следующей задачи. Необходимо прочитать содержимое файла maket.txt и обо всех десятичных и шестнадцатеричных числовых константах собрать информацию о значении константы и номере строки, в которой данная константа встретилась. Вывести информацию о десятичных константах на экран.
Для того чтобы избежать возни с несущественными деталями, введем следующие ограничения:
- содержимое файла – идентификаторы и константы, разделенные не более чем одним пробелом, перед первым или последним идентификатором или константой в строке также следуют по одному пробелу;
- для удобства преобразования предполагаем, что длина и количество строк файла maket.txt находятся в диапазоне 0..99, а общая длина файла – не более 240 байт.