Главная/

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

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

template <class T> class List

{       private:

      List<T> *next;

      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=NULL;      data=new T;   *data=a; }//выделение памяти и копирование

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

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

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

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

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

   q=p->next;

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

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

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

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

{       List<T> *p=this;

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

        return p->data; }

void main()

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

        a.Insert(13,1);a.Insert(33,2);  //вставка элементов

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

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

// 5. Односвязный список

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

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

template <class T> class List

{       private:

      List<T> *next;

      T data;

        public:

        List(T a);

     ~List();

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

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

{       next=NULL; data=a; }//выделение памяти и копирование

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

{       if(next!=NULL) delete next; }//удаление элемента и списка

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

{       if(next==NULL)  //если последний

        {       if(a>data) next=new List<T>(a); else

      { next=new List<T>(data);

        data=a; } } else

   {  if(a<data)  //если вставляемый меньше текущего

      {  next->Add(data);  //раздвигаем

                        data=a; } else

                if(a>data&&a<next->data) //если вставляемый должен быть следующим

        {  List<T> *p=next;

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

         next->next=p; } else

      next->Add(a);   }    } //если вставляемый больше текущего

void main()

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

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

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

// 5. Односвязный список

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

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

template <class T> class List

{       private:

      List<T> *next;

      T data;

        public:

        List(T a);

     ~List();

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

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

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

{       next=NULL; data=a; }//выделение памяти и копирование

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

{       if(next!=NULL) delete next; }//удаление элемента и списка

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

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

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

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

        {       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!=NULL) p=p->next; //ищем место в списке

   q=p->next;

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

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

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

void main()

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

   a.Insert(3,1); a.Insert(9,2); //вставка элементов

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

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

// 5. Односвязный список

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

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

template <class T> class List

{       private:

      List<T> *next;

      T data;

        public:

        List(T a);

     ~List();

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

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

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

{       next=NULL; data=a; }//выделение памяти и копирование

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

{       if(next!=NULL) delete next; }//удаление элемента и списка

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

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

          for(List<T> *q=p->next;q!=NULL;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!=NULL) p=p->next; //ищем место в списке

   q=p->next;

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

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

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

void main()

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

        a.Insert(155,1);a.Insert(77,2);  //вставка элементов

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

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

// 5. Односвязный список

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

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

template <class T> class List

{       private:

      List<T> *next;

      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=NULL; data=a; }//выделение памяти и копирование