Пример: Глобальная сеть INTERNET
Я ищу:
На главную  |  Добавить в избранное  

Главная/

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

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

←предыдущая следующая→
... 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 

*next,*prev;

      T data;

        public:

        List(T a);

     ~List();

                void Insert(T a,int pos);  //вставка элемента

                void Delete(int pos); }; //удаление элемента

template <class T> List<T>::List(T a)

{       next=this; prev=this; data=a; }

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

{       data=-1;        if(next!=NULL&&next->data!=-1) //проверка на зацикливание

                delete next; }//удаление списка

template <class T> void List<T>::Insert(T a,int pos)

{       List<T> *p=this,*q;

        while(pos-->0&&p->next!=this) p=p->next; //ищем место в списке

   q=p->next;

        p->next=new List<T>(p->data);    //создаем новый элемент

        p->data=a;        //записываем данные

        p->next->next=q;

        p->next->prev=p; }  //восстанавливаем последовательность элементов

template <class T> void List<T>::Delete(int pos)

{  if(pos==0||next==this)return;//первый или единственный элемент не удаляется

        List<T> *p=this,*q=next;

        while(pos-->1&&q->next!=this){ p=p->next;q=q->next; }//ищем место в списке

   p->next=q->next;

        q->next->prev=p;

        q->next=NULL;

        delete q; }

void main()

{  List<int> a(10);    //создание списка

        a.Insert(55,1);  //вставка элемента на первую позицию

        a.Delete(1);} //удаление элемента

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

// 6. Двусвязный циклический список

// 1. Хранение объектов

// 7. Поиск и возвращение элемента по номеру.

template <class T> class List

{       private:

      List<T> *next,*prev;

      T data;

        public:

        List(T a);

     ~List();

                void Insert(T a,int pos);  //вставка элемента

                T Get(int num); };//получить элемент по номеру

template <class T> List<T>::List(T a)

{       next=this; prev=this; data=a; }

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

{       data=-1;        if(next!=NULL&&next->data!=-1) //проверка на зацикливание

                delete next; }//удаление списка

template <class T> void List<T>::Insert(T a,int pos)

{       List<T> *p=this,*q;

        while(pos-->0&&p->next!=this) p=p->next; //ищем место в списке

   q=p->next;

        p->next=new List<T>(p->data);    //создаем новый элемент

        p->data=a;        //записываем данные

        p->next->next=q;

        p->next->prev=p; }  //восстанавливаем последовательность элементов

template <class T> T List<T>::Get(int num)

{       List<T> *p=this;

        while(num-->0&&p->next!=this) { p=p->next; }//ищем в списке

        return p->data; }

void main()

{  List<int> a(10);    //создание списка

        a.Insert(15,1); a.Insert(6,1); a.Insert(7,1);  //вставка элементов

        int i=a.Get(2); };  //взять элемент по номеру

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

// 7. Дерево с ограниченным числом потомков

// 1. Хранение указателей на объекты

// 1. Включение элемента с сохранением упорядочености.

template <class T,int size> class Tree

{       private:

      Tree<T,size> *child[size];

      T *data;

        public:

        Tree();

     ~Tree();

                void Add(T a);}  //добавление элемента

template <class T,int size> Tree<T,size>::Tree()

{       for(int i=0;i<size;i++) child[i]=NULL;  data=NULL; }

template <class T,int size> Tree<T,size>::~Tree()

{       if(data!=NULL) delete data;  //удаление элемента

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

        if(child[i]!=NULL) delete child[i]; }//удаление поддеревьев

template <class T,int size> void Tree<T,size>::Add(T a) //добавление элемента

{       if(data==NULL)  {       data=new T; *data=a; return; }

   for(int i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);

   if(child[i]==NULL) child[i]=new Tree<T,size>;

        child[i]->Add(a); }

void main()

{  Tree<int,5> a;    //создание дерева с пятью потомками в вершине

   a.Add(5);   a.Add(11);   a.Add(3);   a.Add(15);} //вставка элементов

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

// 7. Дерево с ограниченным числом потомков

// 1. Хранение указателей на объекты

// 2. Поиск и возвращение минимального обьекта.

template <class T,int size> class Tree

{       private:

      Tree<T,size> *child[size];

      T *data;

        public:

        Tree();

     ~Tree();

                void Add(T a);  //добавление элемента

      T *FindMin(); }//поиск минимального

template <class T,int size> Tree<T,size>::Tree()

{       for(int i=0;i<size;i++) child[i]=NULL;  data=NULL; }

template <class T,int size> Tree<T,size>::~Tree()

{       if(data!=NULL) delete data;  //удаление элемента

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

        if(child[i]!=NULL) delete child[i]; }//удаление поддеревьев

template <class T,int size> void Tree<T,size>::Add(T a) //добавление элемента

{       if(data==NULL)  {       data=new T; *data=a; return; }

   for(int i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);

   if(child[i]==NULL) child[i]=new Tree<T,size>;

        child[i]->Add(a); }

template <class T,int size> T* Tree<T,size>::FindMin()

{       T* tmp=data;         //принимаем начальный за минимальный

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

                if(child[i]!=NULL)

                {  T* tmp2=child[i]->FindMin(); //ищем в поддереве

                        if(*tmp2<*tmp) tmp=tmp2;        }

        return tmp;  }  //возвращаем минимальный

void main()

{  Tree<int,5> a;    //создание дерева с пятью потомками в вершине

   a.Add(5);   a.Add(11);   a.Add(3);   a.Add(15); //вставка элементов

   int k=*a.FindMin(); }  // поиск минимального

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

// 7. Дерево с ограниченным числом потомков

// 1. Хранение указателей на объекты

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

template <class T,int size> class Tree

{       private:

      Tree<T,size> *child[size];

      T *data;

        public:

        Tree();

     ~Tree();

                void Add(T a);  //добавление элемента

                void Sort(); }//сортировка

template <class T,int size> Tree<T,size>::Tree()

{      

←предыдущая следующая→
... 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 


Copyright © 2005—2007 «RefStore.Ru»