ООП - Лабораторные работы. Учебнометодическое пособие для студентов механикоматематического факультета минск бгу 2005 2 удк 681. 142. 2(072)

• Название: Учебнометодическое пособие для студентов механикоматематического факультета минск бгу 2005 2 удк 681. 142. 2(072)
• Анкор: ООП - Лабораторные работы.pdf
• Дата: 17.05.2018
• Размер: 0.65 Mb.
• Имя файла: ООП - Лабораторные работы.pdf
• Тип: Учебно-методическое пособие; #19356
• страница: 2 из 4

Тема. Классы для работы с динамическими структурами
данных
Теоретическое введение. Объекты классов могут храниться в ви- де массивов или динамических связных списков. Если класс содержит конструктор, массив может быть инициализирован, причем конструктор вызывается столько раз, сколько задается элементов массива: samp ob[4]={1,2,3,4};
Список инициализации – это сокращение общей конструкции:
samp ob[4]={samp(1,2),samp(3,4),samp(5,6),samp(7,8)};
При создании динамических объектов используется оператор new, который вызывает конструктор и производит инициализацию. Для разрушения динамического объекта используется оператор delete, который может помещаться в деструкторе.
Кроме указателей на классы используются ссылки. Ссылка является скрытым указателем и работает как другое имя переменной.
При передаче объекта через ссылку в функцию передается адрес объекта и не делается его копия. Это уменьшает вероятность ошибок, связанных с выделением динамической памяти и вызовом деструктора. Так, при передаче в функцию параметра-объекта может возникнуть ошибка из-за разрушения деструктором на выходе копии объекта, которая должна быть исправлена созданием конструктора копирования. В такой ситуации лучше передать в функцию ссылку на объект и возвратить ссылку на объект.
Пример. Создается класс Tree (бинарное дерево). Информацион- ная часть узла дерева содержит целое число. Тестирование класса вы- полняется с помощью меню, которое позволяет сформировать дерево, вывести содержимое его узлов в порядке возрастания, найти узел по ключу, вывести содержимое листьев дерева (вершин, не имеющих по- томков).
#include"vip\menu.cpp" //реализация работы с меню
#include
#include
#include char bufRus[256]; char*Rus(const char*text){
CharToOem(text,bufRus); return bufRus;} struct node
{ int n; //информационное поле узла дерева

20 int count; node*left,*right;
}; class Tree
{ public: node*root;
Tree(){root=0;}
Tree(int t); // Формирование дерева из t случайных чисел void CopyTree(node*&rootnew,node*rootold);
/* Копирует дерево с корнем rootold в дерево с корнем rootnew. В результате деревья находятся в различных динамических участках памяти.*/
Tree(const Tree&ob); //конструктор копирования
// Рекурсивная функция, используемая в деструкторе (освобождение памяти) void DelTree(node *wer);

Tree(){DelTree(root);} void Push(node*&wer,int data);// Вставка элемента в дерево void Look(node*wer); //- Вывод дерева на экран node*Find(node*wer,int key); // Поиск по ключу void PrintLeaves(node *wer); // Вывод листьев дерева на экран
};
//********************** Tree::Tree(int t) *******************
Tree::Tree(int t)
{ root=0; for(int i=0;i Push(root,random(10)-5);
} void Tree::CopyTree(node*&rootnew,node*rootold)
{ if(rootold->left!=0)
{Push(rootnew,(rootold->left)->n);CopyTree(rootnew,rootold->left);} if(rootold->right!=0)
{Push(rootnew,(rootold->right)->n);CopyTree(rootnew,rootold->right);}
}
Tree::Tree(const Tree&ob)
{ if(ob.root==0)root=0; else { root=new node; root->n=ob.root->n; root->count=1; root->left=0; root->right=0;
CopyTree(root,ob.root);
}
}

21 void Tree::DelTree(node *wer)
{ if(wer->left!=0)DelTree(wer->left); if(wer->right!=0)DelTree(wer->right); delete wer;
} void Tree::Push(node*&wer,int data)
{ if(wer==0)
{ wer=new node; wer->n=data; wer->left=0;wer->right=0; wer->count=1;
} else if(datan)Push(wer->left,data); else if(data>wer->n)Push(wer->right,data); else wer->count++;
} void Tree::Look(node*wer)
{ if(wer!=0)
{
Look(wer->left); cout<n<<" - "<count; cout< Look(wer->right);
}
} node* Tree::Find(node*wer,int key)
{ if(wer==0) return 0; else if(keyn) return Find(wer->left,key); else if(key>wer->n) return Find(wer->right,key); else return wer;
} void Tree::PrintLeaves(node *wer)
{ if(wer==0)return; else if( (wer->left==0)&&(wer->right==0) ) { cout<n<<”-“<count; cout< } else
{
PrintLeaves(wer->left);
PrintLeaves(wer->right);

22
}
}
//-------------------------------- MAIN ---------------------------------------- int main(int argc, char* argv[])
{
Tree tr; node *u; int k=0,max,kol; char menu[][100]={ {" PushElement "}, {" ShowTree "}, {" FindElement "},
{" PrintLeaves "}, {" EXIT "}, }; kol=5;//КОЛИЧЕСТВО СТРОК МЕНЮ. Используется в выравнивании строк
// меню по центру.
//------------------ВЫРАВНИВАНИЕ СТРОК МЕНЮ ПО ЦЕНТРУ---------------- max=viravnivaniestrok(menu,kol);
//------------------------ МЕНЮ НА ЭКРАНЕ--------------------------------------- textmode(C80); while(1){ switch(mmm(kol,menu,max,k))
{ case 0: { int data; cout<>data; tr.Push(tr.root,data); k=0;break;
} case 1: { if(tr.root==0)cout< { cout< } while(!kbhit()); k=1;break;
} case 2: { if(tr.root==0)cout< { int key; cout<>key; if((u=tr.Find(tr.root,key))!=0){ cout<count<

23
} else cout< } while(!kbhit()); k=2;break;
} case 3: { if(tr.root==0)cout< } while(!kbhit()); k=3;break;
} case 4:{ exit(0);
}
} } return 0;
}
Задания для самостоятельного решения
При решении задач необходимо описать класс, который использу- ется для представления элементов динамической структуры данных.
Затем разрабатывается класс для работы с используемой динамиче- ской структурой данных, которая при тестировании класса может быть построена путем ввода данных: a) с клавиатуры; б) из файла.
Возможны два варианта решения: а) динамическая структура данных постоянно хранится в памяти; б) динамическая структура данных хранится в файле.
1. Создать класс для работы со стеком. Элемент стека – действи- тельное число. Применить класс для вывода возрастающих серий по- следовательности действительных чисел: a) в обратном порядке; б) в том же порядке (серия – упорядоченная последовательность макси- мальной длины).
2. Построить класс для работы со стеком. Элемент стека – целое число. Ввести две неубывающие последовательности чисел в два сте- ка. Использовать третий стек для слияния двух последовательностей в одну неубывающую.
3. Создать класс для работы со стеком. Элемент стека – символ.
Сформировать два стека, содержащие последовательности символов.
Подсчитать общее число элементов в стеках, предусмотреть восста- новление их исходного расположения.

