Динамические структуры данных

Шаблоны функций

Создать шаблон функции, выполняющей сортировку или поиск элементов в массиве. Протестировать шаблон для массивов с элементами различных типов: для вариантов 2, 10 и 20 – int, short и char, а для остальных вариантов - int, float и char.

 

№.	Метод сортировки (поиска)
	Сортировка простой (линейной) вставкой
	Бинарный поиск
	Сортировка слиянием (метод фон Неймана)
	Сортировка методом бинарной вставки без использования рабочего массива
	Сортировка Шелла (слияние с обменом)
	Быстрая сортировка (метод Хоара)
	Комбинированный метод быстрой сортировки с методом «пузырька»
	Внешняя двухфазная сортировка прямым слиянием
	Челночная сортировка (сортировка с просеиванием)
	Интерполяционный поиск
	Сортировка методом центрированной вставки (нахождение медианы)
	Шейкер – сортировка
	Сортировка методом бинарной вставки с использованием рабочего массива
	Обменная сортировка
	Внешняя однофазная сортировка прямым слиянием
	Внешняя сортировка естественным слиянием
	Сортировка Шелла (слияние с обменом)
	Внешняя сортировка сбалансированным слиянием
	Сортировка простой (линейной) вставкой
	Бинарный поиск

 

Методические указания по выполнению лабораторной работы

Алгоритмы сортировки и поиска приведены ниже. В приведенных алгоритмах массивы упорядочиваются по возрастанию.

 

Обменная сортировка.

Последовательно сравнивается элемент а₀ с каждым последующим a_i и, если a_i< а₀, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а₁ и т. д.

Шейкер – сортировка

В этом методе проходы массива выполняются поочередно: слева направо, а потом справа налево. Последовательно сравниваются пары соседних элементов (а₀ и а₁, а₁ и а₂, и т.д.) и, если надо, переставляются. Запоминается индекс последнего переставляемого элемента (right). Далее массив просматривается справа налево, начиная с индекса right. В этом проходе массива также выполняются сравнения соседних элементов и их перестановка. Запоминается индекс последнего переставляемого элемента (left). Далее опять выполняется проход слева направо от индекса left до индекса right и т.д.

Сортировка Шелла.

Выбирается интервал d между сравниваемыми элементами, и выполняется сортировка массива методом «пузырька», но с шагом d. После этапа сортировки массива с выбранным интервалом, этот интервал уменьшается и опять выполняется сортировка массива методом «пузырька». Рекомендуется следующая последовательность значений d: 1, 3, 7, 15, 31, …,т.е.

d_k=(d_k-1-1)/2

Максимальное значение d не должно превышать длину массива. Таким образом, в этом алгоритме вначале сравниваются и, если надо переставляются далеко стоящие элементы, а на последнем проходе – соседние.

Челночная сортировка

Последовательно сравниваются пары соседних элементов а₀ и а_1, а₁ и а₂, и т.д. и если а_i>a_i+1, то элемент a_i+1 продвигается влево насколько это возможно: он сравнивается со своим предшественником и, если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда передвигаемый влево элемент встречает меньшего предшественника, то процесс передвижения влево прекращается и возобновляется просмотр массива слева направо с той позиции, с которой выполнялся обмен при продвижении слева направо.

Быстрая сортировка (метод Хоара)

Идея метода заключается в том, что вначале переставляются элементы, которые находятся друг от друга на больших расстояниях. Выбирается элемент массива (например, центральный), который разбивает массив на два подмножества. Пусть значение этого элемента х. Элементы массива переставляются таким образом, чтобы слева от x находились элементы а_i<= x, а справа a_j>=x. После перестановок элемент x будет находиться на своем месте. Далее этот алгоритм разделения массива на левую и правую части применяется к левой, а затем к правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из единственного элемента. Таким образом, в этой сортировке используется рекурсия. Алгоритм разделения элементов массива начиная с элемента с индексом left до элемента с индексом right относительно «центрального» элемента x: вводятся два индекса i и j, i = left; j=right. Элементы просматриваются слева направо до тех пор, пока не обнаружится элемент a_i>= x, затем массив просматривается справа налево, пока не обнаружится элемент a_j<= x. После этого элементы меняются местами. Далее процесс просмотра и перестановки повторяется до тех пор, пока не станет i > j.

