ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

2 семестр

Минск 2016

ПРЕДИСЛОВИЕ

Практикум содержит задания для выполнения лабораторных работ на основе приложения Microsoft Visual Studio 2010. В каждой работе имеются краткие теоретические сведения по рассматриваемым вопросам.

Преподаватель определяет, какие лабораторные работы должны выполнять студенты и в каком объеме. Предполагается, что выполнение большинства лабораторных работ занимает у студентов два академических часа.

Для облегчения процесса отладки программ удобнее записывать каждый оператор в отдельной строке. Но в данном пособии некоторые программы представлены в сжатом виде, поскольку это дает возможность видеть весь текст на одной странице, и облегчает анализ алгоритмов.

Задания для выполнения лабораторных работ содержат также кнопки, при нажатии на которые открываются тесты, предназначенные для контроля знаний студентов. Тестирование происходит по команде преподавателя и занимает несколько минут. Для работы тестирующих программ предварительно в приложении Word надо разрешить использование макросов. При этом тексты ответов на формах располагаются каждый раз случайным образом, и ответить на вопросы можно только один раз, так как после нажатия на кнопку «Результаты» форма с вопросами и вариантами ответов исчезает.

Для оформления отчетов по лабораторны работам используется приложение Word. Каждый отчет должен содержать название работы, условия задач, алгоритмы, тексты разработанных программ, результаты. В верхнем колонтитуле записывается фамилия студента и номер группы, в нижнем - номера страниц. Шрифт - 10 или 12, интервал - одинарный, поля - по 1, 5 см. Все отчеты в одном файле.

ОГЛАВЛЕНИЕ

Лабораторная работа № 1. Рекурсивные алгоритмы

Лабораторная работа № 2. Представление информации в виде структуры

Лабораторная работа № 3. Объединения, перечисления, битовые поля

Лабораторная работа № 4. Работа с файлами на языке С

Лабораторная работа № 5. Работа с файлами на языке С++

Лабораторная работа № 6. Динамические структуры данных. Списки

Лабораторная работа № 7. Разработка проекта с использованием списков

Лабораторная работа № 8. Полустатические структуры данных: стеки

Лабораторная работа № 9. Полустатические структуры данных: очереди

Лабораторная работа № 10. Бинарные деревья

Лабораторная работа № 11. Разработка проекта с использованием бинарного дерева

Лабораторная работа № 12. Бинарные кучи

Лабораторная работа № 13. Хэш-таблицы c открытой адресацией

Лабораторная работа № 14. Хэш-таблицы с цепочками

Лабораторная работа № 15. Алгоритмы сортировок обменных, выбором, вставками, разделением

Лабораторная работа № 13. Хэш-таблицы c открытой адресацией

Хэш-табли́ ца (перемешанная таблица) - это структура данных, которая позволяет хранить пары (ключ, значение) и выполнять три операции: добавления новой пары, поиска и удаления пары по ключу. Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа. Выполнение любой операции (поиск, добавление и удаление) в хэш-таблице начинается с вычисления хэш-функции от ключа. Ситуация, когда для различных ключей получается одно и то же значение хэш-функции, называется коллизией.