24 4. Создать класс для работы со стеком. Элемент стека – символ.
Использовать стек для проверки правильности расстановки скобок трех типов (круглых, квадратных и фигурных) в выражении.
5. Построить класс для работы с односвязным списком. Элемент списка – действительное число. Сформировать список, содержащий неубывающую последовательность чисел, и преобразовать его так, чтобы последовательность была невозрастающей. Для этого необхо- димо совершить переворот списка, т. е. такую переустановку указате- лей в списке, при которой элементы его следуют друг за другом в об- ратном порядке.
6. Построить класс для работы с односвязным списком. Элементы списка – целые числа. Сформировать список, упорядочить элементы списка по возрастанию, используя сортировку: a) методом выбора; б) методом пузырька; в) методом вставки.
7. Построить класс для работы с односвязным списком. Элементы списка – действительные числа. Создать два упорядоченных по невоз- растанию списка, слить их в один (также упорядоченный по невозрас- танию), построив новый список.
8. Построить класс для работы с односвязным списком. Элементы списка – слова. Создать список, содержащий некоторую последова- тельность слов. Заменить в списке каждое вхождение заданного слова другим (также заданным).
9. Построить класс для работы с односвязным списком. Создать два списка: List1 и List2. Проверить, содержатся ли элементы списка
List1 в списке List2 в указанном списком List1 порядке.
10. Построить класс для работы с односвязным списком. Элемен- ты списка – целые числа. Создать список List1. Построить список
List2, содержащий порядковые номера максимальных элементов спи- ска List1.
11. Построить класс для работы с двусвязным списком. Элементы списка – действительные числа. Создать список List1, содержащий последовательность
1 2
, , ... ,
n
x
x
x . Построить список List2, содержа- щий последовательность
1 2
1 1
, , ,
, ..., ,
n
n
n
x x
x
x
x
x

