Главная/

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

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

while(*p->data<a&&q!=this) { p=p->next; q=q->next; } //поиск места

        if(*p->data<a) p->next=new List<T>(a); else  // вставка после

        {       p->next=new List<T>(*p->data);         //   -//-  до

                        *p->data=a; }

        p->next->next=q;        p->next->prev=p;  }  //расстановка связей

void main()

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

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

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

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

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

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

template <class T> class List

{       private:

      List<T> *next,*prev;

      T *data;

        public:

        List(T a);

     ~List();

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

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

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

{       next=this; prev=this;

        data=new T; *data=a; }//выделение памяти и копирование

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

{       delete data;    //удаление элемента

        data=NULL;

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

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

template <class T> T* List<T>::FindMin()

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

   List<T> *p=this->next;

        while(p!=this)       //проходим список

        {       if(*p->data<*tmp) tmp=p->data;  //если есть меньший - запоминаем

                p=p->next;      }

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

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; }  //восстанавливаем последовательность элементов

void main()

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

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

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

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

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

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

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

template <class T> class List

{       private:

      List<T> *next,*prev;

      T *data;

        public:

        List(T a);

     ~List();

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

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

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

{       next=this; prev=this;

        data=new T; *data=a; }//выделение памяти и копирование

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

{       delete data;    //удаление элемента

        data=NULL;

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

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

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

{       for(List<T> *p=this;p->next!=this;p=p->next)

          for(List<T> *q=p->next;q!=this;q=q->next)

                if(*p->data>*q->data)       //если слева больший элемент

                {       T* tmp=p->data; p->data=q->data; q->data=tmp; } } //производим обмен

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; }  //восстанавливаем последовательность элементов

void main()

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

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

        a.Sort(); };    //сортировка элементов

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

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

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

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

template <class T> class List

{       private:

      List<T> *next,*prev;

      T *data;

        public:

        List(T a);

     ~List();

                List<T>*Search(int num);

                T* FindBin(T key);

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

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

{       next=this; prev=this;

        data=new T; *data=a; }//выделение памяти и копирование

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

{       delete data;    //удаление элемента

        data=NULL;

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

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

template <class T> List<T>* List<T>::Search(int num)

{       List<T> *p=this;

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

        return p; }

template <class T> T* List<T>::FindBin(T key)

{       int a=0,b=1;     //начало,конец отрезка

   List<T> *p=this;

        while(p->next!=this) { b++; p=p->next; } //подсчет элементов

   while(a<=b)

   {    int m=(a+b)/2;   //середина

      if(*Search(m)->data==key) return Search(m)->data;  //совпало с ключом

      if(*Search(m)->data<key) a=m+1;  //правая часть

                                                       else b=m-1; }//левая часть

   return NULL; } //не найден

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; }  //восстанавливаем последовательность элементов

void main()

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

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

        int j=*a.FindBin(11); };

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

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

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

// 5. Включение элемента