570_Kurapova_E._V._Struktury_i_Algoritmy
.pdfФедеральное агентство связи Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО «СибГУТИ»)
Е. В. Курапова Е. П. Мачикина
СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ
Лабораторный практикум
Новосибирск
2015
УДК 681.3.06
Курапова Е. В., Мачикина Е. П. Структуры и алгоритмы обработки данных: Лабораторный практикум. – Новосибирск: Изд-во СибГУТИ, 2015. – 23 с.
Лабораторный практикум предназначен для студентов, обучающихся по направлению 09.03.01 «Информатика и вычислительная техника», профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем», и изучающих дисциплину «Структуры и алгоритмы обработки данных». Лабораторный практикум содержит описания лабораторных работ по всем разделам курса.
Рисунков – 1, таблиц – 18. Список лит. – 8 назв.
Кафедра прикладной математики и кибернетики
Рецензент: д-р техн. наук С. Н. Мамойленко
Утверждено редакционно-издательским советом СибГУТИ в качестве лабораторного практикума.
Сибирский государственный университет телекоммуникаций и информатики, 2015
2
ОГЛАВЛЕНИЕ |
|
ПРАВИЛА ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ |
..................................4 |
МЕТОДЫ СОРТИРОВКИ И ПОИСКА ДАННЫХ............................................. |
6 |
ЛАБОРАТОРНАЯ РАБОТА 1.................................................................................... |
6 |
ЛАБОРАТОРНАЯ РАБОТА 2.................................................................................... |
6 |
ЛАБОРАТОРНАЯ РАБОТА 3.................................................................................... |
7 |
ЛАБОРАТОРНАЯ РАБОТА 4.................................................................................... |
8 |
ЛАБОРАТОРНАЯ РАБОТА 5.................................................................................... |
9 |
ЛАБОРАТОРНАЯ РАБОТА 6.................................................................................. |
10 |
ЛАБОРАТОРНАЯ РАБОТА 7.................................................................................. |
10 |
ЛАБОРАТОРНАЯ РАБОТА 8.................................................................................. |
11 |
ЛАБОРАТОРНАЯ РАБОТА 9.................................................................................. |
12 |
ЛАБОРАТОРНАЯ РАБОТА 10................................................................................ |
13 |
ДЕРЕВЬЯ ПОИСКА............................................................................................... |
14 |
ЛАБОРАТОРНАЯ РАБОТА 1.................................................................................. |
14 |
ЛАБОРАТОРНАЯ РАБОТА 2.................................................................................. |
15 |
ЛАБОРАТОРНАЯ РАБОТА 3.................................................................................. |
16 |
ЛАБОРАТОРНАЯ РАБОТА 4.................................................................................. |
16 |
ЛАБОРАТОРНАЯ РАБОТА 5.................................................................................. |
17 |
ЛАБОРАТОРНАЯ РАБОТА 6.................................................................................. |
18 |
ЛАБОРАТОРНАЯ РАБОТА 7.................................................................................. |
18 |
ЛАБОРАТОРНАЯ РАБОТА 8.................................................................................. |
19 |
ЛАБОРАТОРНАЯ РАБОТА 9.................................................................................. |
20 |
ЛАБОРАТОРНАЯ РАБОТА 10................................................................................ |
21 |
СПИСОК РЕКОМЕНДОВАННОЙ ЛИТЕРАТУРЫ......................................... |
22 |
3
ПРАВИЛА ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ
Перед выполнением заданий лабораторной работы рекомендуется изучить теоретический материал по теме лабораторной работы и описание методов обработки данных на псевдокоде, используя конспекты лекционных занятий и литературу из списка.
Задания лабораторных работ выполняются на языке программирования С/С++, среда программирования по выбору студента.
Изучаемые методы обработки данных рекомендуется программно реализовывать в виде отдельных функций (подпрограмм), массивы (последовательности) данных должны передаваться в подпрограммы в качестве параметров. Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо также оформлять в виде отдельных подпрограмм.
Задания лабораторных работ, отмеченные звездочкой, не являются обязательными для выполнения.
При выполнении заданий следует обеспечить вывод на экран данных на всех шагах алгоритма. Программа должна иметь дружественный, интуитивно понятный интерфейс (меню пользователя, вывод подсказок, комментарии при вводе/выводе данных и т.д.).
Предварительно необходимо разработать следующие подпрограммы для массива целых чисел (массив и количество элементов должны передаваться в качестве параметров), которые будут использованы в лабораторных работах и выполняют:
заполнение массива возрастающими числами;
заполнение массива убывающими числами;
заполнение массива случайными числами;
вычисление контрольной суммы элементов массива;
определение количества серий в массиве;
вывод на экран элементов массива.
Контрольную сумму следует вычислять как сумму всех элементов массива. Серией называется неубывающая последовательность элементов массива максимальной длины. Аналогичные подпрограммы необходимо разработать и для списка целых чисел.
В программе в ходе выполнения алгоритма необходимо предусмотреть подсчет фактического количества сравнений С и количества пересылок М и вывести их экран.
Тестирование разработанной программы необходимо проводить для различных типов входных данных (случайный массив, упорядоченный массив в прямом и обратном порядке). В программе следует проверять правильность сортировки путем подсчета контрольной суммы и числа серий в массиве (или списке) до и после сортировки.
4
После тестирования необходимо проанализировать полученные результаты, т.е. проверить соответствие полученных экспериментальным путем величин М и С теоретическим оценкам трудоемкости реализованных методов.
Построение графиков можно реализовать программным путем с использованием графических библиотек или воспользоваться графопостроителями современных программных средств.
5
МЕТОДЫ СОРТИРОВКИ И ПОИСКА ДАННЫХ
ЛАБОРАТОРНАЯ РАБОТА 1
Тема: Метод прямого выбора
Цель работы: Изучение методов квадратичной сортировки массивов.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную сортировку методом прямого выбора. При тестировании программы можно использовать данный пример для проверки правильности реализации алгоритма.
2.Разработать подпрограмму сортировки массива методом прямого выбора. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. Предусмотреть подсчет фактического
количества пересылок и сравнений (М и С) и сравнить их |
с |
теоретическими оценками для различных типов массивов. |
|
3.Экспериментально определить среднюю длину серии в случайном массиве.*
4.Придумать способ устранения фиктивных перестановок и оценить его влияние на фактические значения М и С для метода прямого выбора.*
5.Исследовать метод прямого выбора на массивах убывающих, возрастающих и случайных чисел и сделать вывод о зависимости (или независимости) метода от исходной упорядоченности массива.*
ЛАБОРАТОРНАЯ РАБОТА 2
Тема: Метод пузырьковой сортировки и шейкерная сортировка
Цель работы: Изучение методов квадратичной сортировки массивов.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную сортировку методом пузырьковой сортировки и шейкерную сортировку. При тестировании программы можно использовать данные примеры для проверки правильности реализации алгоритмов.
2.Разработать подпрограммы для пузырьковой и шейкерной сортировок массива целых чисел по возрастанию.
3.Предусмотреть подсчет фактического количества пересылок и сравнений (Мф и Сф), сравнить с теоретическими оценками М и С.
6
4. Сравнить время работы пузырьковой и шейкерной сортировок на массивах убывающих, возрастающих и случайных чисел (по сумме М+С). Составить таблицу вида:
Таблица 1
Размер |
|
Мф+Сф пузыр. |
|
Мф+Сф шейкер. |
||||
массива |
Убыв. |
|
Случ. |
Возр. |
Убыв. |
|
Случ. |
Возр. |
100 |
|
|
|
|
|
|
|
|
200 |
|
|
|
|
|
|
|
|
300 |
|
|
|
|
|
|
|
|
400 |
|
|
|
|
|
|
|
|
500 |
|
|
|
|
|
|
|
|
5.Построить на экране в одной координатной плоскости графики зависимости Мф+Сф от длины массива для пузырьковой и шейкерной сортировок (для массива случайных чисел). Сравнить полученные графики зависимостей с графиком квадратичной функции. *
ЛАБОРАТОРНАЯ РАБОТА 3
Тема: Метод прямого включения и метод Шелла
Цель работы: Изучение методов квадратичной сортировки массивов.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную сортировку методом прямого включения и методом Шелла. При тестировании программы можно использовать данные примеры для проверки правильности реализации алгоритмов.
2.Реализовать программно сортировку массива целых чисел методом прямого включения. Сравнить время работы методов квадратичной трудоемкости. Построить таблицу и проанализировать полученные результаты (использовать результаты предыдущих лабораторных работ).
Таблица 2
Длина |
Мф+Сф |
Мф+Сф |
Мф+Сф |
Мф+Сф |
массива |
Метод прямого |
Метод пузырьковой |
Метод шейкерной |
Метод прямого |
|
выбора |
сортировки |
сортировки |
включения |
100 |
|
|
|
|
200 |
|
|
|
|
300 |
|
|
|
|
400 |
|
|
|
|
500 |
|
|
|
|
3.Разработать подпрограмму сортировки массива целых чисел методом Шелла.
7
4.Исследовать трудоемкость метода Шелла для n=10, 100, …, 500, n – количество элементов в массиве. Определить последовательность шагов для предварительных сортировок по формуле Кнута. Построить таблицу и проанализировать полученные результаты:
Таблица 3
Длина |
Количество |
шагов |
Последовательность |
Мф+Сф |
массива |
по формуле Кнута |
шагов по формуле Кнута |
Метод Шелла |
|
|
|
|
|
|
5.Построить на экране в одной координатной плоскости графики зависимости трудоемкости (Мф+Сф) от длины массива для всех методов квадратичной трудоемкости (для массива случайных чисел). Сравнить полученные графики зависимостей с графиком квадратичной функции. *
6.Исследовать метод Шелла на зависимость трудоемкости от выбора последовательности шагов. Подтвердить рекомендацию Кнута или предложить лучший вариант выбора последовательности шагов.*
ЛАБОРАТОРНАЯ РАБОТА 4
Тема: Двоичный поиск
Цель работы: Изучение метода быстрого поиска в массиве.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную быстрый поиск (двумя версиями) первой буквы имени и буквы «Я». При тестировании программы можно использовать данные примеры для проверки правильности реализации алгоритмов.
2.Разработать подпрограммы для двоичного поиска заданного элемента в массиве (две версии), ключ поиска передается в подпрограмму в качестве параметра.
3.Сравнить трудоемкости (фактическое количество сравнений Сф) двух версий двоичного поиска в упорядоченном массиве. Построить таблицу и проанализировать полученные результаты:
Таблица 4
Длина массива |
Сф I версия |
Сф II версия |
100 |
|
|
200 |
|
|
… |
|
|
500 |
|
|
… |
|
|
1000 |
|
|
8
4.Реализовать программно поиск в массиве всех элементов с заданным ключом (две версии), ключ поиска передается в подпрограмму в качестве параметра.
5.Построить графики зависимости Сф от длины массива для двух версий поиска всех элементов с заданным ключом и сравнить построенные графики с графиком логарифмической функции.*
ЛАБОРАТОРНАЯ РАБОТА 5
Тема: Хеширование
Цель работы: Изучение возможностей хеширования данных для организации поиска.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить хеширование вручную методом прямого связывания (размер хеш-таблицы равен 5) и методом открытой адресации (линейные и квадратичные пробы, размер хеш-таблицы равен 11). При тестировании программы можно использовать данные примеры для проверки правильности реализации алгоритмов.
2.Разработать подпрограмму хеширования массива целых чисел методом прямого связывания и подпрограмму поиска в хеш-таблице элемента по заданному ключу. Вывести на экран построенную хеш-таблицу.
3.Реализовать подпрограмму хеширования массива целых чисел методом открытой адресации. Для разрешения коллизий использовать линейные и квадратичные пробы. Вывести на экран заполненные хеш-таблицы для
m=11 в виде:
Таблица 5. Содержимое хеш-таблицы
Номер ячейки |
0 |
1 |
2 |
3 |
… |
|
|
… |
m-1 |
|
|
|
|
|
|
|
|
|
|
Число |
|
|
|
|
|
|
|
|
|
4. Подсчитать и сравнить количество коллизий при линейных и квадратичных пробах. Построить таблицу и проанализировать полученные результаты.
Таблица 6
Размер |
Количество |
Количество коллизий |
|
хеш- |
исходных |
|
|
таблицы |
чисел |
Линейные пробы |
Квадратичные пробы |
|
|
|
|
13 |
15 |
|
|
29 |
30 |
|
|
43 |
45 |
|
|
67 |
70 |
|
|
83 |
85 |
|
|
9
5.Организовать поиск элемента с заданным ключом для метода открытой адресации (линейные и квадратичные пробы). *
ЛАБОРАТОРНАЯ РАБОТА 6
Тема: Метод пирамидальной сортировки
Цель работы: Изучение методов быстрой сортировки массивов.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную сортировку методом пирамидальной сортировки. При тестировании программы можно использовать данный пример для проверки правильности реализации алгоритма.
2.Разработать подпрограмму пирамидальной сортировки массива целых чисел.
3.Проверить работу метода на массивах убывающих, возрастающих и случайных чисел и сделать вывод о зависимости или независимости метода от исходной упорядоченности массива. Построить таблицу и проанализировать полученные результаты.
Таблица 7
Длина |
(Мф+Сф ) метод пирамидальной сортировки |
||
массива |
Возрастающие |
Убывающие |
Случайные числа |
|
числа |
числа |
|
|
|
||
100 |
|
|
|
200 |
|
|
|
300 |
|
|
|
400 |
|
|
|
500 |
|
|
|
4.Построить на экране в одной координатной плоскости графики зависимости трудоемкости (Мф+Сф) от n (n – длина массива) для метода Шелла и пирамидальной сортировки (для массива случайных чисел) и сравнить построенные графики с графиком функции nlogn. *
ЛАБОРАТОРНАЯ РАБОТА 7
Тема: Метод Хоара
Цель работы: Изучение методов быстрой сортировки массивов.
1.Для набора из 12 первых последовательных символов ФИО студента выполнить вручную сортировку методом Хоара. При тестировании программы можно использовать данный пример для проверки правильности реализации алгоритма.
10