Курсовая и Лабораторные работы 1-3 по дисциплине: Структуры и алгоритмы обработки данных (часть 2). Вариант №15

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

ЗАДАНИЕ

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

Таблица 1 - Результаты работы программ

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

------------------------------------------------------------------------------

\Описание программы
\Результаты
\Анализ результатов

=============================================

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

ЗАДАНИЕ

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

------------------------------------------------------------------------------

\Описание программы
\Результаты
\Анализ результатов

=============================================

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

ЗАДАНИЕ

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

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

------------------------------------------------------------------------------

\Описание программы
\Результаты
\Анализ результатов

=============================================
=============================================

Курсовая работа
Вариант No15

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

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

Примечание. Предварительный просмотр содержимого баз данных возможен с помощью программы VIEWBASE.EXE

Вариант 15
Номер шифра А В D
15 3 3.1 1


Описание баз данных Задания
А = 3 (файл base3.dat)
База данных "Обманутые вкладчики"

Структура записи:
• ФИО вкладчика: текстовое поле 32 символа
формат <Фамилия>_<Имя>_<Отчество>
• Сумма вклада: целое число
• Дата вклада: текстовое поле 8 символов
формат дд-мм-гг
• ФИО адвоката: текстовое поле 22 символа
формат <Фамилия>_<буква>_<буква>

Пример записи из БД:
Петров_Иван_Федорович___________
130
15-03-46
Иванова_И_В___________
 B=3.1
Вывести на экран количество и фамилии всех адвокатов из базы данных.
Вывести в алфавитном порядке (по полю ФИО вкладчика) список вкладчиков, которые имеют адвоката с заданной фамилией и вклад больше заданной суммы.
Фамилию адвоката и сумму вводить с клавиатуры.

D = 1 - тип дерева поиска: АВЛ-дерево.

------------------------------------------------------------------------------

Содержание
1 Задание на курсовую работу 
2 Описание структур данных и алгоритмов 
3 Функции программы 
4 Текст программы 
5 Результаты выполнения программы 
Список использованной литературы 

=============================================

Проверил(а): Мачикина Елена Павловна
Оценка: Отлично
Дата оценки: 25.12.2022г.

Помогу с вашим вариантом, другой дисциплиной, онлайн-тестом, либо сессией под ключ.
E-mail: sneroy20@gmail.com
E-mail: ego178@mail.ru