- •Оглавление
- •1. Информация, ее представление и измерение
- •2. Системы счисления и действия в них
- •3. Пространство сообщений. Коды обнаружения и исправления ошибок
- •4. Кодирование и шифрование информации
- •4.1. Криптография и криптоанализ
- •4.2. Традиционные симметричные криптосистемы
- •4.2. Шифрование методом замены
- •4.3. Шифрование методами перестановки
- •4.4. Шифрование методом гаммирования
- •4.3.Элементы криптоанализа
- •5. Функции алгебры логики. Программная реализация логических функций
- •5.1. Основные функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •5.2. Булева алгебра. Функциональная полнота
- •Свойства алгебры Жегалкина
- •1. Коммутативность
- •2. Дистрибутивность
- •3. Идемпотентность
- •5.3. Минимизация функций алгебры логики
- •5.4. Программная реализация логических функций и автоматов
- •6. Логические элементы эвм
- •8. Данные, типы данных, структуры и обработка
- •9. Методы разработки и анализа алгоритмов
- •10. Теория конечных автоматов
- •10.1. Определение конечного автомата
- •10.2. Способы представления конечных автоматов
- •11. Архитектура эвм
- •12. Программное и техническое обеспечение эвм
- •13. Информационные структуры
- •13.1. Последовательное и связанное распределение данных
- •13.2. Стеки и очереди
- •13.3. Деревья
- •13.4. Представление деревьев
- •13.5. Прохождение деревьев, леса
- •14. Формальные языки и грамматики
- •14.1. Введение в теорию формальных языков и грамматик
- •14.2. Выводы цепочек формальных грамматик. Деревья ксг
- •14.3. Основные понятия теории формальных языков и грамматик
- •Литература
13.2. Стеки и очереди
В комбинаторных алгоритмах особую важность представляют две структуры данных, основанные на динамических последовательностях, т.е. последовательностях, которые изменяются вследствие включения новых и исключения имеющихся элементов.
В обоих случаях операции включения и исключения производятся только на концах последовательности [11].
Стек есть последовательность, у которой все включения и исключения происходят только в одном конце, называемом вершиной стека. Соответственно другой конец последовательности называется основанием.
Правило работы со стеком: «Первым пришел — последним ушел».
Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).
Правило работы с очередью: «Первым пришел — первым ушел».
Стеки и очереди имеют важное значение в автоматизации работы с информационными структурами.
13.3. Деревья
Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m 0 поддеревьев Т1, Т2, …, Тm.
Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами [12].
Р ис. 13.5. Дерево с 11 узлами
Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.
Посредством деревьев представляются иерархические структуры, поэтому они являются наиболее важными нелинейными структурами данных.
В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 13.5 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д.
Все рассматриваемые деревья упорядочены, т.е. для них важен относительный порядок поддеревьев каждого узла. Т.е. деревья
считаются различными.
Определим лес как упорядоченное множество деревьев.
Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого Tl и правого Tr.
Б инарные деревья, вообще говоря, не являются подмножеством множества деревьев, они полностью отличаются своей структурой, поскольку
есть разные бинарные деревья.
Различие между бинарным деревом и деревом состоит в том, что не бинарное дерево не может быть пустым, и каждый узел не бинарного дерева может иметь произвольное число поддеревьев. В то же время бинарное дерево может быть пустым и каждая его вершина может иметь 0, 1 или 2 поддерева, также существует различие между левым и правым поддеревьями.
13.4. Представление деревьев
Почти все машинные представления деревьев основаны на связанном распределении данных. Каждый узел состоит из поля INFO и полей для указателей (рис. 13.6). На рис. 13.6 показаны связи от потомков к предку.
Такая операция встречается редко, чаще требуется опуститься по дереву от предков к потомкам. Представление дерева (или леса) с использованием указателей, ведущих от предков к потомкам, довольно сложно из-за узла отца, который может иметь произвольно много сыновей. Другими словами, при таком представлении узлы должны различаться по размеру, что неудобно.
Р ис. 13.6. Дерево, представленное с помощью узлов с полем INFO и указателем FATHER
Один из путей обхода этой трудности состоит в построении соответствия между деревьями и бинарными деревьям, поскольку бинарные деревья легко представить узлами фиксированного размера. Каждый узел при этом имеет три поля: LEFT - указатель местоположения корня левого поддерева, INFO - информационная часть содержимого узла и RIGHT - указатель местоположения корня правого поддерева.
Рис. 13.7. Представление бинарного дерева с помощью узлов с тремя полями LEFT, INFO, RIGHT
Следующее представление дерева (или леса) в виде бинарного дерева будем называть естественным соответствием между деревьями и бинарными деревьями. Оно касается того, что в поле LEFT указывается самый левый сын данного узла, а в поле RIGHT — указывается следующий брат данного узла. Например, лес, показанный на рис. 13.8 преобразуется в бинарное дерево, показанное на рис. 13.9 следующим образом:
Р ис. 13.8. Лес
Р ис. 13.9. Представление леса в виде бинарного дерева