12. Создать класс для работы с бинарным деревом, узлы которого содержат целые числа. Построить дерево, затем копию дерева. Под- считать число листьев в нем (листьями называются узлы, не содержа- щие поддеревьев).
13. Построить класс для работы с бинарным деревом, узлы которо- го содержат действительные числа. Создать дерево. Определить высо- ту дерева (максимальное число узлов, принадлежащих пути от корня

25 дерева до любого из его листьев). Подсчитать число элементов, рав- ных максимальному.
14. Построить класс для работы с бинарным деревом, узлы которо- го содержат действительные числа. Создать дерево для заданной по- следовательности чисел. Используя его, упорядочить последователь- ность по возрастанию, убыванию.
15. Построить класс для работы со списком. Элемент списка со- держит информацию о заявке на авиабилет: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета.
Программа должна обеспечивать: хранение всех заявок в виде списка, добавление заявок в список, удаление заявок, вывод заявок по заданному номеру рейса и дате вылета, вывод всех заявок.
16. Построить класс для работы с бинарным деревом, узел которо- го содержит информацию о заявках на авиабилеты (в последователь- ности, используемой для упорядочения заявок): желаемую дату выле- та, номер рейса, фамилию и инициалы пассажира, пункт назначения.
Программа должна обеспечивать: хранение всех заявок в виде би- нарного дерева, добавление заявок, удаление заявок, вывод заявок по заданному номеру рейса и дате вылета, вывод всех заявок.
17. Построить класс для работы со списком, который содержит динамическую информацию о наличии автобусов в парке: номер ав- тобуса, фамилию и инициалы водителя, номер маршрута, признак ме- стонахождения автобуса – на маршруте или в парке.
Программа должна обеспечивать: начальное формирование спи- ска, введение номера автобуса при выезде и установление программой значения признака «автобус на маршруте». Аналогичным образом из- меняется информация об автобусе при его возвращении в парк. По за- просу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.
18. Решить предыдущую задачу, используя не список, а бинарное дерево.
19. Построить класс для работы с бинарным деревом, содержащим англо-русский словарь.
20. Построить класс для работы со списком, содержащим инфор- мацию о поездах дальнего следования. Элемент списка содержит сле- дующую информацию о поезде: номер поезда, станция назначения, время отправления.
Составить программу, которая обеспечивает первоначальное фор- мирование списка, производит вывод списка, вводит номер поезда и

26 выводит информацию о нем, вводит название станции назначения и выводит данные о всех поездах, следующих до этой станции.
Тесты
1. На каком этапе (компиляция, выполнение) происходит выделение памяти под динамические структуры данных (ДСД)?
2. Какие основные операции выполняются над следующими ДСД:
1) стек;
2) односвязный список;
3) односвязная очередь;
4) двусвязная очередь;
5) бинарное дерево?
3. Есть ли ошибки в деструкторе дерева:
Tree(){del_tree(root);} void del_tree(Node *root){ if(!root){ delete root; del_tree(root->left); del_tree(root->right);}} ?
4. Есть ли ошибки в деструкторе списка:
List(){
Node *V; if(begin){
V=begin; while(V){ delete V;
V=V->next;}}} ?
Здесь begin – указатель на начало списка.
Лабораторная работа № 4
Тема. Шаблоны классов
Теоретическое введение. С помощью шаблонов можно создавать родовые (generic) функции и классы. Родовая функция определяет базовый набор операций, которые будут применяться к разным типам данных, получаемых функцией в качестве параметра.
Определение функции с ключевым словом template (шаблон) имеет вид:
templateTtype>тип имя_функции(список аргументов)
{//тело функции}
Здесь Ttype – фиктивный тип, который используется при объявлении аргументов и локальных переменных функции.
Компилятор заменит этот фиктивный тип на один из реальных и создаст соответственно несколько перегружаемых функций. При этом перегружаемые функции являются ограниченными, поскольку выполняют одни и те же действия над данными различных типов.

27
С помощью шаблона класса можно создать класс, реализующий стек, очередь, дерево и т. д. для любых типов данных. Компилятор будет генерировать правильный тип объекта на основе типа, задаваемого при создании объекта. Общая форма объявления шаблона класса:
template Ttype> class имя_класса {
//имена класса, поля класса
}
Здесь Ttype – фиктивное имя типа, которое заменится компилятором на фактическое. Шаблон класса может иметь больше одного родового типа данных:
template class m {Type1 a;Type2 b;}
Пример. Создается шаблон класса для работы с односвязным спи- ском. Тестирование класса выполняется с использованием меню, ко- торое позволяет создать список из чисел типов integer, float, double и выполнить типичные операции с ним.
#include
#include
#include
#include"vip\menu.cpp" void ListForInt(); void ListForFloat(); void ListForDouble(); char bufRus[256]; char*Rus(const char*text){
CharToOem(text,bufRus); return bufRus;
}
//шаблон класса для работы с односвязным списком templateclass List {
//внутренний класс, для представления элементов списка class Node{ public: mytype d;
Node* next;
Node(mytype dat=0){d=dat; next=0;}
};
Node* pbeg; //указатель на начало списка public:
List(){pbeg=0;} //конструктор
List(); //деструктор
Node * Add(mytype d); //добавление в конец списка
Node * Find(mytype key); //поиск по ключу
Node * Insert(mytype key,mytype d); //вставка узла d после узла с

