Реализация шаблонного двусвязного списка.

#include <iostream>using namespace std; template <typename T>struct Elem{ // Любые данные T data; Elem * next, * prev;}; template <typename T>class List{ // Голова хвост Elem<T> * Head, * Tail; int Count; public: List(); List(const List&); ~List(); int GetCount(); Elem<T>* GetElem(int); void DelAll(); void Del(int); void Del(); void AddTail(); void AddTail(T); void AddHead(T); void AddHead(); void Print(); void Print(int pos); List& operator = (const List&); List operator + (const List&); bool operator == (const List&); bool operator != (const List&); bool operator <= (const List&); bool operator >= (const List&); bool operator < (const List&); bool operator > (const List&); List operator - ();}; template <typename T>List<T>::List(){ Head = Tail = 0; Count = 0;} template <typename T>List<T>::List(const List & L){ Head = Tail = 0; Count = 0; Elem<T> * temp = L.Head; while(temp != 0) { AddTail(temp->data); temp = temp->next; }} template <typename T>List<T>::~List(){ DelAll();} template <typename T>Elem<T>* List<T>::GetElem(int pos){ Elem<T> *temp = Head; // Позиция от 1 до Count? if(pos < 1 || pos > Count) { // Неверная позиция cout << "Incorrect position !!!\n"; return; } int i = 1; while(i < pos && temp != 0) { temp = temp->next; i++; } if(temp == 0) return 0; else return temp;} template <typename T>void List<T>::AddHead(){ Elem<T> * temp = new Elem<T>; temp->prev = 0; int n; cout << "Input new number: "; cin >> n; temp->data = n; temp->next = Head; if(Head != 0) Head->prev = temp; if(Count == 0) Head = Tail = temp; else Head = temp; Count++;} template <typename T>void List<T>::AddHead(T n){ Elem<T> * temp = new Elem<T>; temp->prev = 0; temp->data = n; temp->next = Head; if(Head != 0) Head->prev = temp; if(Count == 0) Head = Tail = temp; else Head = temp; Count++;} template <typename T>void List<T>::AddTail(){ Elem<T> * temp = new Elem<T>; temp->next = 0; int n; cout << "Input new number: "; cin >> n; temp->data = n; temp->prev = Tail; if(Tail != 0) Tail->next = temp; if(Count == 0) Head = Tail = temp; else Tail = temp; Count++;} template <typename T>void List<T>::AddTail(T n){ Elem<T> * temp = new Elem<T>; temp->next = 0; temp->data = n; temp->prev = Tail; if(Tail != 0) Tail->next = temp; if(Count == 0) Head = Tail = temp; else Tail = temp; Count++;} template <typename T>void List<T>::Del(){ int n; cout << "Input position: "; cin >> n; if(n < 1 || n > Count) { cout << "Incorrect position !!!\n"; return; } int i = 1; Elem<T> * Del = Head; while(i <= n) { // Доходим до элемента, который удаляется Del = Del->next; i++; } // Доходим до элемента, который предшествует удаляемому Elem<T> * PrevDel = Del->prev; // Доходим до элемента, который следует за удаляемым Elem<T> * AfterDel = Del->next; if(PrevDel != 0 && Count != 1) PrevDel->next = AfterDel; if(AfterDel != 0 && Count != 1) AfterDel->prev = PrevDel; if(n == 1) Head = AfterDel; if(n == Count) Tail = PrevDel; delete Del; Count--;} template <typename T>void List<T>::Del(int n){ if(n < 1 || n > Count) { cout << "Incorrect position !!!\n"; return; } int i = 1; Elem<T> * Del = Head; while(i < n) { // Доходим до элемента, который удаляется Del = Del->next; i++; } // Доходим до элемента, который предшествует удаляемому Elem<T> * PrevDel = Del->prev; // Доходим до элемента, который следует за удаляемым Elem<T> * AfterDel = Del->next; if(PrevDel != 0 && Count != 1) PrevDel->next = AfterDel; if(AfterDel != 0 && Count != 1) AfterDel->prev = PrevDel; if(n == 1) Head = AfterDel; if(n == Count) Tail = PrevDel; delete Del; Count--;} template <typename T>void List<T>::Print(int pos){ // Позиция от 1 до Count? if(pos < 1 || pos > Count) { // Неверная позиция cout << "Incorrect position !!!\n"; return; } Elem<T> * temp; // Определяем с какой стороны // быстрее двигаться if(pos <= Count / 2) { // Отсчет с головы temp = Head; int i = 1; while(i < pos) { // Двигаемся до нужного элемента temp = temp->next; i++; } } else { // Отсчет с хвоста temp = Tail; int i = 1; while(i <= Count - pos) { // Двигаемся до нужного элемента temp = temp->prev; i++; } } // Вывод элемента cout << pos << " element: "; cout << temp->data << "\n";} template <typename T>void List<T>::Print(){ if(Count != 0) { Elem<T> * temp = Head; while(temp != 0) { cout << temp->data << "\n"; temp = temp->next; } }} template <typename T>void List<T>::DelAll(){ while(Count != 0) Del(1);} template <typename T>int List<T>::GetCount(){ return Count;} template <typename T>List<T>& List<T>::operator = (const List<T> & L){ if(this == &L) return *this; this->~List(); Elem<T> * temp = L.Head; while(temp != 0) { AddTail(temp->data); temp = temp->next; } return *this;} template <typename T>List<T> List<T>::operator + (const List<T>& L){ List Result(*this); Elem<T> * temp = L.Head; while(temp != 0) { Result.AddTail(temp->data); temp = temp->next; } return Result;} template <typename T>bool List<T>::operator == (const List<T>& L){ if(Count != L.Count) return false; Elem<T> *t1, *t2; t1 = Head; t2 = L.Head; while(t1 != 0) { if(t1->data != t2->data) return false; t1 = t1->next; t2 = t2->next; } return true;} template <typename T>bool List<T>::operator != (const List& L){ if(Count != L.Count) return true; Elem<T> *t1, *t2; t1 = Head; t2 = L.Head; while(t1 != 0) { if(t1->data != t2->data) return true; t1 = t1->next; t2 = t2->next; } return false;} template <typename T>bool List<T>::operator >= (const List& L){ if(Count > L.Count) return true; if(*this == L) return true; return false;} template <typename T>bool List<T>::operator <= (const List& L){ if(Count < L.Count) return true; if(*this == L) return true; return false;} template <typename T>bool List<T>::operator > (const List& L){ if(Count > L.Count) return true; return false;} template <typename T>bool List<T>::operator < (const List& L){ if(Count < L.Count) return true; return false;} template <typename T>List<T> List<T>::operator - (){ List Result; Elem<T> * temp = Head; while(temp != 0) { Result.AddHead(temp->data); temp = temp->next; } return Result;} // Тестовый примерvoid main(){ List <int> L; const int n = 10; int a[n] = {0,1,2,3,4,5,6,7,8,9}; // Добавляем элементы, стоящие на четных индексах, в голову, // на нечетных - в хвост for(int i = 0; i < n; i++) if(i % 2 == 0) L.AddHead(a[i]); else L.AddTail(a[i]); // Распечатка списка cout << "List L:\n"; L.Print(); cout << "\n\n"; // Распечатка списка cout << "List L:\n"; L.Print(); // Распечатка 2-го и 8-го элементов списка L.Print(2); L.Print(8); List <int> T; // Копируем список T = L; // Распечатка копии cout << "List T:\n"; T.Print(); // Складываем два списка (первый в перевернутом состоянии) cout << "List Sum:\n"; List <int> Sum = -L + T; // Распечатка списка Sum.Print();}

