Обработка динамических структур данных

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(государственный технический университет)

филиал “Восход”

Кафедра Б22-МиПОИС

                                                                                “УТВЕРЖДАЮ”

Преподаватель Кулепётова Н.Н.             _______«___»__________ 2012 г.

КУРСОВОЙ ПРОЕКТ

по дисциплине: «Архитектура ЭВМ, системное ПО»

        Тема: «Обработка динамических структур данных »

                                                   Студентки гр. ДМ2-35_______Лёвиной М.Н

                                 «____»________ 2012 г.

                                Байконур 2012 г.

МОСКОВСКИЙ  АВИАЦИОННЫЙ  ИНСТИТУТ

(Государственный технический университет)

_________________________________________________________________________________

Кафедра _____М и ПОИС_____________

____________________________

З А Д А Н И Е

на курсовой проект (работу) по курсу____________________________________________________

студенту______________________________________группы________________________________

Тема проекта (работы)_________________________________________________________________

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Подпись студента_____________________________________________________________________

Фамилия, имя, отчество, ученая степень, должность и подпись консультанта__________________

____________________________________________________________________________________

Начало проектирования "____"______________________________________20__г.

Конец проектирования   "____"______________________________________20__г.

ОТЗЫВ КОНСУЛЬТАНТА

Выполненный студентом_______________________________________________________________

курсовой проект (работа) представлен в полном объеме и заслуживает оценки__________________

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

"___"_____________________20__г.               Подпись_______________________________________

ИСХОДНЫЕ ДАННЫЕ

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

_____________________________________________________________________________________

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Аннотация

В курсовом проекте рассматриваются динамические структуры данных, а именно двоичные деревья, а также возможности текстового и графического режима среды ABC Pascal. Проект посвящен разработке алгоритмов и написанию программы, выполняющей обработку динамических структур данных, и программы, формирующей на экране монитора ПЭВМ заданный рисунок (схему).

Содержание

1 Постановка задачи……………………………………………………………………………5

2 Структура разработки программы…………………………………………………………..7

3 Динамические структуры данных …………………………………………………………..9

3.1 Двоичные деревья………………………………………………………………………...9

3.1.1 Бинарные (двоичные) деревья……………………………………………………..9

3.1.2 Типовые операции над двоичными деревьями  …………………………………11

3.2 Метод решения…………………………………………………………………………...16

3.3 Алгоритмизация задачи………………………………………………………………….19

3.3.1 Основной алгоритм……………………………………………………………..….19

3.3.2 Создание корня двоичного дерева………………………………………………...20

3.3.3 Формирование двоичного дерева из текстового файла…..…….……………..…21

3.3.4 Запись двоичного дерева в файл…………………………………………………..21

3.4 Тестирование программы………………………………………………………………..22

3.5 Анализ результатов…………………………………………………………………….…25

4 Построение схемы в среде ABC Pascal …………………………………….……………….26

4.1 Графический режим………………………………………………………………………26

4.1.1 Реализация схем в ABC Pascal…………………………………………………………27

4.2 Алгоритм построения заданного рисунка………………………………………………31

4.3 Анализ качества реализации схемы……………………………………………………..32

5 Инструкции по пользованию программой………………………………………………….33

5.1 Руководство пользователя……………………………………………………………….33

5.2 Руководство программиста………………………………………………………………35

5.3 Руководство по условиям эксплуатации программы…………………………………..36

Заключение ……………………………………………………………………………………..37

Список литературы ………………………………………………………………….................38

Приложение А. Текст программы ………………………………………………….................39

Приложение Б. Результат работы программы ……………………………………………….46

Приложение В. Схемы основных алгоритмов динамических структур …………………...49

Приложение Г. Идентификаторы программы …………………………………….................57

Приложение Д. Схема исходного рисунка ……………………………………......................58

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 Динамические структуры данных

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