28
// ключом key bool Remove(mytype key); //удаление узла void Print(); //печать списка
};
//*********************List() *************************
//ДЕСТРУКТОР. Освобождает память для всех узлов списка template List::List(){ if(pbeg!=0){
Node* pv=pbeg; while(pv){ pv=pv->next; delete pbeg; pbeg=pv;
}
}
}
//*************************** void Add(mytype d) **********
//Добавляет узел в конец списка и возвращает указатель
// на вставленный узел. template List::Node*
List::Add(mytype d){
Node* pv=new Node(d); //Создание нового узла if(pbeg==0)pbeg=pv; //первый узел списка else {
Node* rab=pbeg; while(rab!=0){ if((rab->next)==0){rab->next=pv;return pv;} rab=rab->next;
}
}
}
//*************************** Node* Find(mytype key)
//Выполняет поиск узла с заданным ключом и возвращает указатель
// на него в случае успешного поиска и 0 в случае отсутствия узла в списке template List::Node*
List::Find(mytype key){
Node* pv=pbeg; while(pv){ if((pv->d)==key)break; pv=pv->next;
} return pv;
}
//************* Node* Insert(mytype key,mytype d)
//Вставляет в список узел после узла с ключом key и возвращает
// указатель на вставленный узел. Если такого узла в списке нет,
// вставка не выполняется и возвращается значение 0

29 template List::Node*
List::Insert(mytype key,mytype d){ if(Node* pkey=Find(key)) //поиск узла с ключом key
{
Node* pv=new Node(d);
//выделение памяти под новый узел и его инициализация pv->next=pkey->next;
//установление связи нового узла с последующим pkey->next=pv; //установление связи предыдущего узла с новым return pv;
} return 0;
}
//******************* bool Remove(mytype key)
//Удаляет узел с заданным ключом из списка и возвращает значение true при
//успешном удалении и false, если узел с таким ключом не найден template bool List::Remove(mytype key){ if(Node* pkey=Find(key)){ if(pkey==pbeg)pbeg=pbeg->next; //удаление из начала списка else{ //Находим указатель на узел,
Node*rab=pbeg; //стоящий в списке перед while(rab) //удаляемым узлом.
{ //rab-этот указатель. if((rab->next)==pkey)break; rab=rab->next;
} rab->next=pkey->next;
} delete pkey; return true;
} return false;
}
//******************** void Print() -Печать списка template void List::Print(){
Node*pv=pbeg; cout<d<<' '; pv=pv->next;
} cout<//--------------------------- MAIN --------------------------------------------- int main(int argc, char* argv[]){ int k=0,max,kol; char menu[][100]= {{" ListForInt "}, {" ListForFloat "},
{" ListForDouble "}, {" EXIT "}, };

30 kol=4; //КОЛИЧЕСТВО СТРОК МЕНЮ. Это используется в выравнивании
//строк меню по центру.
//----ВЫРАВНИВАНИЕ СТРОК МЕНЮ ПО ЦЕНТРУ------------------ max=viravnivaniestrok(menu,kol);
//----------------- МЕНЮ НА ЭКРАНЕ--------------------------------------- textmode(C80); while(1){ switch(mmm(kol,menu,max,k))
{ case 0: {
ListForInt(); k=0;break;
} case 1: {
ListForFloat(); k=1;break;
} case 2: {
ListForDouble(); k=2;break;
} case 3:{ exit(0);
}
}
} return 0;
}
//*************************** void ListForInt()
//Эта функция вызывается из главного меню. void ListForInt(){
Listl1; int k=0,max,kol; char menu[][100]=
{ {" PrintList "}, {" Add "}, {" Find "}, {" Insert "},
{" Remove "}, {" EXIT "}, {" Back "} }; kol=7; //КОЛИЧЕСТВО СТРОК МЕНЮ. max=viravnivaniestrok(menu,kol);
//------------------------ МЕНЮ НА ЭКРАНЕ----------------------------- textmode(C80); while(1){ switch(mmm(kol,menu,max,k))
{ case 0: { l1.Print(); while(!kbhit()) k=0;break;} case 1: { cout<

31 int t;cin>>t; if( (l1.Add(t)) )cout<>t; if(l1.Find(t))cout<>t; cout<>key; if( (l1.Insert(key,t)) )cout<>t; if( (l1.Remove(t)) )cout< } } }
Таким же образом, как и функция ListForInt(), реализуются функ- ции ListForFloat() и ListForDouble(), предназначенные для тестирова- ния списков из чисел типа float и double, соответственно.
Задания для самостоятельного решения
Для разработки шаблонов классов можно использовать результаты выполнения лабораторных работ № 2 и № 3. При тестировании со- зданных шаблонов классов необходимо создавать объекты с различ- ными допустимыми значениями параметров шаблона (например, ком- поненты вектора могут быть целыми, действительными или ком- плексными числами).
1. Создать шаблон класса для работы со стеком. Применить его для решения задач № 1 – 4 (лаб. работа № 3).

