Модели и структуры данных

Радиотехникам: Радиотелефоны, Аудио, Антенны



Глава 2. Деки в вычислительных системах


    4.4.2. Деки в вычислительных системах
    4.4.2. Деки в вычислительных системах Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди...
    4.5.1. Логическая структура строки
    4.5.1. Логическая структура строки Строка - это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Строки обладают следующими важ...
    4.5.2. Операции над строками
    4.5.2. Операции над строками Базовыми операциями над строками являются: определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения. Операция...
    4.5.3. Представление строк в памяти.
    4.5.3. Представление строк в памяти. Представление строк в памяти зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче, и средства такого представления варьируются от...
    Векторное представление строк.
    ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Представление строк в виде векторов, принятое в большинстве универсальных языков программирования, позволяет работать со строками, размещенными в статической памяти....
    Рис. 4.3. Представление строк векторами постоянной длины
    Рис. 4.3. Представление строк векторами постоянной длины...
    Представление строк вектором переменной...
    ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ КОНЦА. Этот и все последующие за ним методы учитывают переменную длину строк. Признак конца - это особый символ, принадлежащий алфавиту (т...
    Рис. 4.4. Представление строк...
    Рис. 4.4. Представление строк переменной длины с признаком конца...
    Представление строк вектором переменной длины со счетчиком.
    ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ СО СЧЕТЧИКОМ. Счетчик символов - это целое число, и для него отводится достаточное количество битов, чтобы их с избытком хватало для представления дли...
    Рис.4.5. Представление строк переменной длины со счетчиком
    Рис.4.5. Представление строк переменной длины со счетчиком В двух предыдущих вариантах обеспечивалось максимально эффективное расходование памяти (1-2 "лишних" символа на строку), но изменчивость...
    Вектор с управляемой длиной.
    ВЕКТОР С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память под вектор с управляемой длиной отводится при создании строки и ее размер и размещение остаются неизменными все время существования строки. В дескрипторе такого...
    Рис.4.6. Представление строк вектором с управляемой длиной
    Рис.4.6. Представление строк вектором с управляемой длиной В программном примере 4.4 приведен модуль, реализующий представление строк вектором с управляемой длиной и некоторые операции над такими...
    Символьно - связное представление строк.
    СИМВОЛЬНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Списковое представление строк в памяти обеспечивает гибкость в выполнении разнообразных операций над строками (в частности, операций включения и исключения...
    Однонаправленный линейный список.
    ОДНОНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. Каждый символ строки представляется в виде элемента связного списка; элемент содержит код символа и указатель на следующий элемент, как показано на рис.4.7. Однос...
    Рис.4.7. Представление строки...
    Рис.4.7. Представление строки однонаправленным связным списком...
    Двунаправленный линейный список.
    ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. В каждый элемент списка добавляется также указатель на предыдущий элемент, как показано на рис.4.8. Двустороннее сцепление допускает двустороннее движение вдоль сп...
    Рис.4.8. Представление строки...
    Рис.4.8. Представление строки двунаправленным связным списком...
    Блочно - связное представление строк.
    БЛОЧНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Это представление позволяет в болшинстве операций избежать затрат, связанных с управлением динамической памятью, но в то же время обеспечивает достаточно эффе...
    Многосимвольные звенья фиксированной длины.
    МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ФИКСИРОВАННОЙ ДЛИНЫ. Многосимвольные группы (звенья) организуются в список, так что каждый элемент списка, кроме последнего, содержит группу элементов строки и указатель сле...
    Рис. 4.9. Представление строки...
    Рис. 4.9. Представление строки многосимвольными звеньями постоянной длины Такое представление обеспечивает более эффективное использование памяти, чем символьно-связное. Операции вставки/удаления...
    Многосимвольные звенья переменной длины.
    МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ПЕРЕМЕННОЙ ДЛИНЫ. Переменная длинна блока дает возможность избавиться от пустых символов и тем самым экономить память для строки. Однако появляется потребность в специальном...
    Рис.4.10. Представление строки...
    Рис.4.10. Представление строки многосимвольными звеньями переменной длины Такой метод спискового представления строк особенно удобен в задачах редактирования текста, когда большая часть операций п...
    Многосимвольные звенья с управляемой длиной.
    МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память выделяется блоками фиксированной длины. В каждом блоке помимо символов строки и указателя на следующий блок содержится номера первого и последне...
    Рис.4.11. Представление строки звеньями управляемой длины
    Рис.4.11. Представление строки звеньями управляемой длины В программном примере 4.5 приведен модуль, реализующий представление строк звеньями с управляемой длиной. Даже с первого взгляда видно, чт...
    5.1. Связное представление данных в памяти
    5.1. Связное представление данных в памяти Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью р...
    5.2. Связные линейные списки
    5.2. Связные линейные списки Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения...
    5.2.1. Машинное представление связных линейных списков
    5.2.1. Машинное представление связных линейных списков На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент спи...
    Рис.5.1. Структура односвязного списка
    Рис.5.1. Структура односвязного списка Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает...
    Рис.5.2. Структура двухсвязного списка
    Рис.5.2. Структура двухсвязного списка Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного...
    Рис.5.3. Структура кольцевого двухсвязного списка
    Рис.5.3. Структура кольцевого двухсвязного списка В памяти список представляет собой совокупность дескриптора и одинаковых по размеру и формату записей, размещенных произвольно в некоторой области...
    5.2.2. Реализация операций над связными линейными списками
    5.2.2. Реализация операций над связными линейными списками Ниже рассматриваются некоторые простые операции над линейными списками. Выполнение операций иллюстрируется в общем случае рисунками со сх...
    Перебор элементов списка.
    Перебор элементов списка. Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца спи...
    Вставка элемента в список.
    Вставка элемента в список. Вставка элемента в середину односвязного списка показана на рис.5.4 и в примере 5.2....
    Рис.5.4. Вставка элемента в середину 1-связного списка
    Рис.5.4. Вставка элемента в середину 1-связного списка {==== Программный пример 5.2 ====} { Вставка элемента в середину 1-связного списка } Procedure InsertSll(prev : sllptr; inf : data); { prev -...
    Рис.5.5. Вставка элемента в середину 2-связного списка
    Рис.5.5. Вставка элемента в середину 2-связного списка Приведенные примеры обеспечивают вставку в середину списка, но не могут быть применены для вставки в начало списка. При последней должен моди...
    Рис.5.6. Вставка элемента в начало 1-связного списка
    Рис.5.6. Вставка элемента в начало 1-связного списка Программный пример 5.3 представляет процедуру, выполняющую вставку элемента в любое место односвязного списка. {==== Программный пример 5.3 ===...
    Удаление элемента из списка.
    Удаление элемента из списка. Удаление элемента из односвязного списка показано на рис.5.7....
    Рис.5.7. Удаление элемента из 1-связного списка
    Рис.5.7. Удаление элемента из 1-связного списка Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.5.7.а). Мы, однако, на рис....
    Рис.5.8. Удаление элемента из 2-связного списка
    Рис.5.8. Удаление элемента из 2-связного списка Процедуру удаления элемента из двухсвязного списка окажется даже проще, чем для односвязного, так как в ней не нужен поиск предыдущего элемента, он...
    Перестановка элементов списка.
    Перестановка элементов списка. Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение...
    Рис.5.9. Перестановка соседних элементов 1-связного списка
    Рис.5.9. Перестановка соседних элементов 1-связного списка {==== Программный пример 5.5 ====} { Перестановка двух соседних элементов в 1-связном списке } Procedure ExchangeSll( prev : sllptr { ука...
    Копирование части списка.
    Копирование части списка. При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старо...
    Рис.5.10. Перестановка соседних элементов 2-связного списка
    Рис.5.10. Перестановка соседних элементов 2-связного списка Копирование для односвязного списка показано в программном примере 5.6. {==== Программный пример 5.6 ====} { Копирование части 1-связног...
    Слияние двух списков.
    Слияние двух списков. Операция слияния заключается в формировании из двух списков одного - она аналогична операции сцепления строк. В случае односвязного списка, показанном в примере 5.7, слияние...
    5.2.3. Применение линейных списков
    5.2.3. Применение линейных списков Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных...
    5.3. Мультисписки
    5.3. Мультисписки В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а л...
    Рис.5.11. Пример мультисписка
    Рис.5.11. Пример мультисписка Для того, чтобы при выборке каждого подмножества не выполнять полный просмотр с отсеиванием записей, к требуемому подмножеству не относящихся, в каждую запись включаю...
    5.4.1. Основные понятия
    5.4.1. Основные понятия Нелинейным разветвленным списком является список, элементами которого могут быть тоже списки. В разделе 5.2 мы рассмотрели двухсвязные линейные списки. Если один из указате...
    Рис.5.12. Схематическое представление разветвленного списка
    Рис.5.12. Схематическое представление разветвленного списка Разветвленные списки описываются тремя характеристиками: порядком, глубиной и длиной....
    Порядок.
    Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествуе...
    Глубина.
    Глубина. Это максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е.числом пар...
    Рис.5.13. Схема списка, представляющего...
    Рис.5.13. Схема списка, представляющего алгебраическое выражение Выражение: (a+b)*(c-(d/e))+f будет вычисляться в следующем порядке: a+b d/e c-(d/e) (a+b)*(c-d/e) (a+b)*(c-d/e)+f При представлении...
    5.4.2. Представление списковых структур в памяти.
    5.4.2. Представление списковых структур в памяти. В соответствии со схематичным изображением разветвленных списков типичная структура элемента такого списка в памяти должна быть такой, как показан...
    Рис.5.14. Структура элемента разветвленного списка
    Рис.5.14. Структура элемента разветвленного списка Элементы списка могут быть двух видов: атомы - содержащие данные и узлы - содержащие указатели на подсписки. В атомах не используется поле down э...
    Рис.5.15. Структура элемента разветвленного списка
    Рис.5.15. Структура элемента разветвленного списка Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает н...
    Рис. 5.16. Структура элемента разветвленного списка
    Рис. 5.16. Структура элемента разветвленного списка В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно...
    Рис.5.17. Пример представления...
    Рис.5.17. Пример представления списка элементами одного формата...
    5.4.3. Операции обработки списков
    5.4.3. Операции обработки списков Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom. Операция car в качестве аргумента получает список (указатель на нача...
    5.5. Язык программирования lisp
    5.5. Язык программирования LISP LISP является наиболее развитым и распространенным языком обработки списков. "Идеология" и терминология этого языка в значительной степени повлияла на общепринятые...
    5.6. Управление динамически выделяемой памятью
    5.6. Управление динамически выделяемой памятью Динамические структуры по определению характеризуется непостоянством и непредсказуемостью размера. Поэтому память под отдельные элементы таких структ...
    6.1.1. Логическая структура, определения
    6.1.1. Логическая структура, определения Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта. Многосвязная структура обладает следующи...
    Рис.6.1. Граф неориентированный (а) и ориентированный (б).
    Рис.6.1. Граф неориентированный (а) и ориентированный (б). Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узела -полустепенью исхода. Ко...
    Рис.6.2. Графа и его матрица смежности
    Рис.6.2. Графа и его матрица смежности Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали. Матрицы смежности используются при построении матриц пут...
    Рис.6.3. Матрицы путей
    Рис.6.3. Матрицы путей Матрицы инцидентности используются только для орграфов. В каждой строке содержится упорядоченная последовательность имен узлов, с которыми данный узел связан ориетрированным...
    Рис.6.4. Матрицы инцидентности
    Рис.6.4. Матрицы инцидентности...
    6.1.2. Машинное представление оpгpафов
    6.1.2. Машинное представление оpгpафов Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зави...
    Матричное представление орграфов.
    МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. При использовании матриц смежности их элементы представляются в памяти ЭВМ элементами массива. При этом, для простого графа матрица состоит из нулей и единиц, для...
    Связное представление орграфов.
    СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представле...
    Рис.6.5. Машинное представление графа элементами двух типов
    Рис.6.5. Машинное представление графа элементами двух типов Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель-da...
    Рис.6.6. Машинное представление графа однотипными элементами
    Рис.6.6. Машинное представление графа однотипными элементами Многосвязная структура - граф - находит широкое применение при организации банков данных, управлении базами данных, в системах программ...
    Рис.6.7. Часть дорожной карты...
    Рис.6.7. Часть дорожной карты, представленная в виде взвешенного графа и его матрицы смежности {========== Программный пример 6.1 ==============} { Алгоритм Дейкстры } Program ShortWay; Const n=5;...
    6.2.1. Основные определения
    6.2.1. Основные определения Дерево - это граф, который характеризуется следующими свойствами: 1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент...
    Рис. 6.8. Дерево
    рис. 6.8. Дерево...
    Рис. 6.9. Лес
    рис. 6.9. Лес Ниже будет представлен важный класс орграфов - ориентированные деревья - и соответствующая им терминология. Деревья нужны для описания любой структуры с иерархией. Традиционные приме...
    Рис.6.10. Дерево
    рис.6.10. Дерево Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называетс...
    6.2.2. Логическое представление и изображение деревьев.
    6.2.2. Логическое представление и изображение деревьев. Имеется ряд способов графического изображения деревьев. Первый способ заключается в использовании для изображения поддеревьев известного мет...
    Метод вложенных скобок
    МЕТОД ВЛОЖЕННЫХ СКОБОК (V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))...
    Рис.6.11. Представление дерева...
    Рис.6.11. Представление дерева : а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощь...
    6.2.3. Бинарные деревья.
    6.2.3. Бинарные деревья. Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исх...
    Рис. 6.13. Изображения бинарных деревьев
    Рис. 6.13. Изображения бинарных деревьев Бинарные деревья, изображенные на рис.6.13(a) и 6.13(d), представляют собой разные позиционные деревья, хотя они не являются разными упорядоченными деревья...
    6.2.4. Представление любого дерева...
    6.2.4. Представление любого дерева, леса бинарными деревьями. Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево. Правило построения бинарного дерева...
    Рис.6.14. Исходное дерево
    Рис.6.14. Исходное дерево...
    Рис.6.15 промежуточный результат перестройки дерева
    Рис.6.15 Промежуточный результат перестройки дерева...
    Рис. 6.16. Представление дерева в виде бинарного
    Рис. 6.16. Представление дерева в виде бинарного Описанный выше метод представления произвольных упорядоченных деревьев посредством бинарных деревьев можно обобщить на представление произвольного...
    Рис.6.17. Упорядоченный лес
    рис.6.17. Упорядоченный лес...
    Рис.6.18. Промежуточный результат перестройки леса
    Рис.6.18. Промежуточный результат перестройки леса...
    Рис. 6.19. Представление леса в виде 2-го дерева
    Рис. 6.19. Представление леса в виде 2-го дерева В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом....
    6.2.5. Машинное представление деревьев в памяти эвм.
    6.2.5. Машинное представление деревьев в памяти ЭВМ. Деревья можно представлять с помощью связных списков и массивов (или последовательных списков). Чаще всего используется связное представление д...
    Рис. 6.20. Логическое представление дерева
    Рис. 6.20. Логическое представление дерева...
    Рис. 6.21. Машинное связное представление...
    Рис. 6.21. Машинное связное представление дерева представленного на рис.6.20 Рассмотрим последовательное представление деревьев. Оно удобно и эффективно в случае, если древовидная структура в тече...
    Рис. 6.22. Диаграммы дерева: а)...
    Рис. 6.22. Диаграммы дерева: а) исходное б) перестройка в бинарное Последовательное представление дерева, логическая диаграмма которого дана на рис. 6.22 , задается следующим образом: i 1 2 3 4 5...
    Рис. 6.23. Последовательное представление...
    Рис. 6.23. Последовательное представление дерева методом опускания полей где RPTR,DATA и TAG представляют векторы. В данном методе указатель LPTR не требуется, т.к. если бы он не был пуст, то указ...
    Рис. 6.24. Последовательное представление...
    Рис. 6.24. Последовательное представление дерева с размещением вершин в возрастающем порядке В этом случае поле TAG не требуется поскольку концевой узел определяется условием RANGE(P) = P + 1. Тре...
    Рис. 6.25. Последовательное представление...
    Рис. 6.25. Последовательное представление дерева на основе восходящего обхода В заключении приведем два важных понятия. Подобие бинарных деревьев - два дерева подобны, если они имеют одинаковую ст...
    6.2.6. Основные операции над деревьями.
    6.2.6. Основные операции над деревьями. Над деревьями определены следующие основные операции, для которых приведены реализующие их программы. 1) Поиск узла с заданным ключом ( Find ). 2) Добавлени...
    Поиск записи в дереве( find ).
    ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ). Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом. Пусть построено некоторое дерево и требуется найти звено с ключом...
    Добавление нового узла ( dop ).
    ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ). Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно "подвести" (присоединить) новую вершину, соответствующую включаемой запи...
    Обход дерева.
    ОБХОД ДЕРЕВА. Во многих задачах, связанных с деревьями, требуется осуществить систематический просмотр всех его узлов в определенном порядке. Такой просмотр называется прохождением или обходом дер...
    Рис.6.26. Схема дерева
    Рис.6.26. Схема дерева...
    Нисходящий обход (preorder, r_preorder).
    НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder). В соответствии с алгоритмом, приведенным выше, текст процедуры имеет вид: {=== Программный пример 6.4. Нисходящий обход ===} Procedure Preorder (t: TreePtr...
    Таблица 6.1
    Таблица 6.1...
    Рекурсивный нисходящий обход.
    РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД. Алгоритм существенно упрощается при использовании рекурсии. Так, нисходящий обход можно описать следующим образом: 1). Обработка корневой вершины; 2). Нисходящий обхо...
    Cмешанный обход (inorder, r_inorder).
    CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder). Смешанный обход можно описать следующим образом: 1) Спуститься по левой ветви с запоминанием вершин в стеке; 2) Если стек пуст то перейти к п.5; 3) Выбрать ве...
    Таблица 6.2
    Таблица 6.2 Рекурсивный смешанный обход описывается следующим образом: 1) Смешанный обход левого поддерева; 2) Обработка корневой вершины; 3) Смешанный обход правого поддерева. Текст программы рек...
    Восходящий обход ( postorder, r_postorder ).
    ВОСХОДЯЩИЙ ОБХОД ( Postorder, r_Postorder ). Трудность заключается в том, что в отличие от Preorder в этом алгоритме каждая вершина запоминается в стеке дважды: первый раз - когда обходится левое...
    Рекурсивный смешанный обход
    РЕКУРСИВНЫЙ СМЕШАННЫЙ ОБХОД описывается следующим образом: 1). Восходящий обход левого поддерева; 2). Восходящий обход правого поддерева; 3). Обработка корневой вершины. Текст программы процедуры...
    Процедуры обхода дерева, использующие стек.
    ПРОЦЕДУРЫ ОБХОДА ДЕРЕВА, ИСПОЛЬЗУЮЩИЕ СТЕК. Тип стека при нисходящем обходе. Stack=^Zveno; Zveno = record next: Stack; El: pointer; end; Процедура включения элемента в стек при нисходящем и смешан...
    Прошивка бинарных деревьев.
    ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ. Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу. Рассматривая бинар...
    Рис. 6.27.
    Рис. 6.27. В программном примере 6.14 приведена функция ( Inson ) для определения сына (преемника) данной вершины. { === Програмнный пример 6.14 ====} (*------ Функция, находящая преемника данной...
    Рис. 6.28. Машинное связное представление...
    Рис. 6.28. Машинное связное представление исходного дерева, представленного на рис.6.20 при нисходящем обходе с прошивкой Трассировка нисходящего обхода с прошивкой приведена в табл.6.3. Рассмотри...
    Таблица 6.3
    Таблица 6.3...
    Рис. 6.29. Машинное связное представление...
    Рис. 6.29. Машинное связное представление дерева при смешанном обходе с прошивкой Трассировка смешанного обхода с прошивкой приведена в табл.6.4. @ указателя Узел Обработка узла Выходная строка P:...
    Таблица 6.4.
    Таблица 6.4....
    6.2.7. Приложения деревьев.
    6.2.7. Приложения деревьев. Деревья имеют широкое применение при реализации трансляторов таблиц решений, при работе с арифметическими выражениями, при создании и ведении таблиц символов, где их ис...
    6.2.8 деревья хаффмена (деревья минимального кодирования)
    6.2.8 Деревья Хаффмена (деревья минимального кодирования) Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения. 1...
    Рис.6.30 дерево хаффмена
    Рис.6.30 Дерево Хаффмена Обычно коды создаются на основе частоты во всем множестве сообщений, а не только в одном....
    6.2.9 деревья при работе с арифметическими выражениями
    6.2.9 Деревья при работе с арифметическими выражениями Операция объединения двух символов в один использует структуру бинарного дерева. Каждый узел содержит символ и частоту вхождения. Код любого...
    Манипулирование арифметическими выражениями.
    МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ. Дано выражение а*(-b)+с/d Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,...
    Рис.6.31 представление выражения в виде дерева
    Рис.6.31 Представление выражения в виде дерева...
    Рис. 6.32 представление выражения в виде бинарного дерева.
    Рис. 6.32 Представление выражения в виде бинарного дерева. перемножать, вычитать, дифференцировать, интегрировать, сравнивать на эквивалентность и т.д. Т.е. получаются символьные выражения, которы...
    Рис.6.33 таблица символов
    Рис.6.33 Таблица символов...
    Процедура вычислений:
    Процедура вычислений: Создается семимерный массив меток и его элементам задаются требуемые значения.Оператор генерирует метку исходя из значения поля корневой вершины. И передается управление упра...
    6.2.10 формирование таблиц символов.
    6.2.10 Формирование таблиц символов. В качестве примера приложения бинарных деревьев сформулируем алгоритм ведения древовидно-структурированной таблицы символов. Основной критерий, которому должна...
    Алготитм table.
    АЛГОТИТМ TABLE. На вход подается глобальная переменная n, идентифицирующая номер уровня текущего блока и глобальная переменная FLAG, задающая требуемую операцию. Описываемый алгоритм выполняет эту...
    Описание программы:
    ОПИСАНИЕ ПРОГРАММЫ: Последовательность решения задачи: 1) Ввод выражения; 2) Построение бинарного дерева из данного выражения; 3) Вычисление математического выражения; 4) Вывод дерева на экран; 5)...
    Рис. 6.34.
    Рис. 6.34. Результат выражения = 14.000...
    Определения.
    ОПРЕДЕЛЕНИЯ. Одной из наиболее часто встречающихся задач является поиск необходимых данных. Существуют различные методы, отличающиеся друг от друга временем поиска, сложностью алгоритмов, размерам...
    Операция вставки вершины в сбалансированное дерево.
    ОПЕРАЦИЯ ВСТАВКИ ВЕРШИНЫ В СБАЛАНСИРОВАННОЕ ДЕРЕВО. Предполагается, что новая вершина вставляется на уровне листьев, или терминальных вершин (как левое или правое поддерево). При такой вставке пок...
    Принцип работы алгоритма.
    ПРИНЦИП РАБОТЫ АЛГОРИТМА. Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный...
    Рис. 6.35 последовательное включение...
    Рис. 6.35 Последовательное включение узлов в сбалансированное дерево....
    Алгоритм insert_&_balanse включения...
    АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево. Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (и...
    Описание работы:
    Описание работы: П.1 - осуществляется поиск места для вставки элемента. Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется...
    Текст процедуры insert_&_balanse.
    ТЕКСТ ПРОЦЕДУРЫ Insert_ var p,root:ref; var h:boolean); { x=KEY, p=p, root=ROOT, h=h } var p1,p2:ref; {h=false} Begin if p=nil then Create(x,p,h) {слова нет в дереве,включить его} else if x=p^.key...
    Текст процедуры добавления элемента.
    ТЕКСТ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЭЛЕМЕНТА. Процедура создает новый элемент, заполняет его информационные поля и обнуляет указатели. При создании первого элемента он автоматически становится корнем дерев...
    Операция удаления из сбалансированного дерева.
    ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА. Удаление элемента из сбалансированного дерева является еще более сложной операцией чем включение, так как может удаляться не только какой-либо из лис...
    Пример удаления различных узлов из сбалансированного дерева.
    ПРИМЕР УДАЛЕНИЯ РАЗЛИЧНЫХ УЗЛОВ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА. Узел, который необходимо удалить, обозначен двойной рамкой. Если задано сбалансированное дерево (рис.6.35. a), то последовательное удал...
    Рис.6.36 а..h удаление узлов из сбалансированого дерева.
    Рис.6.36 а..h Удаление узлов из сбалансированого дерева. Удаление элемента из сбалансированного дерева удобнее разбить на 4 отдельных процедуры: 1. Delete - осуществляет рекурсивный поиск по дерев...
    Алгоритм процедуры delete.
    АЛГОРИТМ ПРОЦЕДУРЫ Delete. Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация). Задан: ключ - х, информация -...
    Описание работы алгоритма:
    ОПИСАНИЕ РАБОТЫ АЛГОРИТМА: П.1 - осуществляет поиск удаляемого элемента с помощью рекурсивных вызовов процедуры Delete (т.е. - самой себя). При этом в стеке сохраняется весь путь поиска. Если было...
    Алгоритм процедуры del.
    АЛГОРИТМ ПРОЦЕДУРЫ Del. Дано: указатель - r на элемент дерева с двумя поддеревьями. Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры б...
    Описание работы:
    ОПИСАНИЕ РАБОТЫ: П.1 - производится рекурсивный поиск самого правого элемента в поддереве. Если элемент найден, то он ставится на место удаленного элемента, устанавливается флаг удаления, и осущес...
    Алгоритм процедуры balance_l.
    АЛГОРИТМ ПРОЦЕДУРЫ Balance_L. Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента. Задан: указатель p на место удаленного элемента. Алгоритм производит балансировк...
    Описание работы алгоритма:
    ОПИСАНИЕ РАБОТЫ АЛГОРИТМА: П.1 - если вершина не является критической, то производится изменение показателей сбалансированности. Если вершина критическая - создаются вспомогательные указатели. П.2...
    Алгоритм процедуры balance_r.
    АЛГОРИТМ ПРОЦЕДУРЫ Balance_R. Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента. Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balan...
    Поиск элемента.
    ПОИСК ЭЛЕМЕНТА. Поиск элемента в сбалансированном дереве уже применялся в операциях вставки и удаления элементов. Поэтому необходимо отдельно рассмотреть эту операцию. Пусть дано некоторое бинарно...
    Алгоритм search.
    АЛГОРИТМ Search. Дано: ключ - X. Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента. 1. Поиск элемента:...
    Текст процедуры search.
    ТЕКСТ ПРОЦЕДУРЫ Search. {=====Программный пример 6.21 ===========} Procedure Search (x:integer; var p:ref); begin if x > p^.key then if p=nil then writeln('Элемент на найден') else Search(x,p^.rig...
    Описание программы работы со сбалансированными деревьями.
    ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ. 1. Процедура NOTE. В процессе работы пользователя с программой MAVERIC выводит подсказку в нижней части экрана. Подсказка содержит коды кл...
    Л и т е р а т у р а
    Ленгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. М.: Мир, 1989. Трамбле Ж., Соренсон П. Введение в структуры данных. М.: Машиностроение, 1982. Дж. Уоркли. Архитектура...








Начало