Главная/

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

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

size> T *StackSA<T,size>::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()

{   StackSA<int,30> s;  //стек из 30-ти int

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

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

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

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

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

// 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,10> s;  //стек из 10-ти int

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

   s.Sort();

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

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

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

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

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

// 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

   s.Push(78); s.Push(10); s.Push(5);  //укладываем данные

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

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

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

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

// 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 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> int StackSA<T,size>::Insert(T element,int num)

{  if(sp==size||num>sp||num<0)

                        return -1;//стек полный или номер слишком большой

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

        data[num]=element;

   return sp;   }

void main()

{  StackSA<int,20> s;  //стек из 20-ти int

   s.Push(99); s.Push(45);  //укладываем данные

   s.Insert(33,1);         //вставляем элемент

   int *pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты

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

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

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

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

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 Exclude(int num);  };  //исключение по номеру

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

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;     //стек пустой