Комбинированный метод быстрой сортировки с методом «пузырька»

В этом методе рекурсивный алгоритм разделения массива быстрой сортировки применяется только для подпоследовательностей массива, длина которых не менее определенного размера m (m <= n). Для сортировки коротких подпоследовательностей используется метод «пузырька».

Линейная вставка

Элементы массива делятся на уже упорядоченную последовательность а₀, а₁, …, а_i-1 и неупорядоченную а_i, a_i+1, …,a_n-1. В каждом проходе из неупорядоченной последовательности извлекается элемент а_i (в первом проходе i =1) и вставляется в упорядоченную последовательность из i элементов без нарушения упорядоченности в ней. Этот алгоритм повторяется для i =2,3,…,n-1. Алгоритм вставки а_i в упорядоченную последовательность из i элементов заключается в продвижении вставляемого элемента в начало последовательности, сравнивая его с а_i-1, a_i-2 и т.д. Продвижение заканчивается на элементе а_j<=a_i или при прохождении всей последовательности.

Бинарная вставка

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

Центрированная вставка

Алгоритм использует дополнительный рабочий массив. В позицию, расположенную в центре рабочего массива помещается элемент а₀. Он будет медианой. Слева от медианы надо расположить все элемент, меньшие медианы, а справа – большие или равные. Из сортируемого массива последовательно выбирается элемент, сравнивается с медианой и вставляется без нарушения упорядоченности в левую или правую части массива. Если область памяти, выделенная для одной из частей, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении и значение медианы изменяется. В конце алгоритма упорядоченные элементы должны быть скопированы в исходный массив.

Метод фон Неймана