32 2. Создать шаблон класса для работы с одномерным массивом.
Выполнить тестирование путем создания и обработки массивов, со- держащих элементы различных типов (например, сортировка эле- ментов массивов различными методами).
3. Создать шаблон класса Vector размерности n (см. задачу № 3, лаб. работа № 2).
4. Создать шаблон класса «Квадратная матрица» – Matrix раз- мерности n

n (см. задачу № 4, лаб. работа № 2).
5. Создать шаблон класса Polynom степени n (см. задачу № 5, лаб. работа № 2) или создать шаблон класса для работы с односвяз- ным списком. Применить его для решения задачи № 5 (лаб. работа № 3).
6. Создать шаблон класса для работы с односвязным списком.
Применить шаблон класса для решения задачи № 6 (лаб. работа № 3).
7. Создать шаблон класса для работы с односвязным списком.
Применить шаблон класса для решения задачи № 7 (лаб. работа № 3).
8. Создать шаблон класса для работы с бинарным деревом. При- менить его для сортировки действительных чисел и строк, вводимых с клавиатуры или из файла.
9. Создать шаблон класса Set (множество) мощности n (см. зада- чу № 9, лаб. работа № 2 ) или создать шаблон класса для работы с односвязным списком. Применить шаблон класса для решения зада- чи № 9 (лаб. работа № 3).
10. Создать шаблон класса для работы с односвязным списком.
Применить шаблон класса для решения задачи № 10 (лаб. работа № 3).
11. Создать шаблон класса, обеспечивающего описание матрицы заданного размера n

m и любого минора в ней (см. задачу № 11, лаб. работа № 2) или создать шаблон класса для работы с двусвязным списком. Применить шаблон класса для решения задачи № 11 (лаб. работа № 3).
12. Создать шаблон класса для работы с бинарным деревом. При- менить шаблон класса для решения задачи № 12 (лаб. работа № 3).
13. Создать шаблон класса для работы с бинарным деревом. При- менить шаблон класса для решения задачи № 13 (лаб. работа № 3).
14. Создать шаблон класса для работы с двусвязным списком.
Применить шаблон класса для решения задачи № 15 (лаб. работа № 3).

33 15. Создать шаблон класса для работы с односвязным списком.
Применить шаблон класса для решения задачи № 16 (лаб. работа № 3).
Тесты
1. Отметьте все утверждения, которые считаете верными:
1) нельзя с помощью шаблона создать функцию с таким же именем, как у яв- но определенной функции;
2) цель введения шаблонов – создание функций, которые могут обрабатывать однотипные данные;
*3) при использовании шаблонов функций возможна перегрузка как с по- мощью шаблонов, так и функций;
*4) в качестве описания шаблона функции используется прототип шаблона:
_
_
template список параметров шаблона
2. Можно ли задать шаблон со значением параметра по умолчанию?
Варианты ответа:
*1) да; 2) нет.
3. Каков правильный заголовок шаблона?
Варианты ответа:
*1) template; 2) template ; 3) template ;
4. Сколько параметров может быть у шаблона при определении шаблона функции?
Варианты ответа:
1) 1; 2) столько, сколько аргументов у функции; *3) столько, сколько типов ис- пользуется для параметризации.
5. Отметьте правильный вариант описания шаблона семейства функций:
1) template(class T) void func(T* p1,T* p2){…}
2) template ; void func(T* p1,T* p2){…}
*3) template void func(T* p1,T* p2){…}
4) template void func(T* p1,T* p2){…}
6. Можно ли использовать класс-шаблон в качестве базового класса?
Варианты ответа:
*1) да; 2) нет.
Лабораторная работа № 5