Работа с большими объемами данных становится более продуктивной, когда данные упорядочены, т. е. образуют определенную структуру. Широкое распространение получили три типа структур данных: массивы, списки и деревья. Под массивом понимают индексируемую совокупность элементов с произвольным доступом к ним. Индекс задает позицию соответствующего элемента в массиве. С помощью индекса осуществляется доступ к элементу. Массив обладает размерностью, определяющей число его элементов. Различают одномерные и многомерные массивы. Одномерный массив имеет одно измерение, его примером является вектор который имеет размерность m и в котором индекс j = 1, ..., m указывает номер элемента. Многомерный массив имеет несколько измерений. Его примером может служить двумерный массив данных с двумя индексами (измерениями) i = 1, ..., n, j = 1, ..., m и размерностью n × m. Многомерные массивы бывают однородными и неоднородными. Однородный массив состоит из элементов одного типа, а неоднородный массив — из элементов разного типа. Двумерный неоднородный массив, у которого типы данных одинаковы только в столбцах, называется таблицей. В табл. 1.8 приводятся данные трех типов: в столбце «Газета» — символьные, «Цена» и «Стоимость» — вещественные числа, «Количество» — целые числа. Поиск нужного элемента в таблице осуществляется также, как и в однородном массиве. Строки в таблице называются записями, а столбцы — полями. Элементы записи имеют, вообще говоря, разный тип. Список — это набор записей, расположенных в определенной последовательности. Его примерами могут служить список студентов группы, перечень дел на день или словарь. Различают два типа списков: непрерывный и связный. Непрерывный список предполагает, что его элементы записаны один за другим в последовательные ячейки памяти. На рис. 1.11 показан расположенный в алфавитном порядке список имен, каждое из которых занимает 8 ячеек памяти. Непрерывный список имеет недостаток: при удалении имени из начала списка приходится перемещать последующие имена к началу списка, чтобы сохранить существующий порядок. Еще более сложная проблема возникает при добавлении имени, поскольку в этом случае требуется переместить список для освобождения блока ячеек, необходимого для расширения списка. Связный список состоит из элементов, снабженных указателями на имена смежных элементов. Структура связного списка показана на рис. 1.12. Здесь для записи элемента списка отводится 9 ячеек: первые восемь для имени, а последняя используется как указатель на следующее имя в списке. От указателя идет стрелка к адресу имени, на который тот указывает. Для прохождения списка надо начать с указателя головы и найти первое имя (запись). Далее необходимо по указателям записей переходить от одного имени к другому до достижения пустого указателя (Null). Здесь удаление записи (например, записи «Имя 2, Указатель 2») означает, что меняется Указатель 1, при этом пунктирной линией со стрелкой показана связь с новым элементом, имеющим Имя 3. Важно подчеркнуть, что расположение записей связного списка в памяти компьютера может быть произвольным. Деревья — это последняя структура данных, которым соответствует организационная схема типичного вуза (рис. 1.13). Чтобы дать определение дерева, введем ограничение: ни одно подразделение не подчиняется двум разным подразделениям более высокого уровня. Такую древовидную структуру данных называют иерархической. Каждый элемент дерева называется узлом. Узел, находящийся на самом высоком уровне, называется корневым, а узлы, находящиеся на самом низком уровне, — терминальными. Нетерминальные узлы связаны с нижестоящими узлами, называемыми потомками. При рассмотрении способов хранения деревьев ограничимся бинарными деревьями, т. е. деревьями, с каждым узлом которых могут быть связаны только два узла потомка. Бинарные деревья представляют собой специальную структуру связанных списков — узлов, формат которых показан на рис. 1.14. После ячейки с данными следуют ячейки-указатели на левого потомка (УЛП) и правого потомка (УПП). В терминальных узлах значения обоих указателей равны Nil. Пример 1.21. Построить бинарное дерево, в узлах которого находятся буквы исходной упорядоченной последовательности A, B, C, D, E, F, G и соответствующую ему структуру связных списков — узлов. Бинарное дерево, изображенное на рис. 1.15, строится с помощью бинарного поиска. Первым корневым узлом становится центральный элемент D, разбивающий исходный список на два одинаковых по числу букв подсписка A, B, C и E, F, G, в которых определяются два центральных элемента — узлы B и F, являющиеся левым и правым потомками D. Оставшиеся элементы A, C и E, G образуют левые и правые потомки узлов B и F соответственно. Согласно принятой на рис. 1.14 структуре узла структура связных списков, соответствующая бинарному дереву на рис. 1.15, будет иметь вид, показанный на рис. 1.16. Следует отметить, что поиск заданной буквы достаточно прост: надо двигаться из корневого узла к тем потомкам, где она должна находиться. Кратко