Существуют два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Задание	Краткие теоретические сведения
1. Пункты 1, 2, 3 содержат программный код проекта, в котором реализована хэш-таблица с открытой адресацией. В правой части данного пункта записан заголовочный файл Hash.h. Написать комментарии к программному коду.	#pragma once #define HASHDEL (void) -1 struct Object { void* Data; Object(int, int ()(void)); int Size; int N; int (GetKey)(void); bool Insert(void); int SearchInd(int key); void Search(int key); void* Delete(int key); bool Delete(void); void Scan(void(f)(void)); }; static void DEL = (void)HASHDEL; Object Create(int size, int (getkey)(void*)); #undef HASHDEL
2. В правой части данного пункта представлена структура, главная функция проекта и две вспомогательных функции. Написать комментарии к программе.	#include " stdafx.h" #include " Hash.h" #include < iostream> using namespace std; struct AAA { int key; char mas; AAA(int k, charz) { key = k; mas = z; } AAA() {} }; int key(void* d) { AAA* f = (AAA)d; return f-> key; } void AAA_print(void d) { cout< < " ключ " < < ((AAA)d)-> key< < " - " < < ((AAA)d)-> mas< < endl; } int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, " rus" ); AAA a1(1, " one" ), a2(2, " two" ), a3(4, " three" ), a4 (2, " fo" ); int siz = 10; cout< < " Введите размер хэш-таблицы" < < endl; cin> > siz; Object H = Create(siz, key); //создать int choise; int k; for(;; ) { cout< < " 1 - вывод хэш-таблицы" < < endl; cout< < " 2 - добавление элемента" < < endl; cout< < " 3 - удаление элемента" < < endl; cout< < " 4 - поиск элемента" < < endl; cout< < " 0 - выход" < < endl; cout< < " сделайте выбор" < < endl; cin> > choise; switch(choise) { case 0: exit(0); case 1: H.Scan(AAA_print); break; case 2: AAA a = new AAA; char str = new char [20]; cout< < " введите ключ" < < endl; cin> > k; a-> key = k; cout< < " введите строку" < < endl; cin> > str; a-> mas = str; if(H.N == H.Size) cout< < " Таблица заполнена" < < endl; else H.Insert(a); break; case 3: cout< < " введите ключ для удаления" < < endl; cin> > k; H.Delete(k); break; case 4: cout< < " введите ключ для поиска" < < endl; cin> > k; if (H.Search(k)==NULL) cout< < " Элемент не найден" < < endl; else AAA_print(H.Search(k)); break; } } return 0; }
3. В правой части записан программный модуль Hash.cpp. Написать комментарии к программному коду. Сформировать программный код в один проект и выполнить его.	#include " stdafx.h" #include " Hash.h" #include < iostream> int HashFunction(int key, int size, int p)//хэш-функция { double key2 = 5 * ((0.6180339887499 * key) - int((0.6180339887499 * key))); return (p+key)%size; //return ((int)(p+fmod(((key(sqrt(5.0)-1))/2), 1)))%size; } int Next_hash(int hash, int size, int p) { return (hash + 5 p + 3 * p * p) % size; } Object Create(int size, int(getkey)(void)) { return (new Object(size, getkey)); } Object:: Object(int size, int(getkey)(void)) { N = 0; this-> Size = size; this-> GetKey = getkey; this-> Data = new void[size]; for(int i = 0; i < size; ++i) Data[i] = NULL; } bool Object:: Insert(void* d) { bool b = false; if(N! = Size) for(int i = 0, t = GetKey(d), j = HashFunction(t, Size, 0); i! = Size & & ! b; j = Next_hash(j, Size, ++i)) if(Data[j] == NULL\|\|Data[j] == DEL) { Data[j] = d; N++; b = true; } return b; } int Object:: SearchInd(int key) { int t = -1; bool b = false; if(N! = 0) for(int i = 0, j = HashFunction(key, Size, 0); Data[j]! = NULL & & i! = Size & & ! b; j = HashFunction(key, Size, ++i)) if(Data[j]! = DEL) if(GetKey(Data[j]) == key) { t = j; b = true; } return t; } void* Object:: Search(int key) { int t = SearchInd(key); return(t > = 0)? (Data[t]): (NULL); } void* Object:: Delete(int key) { int i = SearchInd(key); void* t = Data[i]; if(t! = NULL) { Data[i] = DEL; N--; } return t; } bool Object:: Delete(void* d) { return(Delete(GetKey(d))! = NULL); } void Object:: Scan(void(f)(void)) { for(int i = 0; i < this-> Size; i++) { std:: cout< < " Элемент" < < i; if ((this-> Data)[i] == NULL) std:: cout< < " пусто" < < std:: endl; else if((this-> Data)[i] == DEL) std:: cout< < " удален" < < std:: endl; else f((this-> Data)[i]); } }

4. Добавить в проект функцию расчета коэффициента заполнения хэш-таблицы (альфа = n/m – число хранимых элементов /размер массива хэш). Построить хэш-таблицы разного размера (например, 16, 32 или 32, 64, 128) с коллизиями. Исследовать время поиска в построенных в соответствии со своим вариантом хэш-таблицах.

