Лабораторная работа № 1. "Линейные коллекции данных". 2
Задание. 2
Варианты задания: 3
Методические указания по выполнению задания. 3
Лабораторная работа № 2. «Коллекция данных - сбалансированное дерево поиска». 4
Задание. 4
Варианты задания. 5
Методические указания к лабораторной работе. 5
Лабораторная работа № 3. «Коллекция данных - хеш – таблица». 7
Задание. 7
Варианты задания. 8
Методические указания к лабораторной работе: 9
Лабораторная работа № 4 «Внешняя структура поиска». 11
Задание. 11
Варианты задания. 11
Методические указания к лабораторной работе. 12
Литература. 13
Методические указания для выполнения лабораторных работ
по дисциплине “ Структуры и алгоритмы обработки данных ”
для студентов, обучающихся по специальности 220100
Лабораторная работа № 1. "Линейные коллекции данных".
Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список». Освоение методики тестирования трудоёмкости реализации коллекций.
Задание
1. Спроектировать, реализовать и провести тестовые испытания АТД «Список» для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.
Интерфейс АТД "Список" включает следующие операции:
· опрос размера списка,
· очистка списка,
· проверка списка на пустоту,
· опрос наличия элемента с заданным значением,
· доступ к значению элемента с заданным номером в списке,
· получение позиции в списке элемента с заданным значением,
· включение нового элемента в позицию с заданным номером,
· удаление элемента из позиции с заданным номером,
· итератор для доступа к элементам списка с операциями:
- установка на начало списка,
- проверка конца списка,
- доступ к значению текущего элемента,
- переход к следующему элементу списка,
- переход к предыдущему элементу списка (для списков на базе массива или двусвязных структур),
Для тестирования эффективности операций интерфейс АТД "Список" включает дополнительную операцию
· опрос числа элементов списка, просмотренных операцией.
2. Выполнить отладку и тестирование всех операций АТД "Список" с помощью меню операций.
3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.
4. Провести анализ экспериментальных показателей трудоёмкости операций.
5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:
1) титульный лист,
2) цель лабораторной работы,
3) общее задание (пункты 1 – 5) и вариант задания,
4) формат АТД,
5) определение шаблонного класса для коллекции «Список», предназначенное для клиентской программы,
6) описание методики тестирования трудоёмкости операций,
7) таблицы и графики с полученными оценками трудоёмкости операций для среднего случая функционирования АТД. Должны быть приведены графики среднего числа просмотренных элементов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),
8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,
9) выводы,
10) список использованной литературы,
11) приложение с текстами программ:
- полное определение класса и текстов методов класса,
- текст программы тестирования трудоёмкости операций.
Варианты задания:
1. Структура данных – массив заданного размера.
2. Структура данных - надёжный массив.
3. Структура данных – односвязная, на базе массива с индексными указателями.
4. Структура данных – двусвязная, на базе массива с индексными указателями.
5. Структура данных - двусвязная, на базе адресных указателей.
6. Структура данных - кольцевая, односвязная, на базе адресных указателей.
7. Структура данных – кольцевая, двусвязная, на базе адресных указателей.
8. Структура данных - кольцевая, односвязная, на базе адресных указателей, с использованием фиктивного элемента.
Методические указания по выполнению задания
1. Для АТД «Список» разрабатываются формат АТД и шаблонный класс – контейнер.
2. Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
3. Тестирование операций через меню выполняется для списка небольшого размера (до 20 элементов). Тип данных и для некоторых вариантов размер списка задаются с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое списка с помощью итератора.
4. Перед тестированием трудоёмкости операций задаются тип и размер списка. Размер списка варьируется в пределах от 10 до элементов. После тестирования на экран выводятся размер списка и средняя трудоёмкость операций поиска, вставки и удаления (среднее число просмотренных элементов списка).
Лабораторная работа № 2. «Коллекция данных - сбалансированное дерево поиска».
Цели работы: Изучение и исследование методов балансировки двоичных деревьев поиска на примере АТД «Сбалансированное двоичное дерево поиска». Освоение методики модификации коллекций с помощью механизма наследования классов.
Задание
1. Спроектировать, реализовать и провести тестовые испытания АТД «Сбалансированное двоичное дерево поиска» для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.
Интерфейс АТД «Сбалансированное двоичное дерево поиска» включает следующие операции:
· опрос размера дерева,
· очистка дерева,
· проверка дерева на пустоту,
· доступ к значению элемента с заданным ключом,
· включение нового элемента с заданным ключом,
· удаление элемента с заданным ключом,
· итератор для доступа к элементам дерева с операциями:
- установка на корень дерева,
- проверка конца дерева,
- доступ к данным текущего элемента дерева
- переход к следующему по значению ключа элементу дерева,
- переход к предыдущему по значению ключа элементу дерева,
Для тестирования коллекции интерфейс АТД «Сбалансированное двоичное дерево поиска» включает дополнительные операции
· вывод структуры дерева на экран,
· опрос числа просмотренных операцией узлов дерева.
2. Выполнить отладку и тестирование всех операций АТД «Сбалансированное двоичное дерево поиска» с помощью меню операций.
3. Выполнить сравнительное тестирование средней трудоёмкости операций для коллекций «BST – дерево» и «Сбалансированное двоичное дерево поиска» для среднего и худшего случаев.
4. Провести сравнительный анализ экспериментальных показателей трудоёмкости операций.
5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:
1) титульный лист,
2) цель лабораторной работы,
3) общее задание (пункты 1 – 5) и вариант задания,
4) формат АТД,
5) определение шаблонного класса для коллекции «Сбалансированное двоичное дерево поиска», предназначенное для клиентской программы,
6) описание методики тестирования трудоёмкости операций,
7) таблицы и графики с полученными оценками трудоёмкости операций для худшего и среднего случаев функционирования АТД. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления (графики обоих коллекций совмещены в одной системе координат),
8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,
9) выводы,
10) список использованной литературы,
11) приложение с текстами программ:
- полное определение класса и текстов методов класса,
- текст программы тестирования трудоёмкости операций АТД.
Варианты задания
1. АТД «АВЛ – дерево», как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.
2. АТД «АВЛ – дерево», как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в нерекурсивной форме.
3. АТД " RB - дерево", как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.
4. , АТД " RB - дерево", как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в нерекурсивной форме.
5. АТД "Рекурсивное 2-3 дерево". Алгоритмы операций АТД реализуются в рекурсивной форме.
6. АТД "Нерекурсивное 2-3 дерево". Алгоритмы операций АТД реализуются в нерекурсивной форме.
7. АТД " Рандомизированное дерево", как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.
8. АТД "Рандомизированное дерево", как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в нерекурсивной форме.
Методические указания к лабораторной работе
1. Для АТД «Сбалансированное двоичное дерево поиска» разрабатываются формат АТД и шаблонный класс – контейнер.
2. Коллекции «Сбалансированное двоичное дерево поиска», использующие рандомизированне дерево, AVL – дерево или RB – дерево, разрабатываются как модификация класса «BST – дерево» с использованием технологии наследования классов. Коллекция на базе 2-3 – дерева разрабатывается, как самостоятельный класс.
3. Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
4. Тестирование операций через меню выполняется для небольшого размера дерева (до 20 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое дерева с помощью операции вывода структуры дерева. При выводе узла дерева необходимо отражать хранящийся в нём ключ поиска и дополнительный параметр, используемый для балансировки узла.
5. Перед тестированием эффективности операций для обеих коллекций задаются тип данных, и размер. Размер деревьев варьируется в пределах от 10 до элементов. После тестирования на экран выводятся размер деревьев и средняя трудоёмкость операций поиска, вставки и удаления (среднее число пройденных узлов дерева).
Лабораторная работа № 3. «Коллекция данных - хеш – таблица»
Цели работы: Изучение методов построения таблиц с постоянным временем доступа к элементам. Освоение технологии реализации таблиц на примере АТД «Хеш – таблица».
Задание
1. Спроектировать, реализовать и провести тестовые испытания АТД «Хеш-таблица» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой. Коллекция проектируется в двух вариантах:
· АТД «Хеш-таблица с цепочками коллизий»,
· АТД «Хеш-таблица с открытой адресацией»,
Интерфейс АТД «Хеш-таблица» включает следующие операции:
· опрос размера таблицы,
· опрос пустоты таблицы,
· очистка таблицы,
· поиск элемента по ключу,
· вставка элемента по ключу,
· удаление элемента по ключу.
· итератор для доступа к элементам таблицы с операциями:
- установка на начало таблицы,
- проверка конца таблицы,
- доступ к данным текущего элемента таблицы,
- переход к следующему элементу таблицы,
Для тестирования коллекций интерфейс АТД «Хеш-таблица» включает дополнительные операции:
· вывод структуры хеш-таблицы на экран,
· опрос числа проб, выполненных операцией.
2. Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.
3. Получить экспериментальную оценку качества хеш-функции c2, усреднённую по нескольким экспериментам.
4. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий», и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.
5. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.
6. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:
1) титульный лист,
2) цель лабораторной работы,
3) общее задание (пункты 1 – 5) и вариант задания,
4) формат АТД,
5) определение шаблонного класса для коллекции «Хеш-таблица», предназначенное для клиентской программы,
6) описание методики получения экспериментальной оценки c2 и полученная оценка c2, усреднённая по нескольким экспериментам.
7) описание методики тестирования трудоёмкости операций,
8) таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» (графики обеих коллекций совмещены в одной системе координат),
9) сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,
10) выводы,
11) список использованной литературы,
12) приложение с текстами программ:
- полное определение классов и текстов методов класса,
- текст программы получения оценки c2,
- текст программы тестирования трудоёмкости операций АТД.
Варианты задания
1.
Тип ключа - строка текста произвольной длины.
Преобразование строки - конкатенация битовых образов символов.
Метод хеширования - модульный.
Метод разрешения коллизий - линейный.
2.
Тип ключа - вещественное число на интервале [, +10 000.00].
Метод хеширования - мультипликативный.
Метод разрешения коллизий - квадратичный.
3.
Тип ключа - целое число на интервале [0 , +1 ].
Метод хеширования – выбор цифр.
Метод разрешения коллизий - двойное хеширование.
4.
Тип ключа - строка текста произвольной длины.
Метод хеширования - модульный.
Метод разрешения коллизий - линейное хеширование.
5.
Тип ключа - вещественное число на интервале [, +].
Метод хеширования - модульный.
Метод разрешения коллизий - двойное хеширование.
6.
Тип ключа - строка текста произвольной длины.
Преобразование строки - конкатенация битовых образов символов.
Метод хеширования - мультипликативный.
Метод разрешения коллизий - квадратичный.
7.
Тип ключа - вещественное число на интервале [-5 000.000 , ].
Метод хеширования - свёртка.
Метод разрешения коллизий - квадратичный.
8.
Тип ключа – 12-значное натуральное число.
Метод хеширования - свёртка, комбинированная с выбором цифр.
Метод разрешения коллизий - квадратичный.
Методические указания к лабораторной работе:
1. Коллекции «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» разрабатываются, как отдельные шаблонные классы-контейнеры.
2. Параметрами шаблона являются тип ключа, тип данных и класс-функция преобразования значения ключа в натуральное число.
Размер хеш-таблицы вычисляется конструктором коллекции в зависимости от заданного количества элементов с учётом типа хеш-таблицы, метода хеширования, указанного в варианте задания, и рекомендуемой величины α. Рекомендуемые размеры хеш-таблицы (числа Мерсенне) для модульного хеширования:
2n | d | 2n -d |
8 | 5 | 251 |
9 | 3 | 509 |
10 | 3 | 1 021 |
11 | 9 | 2 039 |
12 | 3 | 4 093 |
13 | 1 | 8 191 |
14 | 3 | 16 381 |
15 | 19 | 32 749 |
16 | 15 | 65 521 |
17 | 1 | |
18 | 5 | |
19 | 1 | |
20 | 3 | 1 |
21 | 9 | 2 |
22 | 3 | 4 |
23 | 15 | 8 |
24 | 3 | 16 |
25 | 39 | 33 |
3. Для тестирования разработанного класса – контейнера разрабатываются две программы - программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
4. Тестирование операций через меню выполняется для небольшого размера таблицы (до 7-8 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операции необходимо выводить на экран содержимое структуры хеш-таблицы с помощью операции вывода её структуры. При выводе структуры следует отражать состояние, как свободных, так и занятых позиций хеш-таблицы, содержимое цепочек коллизий.
5. В результате тестовых испытаний хеш - функции получить функцию распределения ключей по пространству
c2 = m/P 
(fi –P/m)2
, где P – количество ключей, использованных для получения распределения, m - размер хеш - таблицы, fi - количество ключей с хеш-значением, равным i [8].
Если использованные ключи являются случайными на всём пространстве значений ключей U, значение функции c2 должно быть равно m ± 
с вероятностью 1 - 1/c, где c=U/m.
6. Для получения оценки c2 использовать количество ключей, минимум в 20 раз превышающее размер хеш-таблицы.
7. Перед тестированием эффективности операций для обеих коллекций задаются тип данных и количество элементов в таблице. В качестве исходных данных для тестирования задаётся коэффициент заполнения α. Для коллекции «Хеш-таблица с цепочками коллизий» изменение α задаётся неравенством 0,1 
α10. Для коллекции «Хеш-таблица с открытой адресацией» изменение α задаётся неравенством 0,1 α1. После тестирования на экран выводится коэффициент заполнения и полученные оценки трудоёмкости для операций поиска, вставки и удаления элементов.
Лабораторная работа № 4 «Внешняя структура поиска»
Цель работы: изучение особенностей организации и алгоритмов управления доступом к данным во внешних структурах поиска.
Задание
1. Спроектировать, реализовать и провести тестовые испытания АТД «Внешняя структура поиска» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.
Интерфейс АТД включает следующие операции:
· опрос размера,
· опрос пустоты,
· очистка структуры,
· поиск элемента по ключу,
· вставка элемента по ключу,
· удаление элемента по ключу.
Для тестирования коллекции интерфейс АТД включает дополнительные операции:
· вывод структуры на экран,
2. Выполнить отладку и тестирование всех операций АТД с помощью меню операций.
3. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления.
4. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.
5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:
6) титульный лист,
7) цель лабораторной работы,
8) общее задание (пункты 1 – 4) и вариант задания,
9) формат АТД,
10) описание методики тестирования трудоёмкости операций,
11) таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД «Внешняя структура поиска» сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,
13) выводы,
14) список использованной литературы,
15) приложение с текстами программ:
- полное определение классов и текстов методов класса,
- текст программы тестирования трудоёмкости операций АТД.
Варианты задания.
1. АТД «Плотный индекс файла». Записи не закрепленные. Ключ записи – вещественное число.
2. АТД «Плотный индекс файла». Записи закрепленные. Ключ записи - вещественное число.
3. АТД «Разреженный индекс файла». Записи не закрепленные. Ключ записи – вещественное число.
4. АТД «Разреженный индекс файла». Записи не закрепленные Ключ записи – вещественное число. Блок файла индексов имеет К = M/10 для возможности дальнейшей вставки записей без выделения новых страниц индексов.
5. АТД «В – дерево файла» с нисходящим разделением полных узлов при вставке записей. Записи не закрепленные. Ключ записи – целое число.
6. АТД «В – дерево файла» с нисходящим разделением полных узлов при вставке записей. Записи закрепленные. Ключ записи – целое число.
7. АТД «В – дерево файла» с восходящим разделением полных узлов при вставке записей. Записи не закрепленные. Ключ записи – целое число.
8. АТД «В – дерево файла» с восходящим разделением полных узлов при вставке записей. Записи закрепленные. Ключ записи – целое число.
9. АТД «Хешированный файл». Метод хеширования – метод цепочек. Записи не закрепленные. Ключ записи – строка символов переменной длины.
10. АТД «Хешированный файл». Метод хеширования – метод цепочек. Записи закрепленные. Ключ записи – строка символов переменной длины.
Методические указания к лабораторной работе.
1. Для АТД «Внешняя структура поиска» разрабатываются формат АТД и шаблонный класс – контейнер.
2. Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
3. Тестирование операций через меню выполняется для структуры небольшого размера (размер страницы – 4 индекса). Тип данных задаётся с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое структуры файла с индексами и файла с данными.
4. Перед тестированием эффективности операций задаются тип данных, количество данных и размер страницы в файле индекса и в файле данных. Размер структуры варьируется в пределах от 100 до элементов. После тестирования на экран выводятся количество страниц в файлах с индексами и с данными до и после тестирования, размер файлов в байтах до и после тестирования, средняя трудоёмкость операций поиска, вставки и удаления (среднее число обращений к диску).
5. Для построения таблиц и графиков трудоёмкости операций при тестировании параметры структуры варьируются в следующих пределах:
N – число записей в файле данных, N = 102, 103, 104, 105.
M – размер страницы, M = 10,100, 1000.
6. Число обращений к блокам файла индексов в процессе выполнения операций должно соответствовать:
- для хешированного файла - N/(M*K), где K – число сегментов хеш – таблицы,
- для плотного индексного файла – 2 + log2(N/M),
- для разреженного индексного файла – 2 + log2(N/M2),
- для B - дерева файла – 2 + logt (N/M), где t – степень В – дерева.
Литература
1. Альфред Ахо, Хопкрофт, Д. Ульман Структуры данных и алгоритмы. - М. - СПб – Киев: «Вильямс», 2000 г. – 384 с.
2. Н. Вирт Алгоритмы + структуры данных = программы. - М.: «Мир», 1985 г. – 406 с.
3. Каррано, Джанет Дж. Причард. Абстракция данных и решение задач на С++. Стены и зеркала. - М. - СПб – Киев: «Вильямс», 2003 г. – 848 с.
4. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М: «Мир», 1976 г. (переиздание - М., Изд. "Вильямс", 2000 г.) – 735 с.
5. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М: «Мир», 1978 г. (переиздание - М., Изд. Изд. Вильямс", 2000 г.) – 844 с.
6. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Анализ и построение. - М: «БИНОМ», 2000 г. – 960 с.
7. Дж. Макконелл. Анализ алгоритмов. Вводный курс. - М: «Техносфера», 2002 г. – 304 с.
8. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 1-4. - М: «DiaSoft», 2001 г. – 688 с.
9. Уильям Топп, Уильям Форд. Структуры данных в С++. – М: «Бином», 2000 г. – 816 с.
10. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. – Киев: «ДиаСофт», 2001г. – 736 с.
