Абстрактные структуры данных

Любая программа предназначена для обработки данных, от способа организации которых зависит ее алгоритм. Для разных задач необходимы различные способы хранения и обработки данных, поэтому выбор структур данных должен предше­ствовать созданию алгоритмов и основываться на требованиях к функциональ­ности и быстродействию программы.

Наиболее часто в программах используются следующие структуры данных: мас­сив, список, стек, очередь, бинарное дерево, хеш-таблица, граф и множество. Да­лее даны краткие характеристики каждой их этих структур.

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

В списке каждый элемент связан со следующим и, возможно, с предыдущим. В пер­вомслучае список называется односвязным, во втором - двусвязным. Также приме­няются термины однонаправленный и двунаправленный. Если последний элемент связать указателем с первым, получается кольцевой список. Количество элемен­тов в списке может изменяться в процессе работы программы.

Каждый элементсписка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью данных, хранящихся в каждом элементе списка. В качестве ключа в процессе работы со списком могут выступать разные части данных.

Например, если создается спи­сок из записей, содержащих фамилию, год рождения, стаж работы и иол, любая часть записи может выступать в качестве ключа: при упорядочивании списка по алфавиту ключом будет фамилия, а при поиске, например, ветеранов труда клю­чом можно сделать стаж. Ключи разных элементов списка могут совпадать.

Над списками можно выполнять следующие операции:

□ добавление элемента в конец списка;

□ чтение элемента с заданным ключом;

□ вставка элемента в заданное место списка;

□ удаление элемента с заданным ключом;

□ упорядочивание списка поключу.

Список не обеспечивает произвольный доступ к элементу, поэтому при выпол­нении операций чтения, вставки и удаления выполняется последовательныйпе­ребор элементов, пока не будет найден элемент с заданным ключом. Для списков большого объема перебор элементов может занимать значительное время, по­скольку среднее время поиска элемента пропорционально количеству элементов в списке.

Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вер­шиной стека. Другие операции состеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (Last In — First Out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячики. Достать первый брошенный мячик можно только после того, как выну­ты все остальные. Стеки широко применяются в системном программном обес­печении, компиляторах, в различных рекурсивных алгоритмах. Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие опе­рации с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (First In — First Out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, в моделировании, диспетчеризации задач операционной системой, буферизован­ном вводе-выводе.

Бинарное дерево — это динамическая структура данных, состоящая из узлов, каж­дый из которых содержит помимо данных не более двух ссылок на различные бинарные поддеревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева.

Пример бинарного дерева приведен на рис. 13.1 (корень обычно изображается сверху). Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется ко­личеством уровней, на которых располагаются его узлы.

Рис. 13.1. Пример бинарного дерева поиска

 

Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева -больше, оно называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму ко­личества узлов. Впрочем, скорость поиска в значительной степени зависит от по­рядка формирования дерева: если на вход подается упорядоченная или почти упорядоченная последовательность ключей, дерево вырождается в список. Для ускорения поиска применяется процедура балансировки дерева, формирующая дерево, поддеревья которого различаются не более чем на один элемент. Бинар­ные деревья применяются для эффективного поиска и сортировки данных. Хеш-таблица, ассоциативный массив, или словарь — это массив, доступ к эле­ментам которого осуществляется не по номеру, а по некоторому ключу. Можно сказать, что это таблица, состоящая из пар «ключ- значение» (табл. 13.1). Хеш-таблица эффективно реализует операцию поиска значения по ключу. При этом ключ преобразуется в число (хеш-код), которое используется для быстрого нахож­дения нужного значения в хеш-таблице.

Таблица 13.1.Пример хеш-таблицы

Ключ Значение

boy мальчик

girl девочка

dog собачка

 

Преобразование выполняется с помощью хеш-функции, или функции расстановки. Эта функция обычно производит какие-либо преобразования внутреннего пред­ставления ключа, например, вычисляет среднее арифметическое кодов составляющих его символов (английское слово «hash» означает перемалывать, перемешивать). Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов массива, то доступ к элементу по ключу выполняется почти так же быстро, как в массиве. Если хеш-функция генерирует для разных ключей оди­наковые хеш-коды, время поиска возрастает и становится сравнимым со временем поиска в списке.