№ варианта	Условие задачи
Варианты с 1по8	Изменить функцию вычисления хэш для решения коллизии на квадратичную функцию, которая строится на основе формулы: h(key, i) = (h'(key) + с₁i+ c₂i²) mod hashTableSize.
Вариантыс 9по16	Изменить функцию вычисления хэш на мультипликативную функцию, которая строится на основе формулы: H(key) = [hashTableSize(keyA mod 1)], где keyA mod 1 – дробная часть key*A, A = (sqrt(5) - 1) / 2 = 0, 6180339887499

В начало практикума

Лабораторная работа № 16. Алгоритмы сортировок подсчетом, пирамидальных, слиянием,

Поразрядных

Задание

Краткие теоретические сведения

1. Написать программу, реализующую алгоритм сортировки подсчетом с использованием функции, приведенной в правой части. Проанализировать алгоритм.

При использовании сортировки подсчетом упорядоченный массив получается из исходного путем сравнения всех пар элементов массива. Для каждого из элементов подсчитывается количество элементов, меньших его. Например, пусть есть массив B = < 20, -5, 10, 8, 7> .Для первого числа имеется 4 элемента, которые меньше первого. Для второго - 0 элементов и т.д. Формируется таким образом массив счетчиков S = < 4, 0, 3, 2, 1>, элементы которого дают местоположе-ния элементов в результирующем массиве B’ = < -5, 7, 8, 10, 20>. Для сортировки требуются дополнительные массивы для размещения результатов и для счетчиков. void CountSort(int in[], int out[], int n) { int i, j, count; for (i = 0; i < n; ++i) { for ( count = 0, j = 0; j < n; ++j) if (in[j] < in[i] || (in[j] == in[i] & & i< j)) count++; out[count] = in[i]; } }

2. Написать программу, реализующую алгоритм пирамидальной сортировки с использованием функций, приведенных в правой части. Проанализировать алгоритм.

Пирамида - это двоичное дерево, в котором значение каждого элемента больше либо равно значениям дочерних элементов. Заполнив дерево элементами в произвольном порядке, можно его отсортировать, превратив в пирамиду. Самый большой элемент пирамиды находится в её вершине. Отделяется вершинный элемент и записывается в конец результирующего массива. На место вершинного элемента помещается элемент из самого нижнего уровня дерева. Восстанавливается (пересортировывается) пирамида. Самый большой элемент из оставшихся элементов снова в вершине и так далее... void heapify (int A[], int pos, int n) { int t, tm; while (2*pos + 1 < n) { t = 2 * pos + 1; if (2 * pos + 2 < n & & A[2 * pos + 2] > = A[t]) t = 2*pos + 2; if (A[pos] < A[t]) { tm = A[pos]; A[pos] = A[t]; A[t] = tm; pos = t; } else break; } } void PiramSort(int A[], int n) { for (int i = n - 1; i > = 0; i--) heapify(A, i, n); while(n> 0) { int tm = A[0]; A[0] = A[n - 1]; A[n - 1] = tm; n--; heapify(A, 0, n); } }

3. Написать программу, реализующую алгоритм сортировки слиянием с использованием функций, приведенных в правой части. Проанализировать алгоритм.

При использовании алгоритма сортировкислиянием исходный массив делится пополам, затем рекурсивно упорядочиваются обе половины и объединяются в одно целое. В ходе слияния элементы, стоящие в разных частях массива, попарно сравниваются друг с другом, и меньший элемент отправляется во временный массив. Этот процесс продолжается до тех пор, пока не будет использована полностью одна из двух частей массива. Затем копируются оставшиеся элементы во временный массив, и далее содержимое временного массива копируется обратно в исходный.

void InsOrd(int m[], int sm, int em, int e) { int buf; int i = sm; while(i < = em & & m[i] < e) { if (i - 1 > = sm) m[i - 1] = m[i]; i++; } m[i - 1] = e; } int* Merge(int m[], int sm, int cm, int em) { for(int i = 0; i < = sm; i++) { if (m[i] > m[cm + 1]) { int buf = m[i]; m[i] = m[cm + 1]; InsOrd(m, cm + 1, em, buf); } } return m; }

int* SortMerge(int m[], int lm, int sm = 0) { if (lm > 1) { SortMerge(m, lm / 2, sm); SortMerge(m, lm – lm / 2, sm + lm / 2); Merge(m, sm, sm + lm / 2 - 1, sm + lm - 1); }; return m; }; Здесь m[] - массив чисел; sm - индекс 1-ого элемента массива (1-й элемент левой части); cm - индекс последнего элемента левой части; em - индекс последнего элемента массива (последний элемент правой части); sm - стартовый элемент для сортировки.

4. Написать программу, реализующую алгоритм сортировки слиянием с использованием функций, приведенных в правой части. Проанализировать алгоритм.

Поразрядная сортировкаоснована на том, что все числа сортируются при помощи устойчивой сортировки сначала по младшему разряду, затем по остальным в порядке их возрастания. При этом ключи сортировки рассматриваются как числа, представленные в сист. счисления с основанием r. Работа идет с отд. цифрами чисел. int VelichRazr(int chislo, int razr) { while(razr> 1) { chislo /= 10; razr--; } return chislo % 10; } void PorazrSort(int B[n][n], int A[n], int razr) { int C[n], i, j, temp = 0; for(i = 0; i < n; i++) C[i] = 0; for(i = 0; i < n; i++) { int a = VelichRazr(A[i], razr); B[C[a]][a] = A[i]; C[a]++; } for(i = 0; i < n; i++) { for(j = 0; j < C[i]; j++) { A[temp] = B[j][i]; temp++; } } } Здесь A[n] -исходный массивположительных чисел, имеющих одинаковое количество разрядов, B[n][n] - вспомогательный двумерный массив чисел; razr - количество разрядов в числах.

5. В соответствии со своим вариантом написать программу сортировок массивов указанными в таблице методами. Исходные массивы заполняются случайными числами. Определить зависимость времени выполнения алгоритмов от количества элементов для каждого из алгоритмов. Выполнить моделирование для массивов размером 1000, 2000, 3000, 4000, 5000. Произвести сравнение эффективности алгоритмов (построить график в приложении Excel).

№ варианта	Методы сортировки массивов
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, пирамидальной, подсчетом, Шелла.
	Ввести массив А, в массив В перенести все элементы массива А, имеющие четный индекс, справа от которых расположены элементы с нечетным значением. Массив В отсортировать по убыванию, используя алгоритмы сортировок поразрядной, простой вставки, подсчетом.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее максимального элемента и имеющие нечетный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, выбором, пирамидальной, Хоара.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые больше минимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок подсчетом, пирамидальной, поразрядной, вставками.
	Ввести массивы Аи В. В массивС перенести элементы массива А с четным значением и элементы массива В с нечетным значением. Массив С отсортировать по возрастанию, используя алгоритмы сортировок разделением, слиянием, пирамидальной, Шелла.
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четное значение. Массив В отсортировать по возрастанию, используя алгоритмы сортировок методом простой вставки, подсчетом, выбором, слиянием.
	Ввести массивы Аи В. В массивС перенести четные элементы массива А и нечетные элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок поразрядной, слиянием, подсчетом, Хоара.
	Ввести массивы Аи В. В массивС перенести элементы массива А с нечетным значением и элементы массива В с нечетным значением. Массив С отсортировать по возрастанию, используя алгоритмы подсчетом, пирамидальной, поразрядной, вставками.
	Ввести массив А, в массив В перенести все элементы массива А, имеющие нечетный индекс, справа от которых расположены элементы с нечетным значением. Массив В отсортировать по возрастанию, используя алгоритмы сортировок слиянием, выбором, поразрядной, разделением.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые больше максимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок разделением, выбором, пирамидальной, пузырьком.
	Ввести массивы Аи В. В массивС перенести элементы массива А с нечетным значением и элементы массива В с четным значением. Массив С отсортировать по возрастанию, используя алгоритмы сортировок пирамидальной, разделением, слиянием, Хоара.
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четный индекс. Массив В отсортировать по возрастанию, используя алгоритмы сортировок подсчетом, выбором, пирамидальной, шейкерной.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее максимального элемента и имеющие четный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, пирамидальной, подсчетом, Шелла.
	Ввести массивы Аи В. В массивС перенести нечетные элементы массива А и четные элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок поразрядной, пирамидальной, подсчетом, вставками.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые меньше максимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок слиянием, выбором, пирамидальной, Хоара.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее минимального элемента и имеющие нечетный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок поразрядной, подсчетом, слиянием, пузырьком.