Реализация с помощью классов динамических структур данных

Пример: реализация класса «список». Он состоит из узлов, связанных между собой с помощью указателей. Каждый узел хранит целое число, являющееся ключом списка.

Опишем вспомогательный класс для представления одного узла списка:

class Node{

public:

int d; // Данные

Node *next; // Указатель на последующий узел

Node *prev; // Указатель на предыдущий узел

Node (int dat = 0){ // Конструктор

d = dat; next = 0; prev = 0;

}

};

Этот класс будет описан внутри класса, представляющего список (класс List), поэтому для простоты доступа из внешнего класса поля сделаны доступными (public). Это позволяет обойтись без функций доступа и изменения полей.

class List{

class Node{…};

Node *pbeg, *pend; // Указатели на начало и конец списка

public:

List(){pbeg = 0; pend =0;} // Конструктор

~List ( ); // Деструктор

void add(int d); // Добавление узла в конец списка

Node * find (int i); // Поиск узла по ключу

Node * insert (int key, int d); // Вставка узла d после узла с ключом key:

bool remove (int key); // Удаление узла

void print( ); // Печать списка в прямом направлении

void print_back( ); // Печать списка в обратном направлении

};

Метод add выделяет память под новый объект типа Node и присоединяет его к списку, обновляя указатели на его начало и конец:

void List::add(int d) {

Node *pv = new Node(d); // Выделение памяти под новый узел

if (pbeg == 0) pbeg = pend = pv; // Первый узел списка

else {

// Связывание нового узла с предыдущим:

pv->prev = pend;

pend->next = pv;

pend = pv; } // Обновление указателя на конец списка

}

Можно получить отсортированный список, заменив данный метод на метод, аналогичный функции формирования отсортированного списка add_sort (лекция «Линейные списки»).

Метод find выполняет поиск узла с заданным ключом и возвращает указатель на него в случае успешного поиска и 0 в случае отсутствия такого узла в списке:

Node * List::find( int d ){

Node *pv = pbeg;

while (pv){

if (pv->d == d) break;

pv = pv->next;

}

return pv;

}

Метод insert вставляет в список узел после узла с ключом key и возвращает указатель на вставленный узел. Если такого узла в списке нет, вставка не выполняется и возвращается значение 0:

Node * List::insert(int key, int d){

if(Node *pkey = find(key)){ // Поиск узла с ключом key

// Выделение памяти под новый узел и его инициализация:

Node *pv = new Node(d);

// Установление связи нового узла с последующим:

pv->next = pkey->next;

// Установление связи нового узла с предыдущим:

pv->prev = рkеу;

// Установление связи предыдущего узла с новым:

pkey->next = pv;

// Установление связи последующего узла с новым:

if ( рkеу != pend) (pv->next)->prev = pv;

// Обновление указателя на конец списка.

// если узел вставляется в конец:

else pend = pv;

return pv;

}

return 0;

}

Метод remove удаляет узел с заданным ключом из списка и возвращает значение true в случае успешного удаления и false, если узел с таким ключом в списке не найден:

bool List::remove(int key){

if(Node *pkey = find(key)){

if (pkey == pbeg){ // Удаление из начала списка

pbeg = pbeg->next;

pbeg->prev = 0;}

else if (pkey == pend){ // Удаление из конца списка

pend = pend->prev;

pend->next - 0;}

else { // Удаление из середины списка

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;}

delete pkey;

return true;

}

return false;

}

Методы печати списка в прямом и обратном направлении поэлементно просматривают список, переходя по соответствующим ссылкам:

void List::print (){

Node *pv = pbeg;

cout << endl << "1ist: ";

while (pv){

cout << pv->d << ' ';

pv = pv->next;}

cout << endl;

}

void List::print_back(){

Node *pv = pend;

cout << endl << "List back: ";

while (pv){

cout << pv->d << ' ';

pv = pv->prev;}

cout << endl;

}

Деструктор списка освобождает память из-под всех его элементов:

