Представление дерева в памяти.

 

Пусть существует дерево t, в состав которого входят узлы со значениями от 1 до n. Тогда наиболее простым способом представления дерева в памяти будет хранение его в виде двухмерной матрицы. Данное представление основано на свойстве дерева, что любой узел имеет только одного родителя. Тогда ячейка матрицы А будет содержать номер узла родителя для соответствующего узла j, при этом корневой узел будет иметь родителя со значением 0.

 

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

- индексом узла в массиве;

- значением узла;

- количеством исходов;

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

 

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

 

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

 

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

 

Операции с деревом:

1) обход дерева: обработка корневой вершины, обработка левой ветви (левого поддерева), обработка правой ветви (правого поддерева).

2) удаление поддерева: исключение из дельнейшего рассмотрения части дерева с указанным родителем

1) поиск родителя поддерева путем обхода дерева

2) разрыв связи с удаляемым поддеревом

3) декремент степени исхода

 

3) вставка поддерева: определение родителя, установка связи с новым поддеревом, инкремент степени исхода

 

Особенным использованием бинарного дерева является двоичное дерево поиска (упорядоченное), для которого выполняются следующие условия:

1) оба поддерева являются двоичными деревьями поиска

2) у всех узлов левого поддерева произвольного узла X значение, хранимое в вершине (ключ), меньше, чем значение ключа самого узла X

3) у произвольного узла X значения всех узлов правого поддерева должно быть не меньше значения ключа данного узла

 

Удаление узла должно заменяться операцией замены левого листа правого поддерева удаляемого элемента; лист поднимается вверх (удаляемый узел и самый левый лист правого поддерева меняются местами).

 

Куча.

Куча - специализированное бинарное дерево, удовлетворяющее следующему свойству:

 

- Если узел B является узлом-потомком узла A, то ключ A должен быть больше либо равен ключу B. Из этого следует, что элемент с наибольшим значением ключа всегда находится на вершине кучи и является корнем (max-куча), также существует min-куча.

- В куче глубина листьев должна отличаться не более, чем на единицу

- Последний слой всегда заполняется слева направо.

 

Представление кучи в памяти:

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

 

Первым элементом массива всегда является корневой, а дочерние элементы каждого узла хранятся в элементах массива с индексами 2i и 2i+1 соответственно.

 

Операции с кучей:

1) добавление элемента в кучу

a. добавление элемента X в конец массива B

b. восстановление свойства кучи

 

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

 

2) удаление узла из кучи

 

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

 

Тогда для обеспечения свойства кучи производят замену удаляемого узла и левого листа кучи, затем осуществляется проталкивание корня вниз до восстановления свойства кучи.

 

Нормализация (восстановление) кучи имеет формализованный алгоритм:

1) сравнить дочерние элементы у элемента с индексом I; если больший из дочерних больше i-го, то меняем i-ый дочерним, при этом изменяется значение I на индекс наибольшего из дочерних элементов.

2) повторять пункт 1, пока у i-го элемента есть дочерние, или наибольший из сыновей меньше или равен элементу с индексом i.

 

Создание консольного приложения с текстовым меню.

 

Для работы приложения может использоваться 2 режима: графический и текстовый. В текстовом режиме единицей ввода информации служит символ. Каждый символ занимает знакоместо. Знакоместо – прямоугольная область 8x16 пикселей (обычно).

Количество знакомест определяется размером и разрешением экрана.

 

Курсор помечает место на экране, куда по умолчанию будет осуществляться вывод очередного символа. Таким образом, курсор определяет текущую позицию экрана. Текущая позиция определяется координатами X и Y. Координата определяется по сетке координат, в которой верхнее левое знакоместо имеет координаты (-1, 1). Операции Write/Writeln работают с текстовым режимом и выводят информацию посимвольно с текущей позиции курсора. При выводе на экран существуют и исключения:

1) при выводе символа с кодом #7 символьная информация не выводится, а выполняется звуковой сигнал;

2) #8 – перемещение текущей позиции курсора на 1 позицию влево;

3) #10 – перемещение курсора на 1 позицию вниз;

4) #13 – перемещение позиции в начало текущей строки.

 

Для работы с символами в текстовом режиме используется модуль CRT, входящий в состав стандартной библиотеки Pascal.

Простейшее case-меню организуется путем ввода символа из предложенного выбора.

 

(пример case-меню)

 

Некоторые функции из модуля CRT:

ClrScr – очистка экрана

ClrEol – очистка текущей строки, начиная с текущей позиции

DelLine – удаление строки, в которой находится курсор

InsLine = ClrEol

Sound: звуковой сигнал (в Hz)

NoSound: выключить звуковые сигналы

 

Работа с цветом:

TextBackground(Color: Byte): цвет фона

TextColor(Color: Byte): цвет текста

TextAttr ret Byte: возвращает цвет текста

 

Для работы с цветами используются цветовые константы, изменяющие свои значения от 0 до 15.

Каждый бит в байте цвета может быть установлен или сброшен. От значения соответствующего бита зависит получаемый цвет. Установка либо снятие старшего бита цвета (7) отвечает за наличие мерцания. 0-3 биты – цвет символа; 4-6 биты – цвет фона; 3 бит – яркость. Цвет определяется в RGB-палитре (2-R, 1-G, 0-B).

 

Позиционирование позволяет установить курсор в требуемую точку экрана.

 

GotoXY(X, Y: Byte);

WhereX: Byte;

WhereY: Byte;

Delay: задержка

ReadKey: Char;: значение символьного типа

KeyPressed: Boolean: True, если нажата клавиша

 

 

Функция ReadKey.

 

В случае использования ReadKey введенный символ не отображается на экране, благодаря чему данная функция широко используется для создания интерактивных программ. ReadKey позволяет распознавать нажатие функциональных клавиш и их сочетания с управляющими клавишами Ctrl, Alt и Shift. Функция ReadKey исходит из того, что все множество клавиш и их сочетаний с управляющими клавишами разбито на 2 подмножества. Эти подмножества принято называть основным и расширенным набором соответственно.

 

В основной набор входят клавиши букв, цифр, разделителей, знаков препинания и их комбинаций с клавишей Shift. Если нажата одна из перечисленных клавиш, ReadKey вернет значение символа в соответствии с кодировкой ASCII.

 

В расширенный набор входят клавиши из основного набора в комбинациях с клавишами Ctrl и Alt, а также функциональные клавиши. Если нажата какая-нибудь клавиша расширенного набора, то функция ReadKey возвращает символ с кодом 0 (#0, Chr(0)). Повторное обращение к ReadKey возвращает код клавиши из расширенного набора (сначала происходит определение расширенного набора, затем – определение нажатой клавиши).

 

Большинство прикладных диалоговых программ используют данную технику взаимодействия с клавиатурой, однако существуют случаи, когда использование ReadKey недостаточно (например, ReadKey не позволит отловить ситуацию Alt + Escape и многие другие).

 

Функция KeyPressed не производит никаких действий с кодом нажатой клавиши; определяет лишь факт нажатия. Код нажатого символа можно получить с помощью функции ReadKey. Организация работы при использовании функций KeyPressed и ReadKey выглядит следующим образом:

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

- Если к моменту вызова ReadKey нажатие уже произошло, т.е. в буфере содержится информация о коде клавиши, то ожидания ввода не будет, а в качестве входной информации будет воспринята информация из буфера.

 

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

1) процедура 1

2) процедура 2

3) завершение работы программы

 

(пример case-меню)