Задание на лабораторную работу № 1.
В рамках лабораторной работы №1 требуется программно реализовать (с помощью указателей (однонаправленных/двунаправленный динамический линенйый связанный список, массива или используя стандартный контейнер библиотеки STL “stack” или «queue» - по варианту) абстрактный тип данных (АТД) в соответствии с заданием (стек, дек, очередь с одной головой, очередь с головой и хвостом).
Абстрактный тип данных должен позволять осуществлять только операции, присущие типу линейного связанного списка:
· получить значение первого элемента (на выходе),
· добавить элемент (на вход),
· удалить элемент из списка (на выходе),
· проверить – список пуст,
· обнулить (проинициализировать) список (конструктур, при необходимости).
· деструктор (при необходимости)
Используя разработанный АТД и указанный набор операций, необходимо реализовать заданный алгоритм сортировки последовательности элементов заданного типа, при этом следует учитывать, что разрешен доступ (чтение/извлечение) только к элементу на выходе.
На основе исходного текста программы получить аналитическую оценку трудоемкости работы алгоритма сортировки, используя О-символику для каждого реализованного метода АТД и сортировки в целом.
Вариант № ___.
Реализация связи элементов линейного списка: ______________________
Способ организации линейного связанный список: ___________________
Алгоритм сортировки: _____________________________________________
Теория о сортировках.
Сортировка естественным двухпутевым слиянием.
Метод сортировки вставками – это есть слияние двух подфайлов, у одного из которого n=1! Следовательно, задачу сортировки можно свести к слияниям, сливая все более длинные подфайлы до тех пор, пока не будет отсортирован весь файл. Для ускорения процесса вставок, можно рассмотреть вставку нескольких элементов за раз (n>1), группируя их. Такой метод слияний – один из самых первых методов сортировки, предложенный в 1945 Джоном фон Нейманом и носит название естественное двухпутевое слияние.
Рисунок иллюстрирует сортировку слиянием, когда мы продвигаемся с обоих концов, подобно методам быстрой сортировки, обменной сортировки и т.д. Мы анализируем исходный файл слева и справа, двигаясь к середине. Пропустим первую строку и рассмотрим вторую. Слева мы видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который перемещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 987 и результат записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается раньше, чем оно может привести к нежелательным последствиям) и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1.
Вертикальными линиями на рисунке отмечены границы между отрезками. Это так называемые ступеньки вниз, где меньший элемент следует за большим. В середине файла возникает двусмысленная ситуация, когда мы с обоих концов читаем один и тот же ключ.
Описанный метод называют "естественным" слиянием, потому что он использует отрезки, которые "естественно" образуются в файле.
Листинг программы с расчетами.
#include "stdafx.h"
#include <locale.h>
#include <ctime>
#include "windows.h"
#include <iostream>
using namespace std;
struct Node
{
// указатель на следующий элемент в очереди
Node *next;
// значение элемента в очереди
int value;
};
class Ochered
{
public:
// Колличество элементов в списке
int N;
int i;
int size = 0;
int size_1 = NULL;
// Счетчик колличества операций
unsigned long long int N_op = 0;
// указатель на первый элемент
Node *head;
// указатель на хвост очереди
Node *tail;
// инициализация очереди
void Init() //2
{
head = NULL; //1
// При инициализации head и tail = NULL
tail = head; //1
}
// добавление элемента в начало очереди, x - значение этого элемента
void Add(int x) //(3+2+2)+(1+2+1)+2=13
{
// создание нового элемента
Node *node = new Node; //3
// в поле next данного элемента записывается NULL
node->next = NULL; //2
// в поле value записывается значение ячейки очереди int
node->value = x; //2
// после инициализации и при создании первого элемента мы проходим по ветке else
if (tail!= NULL) //1
{
/* добавление элемента через хвост в очереди,
tail указывает на первый элемент в очереди перед добавляемым
в поле next первого элемента записывается адрес нового первого элемента*/
tail->next = node; //2
// tail начинает указывать на новый элемент в очереди
tail = node; //1
}
else
{
// хвост указывает на первый элемент в очереди
tail = node; //1
// голова указывает на первый элемент в очереди
head = tail; //1
}
size++; //2
}
// проверка очереди на пустоту
bool Isempty() //1
{
//true, если head = NULL; false, если head указывает на какой-либо элемент в очереди
return head == NULL; //1
}
// удаление элемента из конца очереди
int Del() //1+(2+2+2+1+2+2+2)=14
{
int val = NULL; //1
// если очередь не пуста
if (Isempty()!= 1) //2
{
// создаем указатель на структуру
Node *tmp;
// в указателюь tmp кладем ссылку на next предпоследнего элемента в очереди
tmp = head->next; //2
// в val записываем значение последнего элемента в очереди
val = head->value; //2
// удаляем объект по указателю head (последний элемент в очереди)
delete head;
// head начинает указывать на предпоcледний элемент в очереди (последний удален)
head = tmp; //1
// После удаления последнего элемента из очереди происходит повторная инициализация
if (Isempty() == 1) //2
{
Init(); //2
}
size--; //2
// возвращаем значение последнего элемента в очереди
return val;
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
// получение значения из конца очереди
int Value() //3
{
// если очередь не пуста
if (Isempty()!= 1) //2
{
// через указатель head получить значение value последнего элемента в очереди
return head->value; //1
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
};
// Класс наследник
class Numbers: public Ochered
{
public:
// получение значения из списка, x - номер элемента в списке
int get(int x) //2+1+1+(1+33n)=5+33n
{
// если очередь не пуста
if (Isempty()!= 1) //2
{
size_1 = size; //1
int val1 = NULL; //1
// Перебор всех значений в списке
for (int i = 1; i < size_1 + 1; i++) // 
{
if (i == x) //1
{
// Когда i доходит до номера получаемого элемента, то в val записывается значение данного элемента
val1 = Value(); //4
}
// Перебор начинается только в случае если x не равен нулю
if (x!= 1) //1
{
// Вначале элемент удаляется из конца очереди, и сразу же добавляется в начало очереди, и так в цикле пока не восстановится первоначальное состояние очереди
Add(Del()); //14+13=27
}
else
{
// В противном случае сразу выходим из цикла for
break;
}
}
// Возвращается значение элемента под номером x из очереди
return val1;
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
// установка значения элемента в списке, x - номер элемента в списке, y - значение элемента в списке
void set(int x, int y) //2+3+31n=5+31n
{
// если очередь не пуста
if (Isempty()!= 1) //2
{
if (x <= size) //1+1+1+31n=3+31n
{
size_1 = size; //1
for (int i = 1; i < size_1 + 1; i++) // 
{
if (i == x) //1
{
// Запись значения y в список
head->value = y; //2
}
if (x!= 1) //1
{
Add(Del()); //14+13=27
}
else
{
break;
}
}
}
// Если элемент устанавливается за пределы изначального списка
else // 
{
if (x == size + 1) //2
{
//Если номер элемента в списке на 1 больше размера очереди, значит элемент добавляется в начало очереди
Add(y);
}
else
{
for (i = size + 1; i < x; i++) // 
{
// В противном случае очередь заполняется нулями
Add(0); //13
}
Add(y); //13
}
}
}
else { cout << "Очередь пуста!" << endl; }
}
void sort(int N)
{
int s, f, d, i, j, g, k, p;
s = 1; //1
do
{
s = 1 - s; //2
d = 1; //1
f = 1; //1
if (s == 0) //1
{
i = 1; //1
j = N; //1
k = N + 1; //2
g = 2 * N; //2
}
else
{
i = N + 1; //2
j = 2 * N; //2
k = 1; //1
g = N; //1
}
while (i!= j)// 
{
// if(K[i]<K[j])
if (get(i) > get(j))// 
{
// R[k] = R[j];
set(k, get(j));// 
k = k + d; //2
j = j - 1; //2
// if (!(K[j+1]<=K[j]))
if (get(j + 1) <= get(j)) //5+66n+1+5+66n+1=132n+12
{
}
else
{
do
{
// R[k]=R[i];
set(k, get(i)); //10+128n
k = k + d; //2
i = i + 1; //2
}
// while(!K[i-1]>=K[i]);
while (get(i - 1) < get(i)); // 
f = 0; //1
d = -d; //1
p = k; //1
k = g; //1
g = p; //1
}
}
else
{
// R[k]=R[i];
set(k, get(i));
k = k + d; //2
i = i + 1; //2
// if(K[i-1]<=K[i])
if (get(i - 1) <= get(i)) //…+2
{
}
else
{
do
{
// R[k] = R[j];
set(k, get(j));
k = k + d; //2
j = j - 1; //2
}
// while(K[j+1]>=K[j]);
while (get(j + 1) < get(j)); //…+2
f = 0; //1
d = -d; //1
p = k; //1
k = g; //1
g = p; //1
}
}
}
//R[k]=R[i];
set(k, get(i)); //10+128n
} while (f!= 1); // 
if (s == 0) //1
{
for (int i = 1; i <= N; i++)// 
{
// R[i] = R[i+n];
set(i, get(i + N)); // 
}
}
size_1 = size; //1
for (int i = 1; i <= size_1; i++) // 
{
if (i <= size / 2) //2
{
Add(Del()); //27
}
else
{
Del();
}
}
}
};
int main()
{
setlocale(LC_ALL, "ru");
srand(time(NULL));
// Схема эксперимента
// Инициализация очереди и заполнение хранилища ключей
int i, t_s, t_f;
// Хранилище ключей
int Key[3000];
int N = 300;
Numbers list;
list.Init();
for (i = 0; i < 3000; i++)
{
// Заполнение хранилища ключей случайными числами до 1000
Key[i] = rand() % 999;
}
for (i = 0; i < 10; i++)
{
for (int z = N - 300; z < N; z++)
{
list.Add(Key[z]);
}
list.N_op = 0;
t_s = GetTickCount();
list.sort(N);
t_f = GetTickCount();
cout << "Номер сортировки: " << i + 1 << " Колличество отсортированных элементов: " << N << " Время сортировки (ms): " << t_f - t_s << " Колличество операций (N_op): " << list.N_op << endl; // Шаг в 300 элементов
N = N + 300;
}
return 0;
}
F(n)= 
O(F(n))= 
| Кол-во элементов | F(n) | O(F(n)) | Т(n) (сек) | N_op |
| 3,078 | ||||
| 17,375 | ||||
| 39,109 | ||||
| 69,547 | ||||
| 128,859 | ||||
| 185,438 | ||||
| 296,657 | ||||
| 397,812 | ||||
| 418,672 | ||||
| 752,609 |
Таблица результата экспериментов и графики зависимостей
| С1=F(n)/T(n) | С2=O(F(n))/T(n) | С3=F(n)/N_op | С4=O(F(n))/N_op |
| 9485073,771 | 72182,619 | 139,929 | 1,064 |
| 14994984,695 | 114729,487 | 221,078 | 1,691 |
| 23866033,574 | 182930,949 | 351,313 | 2,692 |
| 33128010,980 | 254150,411 | 487,299 | 3,738 |
| 36000941,572 | 276339,024 | 530,764 | 4,074 |
| 44290729,864 | 340091,954 | 652,677 | 5,011 |
| 44856720,871 | 344525,845 | 661,116 | 5,077 |
| 50794021,516 | 390202,380 | 747,894 | 5,745 |
| 69748118,244 | 535888,409 | 1027,276 | 7,892 |
| 53927579,688 | 414385,375 | 793,342 | 6,096 |
Скриншот работы программы:
Выводы.
По результатам экспериментов было установлено, что графики C1, C2, C3, C4 от N имеют линейную зависимость от количества элементов.
Литература:
1. Структуры данных и алгоритмы. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – М.: Издательский дом «Вильямс», 2000
2. Д. Кнут. Искусство программирования для ЭВМ.
Приложение 1. Применение счетчика операций N_op.
#include "stdafx.h"
#include <locale.h>
#include <ctime>
#include "windows.h"
#include <iostream>
using namespace std;
struct Node
{
// указатель на следующий элемент в очереди
Node *next;
// значение элемента в очереди
int value;
};
class Ochered
{
public:
// Колличество элементов в списке
int N;
int i;
int size = 0;
int size_1 = NULL;
// Счетчик колличества операций
unsigned long long int N_op = 0;
// указатель на первый элемент
Node *head;
// указатель на хвост очереди
Node *tail;
// инициализация очереди
void Init()
{
head = NULL; N_op++;
// При инициализации head и tail = NULL
tail = head; N_op++;
}
// добавление элемента в начало очереди, x - значение этого элемента
void Add(int x)
{
// создание нового элемента
Node *node = new Node; N_op+=3;
// в поле next данного элемента записывается NULL
node->next = NULL; N_op+=2;
// в поле value записывается значение ячейки очереди int
node->value = x; N_op+=2;
// после инициализации и при создании первого элемента мы проходим по ветке else
if (tail!= NULL)
{ N_op++;
/* добавление элемента через хвост в очереди,
tail указывает на первый элемент в очереди перед добавляемым
в поле next первого элемента записывается адрес нового первого элемента*/
tail->next = node; N_op+=2;
// tail начинает указывать на новый элемент в очереди
tail = node; N_op++;
}
else
{ N_op++;
// хвост указывает на первый элемент в очереди
tail = node; N_op++;
// голова указывает на первый элемент в очереди
head = tail; N_op++;
}
size++; N_op+=2;
}
// проверка очереди на пустоту
bool Isempty()
{ N_op++;
//true, если head = NULL; false, если head указывает на какой-либо элемент в очереди
return head == NULL;
}
// удаление элемента из конца очереди
int Del()
{
int val = NULL; N_op++;
// если очередь не пуста
if (Isempty()!= 1)
{ N_op++;
// создаем указатель на структуру
Node *tmp;
// в указателюь tmp кладем ссылку на next предпоследнего элемента в очереди
tmp = head->next; N_op+=2;
// в val записываем значение последнего элемента в очереди
val = head->value; N_op+=2;
// удаляем объект по указателю head (последний элемент в очереди)
delete head;
// head начинает указывать на предпоcледний элемент в очереди (последний удален)
head = tmp; N_op++;
// После удаления последнего элемента из очереди происходит повторная инициализация
if (Isempty() == 1)
{ N_op++;
Init();
}
size--; N_op+=2;
// возвращаем значение последнего элемента в очереди
return val;
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
// получение значения из конца очереди
int Value()
{
// если очередь не пуста
if (Isempty()!= 1)
{ N_op+=2;
// через указатель head получить значение value последнего элемента в очереди
return head->value;
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
};
// Класс наследник
class Numbers: public Ochered
{
public:
// получение значения из списка, x - номер элемента в списке
int get(int x)
{
// если очередь не пуста
if (Isempty()!= 1)
{ N_op++;
size_1 = size; N_op++;
int val1 = NULL; N_op++;
/* Перебор всех значений в списке*/ N_op++;
for (int i = 1; i < size_1 + 1; i++)
{
if (i == x)
{ N_op++;
// Когда i доходит до номера получаемого элемента, то в val записывается значение данного элемента
val1 = Value(); N_op++;
}
// Перебор начинается только в случае если x не равен нулю
if (x!= 1)
{ N_op++;
// Вначале элемент удаляется из конца очереди, и сразу же добавляется в начало очереди, и так в цикле пока не восстановится первоначальное состояние очереди
Add(Del());
}
else
{ N_op++;
// В противном случае сразу выходим из цикла for
break;
}
}
// Возвращается значение элемента под номером x из очереди
return val1;
}
else { cout << "Очередь пуста!" << endl; }
return 0;
}
// установка значения элемента в списке, x - номер элемента в списке, y - значение элемента в списке
void set(int x, int y)
{
// если очередь не пуста
if (Isempty()!= 1)
{ N_op++;
if (x <= size)
{ N_op++;
size_1 = size; N_op++;
N_op++;
for (int i = 1; i < size_1 + 1; i++)
{
if (i == x)
{ N_op++;
// Запись значения y в список
head->value = y; N_op+=2;
}
if (x!= 1)
{ N_op++;
Add(Del());
}
else
{ N_op++;
break;
}
}
}
// Если элемент устанавливается за пределы изначального списка
else
{ N_op++;
if (x == size + 1)
{ N_op+=2;
//Если номер элемента в списке на 1 больше размера очереди, значит элемент добавляется в начало очереди
Add(y);
}
else
{ N_op+=2; N_op++;
for (i = size + 1; i < x; i++)
{
// В противном случае очередь заполняется нулями
Add(0);
}
Add(y);
}
}
}
else { cout << "Очередь пуста!" << endl; }
}
void sort(int N)
{
int s, f, d, i, j, g, k, p;
s = 1; N_op++;
do
{
s = 1 - s; N_op+=2;
d = 1; N_op++;
f = 1; N_op++;
if (s == 0)
{ N_op++;
i = 1; N_op++;
j = N; N_op++;
k = N + 1; N_op+=2;
g = 2 * N; N_op+=2;
}
else
{ N_op++;
i = N + 1; N_op+=2;
j = 2 * N; N_op+=2;
k = 1; N_op++;
g = N; N_op++;
}
while (i!= j)//
{ N_op++;
// if(K[i]<K[j])
if (get(i) > get(j))
{ N_op++;
// R[k] = R[j];
set(k, get(j));
k = k + d; N_op+=2;
j = j - 1; N_op+=2;
// if (!(K[j+1]<=K[j]))
if (get(j + 1) <= get(j))
{
N_op+=2;
}
else
{ N_op+=2;
do
{
// R[k]=R[i];
set(k, get(i));
k = k + d; N_op+=2;
i = i + 1; N_op+=2; N_op+=2;
}
// while(!K[i-1]>=K[i]);
while (get(i - 1) < get(i));
f = 0; N_op++;
d = -d; N_op++;
p = k; N_op++;
k = g; N_op++;
g = p; N_op++;
}
}
else
{ N_op++;
// R[k]=R[i];
set(k, get(i));
k = k + d; N_op+=2;
i = i + 1; N_op+=2;
// if(K[i-1]<=K[i])
if (get(i - 1) <= get(i))
{
N_op+=2;
}
else
{ N_op+=2;
do
{
// R[k] = R[j];
set(k, get(j));
k = k + d; N_op+=2;
j = j - 1; N_op+=2; N_op+=2;
}
// while(K[j+1]>=K[j]);
while (get(j + 1) < get(j));
f = 0; N_op++;
d = -d; N_op++;
p = k; N_op++;
k = g; N_op++;
g = p; N_op++;
}
}
}
//R[k]=R[i];
set(k, get(i)); N_op++;
} while (f!= 1);
if (s == 0)
{ N_op+=2;
for (int i = 1; i <= N; i++)
{ N_op++;
// R[i] = R[i+n];
set(i, get(i + N));
}
}
size_1 = size; N_op+=2;
for (int i = 1; i <= size_1; i++)
{
if (i <= size / 2)
{ N_op+=2;
Add(Del());
}
else
{ N_op+=2;
Del();
}
}
}
};
int main()
{
setlocale(LC_ALL, "ru");
srand(time(NULL));
// Схема эксперимента
// Инициализация очереди и заполнение хранилища ключей
int i, t_s, t_f;
// Хранилище ключей
int Key[3000];
int N = 300;
Numbers list;
list.Init();
for (i = 0; i < 3000; i++)
{
// Заполнение хранилища ключей случайными числами до 1000
Key[i] = rand() % 999;
}
for (i = 0; i < 10; i++)
{
for (int z = N - 300; z < N; z++)
{
list.Add(Key[z]);
}
list.N_op = 0;
t_s = GetTickCount();
list.sort(N);
t_f = GetTickCount();
cout << "Номер сортировки: " << i + 1 << " Колличество отсортированных элементов: " << N << " Время сортировки (ms): " << t_f - t_s << " Колличество операций (N_op): " << list.N_op << endl;
// Шаг в 300 элементов
N = N + 300;
}
return 0;
}