МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра Вычислительной техники
отчет
по лабораторной работе №2
по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»
Тема: МНОЖЕСТВО КАК ОБЪЕКТ
Студент гр.7891 |
|
Хомич В.Д. |
Преподаватель |
|
Манирагена В. |
2020
Составить и отладить программу, реализующую обработку множеств по заданию:
№ варианта |
Универсум |
Что надо вычислить |
10 |
Строчные латинские буквы |
Множество, содержащее буквы, имеющиеся в любом из множеств A или B, но отсутсвующие в C, кроме того, обязательно встречающиеся также и в D |
E = ((A ∪ B) \ C) ⋂ D)
1. Преобразовать программы, созданные по п. 1.4.2, так, чтобы множества были объектами некоторого класса, а операции над ними — функциями-членами этого класса. Добиться, чтобы функция main( ) во всех вариантах была одинакова, менялось только определение классов. Этого можно добиться вынесением определения класса и функций-членов в отдельный h-файл, сделать 4 варианта h-файлов и подменять их в проекте. Второй способ — собрать все варианты в одном h-файле и исключать ненужные включением в комментарий или с помощью препроцессорной переменной.
2. Для одного или двух (с внешней памятью и без неё) вариантов провести эксперимент по отслеживанию вызовов функций при вычислении пятого множества по четырём исходным. Для этого:
— определить для класса все служебные функции, возможно, пустые;
— вставить в каждую из них вывод сообщения о том, какое действие выполняется и для какого объекта.
Рекомендуется отследить, какие множества создаются, используются или уничтожаются каждой из функций. Для этого нужно создать для каждого множества уникальный тег, например, с помощью общего для всех множеств счётчика тегов. Чтобы увидеть уничтожение объектов, объявленных в функции main( ), необходимо заключить её содержимое в дополнительные фигурные скобки и предусмотреть system("pause") после них.
Если некоторая структура данных, например, массив, используется как реализация множества, это означает, что программист просто устанавливает для себя некоторые правила для работы с этим массивом и последовательно их придерживается. Часто большего и не требуется. Однако можно рассматривать множество как абстрактную структуру данных — область памяти, доступ к которой возможен только через некоторый интерфейс, т. е. набор функций, специально созданных для работы с этой памятью. Язык С++ поддерживает работу с абстрактными данными через механизм классов: абстрактная структура данных определяются как класс, в котором задаются как данные, так и связанные с ними операции. Определение класса позволяет расширить язык C++, включив в него множество как пользовательский тип данных. Для работы с множествами-массивами предполагается использовать такой же синтаксис, как для машинных слов. С этой целью функции объединения, пересечения и дополнения множеств объявлены с именами, содержащими ключевое слово «operator», после которого следует знак соответствующей операции. Операции языка С++ «|», «&» и «~» определены так, чтобы их можно было использовать в выражениях, состоящих из данных типа Set. Такой приём называется перегрузкой операций. Чтобы это действительно можно было возможно, функции объявлены так, чтобы была обеспечена совместимость со встроенными операциями языка С++: все функции возвращают объект типа Set, а двуместные операции в качестве аргумента (второго, потому что первый — это сам объект) имеют константную ссылку на объект типа Set. Функции не меняют объект, для которого вызываются. Для контроля за этим в каждом из объявлений после списка параметров помещён спецификатор const.
Если мы объявляем для своего типа данных для операции пересечения перегрузку знака «&», а также перегрузку присваивания «=», то это не делает автоматически доступной комбинированную операцию «&=» — пересечение и присваивание. Такую операцию нужно тоже перегружать явно. Более того, рекомендуется обязательно сделать это и сделать согласованно.
Множество — абстрактная структура данных, для которой определена операция принадлежности. Новые множества создаются из существующих с помощью операций объединения, пересечения, разности, симметрической разности.
Одним из способов задания множества является простое перечисление входящих в него элементов. В памяти ЭВМ элементы такого множества могут быть расположены в последовательности ячеек, т. е. образуют массив. Это самый экономный способ хранения множества в тех случаях, когда мощность множества известна, а его элементы — данные одного типа (во всех случаях, когда это не так, элементы множества можно расположить в памяти произвольным образом и работать с ними через указатели). Память под массив удобно выделить статически. В этом случае её можно сразу инициализировать.
Измерение времени решения задачи для разных объёмов исходных данных — важная составляющая процедуры тестирования любой программы. Для измерения времени можно применять специальные приборы (секундомер) или средства, предоставляемые системой программирования (профайлер). Но для исследования алгоритма удобнее всего организовать измерение времени в самой программе тестирования, используя для этого средства, предоставляемые системой программирования.
Функция clock( ) возвращает значение счётчика тиков внутренних часов ПЭВМ как 32-битное целое типа clock_t, что соответствует unsigned long. Для измерения времени обработки множеств нужно вызвать функцию clock( ) в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов.
Каждый тик соответствует 1/50 с, т. е. 0,017 с, следовательно, о какой-либо точности измерения времени функцией clock( ) можно говорить, если измеряемый интервал времени — порядка нескольких секунд. Чтобы добиться этого, измеряемый процесс приходится многократно повторять (до 1 000 000 раз и даже более). Полученную разность отсчётов времени можно затем разделить на количество повторений.
Чтобы измерить время таким способом, важно приспособить процесс вычислений к многократному повторению, выполнив два условия:
исходные множества не должны искажаться, их память нельзя использовать для получения результата вычислений;
не должно быть «утечки памяти» — выделения в динамической памяти большего объёма, чем освобождается после вычислений. Так, в варианте со списками до начала вычислений следует освобождать память из-под всех результатов, полученных предыдущим проходом.
Другие функции стандартной библиотеки time.h (например, функцию time( ) и т. п.) использовать нет смысла, поскольку источник информации о времени у них всех один и точность измерения у них не больше, чем у clock( ).
Для измерения времени обработки множеств нужно вызвать функцию clock( ) в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов.
Main.cpp //10 вар
/*
Строчные латинские буквы
Множество, содержащее буквы, имеющиеся в любом из множеств A или B, но отсутсвующие в C, кроме того, обязательно встречающиеся
также и в D
((A + B) - C) * D
*/
#include <iostream>
#include <clocale>
#include <stdlib.h>
#include <stdio.h>
#include <Windows.h>
#include <ctime>
#include <conio.h>
#include "set.h"
using namespace std;
int main()
{
setlocale(LC_CTYPE, "rus");
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
const int sizeb = 26;
std::system("CLS");
char ch;
char U[] = { 'a','b','c','d','e','f','g','h','i','g','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
//bitset<sizeb> A;
Set A;
Set B;
Set C;
Set D;
Set E;
Set F;
Set G;
std::system("CLS");
int c = 0;
#pragma region A
std::cout << "Введите количество элементов множества A" << endl;
std::cin >> c;
for (int i = 0; i < c; i++)
{
std::cout << "Введите элемент № " << i + 1 << " множества A строчной буквой латинского алфавита" << endl;
fflush(stdin);
ch = _getch();
if (!((int)ch >= (int)'a' && (int)ch <= (int)'z'))
{
std::cout << "!!!Строка содержит цифру или другой неподходящий символ!!!\n";
i--;
}
else
A.AddElement(ch);
}
std::cout << "Вы ввели множество А: " << endl; //Вывод множества на экран
A.ShowSet();
std::cout << "отображение на универсум А: " << endl; //Вывод множества на экран
A.ShowUniversum();
std::cout << endl;
#pragma endregion A
#pragma region B
std::cout << "Введите количество элементов множества B" << endl;
std::cin >> c;
for (int i = 0; i < c; i++)
{
std::cout << "Введите элемент № " << i + 1 << " множества B строчной буквой латинского алфавита" << endl;
fflush(stdin);
ch = _getch();
if (!((int)ch >= (int)'a' && (int)ch <= (int)'z'))
{
std::cout << "!!!Строка содержит цифру или другой неподходящий символ!!!\n";
i--;
}
else
B.AddElement(ch);
}
std::cout << "Вы ввели множество B: " << endl; //Вывод множества на экран
B.ShowSet();
std::cout << "отображение на универсум B: " << endl; //Вывод множества на экран
B.ShowUniversum();
std::cout << endl;
#pragma endregion B
#pragma region C
std::cout << "Введите количество элементов множества C" << endl;
std::cin >> c;
for (int i = 0; i < c; i++)
{
std::cout << "Введите элемент № " << i + 1 << " множества C строчной буквой латинского алфавита" << endl;
fflush(stdin);
ch = _getch();
if (!((int)ch >= (int)'a' && (int)ch <= (int)'z'))
{
std::cout << "!!!Строка содержит цифру или другой неподходящий символ!!!\n";
i--;
}
else
C.AddElement(ch);
}
std::cout << "Вы ввели множество C: " << endl; //Вывод множества на экран
C.ShowSet();
std::cout << "отображение на универсум C: " << endl; //Вывод множества на экран
C.ShowUniversum();
std::cout << endl;
#pragma endregion C
#pragma region D
std::cout << "Введите количество элементов множества D" << endl;
std::cin >> c;
for (int i = 0; i < c; i++)
{
std::cout << "Введите элемент № " << i + 1 << " множества D строчной буквой латинского алфавита" << endl;
fflush(stdin);
ch = _getch();
if (!((int)ch >= (int)'a' && (int)ch <= (int)'z'))
{
std::cout << "!!!Строка содержит цифру или другой неподходящий символ!!!\n";
i--;
}
else
D.AddElement(ch);
}
std::cout << "Вы ввели множество D: " << endl; //Вывод множества на экран
D.ShowSet();
std::cout << "отображение на универсум D: " << endl; //Вывод множества на экран
D.ShowUniversum();
std::cout << endl;
#pragma endregion D
clock_t timeCheck = clock();
E = A | B;
F = E / C;
G = F & D;
timeCheck = clock() - timeCheck;
std::cout << "Обработка ((A + B) - C) * D с использованием отображения на Универсум заняла " << timeCheck / (double)CLOCKS_PER_SEC << "сек" << endl;
std::cout << "Отображение E = A | B: " << endl; //Вывод множества на экран
E.ShowSet();
std::cout << "Отображение на универсум E: " << endl; //Вывод множества на экран
E.ShowUniversum();
std::cout << endl;
std::cout << "Отображение F = E / C: " << endl; //Вывод множества на экран
E.ShowSet();
std::cout << endl;
std::cout << "Отображение на универсум F: " << endl; //Вывод множества на экран
E.ShowUniversum();
std::cout << endl;
std::cout << "Отображение G = F & D: " << endl; //Вывод множества на экран
G.ShowSet();
std::cout << endl;
std::cout << "Отображение на универсум G: " << endl; //Вывод множества на экран
G.ShowUniversum();
std::cout << endl;
system("pause");
return 0;
} set.h
#pragma once
#include <iostream>
const char U[] = { 'a','b','c','d','e','f','g','h','i','g','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
const int sizeb = 26;
class Set
{
public:
Set();
Set(const Set &other);
Set& operator=(const Set& other);
friend Set operator|(const Set& A, const Set& B);
friend Set operator&(const Set& A, const Set& B);
friend Set operator/(const Set& A, const Set& B);
friend Set operator~(const Set& A);
void AddElement(char element);
void ClearList();
void ShowSet();
void ShowUniversum();
protected:
private:
long int data;
};
Set::Set()
{
data = 0;
}
Set::Set(const Set & other)
{
this->data = other.data;
}
Set& Set::operator=(const Set& other)
{
this->data = other.data;
return *this;
}
void Set::AddElement(char element)
{
this->data |= 1 << ((int)element - (int)'a');
}
void Set::ClearList()
{
this->data = 0;
}
Set operator|(const Set& A, const Set& B)
{
Set C = Set(A);
C.data |= B.data;
return C;
}
Set operator&(const Set& A, const Set& B)
{
Set C = Set(A);
C.data &= B.data;
return C;
}
Set operator/(const Set& A, const Set& B)
{
Set C = Set(A);
C.data &= ~B.data;
return C;
}
Set operator~(const Set& A)
{
Set C = Set(A);
C.data &= ~A.data;
return C;
}
void Set::ShowSet()
{
for (int i = 0; i < sizeb; i++)
if ((this->data >> i) & 1 == 1) std::cout << U[i];
std::cout << std::endl;
}
void Set::ShowUniversum()
{
for (int i = 0; i <= sizeb; i++)
std::cout << ((this->data >> i) & 1);
std::cout << std::endl;
}