|
Шпоры по Си Шаблоны стандартных структур данных
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 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
char[size*sizeof(T*)]; //выделение
памяти под МУ
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
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();}//вытаскиваем упорядоченные
//по возрастанию эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 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
char[size*sizeof(T*)]; //выделение
памяти под МУ
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; //стек пустой
T *min=data[0];
for(int k=1;k<sp;k++)
if(*data[k]<*min) min=data[k]; //поиск мин.
return min; }
void main()
{ StackDA<int> s(20); //стек из 20-ти указателей на int
int a=13,b=5,c=7;
s.Push(a); s.Push(b); s.Push(c);
//укладываем данные
int *m=s.FindMin(); } //
поиск мин.
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 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
char[size*sizeof(T*)]; //выделение
памяти под МУ
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
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();}//вытаскиваем упорядоченные
//по возрастанию эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 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 char[size*sizeof(T*)]; //выделение памяти под МУ
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()
{ StackDA<int> s(20); //стек из 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); } //поиск
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 5. включение
элемента по номеру
template <class
T> class StackDA
{ private:
T **data;
//динамический МУ на данные
int size,sp;
//размер стека,кол-во элементов
public:
StackDA(int _size);
int Push(T &element); //результат:если стек полный то [-1]
//иначе, количество элементов
T *Pop(void); //результат:если стек пустой то [NULL]
int Insert(T &element,int num);
//включение по номеру
//результат:если
нельзя то [-1]
//иначе, количество элементов
~StackDA(void); };
template <class
T> StackDA<T>::StackDA(int _size)
{ size=_size;
data=(T**)new
char[size*sizeof(T*)]; //выделение
памяти под МУ
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> int StackDA<T>::Insert(T &element,int num)
return sp;
template <class
T> StackDA<T>::~StackDA(void)
{ delete data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти указателей на int
int a=13,b=5,c=7;
s.Push(a); s.Push(b); //укладываем данные
s.Insert(c,1); //вставляем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 6. исключение
элемента по номеру
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 *Exclude(int num); //исключение по номеру
//результат:если
нельзя то [NULL]
~StackDA(void); };
template <class
T> StackDA<T>::StackDA(int _size)
{ size=_size;
data=(T**)new
char[size*sizeof(T*)]; //выделение
памяти под МУ
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> T *StackDA<T>::Exclude(int num)
num>=sp
template <class
T> StackDA<T>::~StackDA(void)
{ delete data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти указателей на int
int a=13,b=5,c=7;
s.Push(a); s.Push(b); s.Push(c);
//укладываем данные
int *k=s.Exclude(1); //вытаскиваем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 1. хранение
указателей на объекты
// 7. поиск и
возвращение элемента по номеру
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 *operator[](int num); //взятие по
номеру
//результат:если
нельзя то [NULL]
~StackDA(void); };
template <class
T> StackDA<T>::StackDA(int _size)
{ size=_size;
data=(T**)new
char[size*sizeof(T*)]; //выделение
памяти под МУ
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> T *StackDA<T>::operator[](int num)
return data[num];
template <class
T> StackDA<T>::~StackDA(void)
{ delete data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти указателей на int
int a=13,b=5,c=7;
s.Push(a); s.Push(b); s.Push(c);
//укладываем данные
int *k=s[1]; //берем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 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()
{ StackDA<int> s(20); //стек из 20-ти int
s.Push(78); s.Push(10); s.Push(5); //укладываем данные
s.Sort(); int *k=s.FindBin(78); } //поиск
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 2. хранение
объектов
// 5. включение
элемента по номеру
template <class
T> class StackDA
{ private:
T *data;
int size,sp;
//размер стека,кол-во элементов
public:
StackDA(int _size);
int Push(T element); //результат:если стек полный то [-1]
//иначе, количество элементов
T *Pop(void); //результат:если стек пустой то [NULL]
int Insert(T element,int num);
//включение по номеру
//результат:если нельзя то [-1]
//иначе, количество элементов
~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> int StackDA<T>::Insert(T element,int num)
return sp;
template <class
T> StackDA<T>::~StackDA(void)
{ delete []data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти int
s.Push(99); s.Push(45); //укладываем данные
s.Insert(33,1); //вставляем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 2. хранение
объектов
// 6. исключение элемента
по номеру
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 Exclude(int num); //исключение по номеру
//результат:если
нельзя то [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; //стек полный
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>::Exclude(int num)
num<0)return;//стек
template <class
T> StackDA<T>::~StackDA(void)
{ delete [] data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти int
s.Push(35); s.Push(11); s.Push(89);
//укладываем данные
s.Exclude(1); //вытаскиваем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();
}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 1. стек
представлен динамическим массивом
// 2. хранение
объектов
// 7. поиск и
возвращение элемента по номеру
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 *operator[](int num); //взятие по
номеру
//результат:если
нельзя то [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; //стек полный
data[sp]=element;
return sp++; }
template <class
T> T *StackDA<T>::Pop(void)
{ if(sp==0) return NULL; //стек пустой
return &data[--sp];
}
template <class
T> T *StackDA<T>::operator[](int num)
пустой или номер слишком большой
template <class
T> StackDA<T>::~StackDA(void)
{ delete []data; }
void main()
{ StackDA<int> s(20); //стек из 20-ти int
s.Push(54); s.Push(23); s.Push(87);
//укладываем данные
int *k=s[1]; //берем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен статическим массивом
// 1. хранение
указателей на объекты
// 1. включение
элемента с сохранением упорядоченности
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]
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; //стек полный
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,
int size> T *StackSA<T, size>::Pop(void)
{ if(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 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)
void main()
{ StackSA<int, 20> s; //стек из 20-ти указателей на int
int a=13,b=5,c=7;
s.Push(a); s.Push(b); //укладываем данные
s.Insert(c,1); //вставляем элемент
int *pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();
}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен ссстатическим массивом
// 1. хранение
указателей на объекты
// 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]
T *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; //стек пустой
return data[--sp]; }
template <class T,
int size> T *StackSA<T, size>::Exclude(int num)
T *temp=data[num];
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 *k=s.Exclude(1); //вытаскиваем элемент
int *pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();
}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен статическим массивом
// 1. хранение
указателей на объекты
// 7. поиск и
возвращение элемента по номеру
template <class T,
int size> class StackSA
{ private:
T *data;
//статический МУ на данные
int sp;
//кол-во элементов
public:
StackSA();
int Push(T &element); //результат:если стек полный то [-1]
//иначе, количество элементов
T *Pop(void); //результат:если стек пустой то [NULL]
T
*operator[](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; //стек пустой
return &data[--sp]; }
template <class T,
int size> T *StackSA<T, size>::operator[](int num)
if(sp==0
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 *k=s[1]; //берем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();
}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен статическим массивом
// 2. хранение
объектов
// 1. включение
элемента с сохранением упорядоченности
template <class
T,int size> class StackSA
{ private:
T data[size];
int sp;
//размер стека,кол-во элементов
public:
StackSA();
int Push(T element); //результат:если стек полный то [-1]
//иначе,
количество элементов
T *Pop(void);}; //результат:если стек пустой то
[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; //стек полный
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,int size> T *StackSA<T,size>::Pop(void)
{ if(sp==0) return NULL; //стек пустой
return &data[--sp]; }
void main()
{ StackSA<int,25> s; //стек из 25-ти int
s.Push(27); s.Push(13); s.Push(19); //укладываем данные
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем упорядоченные
//по возрастанию эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен статическим массивом
// 2. хранение
объектов
// 2. поиск и
возвращение минимального объекта
template <class
T,int size> class StackSA
{ private:
T data[size];
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; //стек пустой
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)
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; //стек пустой
return &data[--sp]; }
template <class
T,int size> void StackSA<T,size>::Exclude(int num)
if(sp==0
void main()
{ StackSA<int,20> s; //стек из 20-ти int
s.Push(35); s.Push(11); s.Push(89);
//укладываем данные
s.Exclude(1); //вытаскиваем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();
}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
// 2. стек
представлен статическим массивом
// 2. хранение
объектов
// 7. поиск и
возвращение элемента по номеру
template <class
T,int size> class StackSA
{ private:
T data[size];
int sp;
//размер стека,кол-во элементов
public:
StackSA();
int Push(T element); //результат:если стек полный то [-1]
//иначе, количество элементов
T *Pop(void); //результат:если стек пустой то [NULL]
T *operator[](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; //стек пустой
return &data[--sp]; }
template <class
T,int size> T *StackSA<T,size>::operator[](int num)
пустой или номер слишком большой
void main()
{ StackSA<int,20> s; //стек из 20-ти int
s.Push(54); s.Push(23); s.Push(87);
//укладываем данные
int *k=s[1]; //берем элемент
int
*pa=s.Pop(),*pb=s.Pop(),*pc=s.Pop();}//вытаскиваем эл-ты
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//1. Включение элемента
с сохранением упорядочености.
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
void operator+(T *q);
T* operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> void SArray<T,size>::operator+(T *q)
{ for(int
k=0;k<size&&data[k]!=NULL;k++);
if(k==size) return; //нет места в
массиве
for(;k>0&&*data[k-1]>*q;k--)
data[k]=data[k-1]; //раздвигаем элементы
data[k]=q; } //вставляем элемент
template <class
T,int size> T* SArray<T,size>::operator[](int i)
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a+new int(5); a+new int(25); a+new int(15); //заносим
значения
int k=*a[1]; } // получаем значение
15
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//2. Поиск и
возвращение минимального об"екта.
template <class
T,int size> class SArray
{ private:
T
*data[size];
public:
SArray();
~SArray();
T* Min();
T* operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> T* SArray<T,size>::Min()
{ for(int
k=0;k<size&&data[k]==NULL;k++); //номер первого не NULL элемента
int tmp=k++; //в tmp
for(;k<size;k++)
if(data[k]!=NULL&&*data[k]<*data[tmp]) tmp=k; //поиск
минимального
return data[tmp]; }
template <class
T,int size> T* SArray<T,size>::operator[](int i)
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[1]=5; *a[4]=3; *a[3]=7; //заносим значения
int k=*a.Min(); }
// получаем значение 3
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//3. Сортировка (любым
методом).
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
void Sort();
T* operator[](int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> void
SArray<T,size>::Sort()
{ for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(data[i]==NULL||(data[j]!=NULL&&*data[j]<*data[i])) //сравнение
{ T* tmp=data[j]; data[j]=data[i];
data[i]=tmp; } } //обмен
template <class
T,int size> T* SArray<T,size>::operator[](int i)
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[1]=15; *a[4]=9; *a[3]=17; //заносим значения
a.Sort(); //сортируем
int i=*a[0],j=*a[1],k=*a[2]; }
//достаем отсортированнные по возрастанию
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
T* FindBin(T &key);
T* operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> T* SArray<T,size>::FindBin(T& key)
{ int a=0,b=size-1; //начало,конец отрезка
while(a<=b)
{
int m=(a+b)/2; //середина
while(data[m]==NULL&&m>a)
m--;
{ if(*data[m]==key) return data[m]; //совпало с ключом
if(*data[m]>key) a=m+1; //правая часть
else b=m-1; } } //левая
часть
return NULL; } //не найден
template <class
T,int size> T* SArray<T,size>::operator[](int i)
i>=size) return NULL;
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[0]=5; *a[1]=9; *a[2]=17; //заносим значения
int i=*a.FindBin(17); }
//двоичный поиск
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//5. Включение
элемента по номеру.
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
T* operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> T* SArray<T,size>::operator[](int i)
if(i<0
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6]; i=*a[1];}
//получаем значения
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//6. Исключение
(удаление) элемента по номеру.
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
T* operator[](int i);
void Del(int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> T* SArray<T,size>::operator[](int i)
return data[i];
template <class
T,int size> void SArray<T,size>::Del(int i)
if(i<0
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[0]=500; *a[1]=98; *a[2]=17; //заносим значения
a.Del(0); a.Del(1); a.Del(2); }
//удаляем
//----------------------------------------------------------------------------
//3. статический
массив
//1. хранение
указателей на обьекты
//7. Поиск и
возвращение элемента по номеру.
template <class
T,int size> class SArray
{ private:
T *data[size];
public:
SArray();
~SArray();
T* operator[](int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=NULL; }
template <class
T,int size> SArray<T,size>::~SArray()
{ for(int k=0;k<size;k++)
if(data[k]!=NULL) delete data[k]; }
template <class
T,int size> T* SArray<T,size>::operator[](int i)
if(data[i]==NULL) data[i]=new T;
void main()
{ SArray<int,10> a; //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6]; i=*a[1]; } //получаем значения
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//1. Включение
элемента с сохранением упорядочености.
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
void operator+(T &q);
T& operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> void SArray<T,size>::operator+(T &q)
{ for(int
k=0;k<size&&data[k]!=0;k++);
if(k==size) return; //нет места в
массиве
for(;k>0&&data[k-1]>q;k--)
data[k]=data[k-1]; //раздвигаем элементы
data[k]=q; } //вставляем элемент
template <class
T,int size> T& SArray<T,size>::operator[](int i)
//возвращаем первый элемент
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a+5; a+25; a+15; //заносим значения
int k=a[1]; } // получаем значение 15
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//2. Поиск и
возвращение минимального об"екта.
template <class
T,int size> class SArray
{ private:
T
data[size];
public:
SArray();
T& Min();
T& operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> T& SArray<T,size>::Min()
{ int tmp=0;
for(int k=1;k<size;k++)
if(data[k]<data[tmp])
tmp=k; //поиск минимального
return data[tmp]; }
template <class
T,int size> T& SArray<T,size>::operator[](int i)
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[0]=5; a[1]=3; a[2]=7; //заносим значения
int k=a.Min(); }
// получаем значение 3
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//3. Сортировка
(любым методом).
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
void Sort();
T& operator[](int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> void
SArray<T,size>::Sort()
{ for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(data[j]<data[i]) //сравнение
{ T tmp=data[j]; data[j]=data[i];
data[i]=tmp; } } //обмен
template <class
T,int size> T& SArray<T,size>::operator[](int i)
//если выходит за границы то
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[1]=15; a[4]=9; a[3]=17; //заносим значения
a.Sort(); //сортируем
int i=a[0],j=a[1],k=a[2]; } //достаем
отсортированнные по возрастанию
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
T& FindBin(T &key);
T& operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++) data[k]=0; }
template <class
T,int size> T& SArray<T,size>::FindBin(T& key)
{ int a=0,b=size-1,m; //начало,конец отрезка,середина
while(a<=b)
{
m=(a+b)/2; //середина
if(data[m]==key) return data[m]; //совпало с ключом
if(data[m]>key) a=m+1; //правая часть
else b=m-1; } //левая часть
return data[m]; } //не найден возвращаем ближайший
template <class
T,int size> T& SArray<T,size>::operator[](int i)
i>=size) return data[0];
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[0]=5; a[1]=9; a[2]=17; //заносим значения
int i=a.FindBin(17); }
//двоичный поиск
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//5. Включение
элемента по номеру.
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
T& operator[](int i);};
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> T& SArray<T,size>::operator[](int i)
i>=size) return data[0];
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[4]=6; a[6]=7; a[1]=2; //заносим значения
int i=a[4]; i=a[6]; i=a[1]; } //получаем значения
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//6. Исключение
(удаление) элемента по номеру.
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
T& operator[](int i);
void Del(int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> T& SArray<T,size>::operator[](int i)
return data[i];
template <class
T,int size> void SArray<T,size>::Del(int i)
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[0]=500; a[1]=98; a[2]=17; //заносим значения
a.Del(0); a.Del(1); a.Del(2); }
//"удаляем"
//----------------------------------------------------------------------------
//3. статический
массив
//2. хранение
обьектов
//7. Поиск и
возвращение элемента по номеру.
template <class
T,int size> class SArray
{ private:
T data[size];
public:
SArray();
T& operator[](int i); };
template <class
T,int size> SArray<T,size>::SArray()
{ for(int k=0;k<size;k++)
data[k]=0; }
template <class
T,int size> T& SArray<T,size>::operator[](int i)
//если выходит за границы то
void main()
{ SArray<int,10> a; //заводим массив указателей на int
a[4]=6; a[6]=7; a[1]=2; //заносим значения
int i=a[4]; i=a[6]; i=a[1]; } //получаем значения
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//1. Включение
элемента с сохранением упорядочености.
template <class
T> class DArray
{ private:
T **data;
int
size;
public:
DArray(int _size);
~DArray();
void operator+(T *q);
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> void DArray<T>::operator+(T *q)
{ for(int
k=0;k<size&&data[k]!=NULL;k++);
if(k==size) return; //нет места в
массиве
for(;k>0&&*data[k-1]>*q;k--)
data[k]=data[k-1]; //раздвигаем элементы
data[k]=q; } //вставляем элемент
template <class
T> T* DArray<T>::operator[](int i)
if(i<0
void main()
{ DArray<int> a(10); //заводим массив указателей на int
int x=5,y=99,z=7;
a+&x; a+&y;
a+&z; //заносим значения
int k=*a[1];} // получаем значение 7
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//2. Поиск и
возвращение минимального об"екта.
template <class
T> class DArray
{ private:
T **data;
int size;
public:
DArray(int _size);
~DArray();
T* Min();
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> T* DArray<T>::Min()
{ for(int
k=0;k<size&&data[k]==NULL;k++); //номер первого не NULL элемента
int tmp=k++; //в tmp
for(;k<size;k++)
if(data[k]!=NULL&&*data[k]<*data[tmp]) tmp=k; //поиск
минимального
return data[tmp]; }
template <class
T> T* DArray<T>::operator[](int i)
if(data[i]==NULL) data[i]=new T;
void main()
{ DArray<int> a(20); //заводим массив указателей на int
*a[1]=5; *a[4]=3; *a[3]=7; //заносим значения
int k=*a.Min(); } // получаем значение 3
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//3. Сортировка
(любым методом).
template <class
T> class DArray
{ private:
int
size;
T **data;
public:
DArray(int _size);
~DArray();
void Sort();
T* operator[](int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> void DArray<T>::Sort()
{ for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(data[i]==NULL||(data[j]!=NULL&&*data[j]<*data[i])) //сравнение
{ T* tmp=data[j]; data[j]=data[i];
data[i]=tmp; } } //обмен
template <class
T> T* DArray<T>::operator[](int i)
void main()
{ DArray<int> a(5); //заводим массив указателей на int
*a[1]=15; *a[4]=9; *a[3]=17; //заносим значения
a.Sort(); //сортируем
int i=*a[0],j=*a[1],k=*a[2]; } //достаем отсортированнные по
возрастанию
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T> class DArray
{ private:
int
size;
T **data;
public:
DArray(int _size);
~DArray();
T* FindBin(T &key);
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> T* DArray<T>::FindBin(T& key)
{ int a=0,b=size-1; //начало,конец отрезка
while(a<=b)
{
int m=(a+b)/2; //середина
while(data[m]==NULL&&m>a)
m--;
{ if(*data[m]==key) return data[m]; //совпало с ключом
if(*data[m]>key) a=m+1; //правая часть
else b=m-1; }
} //левая часть
return NULL; } //не найден
template <class
T> T* DArray<T>::operator[](int i)
void main()
{ DArray<int> a(15); //заводим массив указателей на int
*a[0]=5; *a[1]=9; *a[2]=17; //заносим значения
int i=*a.FindBin(17); }
//двоичный поиск
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//5. Включение
элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T **data;
public:
DArray(int _size);
~DArray();
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> T* DArray<T>::operator[](int i)
void main()
{ DArray<int> a(30); //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6];
i=*a[1]; } //получаем
значения
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//6. Исключение
(удаление) элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T **data;
public:
DArray(int _size);
~DArray();
T* operator[](int i);
void Del(int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++)
data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> T* DArray<T>::operator[](int i)
return data[i];
template <class
T> void DArray<T>::Del(int i)
if(i<0
void main()
{ DArray<int> a(30); //заводим массив указателей на int
*a[0]=500; *a[1]=98; *a[2]=17; //заносим значения
a.Del(0); a.Del(1); a.Del(2); }
//удаляем
//----------------------------------------------------------------------------
//4. динамический
массив
//1. хранение
указателей на обьекты
//7. Поиск и
возвращение элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T **data;
public:
DArray(int _size);
~DArray();
T* operator[](int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T**) new char[sizeof(T*)*size];
for(int i=0;i<size;i++) data[i]=NULL; }
template <class
T> DArray<T>::~DArray()
{ delete data; }
template <class
T> T* DArray<T>::operator[](int i)
i>=size) return NULL;
void main()
{ DArray<int> a(20); //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6];
i=*a[1]; } //получаем
значения
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//1. Включение
элемента с сохранением упорядочености.
template <class
T> class DArray
{ private:
T *data;
int size,sp;
public:
DArray(int _size);
~DArray();
void operator+(T q);
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
sp=0;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> void DArray<T>::operator+(T q)
{ if(sp>=size) return;
for(int
k=sp++;k>0&&data[k-1]>q;k--) data[k]=data[k-1]; //раздвигаем
элементы
data[k]=q; } //вставляем элемент
template <class
T> T* DArray<T>::operator[](int i)
if(i<0
void main()
{ DArray<int> a(10); //заводим массив указателей на int
int x=5,y=99,z=7;
a+x; a+y; a+z; //заносим значения
int k=*a[1]; } // получаем
значение 7
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//2. Поиск и
возвращение минимального об"екта.
template <class
T> class DArray
{ private:
T *data;
int
size;
public:
DArray(int _size);
~DArray();
T* Min();
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> T* DArray<T>::Min()
{ int tmp=0;
for(int k=1;k<size;k++)
if(data[k]<data[tmp])
tmp=k; //поиск минимального
return &data[tmp]; }
template <class
T> T* DArray<T>::operator[](int i)
return &data[i];
void main()
{ DArray<int> a(3); //заводим массив указателей на int
*a[0]=5; *a[1]=3; *a[2]=7; //заносим значения
int k=*a.Min(); } // получаем значение 3
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//3. Сортировка
(любым методом).
template <class
T> class DArray
{ private:
int
size;
T *data;
public:
DArray(int _size);
~DArray();
void Sort();
T* operator[](int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> void DArray<T>::Sort()
{ for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(data[j]<data[i]) //сравнение
{ T tmp=data[j]; data[j]=data[i];
data[i]=tmp; } } //обмен
template <class
T> T* DArray<T>::operator[](int i)
i>=size) return NULL;
void main()
{ DArray<int> a(5); //заводим массив указателей на int
*a[1]=15; *a[4]=9; *a[3]=17; //заносим значения
a.Sort(); //сортируем
int i=*a[0],j=*a[1],k=*a[2]; } //достаем отсортированнные по
возрастанию
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T> class DArray
{ private:
int
size;
T *data;
public:
DArray(int _size);
~DArray();
T* FindBin(T &key);
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> T* DArray<T>::FindBin(T& key)
{ int a=0,b=size-1; //начало,конец отрезка
while(a<=b)
{
int m=(a+b)/2; //середина
while(data[m]==NULL&&m>a)
m--;
{ if(data[m]==key) return
&data[m]; //совпало с ключом
if(data[m]>key) a=m+1; //правая часть
else b=m-1; } }
//левая часть
return NULL; } //не найден
template <class
T> T* DArray<T>::operator[](int i)
void main()
{ DArray<int> a(15); //заводим массив указателей на int
*a[0]=5; *a[1]=9; *a[2]=17; //заносим значения
int i=*a.FindBin(17); }
//двоичный поиск
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//5. Включение
элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T *data;
public:
DArray(int _size);
~DArray();
T* operator[](int i);};
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> T* DArray<T>::operator[](int i)
i>=size) return NULL;
void main()
{ DArray<int> a(30); //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6];
i=*a[1]; }
//получаем значения
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//6. Исключение
(удаление) элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T *data;
public:
DArray(int _size);
~DArray();
T* operator[](int i);
void Del(int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> T* DArray<T>::operator[](int i)
return &data[i];
template <class
T> void DArray<T>::Del(int i)
data[i]=0;
void main()
{ DArray<int> a(30); //заводим массив указателей на int
*a[0]=500; *a[1]=98; *a[2]=17; //заносим значения
a.Del(0); a.Del(1); a.Del(2); }
//удаляем
//----------------------------------------------------------------------------
//4. динамический
массив
//2. хранение
обьектов
//7. Поиск и
возвращение элемента по номеру.
template <class
T> class DArray
{ private:
int
size;
T *data;
public:
DArray(int _size);
~DArray();
T* operator[](int i); };
template <class
T> DArray<T>::DArray(int _size)
{ size=_size;
data=(T*) new T[size];
for(int i=0;i<size;i++) data[i]=0; }
template <class
T> DArray<T>::~DArray()
{ delete [] data; }
template <class
T> T* DArray<T>::operator[](int i)
void main()
{ DArray<int> a(20); //заводим массив указателей на int
*a[4]=6; *a[6]=7; *a[1]=2;
//заносим значения
int i=*a[4]; i=*a[6];
i=*a[1]; } //получаем
значения
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 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=new T; *data=a;
}//выделение памяти и копирование
template <class
T> List<T>::~List()
{ delete data; 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. Односвязный
список
// 1. Хранение
указателей на объекты
// 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=new T; *data=a;
}//выделение памяти и копирование
template <class
T> List<T>::~List()
{ delete data; 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(15,1); a.Insert(4,2); a.Insert(7,3);//вставка элементов
int k=*a.FindMin(); } // поиск минимального
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 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=new T; *data=a;
}//выделение памяти и копирование
template <class
T> List<T>::~List()
{ delete data; 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(15,1); a.Insert(4,2); a.Insert(7,3);//вставка элементов
a.Sort(); } //сортировка элементов
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 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=new
T; *data=a; }//выделение памяти и
копирование
template <class
T> List<T>::~List()
{ delete data; if(next!=NULL) delete next; }//удаление элемента и списка
template <class
T> List<T>* List<T>::Search(int num)
{ List<T> *p=this;
while(num-->0&&p->next!=NULL) { 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!=NULL) { 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 NULL; } //не найден
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(3); //создание списка
a.Insert(6,1); a.Insert(9,2); a.Insert(17,3);//вставка элементов
int j=*a.FindBin(11);}
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 5. Включение
элемента по номеру.
template <class
T> class List
{ private:
List<T> *next;
T *data;
public:
List(T a);
~List();
void Insert(T a,int pos); };
//вставка элемента
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; } //восстанавливаем последовательность элементов
void main()
{ List<int> a(10); //создание списка
a.Insert(55,1); } //вставка элемента
на первую позицию
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 6. Исключение
(удаление) элемента по номеру.
template <class
T> class List
{ private:
List<T> *next;
T *data;
public:
List(T a);
~List();
void Insert(T a,int pos); //вставка элемента
void Delete(int pos);}; //удаление элемента
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> void List<T>::Delete(int pos)
{ if(pos==0||next==NULL)return;//первый или
единственный элемент не удаляется
List<T> *p=this,*q=next;
while(pos-->1&&q->next!=NULL){ p=p->next;q=q->next;
}//ищем место в списке
p->next=q->next;
q->next=NULL;
delete q; }
void main()
{ List<int> a(10); //создание списка
a.Insert(55,1); a.Insert(5,2);
a.Insert(17,3);//вставка элементов
a.Delete(1); }//удаление элемента
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 1. Хранение
указателей на объекты
// 7. Поиск и возвращение
элемента по номеру.
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; }//выделение памяти и копирование
template <class
T> List<T>::~List()
{ if(next!=NULL) delete next; }//удаление
элемента и списка
template <class
T> List<T>* List<T>::Search(int num)
{ List<T> *p=this;
while(num-->0&&p->next!=NULL)
{ 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!=NULL) { 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!=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(12,1); a.Insert(15,2);
a.Insert(95,3); //вставка элементов
int j=a.FindBin(11); }
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 2. Хранение
объектов
// 5. Включение
элемента по номеру.
template <class
T> class List
{ private:
List<T> *next;
T data;
public:
List(T a);
~List();
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>::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(15,1); } //вставка элемента
на первую позицию
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 2. Хранение
объектов
// 6. Исключение
(удаление) элемента по номеру.
template <class
T> class List
{ private:
List<T> *next;
T data;
public:
List(T a);
~List();
void Insert(T a,int pos); //вставка элемента
void Delete(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>::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> void List<T>::Delete(int pos)
{ if(pos==0||next==NULL)return;//первый или
единственный элемент не удаляется
List<T> *p=this,*q=next;
while(pos-->1&&q->next!=NULL){ p=p->next;q=q->next;
}//ищем место в списке
p->next=q->next;
q->next=NULL;
delete q; }
void main()
{ List<int> a(10); //создание списка
a.Insert(55,1); //вставка элемента на первую позицию
a.Delete(1); } //удаление элемента
//----------------------------------------------------------------------------
// 5. Односвязный
список
// 2. Хранение
объектов
// 7. Поиск и
возвращение элемента по номеру.
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=a; }//выделение памяти
и копирование
template <class
T> List<T>::~List()
{ 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(55,1); //вставка элемента на первую позицию
int i=a.Get(0); } //взять элемент по номеру
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 1. Хранение
указателей на объекты
// 1. Включение
элемента с сохранением упорядочености.
template <class
T> class List
{ private:
List<T> *next,*prev;
T *data;
public:
List(T a);
~List();
void Add(T a); }; //добавление
элемента
template <class
T> List<T>::List(T a)
{ next=this; prev=this;
data=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
delete next; }//удаление
списка
template <class
T> void List<T>::Add(T a) //добавление элемента
{ List<T> *p=this,*q=next;
while(*p->data<a&&q!=this) { p=p->next; q=q->next; }
//поиск места
if(*p->data<a) p->next=new
List<T>(a); else // вставка после
{ 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.Add(5);
a.Add(11); a.Add(3); };
//вставка элементов
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 1. Хранение
указателей на объекты
// 2. Поиск и
возвращение минимального обьекта.
template <class
T> class List
{ private:
List<T> *next,*prev;
T
*data;
public:
List(T a);
~List();
T *FindMin(); //поиск минимального
void Insert(T a,int pos); };
//вставка элемента
template <class
T> List<T>::List(T a)
{ next=this; prev=this;
data=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
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. Двусвязный
циклический список
// 1. Хранение
указателей на объекты
// 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=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
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=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
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 NULL; } //не найден
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=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
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,*prev;
T *data;
public:
List(T a);
~List();
void Insert(T a,int pos);
//вставка элемента
void Delete(int pos);
};//удаление элемента
template <class
T> List<T>::List(T a)
{ next=this; prev=this;
data=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL) //проверка на зацикливание
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; }
//восстанавливаем последовательность элементов
template <class
T> void List<T>::Delete(int pos)
{ if(pos==0||next==this)return;//первый или
единственный элемент не удаляется
List<T> *p=this,*q=next;
while(pos-->1&&q->next!=this){
p=p->next;q=q->next; }//ищем место в списке
p->next=q->next;
q->next->prev=p;
q->next=NULL;
delete q; }
void main()
{ List<int> a(10); //создание списка
a.Insert(55,1); //вставка элемента на первую позицию
a.Delete(1);} //удаление элемента
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 1. Хранение
указателей на объекты
// 7. Поиск и
возвращение элемента по номеру.
template <class
T> class List
{ private:
List<T> *next,*prev;
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=this; prev=this;
data=new T; *data=a; }//выделение
памяти и копирование
template <class
T> List<T>::~List()
{ delete data; //удаление элемента
data=NULL;
if(next!=NULL&&next->data!=NULL)
//проверка на зацикливание
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; } //восстанавливаем последовательность
элементов
template <class
T> T* List<T>::Get(int num)
{ List<T> *p=this;
while(num-->0&&p->next!=this) { p=p->next; }//ищем в
списке
return p->data; }
void main()
{ List<int> a(10); //создание списка
a.Insert(15,1); a.Insert(6,1);
a.Insert(7,1); //вставка элементов
int i=*a.Get(2); }; //взять элемент по номеру
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 2. Хранение
объектов
// 1. Включение
элемента с сохранением упорядочености.
template <class
T> class List
{ private:
List<T> *next,*prev;
T data;
public:
List(T a);
~List();
void Add(T a); }; //добавление
элемента
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>::Add(T a) //добавление элемента
{ List<T> *p=this,*q=next;
while(p->data<a&&q!=this) { p=p->next;
q=q->next; } //поиск места
if(p->data<a) p->next=new
List<T>(a); else // вставка после
{ 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.Add(5);
a.Add(11); a.Add(3); }; //вставка элементов
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 2. Хранение
объектов
// 2. Поиск и
возвращение минимального обьекта.
template <class
T> class List
{ private:
List<T> *next,*prev;
T data;
public:
List(T a);
~List();
T FindMin(); //поиск минимального
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> 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,*prev;
T data;
public:
List(T a);
~List();
void Insert(T a,int pos); //вставка элемента
void Delete(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; } //восстанавливаем последовательность
элементов
template <class
T> void List<T>::Delete(int pos)
{ if(pos==0||next==this)return;//первый или
единственный элемент не удаляется
List<T> *p=this,*q=next;
while(pos-->1&&q->next!=this){ p=p->next;q=q->next;
}//ищем место в списке
p->next=q->next;
q->next->prev=p;
q->next=NULL;
delete q; }
void main()
{ List<int> a(10); //создание списка
a.Insert(55,1); //вставка элемента на первую позицию
a.Delete(1);} //удаление элемента
//----------------------------------------------------------------------------
// 6. Двусвязный
циклический список
// 1. Хранение
объектов
// 7. Поиск и
возвращение элемента по номеру.
template <class
T> class List
{ private:
List<T> *next,*prev;
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=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; } //восстанавливаем последовательность
элементов
template <class
T> T List<T>::Get(int num)
{ List<T> *p=this;
while(num-->0&&p->next!=this) { p=p->next; }//ищем в
списке
return p->data; }
void main()
{ List<int> a(10); //создание списка
a.Insert(15,1); a.Insert(6,1);
a.Insert(7,1); //вставка элементов
int i=a.Get(2); }; //взять элемент по номеру
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 1. Включение
элемента с сохранением упорядочености.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a);} //добавление элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15);} //вставка элементов
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 2. Поиск и
возвращение минимального обьекта.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T *FindMin(); }//поиск минимального
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T* Tree<T,size>::FindMin()
{ T* tmp=data; //принимаем начальный за минимальный
for(int i=0;i<size;i++)
if(child[i]!=NULL)
{ T* tmp2=child[i]->FindMin(); //ищем в поддереве
if(*tmp2<*tmp)
tmp=tmp2; }
return tmp; } //возвращаем
минимальный
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int k=*a.FindMin(); } // поиск минимального
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 3. Сортировка
(любым методом).
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Sort(); }//сортировка
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++) child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Sort()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL)
child[i]->Sort(); //сортируем поддерево
for(i=0;i<size-1;i++) //сортировка поддеревьев
for(int j=i+1;j<size;j++)
if(child[i]!=NULL&&child[j]!=NULL)
if(*child[j]->data<*child[i]->data) //поиск наибольшего
{ T*
t=child[j]->data;child[j]->data=child[i]->data;
child[i]->data=t;
} } //обмен
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Sort(); } //сортировка элементов
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 4. Двоичный поиск
на основе сравнения с внешним обьектом-ключом
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T* FindBin(T key); }
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T* Tree<T,size>::FindBin(T key)
{ T* p;
if (*data==key) return data;//совпадение
for(int
i=0;i<size&&child[i]!=NULL;i++) //поиск
{ p=child[i]->FindBin(key);
if(p!=NULL) return p; }
//найден
return NULL; } //не найден
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int j=*a.FindBin(11);}
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 5. Включение
элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Insert(T a,int pos); };
//вставка элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Insert(T a,int pos)
{ if(pos==0) //позиция найдена
{ if(data==NULL) { data=new T; *data=a; return; } //вставка
if(child[0]==NULL) child[0]=new
Tree<T,size>;
child[0]->Insert(*data,0);
*data=a; return; } //вставка в поддерево
for(int i=0;i<size;i++) //вставка на
текущий уровень
if(child[i]!=NULL)
if(--pos==0) {
child[i]->Insert(a,pos); return; }
if(i<size) { child[0]=new
Tree<T,size>; child[i]->Insert(a,0); return; }
for(i=0;i<size;i++) //вставка в
поддерево
if(child[i]!=NULL)
{ child[i]->Insert(a,pos); } }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Insert(55,1); } //вставка элемента
на первую позицию
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 6. Исключение
(удаление) элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Delete(int pos);};
//удаление элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Delete(int pos)
{ for(int i=0;i<size;i++) //текущий
уровень
if(child[i]!=NULL)
if(--pos==0) { delete
child[i]->data; child[i]->data=NULL; return; }
for(i=0;i<size;i++) //поддерево
if(child[i]!=NULL)
{ child[i]->Delete(pos); }
}
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Delete(1); }//удаление элемента
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 1. Хранение
указателей на объекты
// 7. Поиск и
возвращение элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T *data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T* Get(int pos);}; //получить
элемент по номеру
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=NULL; }
template <class
T,int size> Tree<T,size>::~Tree()
{ if(data!=NULL) delete data; //удаление элемента
for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==NULL) {
data=new T; *data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>*child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T* Tree<T,size>::Get(int pos)
{ if(pos==0) return data;
for(int i=0;i<size;i++) //текущий
уровень
if(child[i]!=NULL)
if(--pos==0) { return
child[i]->data; }
T* p;
for(i=0;i<size;i++) //поддерево
if(child[i]!=NULL)
{ p=child[i]->Get(pos);
if(p!=NULL) return p;
}
return NULL; }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int i=*a.Get(2); } //взять элемент по номеру
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 1. Включение
элемента с сохранением упорядочености.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); }; //добавление
элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15);} //вставка элементов
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 2. Поиск и
возвращение минимального обьекта.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T FindMin(); }//поиск минимального
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T Tree<T,size>::FindMin()
{ T tmp=data; //принимаем начальный за минимальный
for(int i=0;i<size;i++)
if(child[i]!=NULL)
{ T tmp2=child[i]->FindMin(); //ищем в поддереве
if(tmp2<tmp)
tmp=tmp2; }
return tmp; } //возвращаем
минимальный
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int k=a.FindMin(); } // поиск минимального
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 3. Сортировка
(любым методом).
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Sort(); };//сортировка
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Sort()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL)
child[i]->Sort(); //сортируем поддерево
for(i=0;i<size-1;i++) //сортировка поддеревьев
for(int j=i+1;j<size;j++)
if(child[i]!=NULL&&child[j]!=NULL)
if(child[j]->data<child[i]->data) //поиск наибольшего
{ T
t=child[j]->data;child[j]->data=child[i]->data;
child[i]->data=t; } } //обмен
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Sort(); } //сортировка элементов
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 4. Двоичный поиск
на основе сравнения с внешним обьектом-ключом
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T FindBin(T key);};
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++) child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T Tree<T,size>::FindBin(T key)
{ T p;
if (data==key) return data;//совпадение
for(int
i=0;i<size&&child[i]!=NULL;i++) //поиск
{ p=child[i]->FindBin(key);
if(p!=NULL) return p; }
//найден
return NULL; } //не найден
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int j=a.FindBin(11); }
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 5. Включение
элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Insert(T a,int pos); };
//вставка элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Insert(T a,int pos)
{ if(pos==0) //позиция найдена
{ if(data==NULL) { data=a; return; } //вставка
if(child[0]==NULL) child[0]=new
Tree<T,size>;
child[0]->Insert(data,0);
data=a; return; } //вставка в поддерево
for(int i=0;i<size;i++) //вставка на
текущий уровень
if(child[i]!=NULL)
if(--pos==0) { child[i]->Insert(a,pos);
return; }
if(i<size) { child[0]=new
Tree<T,size>; child[i]->Insert(a,0); return; }
for(i=0;i<size;i++) //вставка в
поддерево
if(child[i]!=NULL)
{ child[i]->Insert(a,pos); } }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Insert(55,1);} //вставка элемента на первую позицию
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 6. Исключение
(удаление) элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
void Delete(int pos);
};//удаление элемента
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> void Tree<T,size>::Delete(int pos)
{ if(pos==0) data=0;
for(int i=0;i<size;i++) //текущий
уровень
if(child[i]!=NULL)
if(--pos==0) {
child[i]->data=0; return; }
for(i=0;i<size;i++) //поддерево
if(child[i]!=NULL)
{ child[i]->Delete(pos); }
}
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
a.Delete(1); }//удаление элемента
//----------------------------------------------------------------------------
// 7. Дерево с
ограниченным числом потомков
// 2. Хранение
объектов
// 7. Поиск и
возвращение элемента по номеру.
template <class
T,int size> class Tree
{ private:
Tree<T,size> *child[size];
T data;
public:
Tree();
~Tree();
void Add(T a); //добавление элемента
T Get(int pos); };//получить
элемент по номеру
template <class
T,int size> Tree<T,size>::Tree()
{ for(int i=0;i<size;i++)
child[i]=NULL; data=0; }
template <class
T,int size> Tree<T,size>::~Tree()
{ for(int i=0;i<size;i++)
if(child[i]!=NULL) delete child[i];
}//удаление поддеревьев
template <class
T,int size> void Tree<T,size>::Add(T a) //добавление элемента
{ if(data==0) { data=a; return; }
for(int
i=0;i<size&&child[i]!=NULL&&a>child[i]->data;i++);
if(child[i]==NULL) child[i]=new
Tree<T,size>;
child[i]->Add(a); }
template <class
T,int size> T Tree<T,size>::Get(int pos)
{ if(pos==0) return data;
for(int i=0;i<size;i++) //текущий
уровень
if(child[i]!=NULL)
if(--pos==0) { return
child[i]->data; }
T p;
for(i=0;i<size;i++) //поддерево
if(child[i]!=NULL)
{ p=child[i]->Get(pos);
if(p!=NULL) return p; }
return 0; }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в
вершине
a.Add(5);
a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int i=a.Get(2); } //взять элемент по номеру
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 1. Включение
элемента с сохранением упорядочености.
template <class
T> class BTree
{ private:
BTree<T> *l,*r;
//указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 2. Поиск и
возвращение минимального об"екта.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
T& Min();
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>; l->Add(a); } } //в левый
template <class
T> T& BTree<T>::Min()
{ T* tmp=data,*tmp2;
if(l!=NULL) {tmp2=&l->Min();
if(*tmp2<*tmp) tmp=tmp2;} //поиск слева
if(r!=NULL) {tmp2=&r->Min();
if(*tmp2<*tmp) tmp=tmp2;} //поиск справа
return *tmp; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; // -//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
long k=a.Min(); }
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 3. Сортировка
(любым методом).
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
void Sort();
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> void BTree<T>::Sort()
{ if(l!=NULL) l->Sort(); //сортировка левого поддерева
if(r!=NULL) r->Sort(); //сортировка правого поддерева
if(l!=NULL&&r!=NULL)
if(*l->data>*r->data){ BTree *t=l; l=r; r=t; } }// обмен
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
a.Sort();}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
T* FindBin(T &key);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>; r->Add(a);
} else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> T* BTree<T>::FindBin(T &key)
{ if(key==*data) return data; T* s=NULL;
if(l!=NULL&&key<*data)
s=l->FindBin(key);
if(s!=NULL) return s;
if(r!=NULL&&key>*data)
s=r->FindBin(key);
if(s!=NULL) return s;
return NULL; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
long j=*a.FindBin(210);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 5. Включение
элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
int Insert(T &a,int k);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> int BTree<T>::Insert(T &a,int k)
{ if(k==0)
{ if(data==NULL) { data=new T; *data=a; return 0; }
if(l!=NULL&&r==NULL)
{ r=new BTree<T>;
r->data=new T;
*r->data=*data; *data=a; return 0; }
if(l==NULL)
{ l=new BTree<T>;
l->data=new T;
*l->data=*data; *data=a;
return 0; }
l->Insert(*data,0);
*data=a; return 0; }
if(k==1&&l!=NULL) return
l->Insert(a,0);
if(k==2&&r!=NULL) return
r->Insert(a,0);
if(l!=NULL) { k-=l->Insert(a,k);
if(k==0) return 0; }
if(r!=NULL) { k-=r->Insert(a,k);
if(k==0) return 0; }
return k; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
a.Insert(111,0);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей
на обьекты
// 6. Исключение
(удаление) элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
int Delete(int k);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> int BTree<T>::Delete(int k)
{ if(k==0) if(data!=NULL) { delete data; data=NULL; return 0; }
if(k==1&&l!=NULL) return l->Delete(0);
if(k==2&&r!=NULL) return
r->Delete(0);
if(l!=NULL) {k-=l->Delete(k); if(k==0)
return 0; }
if(r!=NULL) {k-=r->Delete(k); if(k==0)
return 0; }
return k; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
a.Delete(1); }
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение
указателей на обьекты
// 7. Поиск и
возвращение элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
T* Find(int &k);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a;
return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> T* BTree<T>::Find(int &k)
{ if(k==0) return data;
T* tmp=NULL; k--;
if(l!=NULL) {tmp=l->Find(k); if(tmp!=NULL) return tmp; }
if(r!=NULL) {tmp=r->Find(k);
if(tmp!=NULL) return tmp; }
return NULL; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
long m=*a.Find(1);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 1. Включение
элемента с сохранением упорядочености.
template <class
T> class BTree
{ private:
BTree<T> *l,*r;
//указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0; }//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
}//заполнение
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 2. Поиск и
возвращение минимального об"екта.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
T& Min();
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> T& BTree<T>::Min()
{ T* tmp=&data,*tmp2;
if(l!=NULL) {tmp2=&l->Min();
if(*tmp2<*tmp) tmp=tmp2;} //поиск слева
if(r!=NULL) {tmp2=&r->Min();
if(*tmp2<*tmp) tmp=tmp2;} //поиск справа
return *tmp; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
long k=a.Min(); }
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 3. Сортировка
(любым методом).
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
void Sort();
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> void BTree<T>::Sort()
{ if(l!=NULL) l->Sort(); //сортировка левого поддерева
if(r!=NULL) r->Sort(); //сортировка правого поддерева
if(l!=NULL&&r!=NULL)
if(l->data>r->data){
BTree *t=l; l=r; r=t; } }// обмен
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
a.Sort();}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 4. Двоичный поиск
на основе сравнения с внешним об"ектом-ключом
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
T* FindBin(T &key);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; } //вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> T* BTree<T>::FindBin(T &key)
{ if(key==data) return &data; T* s=NULL;
if(l!=NULL&&key<data)
s=l->FindBin(key);
if(s!=NULL) return s;
if(r!=NULL&&key>data)
s=r->FindBin(key);
if(s!=NULL) return s;
return NULL; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
long j=*a.FindBin(210);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 5. Включение
элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
int Insert(T &a,int k);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> int BTree<T>::Insert(T &a,int k)
{ if(k==0)
{ if(data==0) { data=a; return 0; }
if(l!=NULL&&r==NULL)
{ r=new BTree<T>;
r->data=data; data=a; return 0; }
if(l==NULL)
{ l=new BTree<T>;
l->data=data; data=a; return 0; }
l->Insert(data,0);
data=a; return 0; }
if(k==1&&l!=NULL) return
l->Insert(a,0);
if(k==2&&r!=NULL) return
r->Insert(a,0);
if(l!=NULL) { k-=l->Insert(a,k);
if(k==0) return 0; }
if(r!=NULL) { k-=r->Insert(a,k);
if(k==0) return 0; }
return k; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
a.Insert(111,0);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 6. Исключение
(удаление) элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
int Delete(int k);
BTree();
~BTree(); };
template <class
T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> int BTree<T>::Delete(int k)
{ if(k==0) { data=0; return 0; }
if(k==1&&l!=NULL) return
l->Delete(0);
if(k==2&&r!=NULL) return
r->Delete(0);
if(l!=NULL) {k-=l->Delete(k); if(k==0)
return 0; }
if(r!=NULL) {k-=r->Delete(k); if(k==0)
return 0; }
return k; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
a.Delete(1);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 2. Хранение
обьектов
// 7. Поиск и
возвращение элемента по номеру.
template <class
T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T data;
public:
void Add(T &a);
T* Find(int &k);
BTree();
~BTree(); };
template <class T>
void BTree<T>::Add(T &a)
{ if(data==NULL) { data=a; return; }
//вставка в текущий
if(a>data)
{ if(r==NULL) r=new BTree<T>;
r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>;
l->Add(a); } } //в левый
template <class
T> T* BTree<T>::Find(int &k)
{ if(k==0) return &data;
T* tmp=NULL; k--;
if(l!=NULL) {tmp=l->Find(k);
if(tmp!=NULL) return tmp; }
if(r!=NULL) {tmp=r->Find(k);
if(tmp!=NULL) return tmp; }
return NULL; }
template <class
T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=0;
}//инициализация
template <class
T> BTree<T>::~BTree()
{ data=0; //удаление данных
if(l!=NULL) delete l; //
-//- левого поддерева
if(r!=NULL) delete r; }
// -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево
из long-ов
a.Add(10); a.Add(3); a.Add(210);
a.Add(70);//заполнение
long m=*a.Find(1);}
|
|
|
