Главная/

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

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

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

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

template <class T> class StackDA

{  private:

        T               *data;

      int               size,sp;       //размер стека,кол-во элементов

   public:

        StackDA(int _size);

      int Push(T element);   //результат:если стек полный то [-1]

                                               //иначе, количество элементов

      T *Pop(void);           //результат:если стек пустой то [NULL]

     ~StackDA(void);    };

template <class T> StackDA<T>::StackDA(int _size)

{       size=_size;

        data=(T*)new T[size];     //выделение памяти

   sp=0;   }

template <class T> int StackDA<T>::Push(T element)

{  if(sp==size) return -1;    //стек полный

   for(int k=0;k<sp&&element<data[k];k++);

   for(int p=++sp;p>k;p--) data[p]=data[p-1];

        data[k]=element;

   return sp;   }

template <class T> T *StackDA<T>::Pop(void)

{  if(sp==0) return NULL;     //стек пустой

        return &data[--sp];      }

template <class T> StackDA<T>::~StackDA(void)

{       delete [] data;    }

void main()

{  StackDA<int> s(20);  //стек из 20-ти int

   s.Push(27); s.Push(13); s.Push(19);  //укладываем данные

   int *pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();

        }//вытаскиваем упорядоченные

        //по возрастанию эл-ты

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

// 1. стек представлен динамическим массивом

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

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

template <class T> class StackDA

{  private:

        T               *data;

      int               size,sp;       //размер стека,кол-во элементов

   public:

        StackDA(int _size);

      int Push(T element);   //результат:если стек полный то [-1]

                                               //иначе, количество элементов

      T *Pop(void);           //результат:если стек пустой то [NULL]

      T *FindMin(void);

     ~StackDA(void);    };

template <class T> StackDA<T>::StackDA(int _size)

{       size=_size;

        data=(T*)new T[size];     //выделение памяти

   sp=0;   }

template <class T> int StackDA<T>::Push(T element)

{  if(sp==size) return -1;    //стек полный

        data[sp]=element;

   return sp++; }

template <class T> T *StackDA<T>::Pop(void)

{  if(sp==0) return NULL;     //стек пустой

        return &data[--sp];      }

template <class T> StackDA<T>::~StackDA(void)

{       delete [] data;    }

template <class T> T *StackDA<T>::FindMin(void)

{  if(sp==0) return NULL;     //стек пустой

   int min=data[0];

   for(int k=1;k<sp;k++) if(data[k]<data[min]) min=k; //поиск мин.

   return &data[min];  }

void main()

{   StackDA<int> s(20);  //стек из 20-ти int

   s.Push(55);   s.Push(11);   s.Push(33);  //укладываем данные

   int *m=s.FindMin();  }  // поиск мин.

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

// 1. стек представлен динамическим массивом

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

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

template <class T> class StackDA

{  private:

        T               *data;

      int               size,sp;       //размер стека,кол-во элементов

   public:

        StackDA(int _size);

      int Push(T element);   //результат:если стек полный то [-1]

                                               //иначе, количество элементов

      T *Pop(void);           //результат:если стек пустой то [NULL]

      void Sort(void);

     ~StackDA(void);    };

template <class T> StackDA<T>::StackDA(int _size)

{       size=_size;

        data=(T*)new T[size];     //выделение памяти

   sp=0;   }

template <class T> int StackDA<T>::Push(T element)

{  if(sp==size) return -1;    //стек полный

        data[sp]=element;

   return sp++; }

template <class T> T *StackDA<T>::Pop(void)

{  if(sp==0) return NULL;     //стек пустой

        return &data[--sp];      }

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

{  for(int i=0;i<sp-1;i++)

   for(int j=i+1;j<sp;j++)

        if(data[j]>data[i])

                { T temp=data[j];data[j]=data[i];data[i]=temp; }  } // обмен

template <class T> StackDA<T>::~StackDA(void)

{       delete [] data;    }

void main()

{       StackDA<int> s(20);  //стек из 20-ти int

   s.Push(35); s.Push(17); s.Push(29);  //укладываем данные

   s.Sort();

   int *pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем упорядоченные

                                           //по возрастанию эл-ты

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

// 1. стек представлен динамическим массивом

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

// 4. двоичный поиск по ключу

template <class T> class StackDA

{  private:

        T               *data;

      int               size,sp;       //размер стека,кол-во элементов

   public:

        StackDA(int _size);

      int Push(T element);   //результат:если стек полный то [-1]

                                               //иначе, количество элементов

      T *Pop(void);           //результат:если стек пустой то [NULL]

      void Sort(void);

      T *FindBin(T key);     //двоичный поиск

     ~StackDA(void);    };

template <class T> StackDA<T>::StackDA(int _size)

{       size=_size;

        data=(T*)new T[size];     //выделение памяти

                  sp=0;   }

template <class T> int StackDA<T>::Push(T element)

{  if(sp==size) return -1;    //стек полный

        data[sp]=element;

   return sp++; }

template <class T> T *StackDA<T>::Pop(void)

{  if(sp==0) return NULL;     //стек пустой

        return &data[--sp];      }

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

{  for(int i=0;i<sp-1;i++)

   for(int j=i+1;j<sp;j++)

        if(data[j]>data[i])

                { T temp=data[j];data[j]=data[i];data[i]=temp; }  } // обмен

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

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

   while(a<=b)

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

      if(data[m]==key) return &data[m];  //совпало с ключом

      if(data[m]>key) a=m+1;  //правая часть

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

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

template <class T> StackDA<T>::~StackDA(void)

{       delete [] data;    }

void main()

{