10.ПРИМЕРЫ РЕАЛИЗАЦИИ КОНТЕЙНЕРНЫХ КЛАССОВ

10.1.Связанные списки

Связанные списки − это способ размещения данных, при котором одни данные ссылаются на другие. Списки представляют собой пример контейнер- ных классов. В общем, список напоминает массив с тем отличием, что его раз- меры не фиксированы: он может расти и уменьшаться по мере работы с ним.

Очередной элемент списка размещается в памяти динамически и связывается с остальной частью списка посредством указателей. В случае если некоторый элемент списка более не нужен, то освобождается память, отведенная под этот

элемент. Частным случаем списков являются стеки, очереди и кольца.											Р
10.1.1. Реализация односвязного списка										У
Односвязный список предполагает организацию хранения данных в памя-
									Г
ти, при которой перемещение может быть выполнено только в одномИнаправле-
нии (от начала списка в конец). Расположение в памяти элементов односвязного
списка можно изобразить следующим образом (рис. 10).
В настоящем пособии реализация односвязного списка не приводится
							а
(предлагается выполнить самостоятельно, основываясь на информации о реали-
зации двусвязного списка, приводимого ниже).								Б
						к
					е
Голова			и		т		Эл-т вне списка
		Р с. 10. Одн связный список
		полож
10.1.2. Реализац я двусвязного списка
Двусвязный список − это организация хранения данных в памяти, позво-
	б
ляющая выполнять перемещение в обоих направлениях (от начала списка в ко-
и				ение в памяти двусвязного списка можно изобразить
нец и наоборот). Рас
следующ м о разом (рис. 11).
Б
Голова							Эл-т вне списка

Рис. 11. Двусвязный список

В приведенном ниже примере для доступа к элементам списка использу-

230

ется разработанный класс, реализующий простые итераторы.

#include <iostream> #include <cassert> using namespace std; template <class T>

	class D_List
	{private:
	class D_Node								Р
	{ public:
		D_Node *next;		// указатель на следующий узел
		D_Node *prev;						И
				// указатель на предыдущий узел
		T val;		// поле данного			У
		D_Node(T node_val) : val(node_val) { } // конструктор
		D_Node() {}				Г
						// конструктор
		~D_Node(){}				// деструктор
						Б
		// для вывода элементов, тип которых определен пользователем,
		// неодходимо перегрузить опер цию <<						operator<<( ).
					а
		void print_val( ) { cout << val << " "; }
	};			к
	public:			е
	class iterator
	{private:
		friend class D_List<T>;
			о
		D_Node * the node;
	public:
		и
		iterator( ) : the тnode(0) { }
		л
		iterator(D Node * dn) : the_node(dn) { }
		// Copy constructor
и		iterator(const iterator & it) : the_node(it.the_node) { }
		iterator& operator=(const iterator& it)
Б	б{ the_node = it.the_node;

return *this;

}

bool operator==(const iterator& it) const { return (the_node == it.the_node); }

bool operator!=(const iterator& it) const { return !(it == *this); }

iterator& operator++( ) { if ( the_node == 0 )

231

throw "incremented an empty iterator"; if ( the_node->next == 0 )

throw "tried to increment too far past the end"; the_node = the_node->next;

return *this;

}

iterator& operator--( )

{ if ( the_node == 0 )

throw "decremented an empty iterator";

Р

if ( the_node->prev == 0 )

throw "tried to decrement past the beginning";

the_node = the_node->prev;

return *this;

И

}

T& operator*( ) const

У

{ if ( the_node == 0 )

throw "tried to dereference an empty iterator";

Г

return the_node->val;

Б

}

};

а

private:

// указатель на началоксписка

D_Node *head;

D_Node *tail;

// указа ель на эл

нт вне списка

ме

D_List & operator=(const D List &);

D_List(const D_List &);

т

iterator head_iterator;

iterator tail_iterator;

о

public:

и

D_List( )

л

{ head = tail = new D_Node;

tail->next = 0;

б

tail->prev = 0;

headиiterator = iterator(head);

tail iterator = iterator(tail);

Б}

// конструктор (создание списка, содержащего один элемент) D_List(T node_val)

{head = tail = new D_Node; tail->next = 0;

tail->prev = 0;

232

}

head_iterator = iterator(head); tail_iterator = iterator(tail); add_front(node_val);

// деструктор
~D_List( )
{ D_Node *node_to_delete = head;
for (D_Node *sn = head; sn != tail;)
{ sn = sn->next;	Р
delete node_to_delete;
node_to_delete = sn;
}
delete node_to_delete;

	}									И
	bool is_empty( ) {return head == tail;}
	iterator front( ) { return head_iterator; }								У
	iterator rear( ) { return tail_iterator; }
									Г
	void add_front(T node_val)
	{ D_Node *node_to_add = new D Node(nodeБ_val);
		node_to_add->next = head;						а
		node_to_add->prev = 0;
		head->prev = node_to add;
		head = node_to add;					к
		head_iterator = iterator(head);
	}					е
		// добавление нового элемента в начало списка
	void add				rear(T nodeтval)
	{ if ( is				empty(о) ) // список не пустой
		add			front(node_val);
		else	и
		л// не выполняется для пустого списка, т.к. tail->prev =NULL
	б			// и, следовательно, tail->prev->next бессмысленно
и
Б

{ D_Node *node_to_add = new D_Node(node_val); node_to_add->next = tail;

node_to_add->prev = tail->prev; tail->prev->next = node_to_add; tail->prev = node_to_add; tail_iterator = iterator(tail);

}

}

bool remove_it(iterator & key_i)

233

{ for ( D_Node *dn = head; dn != tail; dn = dn->next )

if ( dn == key_i.the_node ) // найден узел для удаления

{dn->prev->next = dn->next; dn->next->prev = dn->prev;

	delete dn;				// удаление узла
	key_i.the_node = 0;
	return true;
	}
}	return false;									Р
	// поиск итератора по значению узла
iterator find(T node_val) const
{	for ( D_Node *dn = head; dn != tail; dn = dn->next )							У
	if ( dn->val == node_val ) return iterator(dn);						Г		И
}	return tail_iterator;
	// подсчет числа элементов очереди
int size( ) const						а
{	int count = 0;
	for ( D_Node *dn = head; dn != tail; dn = dn->nextБ) ++count;
}	return count;					к
	// вывод содержимого списка
}
					т
