Главная/

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

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

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> 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. Двусвязный циклический список

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

// 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=a; }

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

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

                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=a; }

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

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

                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 0;    } //не найден

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. Включение элемента по номеру.

template <class T> class List

{       private:

      List<T> *next,*prev;

      T data;

        public:

        List(T a);

     ~List();

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

void main()

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

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

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

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

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

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

template <class T> class List

{       private:

      List<T> *next