Главная/

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

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

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

        return data[--sp];      }

void main()

{       StackSA<int, 20> s;  //стек из 20-ти указателей на int

   int a=13,b=5,c=7;

   s.Push(a); s.Push(b); s.Push(c);  //укладываем данные

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

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

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

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

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

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

template <class T, int size> class StackSA

{  private:

        T                *data[size];          //cтатический МУ на данные

      int               sp;       //кол-во элементов

   public:

        StackSA();

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

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

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

      T *FindMin(void);};

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

{       sp=0;   }

template <class T, int size> int StackSA<T, size>::Push(T &element)

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

        data[sp]=&element;

   return sp++; }

template <class T, int size> T *StackSA<T, size>::Pop(void)

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

        return data[--sp];      }

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

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

        T *min=data[0];

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

   return min;  }

void main()

{       StackSA<int, 20> s;  //стек из 20-ти указателей на int

   int a=13,b=5,c=7;

   s.Push(a);   s.Push(b);   s.Push(c);  //укладываем данные

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

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

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

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

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

template <class T, int size> class StackSA

{  private:

        T                *data[size];          //статический МУ на данные

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

   public:

        StackSA();

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

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

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

      void Sort(void);};

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

{       sp=0;   }

template <class T, int size> int StackSA<T, size>::Push(T &element)

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

        data[sp]=&element;

   return sp++; }

template <class T, int size> T *StackSA<T, size>::Pop(void)

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

        return data[--sp];      }

template <class T, int size> void StackSA<T, size>::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; }  } // обмен

void main()

{       StackSA<int, 20> s;  //стек из 20-ти указателей на int

   int a=13,b=5,c=7;

   s.Push(a); s.Push(b); s.Push(c);  //укладываем данные

   s.Sort();

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

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

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

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

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

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

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

template <class T, int size> class StackSA

{  private:

        T                *data[size];          //статический МУ на данные

      int               sp;       //кол-во элементов

   public:

        StackSA();

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

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

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

      void Sort(void);

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

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

{       sp=0;   }

template <class T, int size> int StackSA<T, size>::Push(T &element)

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

        data[sp]=&element;

   return sp++; }

template <class T, int size> T *StackSA<T, size>::Pop(void)

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

        return data[--sp];      }

template <class T, int size> void StackSA<T, size>::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, int size> T *StackSA<T, size>::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; } //не найден

void main()

{       StackSA<int, 20> s;  //стек из 20-ти указателей на int

   int a=13,b=5,c=7,d=13;

   s.Push(a); s.Push(b); s.Push(c);  //укладываем данные

   s.Sort(); int *k=s.FindBin(d);} //поиск

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

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

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

// 5. включение элемента по номеру

template <class T, int size> class StackSA

{  private:

        T                *data[size];          //статический МУ на данные

      int               sp;       //кол-во элементов

   public:

        StackSA();

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

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

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

      int Insert(T &element,int num); //включение по номеру

                              //результат:если нельзя то [-1]

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

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

{   sp=0;   }

template <class T, int size> int StackSA<T, size>::Push(T &element)

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

        data[sp]=&element;

   return