МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра математического обеспечения и применения ЭВМ
Отчет по лабораторной работе №2
по дисциплине «Алгоритмы и структуры данных»
Студент гр. 930 |
|
Преподаватель |
Колинько П.Г. |
Тема: Множество как объект
Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3 Контрольные тесты ...................................................................................... 4
Вывод ............................................................................................................. 6
Список использованных источников........................................................... 7
Текст программы ........................................................................................... 8
Цель работы
Исследование эффекта от использования классов
Задание
Инициализировать множество Е, содержащее шестнадцатеричные цифры, имеющиеся в А или В, но отсутствующие в С и в D
E = A+B – С - D
Постановка задачи и описание решения
Задача заключается в том, чтобы образовать объединение множеств А и В и вычесть из него С и D.
Для реализации задачи используется 4 способа хранения множеств: массивы, списки, массивы битов и машинное слово.
Для генерации тестов сперва инициализируются случайные размеры массивов, а потом они заполняются уникальными символами (если размер массива меньше универсума, то оставшаяся часть заполняется нулями-терминаторами). Затем информацией из массивов заполняются списки, массивы битов и машинные слова.
Для универсума был создан отдельный массив для того, чтобы не вставлять два цикла в некоторые места, где можно было бы обойтись и одним
Для каждого из классов использовались перегрузки операторов
Все данные находятся в виде доступа private, однако, по желанию, их можно достать с помощью getter’ов(получателей). Делается это для предотвращения несанкционированного доступа к данным объектов
Объекты уничтожались тогда, когда они уже не были нужны (после последнего использования)
Замеряемое время указывается в тиках: чем меньше тиков приходится на исполнение алгоритма, тем он эффективнее. Каждый алгоритм прогоняется 100000 раз.
Контрольные тесты
Задаются 4 массива со случайными размерами и уникальными символами.
Каждое задание отделяется друг от друга. Первый алгоритм проводился над массивами, второй – над массивами битов, третий – над списками, четвертый – над машинными словами
В четвертой задаче ответ предоставляется в виде машинного слова (для проверки используется ответ из второго алгоритма)
В первом примере сгенерировались массивы, размером гораздо меньше универсума. Поэтому было затрачено гораздо меньше времени, чем в следующем примере. Алгоритм с машинным словом выполняется в 81 раз быстрее, чем со списком
Здесь было затрачено больше времени, так как обрабатывались бОльшие массивы (ответ тоже получился большим) Алгоритм с машинным словом выполняется в 78 раз быстрее, чем со списком
Вывод
Таким образом, самым эффективным способом хранения данных является машинное слово. После него идет массив битов, потом обычный массив, а на последнем месте список.
По сравнению с использованием структур данных вне классов, те протекали гораздо быстрее, так как не затрачивалось время на вход в функции.
Классы целесообразнее использовать тогда, когда для структуры данных надо сделать некоторые свойства в спецификаторе доступа private и, конечно, для создания уникальных методов для управления объектами
Список использованных источников
Стивен Прата: Язык программирования С++. Лекции и упражнения. - 2012. – 1248 с.
Колинько П.Г.: Методические указания по дисциплине “Алгоритмы и структуры данных, часть 1”. – 2020. – 64 с.
Текст программы
//Файл main.cpp
#include "includesH/AllClasses.h"
#include "includesCPP/array.cpp"
#include "includesCPP/bool.cpp"
#include "includesCPP/list.cpp"
#include "includesCPP/word.cpp"
//Моя формула: E = (A + B) - (C + D)
int main()
{
srand(time(0));
int i;
cout << "Working with arrays:\n";
Array A('A'), B('B'), C('C'), D('D'), E;
clock_t start=clock();
for (i=0; i<TIMES; i++) E = (A | B) & ~(C|D);
cout << "Time is "<<clock()-start<<'/'<<TIMES<<endl;
E.Show();
//--------------------------------------------------
cout << "\n"<<textbar;
cout << "Working with boolean arrays:\n";
Bool bA(A.GetA()),
bB(B.GetA()),
bC(C.GetA()),
bD(D.GetA()),
bE;
start = clock();
for (i=0; i<TIMES; i++) bE = (bA | bB) & ~(bC | bD);
cout << "Time is "<<clock()-start<<'/'<<TIMES<<endl;
bE.Show();
//--------------------------------------------------
cout << "\n"<<textbar;
cout << "Working with lists:\n";
ListSet lA(A.GetA()),
lB(B.GetA()),
lC(C.GetA()),
lD(D.GetA()),
lE;
start = clock();
for (i=0; i<TIMES; i++) lE = (lA | lB) & ~(lC | lD);
cout << "Time is "<<clock()-start<<'/'<<TIMES<<endl;
lE.Show();
//--------------------------------------------------
cout << "\n"<<textbar;
cout << "Working with machine words:\n";
Word wA(A.GetA()),
wB(B.GetA()),
wC(C.GetA()),
wD(D.GetA()),
wE;
start = clock();
for (i=0; i<TIMES; i++) wE = (wA | wB) & ~(wC | wD);
cout << "Time is "<<clock()-start<<'/'<<TIMES<<endl;
wE.Show();
return 0;
}
//Файл AllClasses.h
#include <iostream>
#include <ctime>
#include <cstring>
#pragma once
using namespace std;
const int N=16;
const char* Universum= "0123456789abcdef";
const int TIMES=100000;
const char *textbar="+---------------------------------+\n";
class Array{
private:
static int cnt; // мощность универсума и счетчик множеств
int n; // мощность множества
char S, *A;//название (тэг) и память для множества
public:
Array operator | (const Array&)const;//объединение
Array& operator |= (const Array&);
Array operator & (const Array&)const;//пересечение
Array& operator &= (const Array&);
Array operator ~ ()const;//дополнение до универсума
void Show() {cout <<S<< " = ["<< A<< "]\n";}
char* GetA() {return A;}
int power() {return n;}//получение мощности
Array(char);//конструктор множества
Array();//конструктор пустого множества
Array(const Array&);//конструктор копии
Array& operator = (const Array&);//оператор присваивания
~Array() {delete []A;}//деструктор
};
int Array::cnt=0;
class Bool{
private:
static int cnt;
char S;
bool *A;
public:
Bool operator | (const Bool&)const;//объединение
Bool& operator |= (const Bool&);
Bool operator & (const Bool&)const;//пересечение
Bool& operator &= (const Bool&);
Bool operator ~ ()const;//дополнение до универсума
void Show() {cout <<S<< " = ["; for (int i=0; i<N; i++) cout << A[i]; cout <<"]\n";}
Bool(char* Arr);//конструктор множества
Bool();//конструктор пустого множества
Bool(const Bool&);//конструктор копии
Bool& operator = (const Bool&);//оператор присваивания
~Bool() {delete []A;}//деструктор
};
int Bool::cnt=0;
struct List
{
char ch;
List *next;
List(char ch, List* n=nullptr): ch(ch), next(n){}
~List() {delete next; next = nullptr;}
};
class ListSet{
private:
List *Head;
static int cnt; // мощность универсума и счетчик множеств
char S;
int n;
public:
ListSet operator | (const ListSet&)const;//объединение
ListSet operator & (const ListSet&)const;//пересечение
ListSet operator ~ ()const;//дополнение до универсума
void Show();
int power() { return n; }
ListSet(char*);
ListSet();//конструктор пустого множества
ListSet(const ListSet&);//конструктор копии
~ListSet() { delete Head; }
ListSet& operator = (const ListSet&);//оператор присваивания
};
int ListSet::cnt=0;
class Word{
private:
int w;
static int cnt;
char S;
public:
Word operator | (const Word&) const;
Word operator & (const Word&) const;
Word operator ~ ()const;
void Show() { cout << S << " = "<< w <<endl; }
Word(char*);
Word();
Word(const Word&);
Word& operator = (const Word&);
};
int Word::cnt = 0;
//Файл array.cpp
#pragma once
#include "../includesH/AllClasses.h"
//Указатель this используется для создания указателя на адрес объекта
//Через него можно обращаться к собственным полям и методам
Array :: Array(): n(0), S('A'+cnt++), A(new char[N+1]) {A[0] = 0;} //конструктор пустого множества
Array ::Array(char): S('A'+cnt++), n(0), A(new char[N+1])
{
/*S='A'+cnt++; n=0; A=new char[N+1];// менее удобная запись*/
bool flagsame;
char buf;
int sArr=rand()%N+1, i;
for (i=0; i<sArr; i++)
{
do
{
flagsame=false;
if (rand()%2)
buf=rand()%10+ '0';
else buf=rand()%6+ 'a';
for (int j=0; j<sArr; j++)
if (buf == A[j]) flagsame=true;
}
while(flagsame);
if (!flagsame) { A[i]=buf; n++;}
}
A[i]=0;
cout <<S<<" = ["<<A<<"]\n";
}
//Конструктор копии
Array :: Array(const Array& B): S('A'+cnt++), n(0), A(new char[N+1])
{
char *dst(A), *src(B.A); //Инициализация адресов
while (*dst++ = *src++) n++; //Копирование символов до обнаружения 0
}//ошибка Колинько
Array& Array :: operator &= (const Array & B)
{
Array C(*this);
n=0;
for (int i=0; i<C.n; i++)
for (int j=0; j<B.n; j++)
if (C.A[i] == B.A[j]) A[n++]=C.A[i];
A[n]=0;
return *this;
}
Array Array :: operator & (const Array& B) const
{
Array C(*this);
return (C &= B);
}
Array& Array :: operator |= (const Array & B)
{
//cout << n << " " << B.n<<endl;
for (int i=0; i< B.n; i++)
{
bool f = true;
for (int j=0; j<n; j++)
if (B.A[i] == A[j]) f = false;
if (f)
{
A[n++] = B.A[i];
//cout << A[n-1]<< " ";
}
}
A[n]=0;
return *this;
}
Array Array :: operator | (const Array& B) const
{
Array C(*this); //C.n=n; ошибка при создании конструктора копии
return (C |= B);
}
Array Array :: operator ~ ()const
{
Array C; //C.n == 0
int i=0;
for (char c=Universum[i]; Universum[i] !='\0'; i++)//цикл по универсуму
{
c=Universum[i];
bool f = true;
for (int j=0; j<n; ++j)
if (c == A[j]) f = false;
//если в массиве А не встретился элемент универсума, то заносим его в массив С.А
if (f) {C.A[C.n++] = c; //cout << c << " ";
}
}
C.A[C.n]=0;
return C;
}
Array& Array :: operator = (const Array& B)
{
if (this != &B)
{
char *dst(A), *src(B.A);
n=B.n;
while (*dst++ = *src++);//копирование до 0
S = 'A' + cnt++;
}
return *this;
}
//файл bool.cpp
#pragma once
#include "../includesH/AllClasses.h"
Bool :: Bool(): S('A'+cnt++), A(new bool[N]) {for (int i=0; i<N; i++) A[i] = 0;} //конструктор пустого множества
Bool::Bool(char* Arr): S('A'+cnt++), A(new bool[N])
{
for (int i=0; i<N; i++) A[i] = 0;
int len = strlen(Arr);
for (int i=0; i<len; i++) A[(Arr[i] <= '9')? Arr[i]-'0' : Arr[i]-'a'+10] = 1;
(*this).Show();
}
Bool :: Bool(const Bool& B): S('A'+cnt++), A(new bool[N])
{
for (int i=0; i<N; i++)
A[i] = B.A[i];
}
Bool& Bool :: operator = (const Bool& B)
{
if (this != &B)
{
for (int i=0; i<N; i++) A[i] = B.A[i];
S = 'A' + cnt++;
}
return *this;
}
Bool& Bool :: operator &= (const Bool & B) //ok
{
for (int i=0; i<N; i++)
A[i] &= B.A[i];
return *this;
}
Bool Bool :: operator & (const Bool& B) const
{
Bool C(*this);
return (C &= B);
}
Bool& Bool :: operator |= (const Bool & B)
{
for (int i=0; i<N; i++)
A[i] |= B.A[i];
return *this;
}
Bool Bool :: operator | (const Bool& B) const
{
Bool C(*this);
return (C |= B);
}
Bool Bool :: operator ~ ()const
{
Bool C;
for (int i=0; i<N; i++) C.A[i] = !A[i];
return C;
}
//Файл list.cpp
#pragma once
#include "../includesH/AllClasses.h"
ListSet :: ListSet(): Head(nullptr), S('A'+cnt++), n(0) {}
ListSet::ListSet(char* array): S('A' + cnt++), n(0), Head(nullptr)
{
//сюда не может попасть пустой массив
Head = new List(array[0]); //голова списка
n++;
List *buff = Head;
for(int i = 1; array[i]; i++, n++)
{
buff->next = new List(array[i]);
buff = buff->next;
}
this->Show();
}
ListSet::ListSet(const ListSet& B): n(B.n), S(B.S)
{
Head = nullptr; //this->Head = nullptr;
if(B.Head != nullptr)
Head = new List(B.Head->ch); //выделение памяти для первого узла
List* buff = nullptr; //отвечает за оригинал
List* buffB = nullptr;//отвечает за копируемое
if(Head != nullptr)
{
buff = Head;
buffB = B.Head->next;
}
for(; buffB != nullptr; buff=buff->next, buffB = buffB->next)
buff->next = new List(buffB->ch); //в оригинал заносятся данные из копии
}
/* Пересечение множеств */
ListSet ListSet::operator & (const ListSet& B) const
{
ListSet res;
bool f;
List* buffThis = nullptr;
List* buffRes = nullptr;
for(List* buffB = B.Head; buffB != nullptr; buffB = buffB->next)
{
for(buffThis = this->Head, f = false; buffThis != nullptr && !f; buffThis = buffThis->next)
if(buffThis->ch == buffB->ch)
f = true;
if(f)
if(res.Head == nullptr)
{
res.Head = new List(buffB->ch);
buffRes = res.Head;
}
else
{
buffRes->next = new List(buffB->ch);
buffRes = buffRes->next;
}
}
return res;
}
ListSet ListSet::operator | (const ListSet& B) const
{
ListSet res(*this);
bool f;
List* buffThis = nullptr;
for(List* buffB = B.Head; buffB != nullptr; buffB = buffB->next)
{
for(buffThis = res.Head, f = true; buffThis != nullptr; buffThis = buffThis->next)
if(buffThis->ch == buffB->ch)
f = false;
if(f)
{
buffThis = res.Head;
res.Head = new List(buffB->ch, buffThis);
}
}
return res;
}
ListSet& ListSet::operator = (const ListSet & B)
{
if (this != &B)
{
delete Head;
Head = nullptr;
n = 0;
for (List* p = B.Head; p; p = p->next)
Head = new List(p->ch, Head), ++n;
S = 'A' + cnt++;
}
return *this;
}
ListSet ListSet::operator ~ ()const
{
ListSet C;
int i=0;
for (char c = Universum[i]; Universum[i] != '\0'; i++)
{
c=Universum[i];
bool f = true;
for (List* j = Head; j && f; j = j->next)
if(c == j->ch) f = false;
if (f)
C.Head = new List(c, C.Head) , ++C.n;
}
return C;
}
void ListSet :: Show()
{
List *C = this->Head;
cout <<S<< " = [";
while (C != nullptr)
{
cout << C->ch;
C = C->next;
}
cout << "]\n";
}
//Файл word.cpp
#pragma once
#include "../includesH/AllClasses.h"
Word :: Word(): S('A'+cnt++), w(0) {}
Word::Word(char* Arr): S('A'+cnt++), w(0)
{
for (int i=0; Arr[i]; i++)
w |= (1 << ((Arr[i] <= '9')? Arr[i]-'0' : Arr[i]-'a'+10));
(*this).Show();
}
Word :: Word(const Word& B): S('A'+cnt++), w(0)
{
w = B.w;
}
Word& Word :: operator = (const Word& B)
{
if (this != &B)
{
w = B.w;
S = 'A' + cnt++;
}
return *this;
}
Word Word :: operator & (const Word& B) const
{
Word C(*this);
C.w &= B.w;
return C;
}
Word Word :: operator | (const Word& B) const
{
Word C(*this);
C.w |= B.w;
return C;
}
Word Word :: operator ~ () const
{
Word C;
C.w = ~w;
return C;
}
Санкт-Петербург
2020