Курсовая работа

Задание для курсового проекта

1. Хранящуюся в файле базу данных, состоящую из 4000 записей (формат базы данных определяется вариантом) загрузить в оперативную память компьютера и построить дерево поиска заданного типа для решения задачи по поиску записей (задача определяется вариантом). Из найденных записей организовать список (очередь) и вывести их на экран.
2. Созданное приложение должно иметь дружественный интерфейс, выводить подсказки при вводе и выводе данных, проверять корректность вводимых данных и пр. Операции, выражающие логически завершенные действия, рекомендуется оформлять в виде функций, грамотно выбирая параметры функций. Имена переменных подпрограмм, параметры подпрограмм, используемые языковые конструкции должны способствовать удобочитаемости программы.
3. Протестировать созданное приложение, скриншоты приложения включить в отчет

Ваpианты баз данных (БД) и заданий:
Общие замечания:

1. Все текстовые поля следует pассматpивать как символьные массивы. Если длина поля пpевышает pазмеp хpанимой в нем инфоpмации , то оно дополняется пpобелами спpава. Каждое текстовое поле имеет свой фоpмат, котоpый опpеделяет смысл записанных в него данных. Пpи описании фоpмата в угловых скобках < и > указываются отдельные его элементы (сами угловые скобки в состав текста не входят); пpобелы обозначаются с помощью символа подчеpкивания. Если поле включает только один текстовый элемент, то фоpмат не указывается.
2. Целочисленные поля пpедставляются 16-pазpядными положительными числами.
3. При описании стpуктуpы записей в пpогpаммах необходимо точно соблюдать поpядок и pазмеp полей.

ПРИМЕЧАНИЕ. Предварительный просмотр содержимого баз данных возможен с помощью программы VIEWBASE.EXE

Таблица соответствия вариантов

Последние две цифры пароля А В D
1 1 1.2 1
2 2 2.1 2
3 3 3.3 1
4 4 4.2 2
5 1 1.1 1
6 2 2.2 2
7 3 3.2 1
8 4 4.1 2
9 1 1.3 1
10 2 2.3 1
11 3 3.4 2
12 4 4.3 1
13 1 1.3 2
14 2 2.3 2
15 3 3.1 1
16 4 4.4 2
17 1 1.4 1
18 2 2.4 1
19 3 3.1 2
20 4 4.2 1
21 1 1.2 2
22 2 2.4 2
23 3 3.4 1
24 4 4.1 1
25 1 1.1 2
=============================================

Лабораторная работа 1

Тема: Идеально сбалансированное дерево поиска (ИСДП) и случайное дерево поиска (СДП)
Цель работы: Изучение процесса программного построения ИСДП и СДП.

1. Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют:

• размер дерева;
• высоту дерева;
• среднюю высоту дерева;
• контрольную сумму данных в вершинах дерева;
• Проверить их работу на конкретном примере.

1. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
2. Разработать подпрограмму поиска вершины с заданным ключом в двоичном дереве поиска.
3. Разработать подпрограмму построения идеально сбалансированного дерева поиска (ИСДП) для массива случайных чисел, а также логическую функцию для определения является ли данное двоичное дерево деревом поиска. Построить ИСДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенных деревьев вычислить размер, контрольную сумму, высоту и среднюю высоту, используя разработанные функции. Заполнить таблицу (таблица 1) и проанализировать полученные результаты.
4. Разработать подпрограмму построения случайного дерева поиска (СДП). Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП.Заполнить таблицу (таблица 1) и проанализировать полученные результаты.

Таблица 1 - Результаты работы программ
Размер дерева СДП ИСДП
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Высота фактическая Теор. оценки для сред. высоты
100
200
300
400
500

Лабораторная работа 2

Тема: Сбалансированные по высоте деревья поиска (АВЛ)
Цель работы: Изучение процесса программного построения АВЛ-дерева.
Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.
Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 2 и проанализировать полученные результаты/
Таблица 2 - Результаты работы программы построения АВЛ-дерева для массива целых чисел
Размер дерева АВЛ-дерево ИСДП
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Высота фактическая Теор. оценки для сред. высоты
100
200
300
400
500

Лабораторная работа 3

Тема: Двоичное Б-дерево поиска (ДБД)
Цель работы: Изучение процесса программного построения ДБД.
Разработать подпрограмму построения ДБ-дерева для массива целых чисел.
Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 3 и проанализировать полученные результаты.

Таблица 3 - Результаты работы подпрограммы построения ДБ-дерева
Размер дерева АВЛ-дерево ДБД
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Кол-во уровней Теор. оценки для высоты ДБД Теор. оценки для сред. высоты двоичного дерева
100
200
300
400
500