Упорядочить пары соседних элементов массива а (а₀ и а₁, а₂ и а₃ и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а.

Внешняя двухфазная сортировка прямым слиянием

Внешняя сортировка используется для сортировки файлов, размеры которых не позволяют записать их во временные массивы в оперативной памяти. Для сортировки используются три файла: c (исходный файл), a и b (вспомогательные файлы). Элементы исходного файла с попеременно записываются то в а, то в файл b (фаза разделения). Таким образом, в каждом файле создаются одноэлементные последовательности. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b (фаза слияния). Эти двухэлементные последовательности записываются в файл с. Далее двухэлементные последовательности попеременно записываются то в а, то в файл b (фаза разделения). Затем двухэлементные последовательности из файлов a и b сливаются в упорядоченные четверки и записываются в файл с (фаза слияния). Алгоритм разбиения файла с пополам и формирование упорядоченных последовательностей путем слияния пар последовательностей из файлов a и b повторяется до тех пор, пока в файлах a и b не образуется по одной упорядоченной последовательности, которые окончательно сливаются в отсортированный файл с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя однофазная сортировка прямым слиянием

Для сортировки используются четыре файла: c (исходный файл), a, b и d (вспомогательные файлы). При первом проходе элементы исходного файла с попеременно записываются то в а, то в файл b. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b. Эти двухэлементные последовательности попеременно записываются в файлы с и d. Затем сливаются пары двухэлементных последовательностей из файлов c и d в упорядоченные четверки, которые записываются попеременно в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя сортировка естественным слиянием

Сортировка, при которой сливаются две самые длинные из возможных упорядоченных последовательностей, называется естественным слиянием. В алгоритме используется исходный файл с и два вспомогательных файла a и b. В алгоритме при первом проходе определяются как можно более длинные упорядоченные последовательности файла с. Далее эти последовательности попеременно записываются в файлы a и b. На каждом следующем проходе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и переносятся в файл с, после чего наступает фаза разделения: последовательности попеременно записываются в файлы a. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя сортировка сбалансированным слиянием

В алгоритме используется исходный файл с и три вспомогательных файла a, b, d. В данном алгоритме при первом проходе определяются как можно более длинные упорядоченные участки файла с. Далее эти участки попеременно записываются в файлы a и b. На следующем этапе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и попеременно переносятся в файлы с и d. Затем сливаются пары последовательностей файлов с и d и попеременно переносятся в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Бинарный поиск

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Сначала х сравнивается со средним элементом массива. Если совпадение найдено, то возвращается индекс среднего элемента, иначе определяется, в какой половине массива следует выполнять поиск, применяя к ней алгоритм бинарного поиска.

Интерполяционный поиск

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Если известно, что х находится между элементами a_l и a_r, то номер очередного элемента для сравнения вычисляется по формуле

m=l+(r-l)*(x-a_l)/(a_r-a_l)

Если совпадение найдено, то возвращается индекс элемента (m), иначе определяется, в какой части массива следует выполнять поиск, применяя к ней алгоритм интерполяционного поиска.

 

Пример 1. Шаблон функции перестановки значения двух числовых переменных:

template <class t>

void change (t a, t b)

{ t c;

c=a; a=b; b=c; }

 

Пример 2.

#include <iostream>

#include <conio>

template <class T>

T maximum(T value1, T value2, T value3)

{ T max=value1;

if (value2>max) max=value2;

if (value3>max) max=value3;

return max;}

void main(){

int i1, i2, i3;

cout<<"Введите три целых числа: ";

cin>>i1>>i2>>i3;

cout<<"Максимальное значение: "<<maximum(i1, i2, i3);

double d1, d2, d3;

cout<<"Введите три числа типа double: ";

cin>>d1>>d2>>d3;

cout<<"Максимальное значение: "<<maximum(d1, d2, d3);

char ch1, ch2, ch3;

cout<<"Введите три символа: ";

cin>>ch1>>ch2>>ch3;

cout<<"Максимальное значение: "<<maximum(ch1, ch2, ch3);

getch();}

 

Пример 3. Составить программу с использованием шаблонов для примера 2, когда переменные задаются в виде массивов.

Способ 1.

#include <iostream>

#include <conio>

template <class Tree>

Tree maximum(Tree M, Tree MM)

{ Tree max=MM;

if (M>max) max=M;

return max;}

void main(){

int i;

int Vremi,MI[10];

cout<<"*** Int *** \n";

for (i=0; i<=10; i++){

cin>>MI[i];

if (i==0) Vremi=MI[i];

Vremi=maximum(MI[i],Vremi);}

cout<<"Max: "<<Vremi<<"\n";

double Vremd,MD[10];

cout<<"*** Double *** \n";

for (i=0; i<=10; i++){

cin>>MD[i];

if (i==0) Vremd=MD[i];

Vremd=maximum(MD[i],Vremd);}

cout<<"Max: "<<Vremd<<"\n";

char VremCh,MCh[10];

cout<<"*** Char *** \n";

for (i=0; i<=10; i++){

cin>>MCh[i];

if (i==0) VremCh=MCh[i];

VremCh=maximum(MCh[10],VremCh);}

cout<<"Max: "<<Vremd<<"\n";

getch();}

Способ 2.

#include <iostream>

#include <conio>

template <class Tree>

Tree maximum(const Tree *array)

{ Tree max=array[0];

for (int i=0; i<=10; i++)

if (array[i]>max) max=array[i];

return max;}

void main(){

int i;

int MI[10];

cout<<"*** Int *** \n";

for (i=0; i<=10; i++) cin>>MI[i];

cout<<"Max: "<<maximum(MI)<<"\n";

double MD[10];

cout<<"*** Double *** \n";

for (i=0; i<=10; i++) cin>>MD[i];

cout<<"Max: "<<maximum(MD)<<"\n";

char MCh[10];

cout<<"*** Char *** \n";

for (i=0; i<=10; i++) cin>>MCh[i];

cout<<"Max: "<<maximum(MCh)<<"\n";

getch();}

Лабораторная работа № 6.

Динамические структуры данных

Разработать программу, выполняющую операции со структурами данных, реализованными в виде связанных списков. Алгоритмы выполнения каждой операции оформить в виде функции. Программа должна содержать меню, позволяющее протестировать все операции с динамической структурой. Варианты заданий приведены в табл. 1 -3.

 

Таблица 1

Варианты структур данных

Структура данных	Операции	Варианты
Линейный список	Добавление элемента в начало, создание списка из n элементов, проверка списка на отсутствие в нем элементов, поиск позиции элемента с заданным значением, удаление элемента после элемента с заданной позицией (вар.1), удаление дубликатов (вар.11), получение значения элемента по его позиции, вывод списка	1, 11
Циклический список	Добавление элемента, создание списка из n элементов, проверка списка на отсутствие в нем элементов, удаление дубликатов (вар. 12), удаление элемента с заданным значением (вар. 2, 18), вывод списка	2, 12, 18
Стек	Добавление элемента, удаление элемента, создание стека из n элементов, проверка стека на отсутствие в нем элементов, получение значения элемента из вершины стека, очистка стека, вывод стека	3, 13
Очередь	Добавление элемента в конец, создание очереди из n элементов, проверка очереди на отсутствие в ней элементов, удаление элемента из начала, удаление всех элементов, получение значения из начала очереди, вывод очереди	4,14, 15
Очередь с приоритетами	Создание пустой очереди, добавление элемента, проверка очереди на отсутствие в ней элементов, удаление элемента с наибольшим приоритетом, получение элемента с наибольшим приоритетом, сцепление двух очередей, вывод очереди	5, 16
Дек	Добавление элемента справа, удаление элемента слева (вар. 17), удаление элемента справа (вар.6), создание списка из n элементов, проверка списка на отсутствие в нем элементов, копирование дека (вар. 6), копирование дека в обратном порядке (вар. 17), получение значения правого элемента, вывод дека	6, 17
Дек с ограниченным выходом	Добавление элемента справа, добавление элемента слева, создание дека из n элементов, проверка дека на отсутствие в нем элементов, удаление элемента справа, удаление всех элементов, получение значения правого элемента, вывод дека
Дек с ограниченным входом	Добавление элемента слева, создание дека из n элементов, проверка дека на отсутствие в нем элементов, удаление элемента справа, удаление элемента слева, получение значения левого элемента, удаление всех элементов, сравнение двух деков, вывод дека
Множество	Создание пустого множества, проверка вхождения элемента в множество, включение элемента в множество, объединение двух множеств, пересечение двух множеств, разность двух множеств, вывод множества	9, 19
Словарь	Создание пустого словаря, проверка словаря на отсутствие в нем элементов, включение элемента в словарь, поиск значения по ключу, исключение элемента из словаря по ключу, вывод словаря, удаление всех элементов.	10, 20

 

Таблица 2

Варианты способа реализации структуры

Способ реализации	Варианты
Связанный однонаправленный линейный список	1, 3, 4, 5, 19, 20
Связанный однонаправленный линейный список с указателями на данные	13, 15
Связанный упорядоченный однонаправленный линейный список	9, 10
Связанный однонаправленный циклический список
Связанный двунаправленный циклический список
Связанный двунаправленный линейный список	6, 7, 8, 11, 14, 16, 17
Связанный однонаправленный циклический список с указателями на данные

 

Таблица 3

Варианты элементов данных

Элемент данных	Варианты
Шифр студента – 9 символов, ФИО – 25 символов, средний балл – вещественное число	1, 2, 3, 4, 6,
Авторы – 20 символов, название - 20 символов, год издания – целое число	7, 8, 11, 12, 14, 17
Приоритет – целое число, наименование задания – 20символов, количество страниц - целое	5, 16
Название дисциплины – строка переменной длины	13, 15, 18
Код дисциплины – целое число, название дисциплины – 20 символов	9, 19
Телефон (ключ) – целое число, ФИО абонента (значение)– 25 символов	10, 20

 

Методические указания по выполнению лабораторной работы

Пример программы создания циклического однонаправленного списка с заголовком приведен ниже.

 

#include <iostream.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

struct tlist //тип элемента списка

{

char info[10]; //информационное поле

tlist *next; //указатель на следующий элемент

};

typedef tlist *plist; // тип "указатель на элемент"

void add(plist &list, char s[])

{

plist node; //указатель на новый элемент

node=new tlist; //выделение памяти под элемент

strcpy(node->info,s); //заполнение элемента

node->next=list->next;

list->next=node; //включение элемента в список

}

void main(void)

{

plist list; //указатель на список

char s[10];

//создание пустого списка с заголовочным элементом

list=new tlist;

list->next=list;

//добавление элемента в список

cout<<"s? ";

cin>>s;

add(list,s);

cout<< list->next->info; //вывод элемента

getch();

}