Предыдущая	Оглавление	Следующая
Предыдущая	Оглавление	Следующая

Домашнее задание

Добавить в класс "Односвязный список" следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента (функция возвращает позицию найденного элемента в случае успеха или NULL в случае неудачи).
Реализовать шаблонный класс "Очередь" на основе двусвязного списка.
Создать шаблонный класс-контейнер Array, который представляет собой массив, позволяющий хранить объекты заданного типа. Класс должен реализовывать следующие функции:

GetSize - получение размера массива (количество элементов, под которые выделена память)
SetSize(int size, int grow = 1) - установка размера массива (если параметр size больше предыдущего размера массива, то выделяется дополнительный блок памяти, если нет, то "лишние" элементы теряются и память освобождается); параметр grow определяет для какого количества элементов необходимо выделить память, если количество элементов превосходит текущий размер массива. Например, SetSize(5, 5); означает, что при добавлении 6-го элемента размер массива становится равным 10, при добавлении 11-го - 15 и т. д.
GetUpperBound - получение последнего допустимого индекса в массиве. Например, если при размере массива 10, вы добавляете в него 4 элемента, то функция вернет 3.
IsEmpty - массив пуст?
FreeExtra - удалить "лишнюю" память (выше последнего допустимого индекса)
RemoveAll - удалить все
GetAt -получение определенного элемента (по индексу)
SetAt - установка нового значения для определенного элемента (индекс элемента должен быть меньше текущего размера массива)
operator [] - для реализации двух предыдущих функций
Add - добавление элемента в массив (при необходимости массив увеличивается на значение grow функции SetSize)
Append - "сложение" двух массивов
operator =
GetData - получения адреса массива с данными
InsertAt - вставка элемента(-ов) в заданную позицию
RemoveAt - удаление элемента(-ов) с заданной позиции

Оглавление

Урок №28.

Бинарное дерево.
Реализация бинарного дерева.
Файлы. Введение.
Функции для работы с файлами библиотеки языка C.
Пример программы. Копирование файлов.
Пример программы. Игра "Виселица".
Домашнее задание.

Предыдущая	Оглавление	Следующая
Предыдущая	Оглавление	Следующая

Бинарное дерево.

Сегодня мы с вами познакомимся с новой, отнюдь не линейной структурой данных. Называется эта структура двоичное (или бинарное) дерево. Для начала дадим определение самой структуре, а затем рассмотрим несколько, терминов использующихся при работе с ней.

Бинарное дерево (binary tree) - это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя). Рассмотрим схематичное изображение бинарного дерева:

⇐ Предыдущая 14 15 16 17 181920 21 22 23 Следующая ⇒