List::~List () {

if (pbeg!= 0){

Node *pv = pbeg;

while (pv){

pv = pv->next;

delete pbeg;

pbeg = pv;}

}

В функции main, используется класс List: формируется список из 5 чисел, выводится на экран, добавляется число в список, удаляется число из списка и снова выводится список на экран:

int main( ){

List L;

for (int i = 2; i<6; i++) L.add(i);

L.print();

L.print_back();

L.insert(2, 200);

if (!L.remove(5)) cout << "not found";

L.print();

L.print_back(); }

Тема 2.11

Шаблоны классов

Шаблоны классов позволяют создавать параметризованные классы. Параметризованный класс - семейство родственных классов, которые можно применять к любому типу данных, передаваемому в качестве параметра.

Наиболее широкое применение шаблоны находят при создании контейнерных классов. Такие классы предназначены для хранения каким-либо образом организованных данных и работы с ними. Стандартная библиотека C++ содержит множество контейнерных классов для организации структур данных различного вида.

Преимущество использования шаблонов состоит в том, что если определен алгоритм работы с данными, он может применяться к любым типам данных без переписывания кода.

Пример:

Определить в виде класса параметризованного класса двухсвязный список (список может потребоваться хранить данные различных типов).

Класс List предназначен для хранения целых чисел. Чтобы хранить в нем данные любого типа, требуется описать этот класс как шаблон и передать тип в качестве параметра.

Синтаксис описания шаблона:

template <описание_параметров_шаблона> определение_класса;

Параметры шаблона перечисляются через запятую. В качестве параметров могут использоваться типы, шаблоны и переменные. Типы могут быть стандартными или определенными пользователем. Для их описания используется ключевое слово class. Внутри шаблона параметр типа может применяться в любом месте, где допустимо использовать спецификацию типа:

template <class Data> class List{

class Node{

public:

Data d;

Node *next;

Node *prev;

Node (Data dat = 0){d = dat; next = 0; prev = 0;}

};

…

}

Класс Data является формальным параметром. На его место при компиляции будет подставлен конкретный тип данных.

Для любых параметров шаблона могут задаваться значения по умолчанию:

template <class Т> class myarray {/*..*/};

template <class K, class V, template <class T> class С = myarray>

class Map{

C<K> key;

C<V> value;

…

};

Область действия параметра шаблона – от точки описания до конца шаблона, поэтому параметр можно использовать при описании следующих за ним:

template <class Т, Т* p, class U = Т> class X { /* ... */ };

Методы шаблона класса автоматически становятся шаблонами функций. Если метод описывается вне шаблона, его заголовок должен иметь следующие элементы:

template <описание_параметров_шаблона>

возвр_тип имя_класса <параметры_шаблона>::

имя_функции (список_параметров функции)

Описание параметров шаблона в заголовке функции должно соответствовать шаблону класса. При этом имена параметров могут не совпадать.

template <class Data> void List<Data>::print()

{ / * тело функции */ }

<class Data> - описание параметра шаблона, void – тип возвращаемого функцией значения, List – имя класса, <Data> - параметр шаблона, print — имя функции без параметров.

В случае нескольких параметров порядок их следования в списках <описание_параметров_шаблона> и <параметры_шаблона> должен совпадать:

template<class T1, class T2> struct A{

void f1 ( );

};

template <class T2, class T1> void A<T2, T1>::f1() { ... }

Правила описания шаблонов:

· Локальные классы не могут содержать шаблоны в качестве элементов,

· Шаблоны методов не могут быть виртуальными,

· Шаблоны классов могут содержать статические элементы, дружественные функции и классы,

· Шаблоны могут быть производными от шаблонов и от обычных классов, а также являться базовыми для шаблонов и обычных классов,

· Внутри шаблона нельзя определять friend-шаблоны.

Пример: полное описание параметризованного класса двусвязного списка List.

template <class Data> class List{

class Node{

public:

Data d;

Node *next, *prev;

Node (Data dat = 0){d = dat; next = 0; prev = 0;}

};

Node *pbeg, *pend;

public:

List( ){pbeg = 0; pend = 0;}

~List ( );

void add(Data d);

Node * find(Data i);

Node * insert(Data key, Data d);

bool remove(Data key);

void print();

void print_back();

};

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

template <class Data>

List <Data>::~List(){

if (pbeg !=0){

Node *pv = pbeg;

while (pv){

pv = pv->next;

delete pbeg;

pbeg = pv;

}

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

template <class Data>

void List <Data>::print( ){

Node *pv = pbeg;

cout << endl << "list: ";

while (pv){

cout << pv->d << ' ';

pv = pv->next;

}

cout << endl;

}

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

template <class Data>

void List <Data>::print_back(){

Node *pv = pend;

cout << endl << " list back: ";

while (pv){

cout << pv->d << ' ';

pv = pv->prev;

}

cout << endl;

}

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

template <class Data>

void List <Data>::add(Data d){

Node *pv = new Node(d);

if (pbeg == 0) pbeg = pend = pv;

else{

pv->prev = pend;

pend->next = pv;

pend = pv;

}

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

template <class Data>

Node * List <Data>::find(Data d){

Node *pv = pbeg;

while (pv){

if(pv->d == d) break;

pv = pv->next;

}

return pv;

}

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

template <class Data>

Node * List <Data>::insert(Data key, Data d){

if(Node *pkey = find(key)){

Node *pv = new Node(d);

pv->next = pkey->next;

pv->prev = рkеу;

pkey->next = pv;

if ( рkеу != pend) (pv->next)->prev = pv;

else pend = pv;

return pv;

}

return 0;

}

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

template <class Data>

bool List <Data>::remove(Data key){

if(Node *pkey = find(key)){

if (pkey == pbeg){

pbeg = pbeg->next;

pbeg->prev = 0;

}

else if (pkey == pend){

pend = pend->prev;

pend->next = 0;

}

else {

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;

}

delete pkey;

return true;

}

return false;

}

Если требуется использовать шаблон List для хранения данных пользовательского типа, в описание этого типа необходимо добавить перегрузку операции вывода в поток и сравнения на равенство, а если для его полей используется динамическое выделение памяти, то и операцию присваивания.

Переменные, передаваемые в шаблон, могут быть целого или перечисляемого типа, а также указателями или ссылками на объект или функцию. В теле шаблона они могут применяться в любом месте, где допустимо использовать константное выражение.

Пример: шаблон класса, содержащего блок памяти определенной длины и типа:

template <class Type, int kol>

class Block{

public:

Block(){p = new Type [kol];}

~Block(){delete [] p;}

operator Type *( );

protected:

Type * p;

template <class Type, int kol>

Block <Type, kol>:: operator Type *(){

return p;