void print( ) const
{ for ( D_Node *dn = head; dn е!= tail; dn = dn->next )
};	dn->print_val( );			о
	cout << endl;		и
		л
В файле d_list.cpp содержится main-функция, демонстрирующая некото-
	б
рые примеры ра оты со списком.
	и
#include "dlist 2.h"
typedef int tip;
D	List<tip> the_list;			// создается пустой список
int main()
Б{ int ret = 0;

D_List<tip>::iterator list_iter;

//занесение значений 0 1 2 3 4 в список for (int j = 0; j < 5; ++j) the_list.add_front(j);

//вывод содержимого списка, используя компоненту-функцию

234

// повторный вывод значения содержимого списка // используя итератор

for ( list_iter = the_list.front( ) ; list_iter != the_list.rear( ) ; ++list_iter )

cout << *list_iter << " "; cout << endl;

// класса D_List the_list.print( );

// вывод содержимого списка в обратном порядке

for ( list_iter = the_list.rear( ) ; list_iter != the_list.front( ) ; )Р

{

--list_iter;

// декремент итератора

cout << *list_iter << " ";

И

}

У

cout << endl;

Г

Б

the_list.remove_it(the_list.find(3));

the_list.print( );

cout<<the_list.size( )<<endl;

а

return 0;

}

к

Результат работы программы:

3

2

1

0

е

3

2

1

0

0

1

2

3

4

о

2

1

0

4

ли

Итератор реа

з тван как открытый вложенный класс D_List::iterator. Так

как класс открытый, в main может быть создан его объект. Класс iterator объяв-

л

ляется дружественным классу D_List, чтобы функция remuv_it класа D_List

имела возможность обращаться к private-члену the_node класса iterator.

В допо нение к стандартным указателям на голову и хвост списка (адрес

и

за пределами списка) в программе (в d_list.h) объявлены итераторы head_iterator

Б

tail бiterator, также ссылающиеся на голову и хвост списка.

Использование итератора позволяет скрыть единственный элемент дан- ных класса D_List:

D_Node * the_node.

В классе iterator выполнена перегрузка некоторых операций, позволяю- щих манипулировать узлом в строго определенных правилах (табл. 5).

Для поддержки использования итераторов в качестве аргументов или воз- вращаемых значений определен конструктор копирования.

В программе функция find(T) возвращает не bool, а iterator, который мо- жет быть передан другим функциям, принимающим параметры-итераторы, для

235