Выполнение
Выбрать тип информационной структуры для решения задачи.
Разработать алгоритм решения задачи.
Выбрать форму представления информационной структуры и формат баз данных.
Разработать логическую схему программы.
Описать логическую схему на одном из языков программирования.
Осуществить отладку и тестирование программы.
Оформление отчета
В отчете должны быть представлены:
Название работы.
Постановку задачи.
Описание алгоритма (метода) решения.
Описание баз данных программы.
Текст программы с описанием.
Результаты работы программы на контрольных примерах.
Библиографический список
Кнут Д. Искусство программирования на ЭВМ. T.1. Основные алгоритмы.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 2. Компиляция.
Лабораторная работа № 2
Сортировка и поиск
Цель работы
Изучение основных подходов и алгоритмов организации сортировки и поиска в информационных структурах различных типов, а также приобретение навыков реализации рассматривавши алгоритмов на одном из языков программирования.
Задание по вариантам
– 17. Необходимо запрограммировать различные алгоритмы сортировки и поиска, оформив их в виде подпрограмм. Тип информационной структуры обозначен цифрами 1 и 2, которые обозначают линейный список с последовательным и связанным распределением соответственно. Бинарное дерево обозначено цифрой 3. Структура записей и содержимое ключей выбрать произвольным, но не совпадающим о вариантами №№ 18–25.
|
№ варианта |
Алгоритм |
Тип информационной структуры |
|
|
Сортировка подсчетом |
1 |
|
|
Сортировка подсчетом |
2 |
|
|
Сортировка простыми вставками |
1 |
|
|
Сортировка простыми вставками |
2 |
|
|
Сортировка с убывающим шагом — метод Шелла |
1 |
|
|
Сортировка методом пузырька |
1 |
|
|
Сортировка методом пузырька |
2 |
|
|
Обменная поразрядная сортировка |
1 |
|
|
Обменная поразрядная сортировка |
2 |
|
|
Сортировка посредством простого выбора |
1 |
|
|
Сортировка посредством простого выбора |
2 |
|
|
Последовательный поиск |
1 |
|
|
Последовательный поиск |
2 |
|
|
Быстрый последовательный поиск |
1 |
|
|
Быстрый последовательный поиск |
2 |
|
|
Бинарный поиск |
1 |
|
|
Поиск со вставкой по дереву |
3 |
Имеется некоторый массив данных. Разработать программу удаления одинаковых записей (дублей) с использованием сортировки подсчетом. (В результате должен получиться массив, в котором имеется только один экземпляр каждой записи).
В языке Паскаль имеются данные типа «множество». Элементы множества представляется в памяти при помощи линейного списка со связанным распределением. Разработайте программу нахождения объединения двух множеств с использованием сортировки.
Выполнить задание варианта № 19, если необходимо найти пересечение множеств.
Выполнить задание варианта № 19, если необходимо найти разность множеств.
Каждая запись Rj содержит 4 ключа Кj(1), Кj(2), Кj(3), Кj(4). Модифицировать алгоритм пузырьковой сортировки для записей такого типа и разработать соответствующую программу. В результате файл должен быть упорядочен по всем ключам, причем младшие (т.е. имеющие больший номер) ключи должны упорядочиваться только при одинаковых значениях старших ключей.
Имеется два массива (файла) записей, упорядоченных по возрастанию ключей. Разработать программу их объединения в один упорядоченный по возрастанию ключей файл.(Этот метод сортировки носит название сортировка слиянием).
Разработать программу подсчета числа различных записей в файле, используя какой-либо алгоритм сортировки.
Выполнить задание варианта № 18, используя алгоритм сортировки с убывающим шагом — метод Шелла.