1.2. Рекурсивные структуры данных и рекурсивные подпрограммы.

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

1.3. Линейная рекурсия в списке.

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

1.4. Деревья.

Определение дерева имеет исключительно рекурсивную природу. Элемент этой структуры данных называется вершиной или узлом. Дерево представляет собой либо отдельную вершину, либо вершину, имеющую ограниченное число связей к другим деревьям (ветвей). Нижележащие деревья для текущей вершины называются поддеревьями, а их вершины – потомками. По отношению к потомкам текущая вершина называется предком.

Вершина дерева является структурированной переменной, содержащей некоторое количество (отдельные переменные, массив, динамический массив) указателей на потомков.

1.4.1. Обход дерева.

Рекурсивная подпрограмма обхода дерева получает в качестве формального параметра указатель на текущую вершину, в теле подпрограммы присутствует цикл, в котором производится рекурсивный вызов с параметром-указателем на потомка. Обход ограничивается обнаружением NIL-указателя – отсутствием потомка.

1.4.2. Двоичное (бинарное) дерево с указателями на объекты произвольного типа.

При рассмотрении самого простого варианта корневая вершина двоичного дерева является одновременно объектом-заголовком, но, поскольку дерево может быть также пустым, следует допустить наличие в вершине дерева NIL-указателя на элемент данных. Такая вершина будет считаться незанятой. Конструктор объекта-вершины дерева должен создавать именно такую незанятую вершину.

Особенностью методов для объектов деревьев является то, что они – рекурсивные, т. е. тот же самый метод необходимовызватьдля объекта-потомка через соответствующий указатель в текущем объекте – текущей вершине дерева.

Двоичное дерево обеспечивает естественную упорядоченность хранимых данных в порядке его обхода: левое поддерево – вершина – правое поддерево. Поэтому операция включения производится только с сохранением упорядоченности.

2. Функция ввода

Чтение ввода – часто самая трудная часть программы, поскольку, данная подпрограмма общается с человеком, который может допускать ошибки при вводе.

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

3. Таблица имен

3.1. Поиск в таблице.

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

Задача поиска состоит в определении по заданному ключу адреса хранения табличной записи, если имеется такая запись в таблице.

Поиск в массиве иногда называют поиском в таблице, особенно, если ключ сам является составным объектом, таким, как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами.

Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены (отсортированы) согласно некоторому естественному порядку.

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

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

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