Разработка шаблонов структуры данных в памяти

Lab4.cpp

#include "tmplt.h"

int main(int argc, char* argv[])

{

            int a=1,b=4,c=7;

            int d=8,e=9,f=19;

            btree<int> A;

            A.ins(a); A.ins(c);

            A.ins(b); A.ins(f);

            A.ins(e); A.ins(d);

            A.scn(1);

            cout<<A;

            cout<<"------------\n";

            A.shw(0);

            cout<<"------------\n";

            cout<<A.get(3)<<endl;

            cout<<A.get(0)<<endl;

            cout<<A.get(6)<<endl;

            cout<<"------------\n";

            cout<<A.srch(e)<<endl;

            cout<<A.srch(0)<<endl;

            cout<<"------------\n";

            cin>>A;

            cout<<"------------\n";

            cout<<A;

            return 0;

}

TMPLT.H

1. Группа Аp318: Иванчиков И.В., Моисеев Е. Вариант № 7.

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

    Разработать шаблоны структуры данных в памяти.

Тип хранимого элемента параметр шаблона. Шаблон может содержать указатель

на объект, либо сам объект (в зависимости от варианта). Реализовать включение

с сохранением порядка, получение указателя на объект по ключу, получение

указателя на объект по логическому номеру, полный загрузки хранимых элементов

в структуру данных из последовательного потока. Проверить работу шаблона на

разработанном классе, используя его как параметр шаблона.

    Cтруктура данных :7. . двоичное дерево ;

 3. Текст программы с комментариями:

//#ifndef _TMPLT_H_

#define _TMPLT_H_

#include <iostream.h>

template <class T> class btree          //шаблон класс двоичного дерева

{

            struct node             //внутренняя для класса btree структура

            {

            public:

                        int cnt, lnum;  //счетчики для ветвления и полного обхода

            //необходимый для определения номера узла дерева и количества верштн в дереве

            //данный параметр необходим для вставки узла по номеру и проверки на выход за границы дерева.

                        T dat;          //хранимый в вершине дерева объект типа Т

                        node *l,*r;      //левый и правый потомки

                        node(T q) {l=r=NULL; dat=q; cnt=1; lnum=0;} //конструктор

                        ~node() {if (l!=NULL) delete l; if (r!=NULL) delete r;}  //деструктор

                        void shw(int lv)     //просмотр дерева с указанием всех параметров вершины

                        {

                                   if (l!=NULL) l->shw(lv+1);  //если левая ветвь не пустая, спуск до левой нижней вершины

                                   cout<<"lnum="<<lnum<<" lv="<<lv<<" cnt="<<cnt<<" :: "<<dat<<endl;

                                   if (r!=NULL) r->shw(lv+1); //если правая ветвь не пустая, спуск до правой нижней вершины

                        }

                        /*-----------------------------------------------------------------------------------------*/

                        void scn(int &n)        //полный обход

                        {

                                    if (l!=NULL) l->scn(n); //если левая ветвь не пустая, делаем полный обход с нумерацией вершин

                                   lnum=n; //для нумерации ветвей

                                   n++;

                                   if (r!=NULL) r->scn(n); //если правая ветвь не пустая, делаем полный обход с нумерацией вершин

                        }

                        /*-----------------------------------------------------------------------------------------*/

                        void ins(T q)  //вставка с сохранением порядка

                        {

                                   cnt++;//увеличения счетчика вершин на 1

                                   if (q<dat)

                                   {

                                               if (l==NULL) l=new node(q);

                                               //выделение памяти под переменную типа node(узел дерева)

                                               //и инициализация узла переменной q

                                               else l->ins(q);

                                               //вызываем метод вставки вершины с сохранением порядка для указателя

                                               //на левую ветку дерева.

                                   }

                                   //-> обращение к полям структуры через указатель

                                   else

                                   {

                                               //тоже самое только для правой ветки

                                               if (r==NULL) r=new node(q);