Задание
Использовать ранее разработанный контейнер, методы поиска, сортировки функций. Контейнерные классы стандартные библиотеки шаблонов и стандартные алгоритмы.
Выбор алгоритма решения задачи
Для решения поставленной задачи, необходима программа находящаяся здесь и программа, которая выполняет те же действия, но написана с использованием стандартных шаблонов (STL). Необходимо проверить время выполнения программы, написанной моим алгоритмом и проверить время выполнения программы, написанной с использованием шаблонов STL.
Описание решения задачи
Для откровение стандартного шаблона STL, необходимо написать следующее:
std::list< int > values;
Для внесения чисел до двунаправленного списка, необходимо написать:
values.push_front ();
Для выполнения сортировки:
values.sort();
Текст программы
1.1. telef.h
#ifndef Telef_h
#define Telef_h
#include<string.h>
#include<iostream.h>
/////////////////////////////////////////////////
struct Data{
int x;
Data *Next;
Data *Pred;
};
//////////////////////////////////////////////////
class telef
{
public:
telef(){BeginPtr = new Data; EndPtr = NULL;};
~telef(){BeginPtr = NULL;};
Data *getBeginPtr(){return BeginPtr;};
Data *getEndPtr(){return EndPtr;};
void setEndPtr(Data *End){EndPtr = End;}; // тоже необходимо занести.
void setBeginPtr(Data *Begin){BeginPtr = Begin;};
void Add(Data *,Data *, int);
void Del_all(Data *);
void show(Data *);
void Poisk_of_chislo(Data *);
void Sort_of_chislo(Data *);
private:
Data *BeginPtr;
Data *EndPtr;
};
#endif
1.2. telef.cpp
#include<string.h>
#include<iostream.h>
#include<list>
#include<algorithm>
#include "telef.h"
void telef::Add(Data *posl, Data *begin,int temp)
{
if (posl == NULL){
posl = begin;
posl->Pred = NULL;
}
else { posl->Next = new Data;
posl->Next->Pred = posl;
posl = posl->Next;
}
posl->x = temp;
posl->Next = NULL;
setEndPtr(posl);
}
////////////////////////////////////////////////////////
void telef::Del_all(Data *begin)
{
Data *prom;
prom = begin;
while ( prom != NULL) {
begin = begin->Next; //когда все удалено, то количество необходимо поставить в ноль!!!
delete prom;
prom = begin;
}
cout << "DELETE ALL"<<endl;
setBeginPtr(new Data);
setEndPtr(NULL);
}
////////////////////////////////////////////////////////
void telef::show(Data *begin)
{
cout << "Prosmotr spiska!!! \n\n";
while ( begin != NULL) {
cout << begin->x <<" ";
begin = begin->Next;
}
cout<<endl;
}
////////////////////////////////////////////////////////
void telef::Poisk_of_chislo(Data *begin)
{
int x = 0, temp;
cout << "<POISK PO NAME> \n";
cout <<"chislo = 3 ";
temp = 3;
while ( begin != NULL) {
if ( begin->x == temp ){
cout << "\nTakoe chislo naydeno";
x = 1;
}
begin = begin->Next;
}
if (x == 0 ) cout<<"\ntakogo chisla nety";
cout << endl;
}
////////////////////////////////////////////////////////
void telef::Sort_of_chislo(Data *begin)
{
int x_temp;
Data *Work;
int k = 1, _k = 1;
Work = begin;
while (k == 1){
begin = Work;
while ( begin->Next != NULL) {
if (begin->x > begin->Next->x) {
x_temp = begin->x;
begin->x = begin->Next->x;
begin->Next->x = x_temp;
_k = 0;
}
begin = begin->Next;
}
if (_k == 1)
k = 0;
_k = 1;
}
cout <<"\nSortirovka osyshestvlena!!!\n";
}
1.3. Main.cpp
#include<stdlib.h>
#include<conio.h>
#include<iostream.h>
#include<windows.h>
#include "telef.h"
long getTime( int tm ) {
return labs( GetTickCount() - tm );
} /*getTime()*/
int main ()
{
long tm1 = getTime( 0L );
cout<<" - "<<GetTickCount()<<"\n";
telef T;
int chislo;
for (int i = 0; i<1000;i++){
chislo = rand() % 150;
T.Add(T.getEndPtr(),T.getBeginPtr(),chislo);
}
T.show(T.getBeginPtr());
T.Poisk_of_chislo(T.getBeginPtr());
T.Sort_of_chislo(T.getBeginPtr());
T.show(T.getBeginPtr());
T.Del_all(T.getBeginPtr()); // {очистка памяти}
cout<<" - "<<GetTickCount()<<"\n";
tm1 = getTime( tm1 );
cout << "\nTime: " << tm1 << endl;
cout<<" Press key..."<<endl;
getch();
return 0;
}
2.1. Main.cpp
#include<iostream.h>
#include<list>
#include<iterator>
#include<string.h>
#include<conio.h>
#include<windows.h>
#include <stdlib.h>
using namespace std;
long getTime( int tm ) {
return labs( GetTickCount() - tm );
} /*getTime()*/
int main()
{
long tm1 = getTime( 0L );
cout<<" - "<<GetTickCount()<<"\n";
std::list< int > values;
int x = 2,y;
for (int i = 0 ; i < 1000; i++ ){
y = rand() % 150;
values.push_front ( y );
}
cout << "valuex soderjit : ";
list<int>::iterator p = values.begin();
while(p != values.end()) {
cout << *p<<" ";
p++;
}
values.sort();
cout << "\nvalues posle SORT soderjit: ";
p = values.begin();
while(p != values.end()) {
cout << *p<<" ";
p++;
}
cout<<"\nPoisk: ";
p = values.begin();
while(p != values.end()) {
if ( *p == 2) cout<<"\n2 - vhodit v spisok!!!";
p++;
}
cout<<" - "<<GetTickCount()<<"\n";
tm1 = getTime( tm1 );
cout << "\nTime: " << tm1 << endl;
cout<<endl;
getch();
return 0;
}
Результат работы программы
Вывод: изучил возможности, предоставляемые стандартной библиотекой шаблонов. Замерил время выполнения моего алгоритма и уже существующего, и замерил время выполнения стандартной библиотеки шаблонов. Получил такие результаты: моя программа заняла 78 условных единиц, а программа на основе стандартной библиотеки шаблонов заняла 47 условных единиц. Итак, стандартная библиотека шаблонов выполняет те же действия в 1,66 раз быстрее. Она оптимизирована, стандартизирована, универсальная. И для корректности программного обеспечения следует ее применять.
