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

1. Постановка задачи:

1) Определить класс-контейнер МНОЖЕСТВО с элементами типа int.

2) Реализовать конструкторы, деструктор, операции ввода-вывода, операцию присваивания.

3) Реализовать следующие перегруженные операции:

• [] – доступа по индексу;

• int() – определение размеров множества;

• + - объединение множеств;

• ++ – переход вправо к следующему элементу (с помощью класса-итератора).

4) Реализовать класс-итератор. Реализовать с его помощью операции последовательного доступа.

5)Написать тестирующую программу, иллюстрирующую выполнение операций.

2. Описание класса-контейнера.

class My_Set

{

int size; //размер множества

int *data; //указатель на массив значений элементов множества

Iterator begin; //указатель на первый элемент множества

Iterator end; //указатель на элемент, следующий за последним

public:

My_Set(); //Конструктор - пустое множество

My_Set(int n); //Конструктор с параметром типа int

My_Set(My_Set& set1); //конструктор с параметром типа My_Set

~My_Set(); //деструктор

My_Set& operator=(My_Set & set1); //перегруженный оператор присваивания

int operator[](int n); //перегруженный оператор обращения к элементу множества

int operator() (); //размер множества

My_Set operator+ (My_Set& set1); //перегруженный оператор объединения множеств

friend istream& operator >>(istream& input,My_Set& set1); //перегруженный оператор ввода

friend ostream& operator <<(ostream& output,My_Set& set1); //перегруженный оператор вывода

Iterator first() {return begin;} //извлекает указатель на первый элемент

Iterator last() {return end;} //извлекает указатель на элемент, следующий за последним

};

3) Описание компонентных и дружественных функций.

//Конструктор пустого множества

My_Set::My_Set()

{

size=0;

data=0;

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

begin.element=&data[0];

end.element=&data[size];

}

//конструктор с параметром типа int

My_Set::My_Set(int n)

{

size=n;

data=new int[size];

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

data[i]=i;

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

begin.element=&data[0];

end.element=&data[size];

}

My_Set::My_Set(My_Set& set1) //конструктор с параметром типа My_Set

{

size=set1.size;

data=new int[size];

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

data[i]=set1.data[i];

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

begin.element=&data[0];

end.element=&data[size];

}

My_Set::~My_Set() //деструктор

{

delete[] data;

size=0;

}

My_Set& My_Set::operator=(My_Set& set1) //перегруженный оператор присваивания

{

if (this==&set1)

return *this; //проверка на самоприсваивание

if (size!=0)

delete [] data;

size=set1.size;

data=new int[size];

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

data[i]=set1.data[i];

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

begin.element=&data[0];

end.element=&data[size];

return *this;

}

int My_Set::operator[](int n) //перегруженный оператор обращения к элементу множества

{

if (n<0 || n>=size)

{

cout<<"Index out of range"<<endl;

}

else

return data[n];

}

int My_Set::operator() () //длина множества

{

return size;

}

My_Set My_Set::operator+ (My_Set& set1) //перегруженный оператор объединения множеств

{

int newsize=0,i1=0,i2=0;

int *un;

un=new int[size+set1.size+1];

//******Слияние упорядоченных множеств*********

while (i1<size && i2<set1.size)

{

if (data[i1]==set1.data[i2])

{

un[newsize++]=data[i1++];

i2++;

}

else

{

if (data[i1]>set1.data[i2])

un[newsize++]=set1.data[i2++];

else

if (data[i1]<set1.data[i2])

un[newsize++]=data[i1++];

}

}

for (int i=i1;i<size;i++)

un[newsize++]=data[i];

for (int i=i2;i<set1.size;i++)

un[newsize++]=set1.data[i];

//*****************************************

My_Set set2(newsize);

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

set2.data[i]=un[i];

delete [] un;

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

set2.begin.element=&(set2.data[0]);

set2.end.element=&(set2.data[size]);

return set2;

}

istream& operator>>(istream& input,My_Set& set1) //перегруженный оператор ввода

{

int s,n,realsize,i,j,j1;

int *all;

cout<<"input size"<<endl;

input>>s;

if (s<0)

{

cout<<"Incorrect size"<<endl;

return input;

}

all=new int[s];

cout<<"input data"<<endl;

//****Ввод с упорядочением****

realsize=0;

for (i=0;i<s;i++)

{

input>>n;

j=0;

while (all[j]<n && j<realsize)

j++;

if (all[j]!=n)

{

for(j1=realsize;j1>j;j1--)

all[j1]=all[j1-1];

all[j]=n;

realsize++;

}

}

//*****************************

if (realsize!=set1.size)

{

My_Set set2(realsize);

set1=set2;

}

set1.size=realsize;

for (i=0;i<realsize;i++)

set1.data[i]=all[i];

delete [] all;

return input;

}

