Обработка динамических структур данных
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(государственный технический университет)
филиал “Восход”
Кафедра Б22-МиПОИС
Преподаватель Кулепётова Н.Н. _______«___»__________ 2012 г.
КУРСОВОЙ ПРОЕКТ
по дисциплине: «Архитектура ЭВМ, системное ПО»
Тема: «Обработка динамических структур данных »
«____»________ 2012 г.
Байконур 2012 г.
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(Государственный технический университет)
______________________________
Кафедра _____М и ПОИС_____________
____________________________
З А Д А Н И Е
на курсовой проект (работу) по курсу_________________________
студенту______________________
Тема проекта (работы)______________________
______________________________
Подпись студента______________________
Фамилия, имя, отчество, ученая степень, должность и подпись консультанта__________________
______________________________
Начало проектирования "____"________________________
Конец проектирования "____"________________________
ОТЗЫВ КОНСУЛЬТАНТА
Выполненный студентом_____________________
курсовой проект (работа) представлен в полном объеме и заслуживает оценки__________________
______________________________
"___"_____________________20__
ИСХОДНЫЕ ДАННЫЕ
______________________________
______________________________
______________________________
Аннотация
В курсовом проекте рассматриваются динамические структуры данных, а именно двоичные деревья, а также возможности текстового и графического режима среды ABC Pascal. Проект посвящен разработке алгоритмов и написанию программы, выполняющей обработку динамических структур данных, и программы, формирующей на экране монитора ПЭВМ заданный рисунок (схему).
Содержание
1 Постановка задачи………………………………………………………………
2 Структура разработки программы………………………………………………………
3 Динамические структуры данных …………………………………………………………..9
3.1 Двоичные деревья……………………………………………………………
3.1.1 Бинарные (двоичные) деревья……………………………………………………..9
3.1.2 Типовые операции над двоичными деревьями …………………………………11
3.2 Метод решения……………………………………………………………
3.3 Алгоритмизация задачи………………………………………………………………
3.3.1 Основной алгоритм…………………………………………………………
3.3.2 Создание корня двоичного дерева………………………………………………...20
3.3.3 Формирование двоичного дерева из текстового файла…..…….……………..…21
3.3.4 Запись двоичного дерева в файл…………………………………………………..21
3.4 Тестирование программы………………………………………………………
3.5 Анализ результатов…………………………………………………
4 Построение схемы в среде ABC Pascal …………………………………….……………….26
4.1 Графический режим…………………………………………………………………
4.1.1 Реализация схем в ABC Pascal…………………………………………………………27
4.2 Алгоритм построения заданного рисунка………………………………………………31
4.3 Анализ качества реализации схемы……………………………………………………..32
5 Инструкции по пользованию программой………………………………………………….
5.1 Руководство пользователя………………………………………………
5.2 Руководство программиста………………………………………………
5.3 Руководство по условиям эксплуатации программы…………………………………..36
Заключение ………………………………………………………………………………
Список литературы ………………………………………………………………….....
Приложение А. Текст программы …………………………………………………...........
Приложение Б. Результат работы программы ……………………………………………….46
Приложение В. Схемы основных алгоритмов динамических структур …………………...49
Приложение Г. Идентификаторы программы ……………………………………................
Приложение Д. Схема исходного рисунка ……………………………………................
1 Постановка задачи
Задание 1.
Разработать алгоритм и написать программу обработки динамических структур данных двоичных деревьев поиска.
Необходимо:
1.1. Показать достоинства и недостатки, формы представления и хранения в памяти ВМ указанной в задании динамической структуры данных.
1.2. Описать основные операции над элементами структуры и структурами данного вида в целом с графическими иллюстрациями применительно к обрабатываемой в курсовом проекте информации.
1.3. Выполнить алгоритмизацию решаемой задачи со ссылками на схемы разработанных алгоритмов.
1.4. Выполнить тестирование программы:
а) в нормальных условиях;
б) на «нулевых» примерах (отсутствие информации);
в) в экспериментальных условиях (т.е. для данных, на которых программа не рассчитана).
1.5. Выполнить анализ полученных результатов и дать рекомендации по области и условиям применения программы.
1.6. Разработать инструкции по пользованию программой, включающие:
а) руководство пользователя;
б) руководство программиста;
в) руководство по условиям эксплуатации программы.
Требования к программе:
а) программа должна иметь удобный интерфейс;
б) в программе должна быть предусмотрена возможность ввода данных из файла и с клавиатуры и вывода данных на экран либо их сохранения в файле.
в) программа должна быть самодокументируемой;
г) базовые операции над структурами реализовать с использованием процедур, функций или пользовательских модулей.
Необходимо:
Разработать программу реализующую игру «20 вопросов»:
Примечания: 1) реализация программы должна обеспечить представление данных в виде двоичного дерева.
2) программа должна хранить содержимое дерева решений в виде текстового файла;
Задание 2.
Создать программу, формирующую на экране монитора ПЭВМ рисунок, определенный заданием.
Необходимо:
2.1. Описать возможности текстового и графического режимов среды ABC Pascal для построения схем и рисунков.
2.2. Описать особенности реализации схем в ABC Pascal, а также функции и процедуры ABC Pascal, необходимые для построения исходного рисунка на экране монитора.
2.3. Разработать укрупненный алгоритм построения заданного рисунка (схемы).
2.4. Выполнить анализ качества реализации схемы.
2 Структура разработки программы
В соответствии с постановкой задачи программа должна включать в себя интерфейс (меню).
Программа, в общем случае, состоит из заставки, набора процедур, функций и глобального блока (функционирующего посредством меню). Обязательным в этом списке является только глобальный блок.
Заставка является визитной карточкой программы. Она выводится на экран сразу после старта программы и содержит информацию о названии программы, ее назначении, авторе и т.д.
Меню – это перечисление возможностей системы, из которых пользователь выбирает необходимую в данный момент. В программах для ПЭВМ оформлению меню с точки зрения структуры, дизайна и требований эргономики придается очень большое значение, так как именно через него реализуются функции управляющей программы в большинстве существующих систем.
Меню должно быть простым в работе и понятным даже для самого неподготовленного пользователя. Более или менее сложная система обычно имеет несколько меню. Каждый элемент главного меню может генерировать новое (вложенное) меню, являющееся второстепенным по отношению к главному. В свою очередь второстепенное меню может также активизировать подчиненное ему меню и т.д. Уровень вложения меню ограничивается только логической структурой решаемой задачи. Наиболее эффективны меню, которые жестко навязывают ответ, используя для управления несколько клавиш (например, клавиши → , ← , ↑ , ↓ , <Esc>, <Enter>) и автоматически игнорируя нажатие других.
Заставка, в общем случае, оформляется как автономная процедура, которая стартует первой в разделе операторов глобального блока, но возможны и другие варианты. Обычно применяется три сценария работы с заставкой (хотя и не исключены десятки других вариантов).
Сценарий 1:
1) Очистка экрана;
2) Вывод заставки на экран;
3) Удержание заставки на экране в течении фиксированного или неопределенно
долгого времени;
4) Очистка экрана;
5) Вывод главного меню;
6) Работа с режимами меню.
Сценарий 2:
1) Очистка экрана;
2) Одновременный вывод заставки и главного меню;
3) Работа с режимами меню;
4) Вывод заставки в любой момент, когда на экране находится главное меню.
Сценарий 3:
1) Очистка экрана;
2) Вывод меню;
3) Вывод заставки поверх меню;
4) Удержание заставки на экране в течение фиксированного или неопределенно
долгого времени;
5) Исчезновение заставки и восстановление полной картинки меню;
6) Работа с меню.
Первый сценарий используется значительно чаще, так как при реализации второго, часть экрана, занятая заставкой, не может применяться для других, возможно, более полезных целей. Кроме того, наличие лишней информации на экране отвлекает внимание пользователя. Третий сценарий практически ничем не отличается от первого, кроме исключения очистки экрана пред выводом меню и восстановления экрана после исчезновения заставки.
Простой запрос представляет собой наиболее несложный вид меню. Применяется как в простейших программах, так и в крупных программных системах (в частности, для выбора большого количества альтернатив). Он прост в организации и не вызывает ошибок эксплуатации даже у начинающих пользователей.
В качестве примера представим вариант главного меню:
ГЛАВНОЕ МЕНЮ
1 – Графика
2 – Динамические структуры
0 – Выход
Это меню инициирует в зависимости от выбранного режима все функциональные блоки системы. Режим 0 обеспечивает выход из программы. Такое меню однозначно и не требует дополнительной информации. Подсказка дана в самом запросе о выборе режима. Нужная программа активизируется в зависимости от значения цифры, которую введет пользователь. Меню легко реализуется на предварительно очищенном экране с помощью оператора Case.
3 Динамические структуры данных
Обработка динамических структур приобретает особое значение, когда простейшие методы использования памяти оказываются неприемлемыми. Эффективным инструментом реализации динамического распределения памяти в Паскале является совместное использование указателей и динамических структур данных, таких как: одно- и двунаправленные списки, очереди, стеки, деревья.
3.1. Деревья
Граф – это один из видов нелинейных структур данных, состоящий из конечного, непустого множества узлов и множества рёбер. Если все рёбра графа представлены в виде упорядоченных пар узлов или вершин, то граф называется ориентированным. Ориентированный граф без цикла называется ориентированным ациклическим графом.
Дерево – ориентированный ациклический граф, удовлетворяющий следующим условиям:
1) имеется в точности один узел, называемый корнем, в который не входит ни одно ребро;
2) в каждый узел, кроме корня, входит ровно одно ребро;
3) из корня к каждому узлу идет путь, который является единственным;
Дерево называется упорядоченным, если множество сыновей каждого узла упорядочено, то есть для каждой вершины множество потомков упорядочено по отношению друг к другу.
3.1.1. Бинарные (двоичные) деревья
Двоичным деревом называется такое упорядоченное дерево, что:
1) каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын;
2) каждый узел имеет не более одного левого сына и не более одного правого.
Двоичное дерево обычно представляется в виде двух массивов: левый сын и правый сын.
Обходы деревьев.
Большинство алгоритмов, использующие деревья «проходят» дерево, то есть посещают его узлы в некотором порядке.
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается точно один раз. Алгоритм перебора или посещения вершин называется алгоритмом обхода.
Произвольное бинарное дерево можно обходить:
1) прямым (нисходящим) обходом, то есть от корневого узла вниз к листьям;
2) кольцевым (восходящим) обходом, то есть от листьев вверх к корню.
3) обратным (смешанным) обходом, то есть от самого левого листа через корень к самому правому.
Способы обхода отличаются точкой входа в дерево, направлением движения по дереву и моментом обработки корневого узла относительно поддеревьев. При нисходящем обходе корневой узел обрабатывается до того, как обработаны оба его поддерева, причем в начале – левое, потом – правое. При восходящем обходе - после того, как обработаны левые и правые поддеревья. При смешанном обходе – после того, как обработано левое поддерево, но до того, как обработано правое поддерево.
Алгоритм 1: нисходящий обход двоичного дерева:
1) если дерево пусто, то закончить обход дерева;
2) иначе обработать (прочитать) корень;
3) обойти левое поддерево. Если пути влево нет, то движение продолжается по ближайшему пути (правому). При этом сразу после рассмотрения очередного узла просматриваются слева направо исходящие из них ветки;
4) обойти правое поддерево;
5) закончить обход дерева.
Алгоритм нисходящего обхода дерева двоичного поиска представлен ниже на рисунке 1, а).
Алгоритм 2: восходящий обход двоичного дерева:
1) если дерево пусто, то закончить обход дерева;
2) иначе обойти левое поддерево; чтение начинается с левого листа. Каждый узел читается после того, как прочитаны его левые и правые порожденные;
3) обойти правое поддерево;
4) обработать корень, закончить обход дерева.
Алгоритм восходящего обхода дерева двоичного поиска представлен ниже на рисунке 1, б).
Алгоритм 3: смешанный обход двоичного дерева:
1) если дерево пусто, то закончить обход дерева;
2) иначе обойти левое поддерево. Обработать корень, обойти правое дерево;
3) закончить обход дерева.
Алгоритм смешанного обхода дерева двоичного поиска представлен ниже на рисунке 1, в).
а)
3.1.2. Типовые операции над двоичными деревьями:
1) добавление элемента в дерево;
2) удаление элемента из дерева;
3) обход дерева (для печати элементов и т.д.);
4) поиск в дереве.
Поскольку определение двоичного дерева рекурсивно, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Отметим лишь, что использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении.
1. Добавление элемента в дерево
Для включения нового элемента в двоичное дерево поиска вначале нужно определить его точное положение — а именно внешний узел, который должен быть заменен путем отслеживания пути поиска элемента, начиная с корня. Кроме сохранения указателя n на текущий узел мы будем хранить указатель р на предка узла n. Таким образом, когда n достигнет некоторого внешнего узла, р будет указывать на узел, который должен стать предком нового узла. Для осуществления включения узла мы создадим новый узел, содержащий новый элемент, и затем свяжем предок р с этим новым узлом (рисунок 2).
Рисунок 2
2. Удаление элемента в дереве
Удаление элемента из двоичного дерева поиска гораздо сложнее, чем включение, поскольку может быть значительно изменена форма дерева. Удаление узла, у которого есть не более чем один непустой потомок, является сравнительно простой задачей — устанавливается ссылка от предка узла на потомок. Однако ситуация становится гораздо сложнее, если у подлежащего удалению узла есть два непустых потомка: предок узла может быть связан с одним из потомков, а что делать с другим? Решение может заключаться не в удалении узла из дерева, а скорее в замене элемента, содержащегося в нем, на последователя этого элемента, а затем в удалении узла, содержащего этот последователь.
Рисунок 3
Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рисунке 3:
1) узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n;
2) у узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n;
3) узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.
Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.
Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.
На рисунке 4 показана последовательность операций удаления, при которой возникают все три ситуации. Напомним, что симметричный обход каждого дерева в этой последовательности проходит все узлы в возрастающем порядке, проверяя, что в каждом случае это двоичные деревья поиска.
Компонентная функция remove является общедоступной компонентной функцией для удаления узла, содержащего заданный элемент. Она обращается к собственной компонентной функции _remove, которая выполняет фактическую работу:
Рисунок 4
3. Поиск в двоичном дереве
Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья. В каждом таком дереве естественно определяются левое и правое поддеревья. Двоичное дерево называется идеально сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1 (легко видеть, что при соблюдении этого условия длины пути до любой листовой вершины дерева отличаются не больше, чем на 1). Примеры идеально сбалансированных деревьев показаны на рисунке 5.
Рисунок 5
При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершины правого поддерева (рисунок 6).
Рисунок 6
Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 7).
Рисунок 7
Высота идеально сбалансированного двоичного дерева с n вершинами составляет не более, чем log n (логарифм двоичный), поэтому при применении таких деревьев в качестве деревьев поиска (рисунок 8) потребуется не более log n сравнений.
Рисунок 8
Применение деревьев как объектов с динамической структурой особенно полезно, если допускать выполнение не только операции поиска по значению ключа, но и операций включения новых и исключения существующих ключей. Если не принимать во внимание потенциальное желание поддерживать идеальную балансировку дерева, то процедуры включения и исключения ключей очень просты.
3.2. Метод решения
Игра «20 вопросов» это классическая программа из класса «интеллектуальных» построена для того чтобы отгадывать задуманные пользователем объекты. Эта программа использует двоичное дерево как главную структуру данных. Нелистьевые вершины такого дерева содержат предикаты (вопросы, ответы на которые могут принимать только «да» или «нет») Пользователь должен задумать простой объект и давать ответы на вопросы программы в соответствии со свойствами этого объекта. Пользователь получает вопросы, содержащиеся в вершинах дерева начиная с его корня. Ответ «да» пользователя соответствует пути, проходящему через левую дочь текущей вершины, а ответ «нет»— пути, проходящему через правую дочь текущей вершины. После каждого ответа выбирается соответствующая ветвь и процесс повторяется. Листьевые вершины содержат определение того объекта, которому соответствует последовательность ответов пользователя ведущих от корня дерева к каждому листу. Когда в процессе движения программа доходит до листа она выводит содержащееся там определение объекта «угадывая» тем самым объект задуманный пользователем. Если программа угадала верно, считается, что она выиграла. Если ответ не верен, программа начинает «обучаться», предлагая пользователю ввести вопрос (ответ «да» или «нет») на который зафиксирует различие между объектом, который задумал пользователь, и объектом, который вычислила программа. Вопрос сформулированный пользователем затем помещается в новую вершину дерева, дочерними вершинами которого становятся лист с определением «старого» объекта и лист с определением нового объекта. После этого пользователь может начать новый тур. Конец игры определяется программой по ответу пользователя на специальное приглашение к новому туру.
Рассмотрим пример работы такой программы.
Предположим, что начальное состояние дерева имеет следующий вид:
Имеет две ноги?
Лошадь
Работа программы начинается с вывода на экран предложения загадать объект. Так же выводит на экран сообщение о вариантах ответа и соответствующих им значений необходимых для ввода в программу. Затем программа начинает задавать вопросы, которые на экране монитора имеют следующий вид:
Загадайте животное.
да-1; нет-0;
Затем программа начинает задавать вопросы, которые на экране монитора имеют следующий вид:
ВОПРОС: Имеет две ноги?
Ответ:1;
Программа повторяет вывод вопросов (содержимого вершин дерева) начиная с его корня дерева и продвигаясь по его потомкам в соответствии с ответам пользователя. Как только программа достигнет некоторый лист, его содержимое интерпретируется как результат «угадывания» задуманного пользователем объекта. Этот результат выводится на экран в форме:
- Обработка дискретных сигналов
- Обработка застежки женских брюк-галифе с тесьмой-молнией
- Обработка звуковой информации
- Обработка и анализ маркетинговой информации
- Обработка и анализ результатов маркетинговых исследований
- Обработка и анализ экономических данных. Эконометрические модели
- Обработка изображений в среде Matlab
- Обработка деталей на сверлильных и расточных станках
- Обработка детали
- Обработка детали качалка
- Обработка детали машин
- Обработка детали проходным резцом
- Обработка динамических массивов структур данных
- Обработка динамических структур данных
