Главная страница
Навигация по странице:

  • Пример. Создается класс Tree

  • Задания для самостоятельного решения

  • Лабораторная работа № 4 Тема. Шаблоны классов Теоретическое введение . С помощью шаблонов можно создавать родовые (generic)

  • Vector размерности n (см. задачу № 3, лаб. работа № 2). 4.Создать шаблон класса «Квадратная матрица» – Matrix

  • Лабораторная работа № 5

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


    Скачать 0.5 Mb.
    НазваниеУчебнометодическое пособие для студентов механикоматематического факультета минск бгу 2005 2 удк 681. 142. 2(072)
    Дата03.10.2022
    Размер0.5 Mb.
    Формат файлаpdf
    Имя файлаПракт. по классам_посмотреть.pdf
    ТипУчебно-методическое пособие
    #710353
    страница2 из 4
    1   2   3   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
    1   2   3   4


    написать администратору сайта