ostream& operator <<(ostream& output,My_Set& set1) //перегруженный оператор вывода

{

for (int i=0;i<set1.size;i++)

output<<set1.data[i]<<" ";

return output;

}

4. Описание класса-итератора.

class Iterator

{

int *element; //указатель на элемент вектора

friend class My_Set; //объявление класса My_Set как дружественного

public:

Iterator() {element=0;} //создание пустого указателя

Iterator(Iterator& itt1) {element=itt1.element;} //создание указателя-копии

int& operator* () {return *element;} //перегруженный оператор разыменования указателя

int operator ==(Iterator& itt1) {return element==itt1.element;} //перегруженный оператор равенства

int operator !=(Iterator& itt1) {return element!=itt1.element;} //перегруженный оператор неравенства

Iterator& operator ++(int n); //сдвиг указателя на 1 позицию вправо

};

Компонентная функция класса-итератора.

/сдвиг указателя на одну позицию вправо

Iterator& Iterator::operator ++(int n)

{

element++;

return *this;

}

5. Функция main()

void main()

{

char ch;

My_Set a(5),b;

// создание множества с 5 элементами и пустого множества

cin>>b; //ввод множества b

cout<<a<<endl; //вывод множества a

cout<<b<<endl; //вывод множества b

cout<<"Size of set b is "<<b()<<endl; //размер множества b

My_Set d(a); //создание множества-копии из множества a

d=b+a; //множеству d присваивается объединение множества a и множества b

cout<<d<<endl; //вывод множества d

Iterator itt1,itt2;

itt1=d.first();

itt2=b.first();

cout<<"First elements of sets b and d are "<<*itt2<<" "<<*itt1<<endl; //первые элементы множеств

cout<<"Set d"<<endl;

while (itt1!=d.last())

{

cout<<*itt1<<" "; //вывод очередного элемента

itt1++; // смещение к следующему элементу

}

cout<<endl;

cout<<"Press any key";

cin>>ch;

}

6. Результат работы программы:

input size

4

input data

1 5 2 9

0 1 2 3 4

1 2 5 9

Size of set b is 4

0 1 2 3 4 5 9

First elements of sets b and d are 1 0

Set d

0 1 2 3 4 5 9

Press any key

7.

1) Абстрактным называется тип данных, определяемый через операции, которые можно совершать над его содержимым. Представление содержащихся данных не имеет значения.

Примерами абстрактных типов могут служить функция или класс в C++.

2) Примером абстракции через параметризацию может являться функция.

3) Примером абстракции через спецификацию является класс.

4) Контейнером называется объект, содержащий набор однотипных элементов. Примерами контейнеров могут быть массив и список.

5) Основные группы операций с контейнерами:

• операции доступа;

• операции добавления;

• операции поиска;

• операции объединения.

6) Доступ к элементам контейнера может быть последовательным, прямым или ассоциативным. Пример последовательного доступа – линейный список, пример произвольного доступа – массив.

7) Итератор – это объект, который обеспечивает последовательный доступ к элементам контейнера.

8) Итератор можно реализовать как набор функций – членов класса-контейнера или как самостоятельный класс.

9) Объединение контейнеров может быть реализовано следующими способами:

• сцепление (последовательное добавление данных из второго контейнера);

• добавление в упорядоченный набор с сохранением порядка;

• добавление только элементов, не содержащихся в первом контейнере (объединение множеств).

• добавление только элементов, содержащихся в обоих контейнерах (пересечение множеств).

• удаление из первого контейнера данных, содержащихся во втором (вычитание множеств)

• извлечение части контейнера.

10) Контейнер, состоящий из элементов «ключ-значение» предоставляет ассоциативный доступ к данным.

11) Контейнер, в котором вставка и удаление элементов выполняется на одном конце, называется стек.

12) d int mas[100] – контейнер-массив из 100 элементов.

13) d int mas – переменная типа int, не являющаяся контейнером.

14) Доступ к элементам динамического массива будет прямым.

15) Доступ к линейному списку будет последовательным.