Главная/

Программирование, базы данных. /

Шпоры по Си++. Шаблоны стандартных структур данных

                T data;

        public:

                void Add(T &a);

      T& Min();

                BTree();

     ~BTree(); };

template <class T> void BTree<T>::Add(T &a)

{       if(data==NULL) { data=a; return; } //вставка в текущий

        if(a>data)

        { if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый

        { if(l==NULL) l=new BTree<T>; l->Add(a); } }    //в левый

template <class T> T& BTree<T>::Min()

{       T* tmp=&data,*tmp2;

   if(l!=NULL) {tmp2=&l->Min(); if(*tmp2<*tmp) tmp=tmp2;} //поиск слева

   if(r!=NULL) {tmp2=&r->Min(); if(*tmp2<*tmp) tmp=tmp2;} //поиск справа

        return *tmp;  }

template <class T> BTree<T>::BTree()

{       l=NULL; r=NULL; data=0; }//инициализация

template <class T> BTree<T>::~BTree()

{       data=0;  //удаление данных

        if(l!=NULL) delete l;        //  -//-   левого поддерева

        if(r!=NULL) delete r;  }     //  -//-   правого поддерева

void main()

{       BTree<long> a; //двоичное дерево из long-ов

   a.Add(10); a.Add(3); a.Add(210); a.Add(70);//заполнение

        long k=a.Min(); }

//----------------------------------------------------------------------------

// 8. Двоичное дерево

// 2. Хранение обьектов

// 3. Сортировка (любым методом).

template <class T> class BTree

{       private:

                BTree<T> *l,*r;  //указатели на левое и правое поддеревья

                T data;

        public:

                void Add(T &a);

                void Sort();

                BTree();

     ~BTree(); };

template <class T> void BTree<T>::Add(T &a)

{       if(data==NULL) { data=a; return; } //вставка в текущий

        if(a>data)

        { if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый

        { if(l==NULL) l=new BTree<T>; l->Add(a); } }    //в левый

template <class T> void BTree<T>::Sort()

{  if(l!=NULL) l->Sort();  //сортировка левого поддерева

   if(r!=NULL) r->Sort();  //сортировка правого поддерева

        if(l!=NULL&&r!=NULL)

                if(l->data>r->data){ BTree *t=l; l=r; r=t; } }// обмен

template <class T> BTree<T>::BTree()

{       l=NULL; r=NULL; data=0; }//инициализация

template <class T> BTree<T>::~BTree()

{       data=0;  //удаление данных

        if(l!=NULL) delete l;        //  -//-   левого поддерева

        if(r!=NULL) delete r;  }     //  -//-   правого поддерева

void main()

{       BTree<long> a; //двоичное дерево из long-ов

   a.Add(10); a.Add(3); a.Add(210); a.Add(70);//заполнение

        a.Sort();}

//----------------------------------------------------------------------------

// 8. Двоичное дерево

// 2. Хранение обьектов

// 4. Двоичный поиск на основе сравнения с внешним об"ектом-ключом

template <class T> class BTree

{       private:

                BTree<T> *l,*r;  //указатели на левое и правое поддеревья

                T data;

        public:

                void Add(T &a);

                T* FindBin(T &key);

                BTree();

     ~BTree(); };

template <class T> void BTree<T>::Add(T &a)

{       if(data==NULL) { data=a; return; } //вставка в текущий

        if(a>data)

        { if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый

        { if(l==NULL) l=new BTree<T>; l->Add(a); } }    //в левый

template <class T> T* BTree<T>::FindBin(T &key)

{       if(key==data) return &data;   T* s=NULL;

        if(l!=NULL&&key<data) s=l->FindBin(key);

        if(s!=NULL) return s;

        if(r!=NULL&&key>data) s=r->FindBin(key);

        if(s!=NULL) return s;

        return NULL;  }

template <class T> BTree<T>::BTree()

{       l=NULL; r=NULL; data=0; }//инициализация

template <class T> BTree<T>::~BTree()

{       data=0;  //удаление данных

        if(l!=NULL) delete l;        //  -//-   левого поддерева

        if(r!=NULL) delete r;  }     //  -//-   правого поддерева

void main()

{       BTree<long> a; //двоичное дерево из long-ов

   a.Add(10); a.Add(3); a.Add(210); a.Add(70);//заполнение

        long j=*a.FindBin(210);}

//----------------------------------------------------------------------------

// 8. Двоичное дерево

// 2. Хранение обьектов

// 5. Включение элемента по номеру.

template <class T> class BTree

{       private:

                BTree<T> *l,*r;  //указатели на левое и правое поддеревья

                T data;

        public:

                void Add(T &a);

                int Insert(T &a,int k);

                BTree();

     ~BTree(); };

template <class T> void BTree<T>::Add(T &a)

{       if(data==NULL) { data=a; return; } //вставка в текущий

        if(a>data)

        { if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый

        { if(l==NULL) l=new BTree<T>; l->Add(a); } }    //в левый

template <class T> int BTree<T>::Insert(T &a,int k)

{       if(k==0)

        {       if(data==0) { data=a; return 0; }

                if(l!=NULL&&r==NULL)

                { r=new BTree<T>; r->data=data; data=a; return 0; }

                if(l==NULL)

                { l=new BTree<T>; l->data=data; data=a; return 0; }

      l->Insert(data,0);

                data=a; return 0; }

   if(k==1&&l!=NULL) return l->Insert(a,0);

   if(k==2&&r!=NULL) return r->Insert(a,0);

   if(l!=NULL) { k-=l->Insert(a,k); if(k==0) return 0; }

   if(r!=NULL) { k-=r->Insert(a,k); if(k==0) return 0; }

        return k; }

template <class T> BTree<T>::BTree()

{       l=NULL; r=NULL; data=0; }//инициализация

template <class T> BTree<T>::~BTree()

{       data=0;  //удаление данных

        if(l!=NULL) delete l;        //  -//-   левого поддерева

        if(r!=NULL) delete r;  }     //  -//-   правого поддерева

void main()

{       BTree<long> a; //двоичное дерево из long-ов

   a.Add(10); a.Add(3); a.Add(210); a.Add(70);//заполнение

        a.Insert(111,0);}

//----------------------------------------------------------------------------

// 8. Двоичное дерево

// 2. Хранение обьектов

// 6. Исключение (удаление) элемента по номеру.

template <class T> class BTree

{       private:

                BTree<T> *l,*r;  //указатели на левое и правое поддеревья

                T data;