←предыдущая следующая→
... 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
*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()
{
←предыдущая следующая→
... 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
|