Загрузка...
 
Печать
Кодим 3D FPS DX9

1.3 Добавляем поддержку связных списков (LinkedList.h)




Напомним, что поддержка технологии связных списков(external link) (Linked lists) очень важна для нашего движка, т.к. именно на ней будет основан наш менеджер ресурсов, который мы создадим чуть позднее.1 Вот почему мы сначала вводим поддержку связных списков, а уже затем поговорим о менеджменте ресурсов, а не наоборот.
Сейчас в Проекте нашего движка всего два файла: Engine.h и Engine.cpp, которые мы создали в Главе 1.2.

Добавляем LinkedList.h (Проект Engine)

В заголовочном файле LinkedList.h будут содержаться объявления классов и функций, ответственных за манипуляции со связными списками.
Закрыть
noteПримечание

Напомним, что директива #include "LinkedList.h" (ссылка на заголовок) уже указана в Engine.h (Проверь!). Таким образом, для того, чтобы воспользоваться функционалом сразу всех заголовочных файлов (в том числе LinkedList.h), достаточно в любом из файлов исходного кода (.cpp) указать всего 1 директиву: #include "Engine.h". Это соответствует концепции единой точки контакта.

ОК, приступаем.
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Заголовочные файлы" (Header Files).
  • Во всплывающем меню Добавить->Создать элемент...
Image
  • В появившемся окне выбери "Заголовочный файл (.h)" и в поле "Имя" введи LinkedList.h.
  • Жмём "Добавить".
Image
Добавленный файл сразу откроется в правой части MSVC++2010.
  • В только что созданном и открытом файле LinkedList.h набираем следующий код:
LinkedList.h
//-----------------------------------------------------------------------------
//  File: LinkedList.h
//	Сборник функций и классов для работы со
//	связными списками (LinkedLists).
//
//	Original SourceCode:
//	Programming a Multiplayer First Person Shooter in DirectX
//	Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

//----------------------------------------------------------------------------
// Macros
// Макросы безопасного удаления
//----------------------------------------------------------------------------
#define SAFE_DELETE( p )       { if( p ) { delete ( p );     ( p ) = NULL; } }
#define SAFE_DELETE_ARRAY( p ) { if( p ) { delete[] ( p );   ( p ) = NULL; } }
#define SAFE_RELEASE( p )      { if( p ) { ( p )->Release(); ( p ) = NULL; } }

//-----------------------------------------------------------------------------
// Linked List Class
//-----------------------------------------------------------------------------
template< class Type > class LinkedList
{
public:
	//-------------------------------------------------------------------------
	// Element Structure
	//-------------------------------------------------------------------------
	struct Element
	{
		Type *data; // Pointer to the data held in the element.
				// Указатель на данные, содержащиеся в элементе.
		Element *next; // Pointer to the next element in the list.
				// Указатель на следующий элемент в списке.
		Element *prev; // Pointer to the previous element in the list.
				// Указатель на предыдущий элемент в списке.

		//---------------------------------------------------------------------
		// The element structure constructor.
		//---------------------------------------------------------------------
		Element( Type *element )
		{
			data = element;
			next = prev = NULL;
		}

		//---------------------------------------------------------------------
		// The element structure destructor.
		//---------------------------------------------------------------------
		~Element()
		{
			SAFE_DELETE( data );

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

	//-------------------------------------------------------------------------
	// The linked list class constructor.
	//-------------------------------------------------------------------------
	LinkedList()
	{
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// The linked list class destructor.
	//-------------------------------------------------------------------------
	~LinkedList()
	{
		Empty();
	}

	//-------------------------------------------------------------------------
	// Adds the given element to the end of the linked list.
	// Добавляет (add) данный элемент в конец списка.
	//-------------------------------------------------------------------------
	Type *Add( Type *element )
	{
		if( element == NULL )
			return NULL;

		if( m_first == NULL )
		{
			m_first = new Element( element );
			m_last = m_first;
		}
		else
		{
			m_last->next = new Element( element );
			m_last->next->prev = m_last;
			m_last = m_last->next;
		}

		m_totalElements++;

		return m_last->data;
	}

	//-------------------------------------------------------------------------
	// Inserts the given element into the linked list just before nextElement.
	// Вставляет данный элемент в связный список сразу перед nextElement.
	//-------------------------------------------------------------------------
	Type *InsertBefore( Type *element, Element *nextElement )
	{
		m_temp = nextElement->prev;

		m_totalElements++;

		if( m_temp == NULL )
		{
			m_first = new Element( element );
			m_first->next = nextElement;
			nextElement->prev = m_first;

			return m_first->data;
		}
		else
		{
			m_temp->next = new Element( element );
			m_temp->next->prev = m_temp;
			m_temp->next->next = nextElement;
			nextElement->prev = m_temp->next;

			return m_temp->next->data;
		}
	}

	//-------------------------------------------------------------------------
	// Removes the given element from the linked list and destroys its data.
	// Удаляет данный элемент из списка и уничтожает его данные.
	//-------------------------------------------------------------------------
	void Remove( Type **element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == *element )
			{
				if( m_temp == m_first )
				{
					m_first = m_first->next;
					if( m_first )
						m_first->prev = NULL;
				}
				if( m_temp == m_last )
				{
					m_last = m_last->prev;
					if( m_last )
						m_last->next = NULL;
				}

				SAFE_DELETE( m_temp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_temp = m_temp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Destroys all the elements in the linked list as well as their data.
	// Убирает (удаляет) все элементы связного списка вместе с их данными.
	//-------------------------------------------------------------------------
	void Empty()
	{
		while( m_last != NULL )
		{
			m_temp = m_last;
			m_last = m_last->prev;
			SAFE_DELETE( m_temp );
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes all the elements and clears their data pointers.
	// Warning: This function does not destroy the data held be each element.
	// Убирает (удаляет) все элементы связного списка вместе с указателями.
	// Внимание: Эта функция не уничтожает данные, содерж. в элементах.
	//-------------------------------------------------------------------------
	void ClearPointers()
	{
		while( m_last != NULL )
		{
			m_temp = m_last;
			m_temp->data = NULL;
			m_last = m_last->prev;
			SAFE_DELETE( m_temp );
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes the given element and clears its data pointer.
	// Warning: This function does not destroy the data held by the element.
	// Убирает (удаляет) данный элемент списка и очищает указатель на него.
	// Внимание: Эта функция не уничтожает данные, содерж. в данном элементе.
	//-------------------------------------------------------------------------
	void ClearPointer( Type **element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == *element )
			{
				if( m_temp == m_first )
				{
					m_first = m_first->next;
					if( m_first )
						m_first->prev = NULL;
				}
				if( m_temp == m_last )
				{
					m_last = m_last->prev;
					if( m_last )
						m_last->next = NULL;
				}

				m_temp->data = NULL;

				SAFE_DELETE( m_temp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_temp = m_temp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Iterates through the elements in the linked list.
	// Итерация (сканирование) каждого элемента в списке
	//-------------------------------------------------------------------------
	Type *Iterate( bool restart = false )
	{
		if( restart )
			m_iterate = NULL;
		else
		{
			if( m_iterate == NULL )
				m_iterate = m_first;
			else
				m_iterate = m_iterate->next;
		}

		if( m_iterate == NULL )
			return NULL;
		else
			return m_iterate->data;
	}

	//-------------------------------------------------------------------------
	// Returns the currently iterated element in the linked list.
	// Возвращает элемент связного списка, итерируемый в данный момент.
	//-------------------------------------------------------------------------
	Type *GetCurrent()
	{
		if( m_iterate )
			return m_iterate->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the first element in the linked list.
	// Возвращает первый элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetFirst()
	{
		if( m_first )
			return m_first->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the last element in the linked list.
	// Возвращает последний элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetLast()
	{
		if( m_last )
			return m_last->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the next element in the linked list from the given element.
	// Возвращает элемент связного списка, следующий за данным.
	//-------------------------------------------------------------------------
	Type *GetNext( Type *element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == element )
			{
				if( m_temp->next == NULL )
					return NULL;
				else
					return m_temp->next->data;
			}

			m_temp = m_temp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns a random element from the linked list.
	// Возвращает случайный элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetRandom()
	{
		if( m_totalElements == 0 )
			return NULL;
		else if( m_totalElements == 1 )
			return m_first->data;

		unsigned long element = rand() * m_totalElements / RAND_MAX;

		m_temp = m_first;
		for( unsigned long e = 0; e < element; e++ )
			m_temp = m_temp->next;

		return m_temp->data;
	}

	//-------------------------------------------------------------------------
	// Returns the complete element (including its next and previous pointers).
	// Возвращает полный элемент списка
	// (включая указатели на предыдущий и след. элементы).
	//-------------------------------------------------------------------------
	Element *GetCompleteElement( Type *element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == element )
					return m_temp;

			m_temp = m_temp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the total number of elements in the linked list.
	// Возвращает число элементов в связном списке.
	//-------------------------------------------------------------------------
	unsigned long GetTotalElements()
	{
		return m_totalElements;
	}

private:
	Element *m_first; // Первый элемент связного списка.
	Element *m_last; // Последний элемент связного списка.
	Element *m_iterate; // Используется для итерации связного списка.
	Element *m_temp; // // Используется как временное хранилище при различных операциях.

	unsigned long m_totalElements; // Total number of elements in the linked list.
								// Общее количество элементов в связном списке.
};

#endif

  • Сохрани Решение (Файл -> Сохранить все).

Исследуем код LinkedList.h

Самый важный элемент LinkedList.h - это объявление шаблонного класса LinkedList:
Фрагмент LinkedList.h
...
//-----------------------------------------------------------------------------
// Linked List Class
//-----------------------------------------------------------------------------
template< class Type > class LinkedList
...

Важно помнить, что этот класс является шаблоном, а значит представленный выше фрагмент кода по большому счёту не является объявлением класса! Это, скорее, некий трафарет или клише для объявления класса. Действительное объявление класса LinkedList не произойдёт до тех пор, пока ты не создашь экземпляр (инстанс) шаблонного класса LinkedList, указав определённый тип данных. Более подробно см. раздел Шаблоны (Templates) функций и классов в статье Основы языка Cpp.

Структура Element

Шаблонный класс LinkedList использует маленькую структуру Element, которая хранит данные об одном элементе связного списка:
Фрагмент LinkedList.h
...
struct Element
	{
		Type *data; // Pointer to the data held in the element.
				// Указатель на данные, содержащиеся в элементе.
		Element *next; // Pointer to the next element in the list.
				// Указатель на следующий элемент в списке.
		Element *prev; // Pointer to the previous element in the list.
				// Указатель на предыдущий элемент в списке.

		//---------------------------------------------------------------------
		// The element structure constructor.
		//---------------------------------------------------------------------
		Element( Type *element )
		{
			data = element;
			next = prev = NULL;
		}

		//---------------------------------------------------------------------
		// The element structure destructor.
		//---------------------------------------------------------------------
		~Element()
		{
			SAFE_DELETE( data );

			if( next )
				next->prev = prev;
			if( prev )
				prev->next = next;
		}
	};
...

Структура Element расположена внутри шаблонного класса. В её объявлении видим ключевое слово Type, означающее, что тип данных элемента напрямую зависит от типа данных, указанных при создании экземпляра (инстанса) шаблонного класса LinkedList. Таким образом, указатель переменная *data хранит информацию об элементе, используя тип данных, указанный программером при создании экземпляра (инстанса) шаблонного класса LinkedList.

Image
Рис.1 Бережное удаление элемента из связного списка


Следующие две переменные хранят в себе указатели на предыдущий и следующий элементы связного списка, позволяя, таким образом, элементу определять себя в качестве ссылки в связном списке.
Далее следует конструктор структуры Element, который назначает переменную для хранения данных элемента и очищает указатели-ссылки (на предыдущий и следующий элементы). Сам по себе класс LinkedList ответственен за корректное добавление (и назначение ссылок) элемента в связный список.
В след за конструктором идёт деструктор структуры Element, который специально разработан для:
  • автоматического уничтожения данных, которые хранит элемент (освобождение памяти, занимаемой ими),
  • бережного удаления элемента из связного списка, без разрушения самого связного списка.
Обрати внимание, как при удалении элемента предыдущий и следующий элементы смыкаются вместе (См. Рис.1).

Остальной код

Дальнейший код LinkedList.h рассмотри самостоятельно, изучив комментарии к каждой из функций. Вот конструктор, который подготавливает связный список, и деструктор, который очищает связный список перед удалением.
При очищении связного списка все элементы уничтожаются, как и данные, хранящиеся в них. Чуть ниже в LinkedList.h ты можешь видеть другие функции для:
  • добавления элементов (Add),
  • вставки элементов (InsertBefore),
  • удаления элементов из списка (Remove, Empty),
  • "ручного" удаления данных в каждом элементе,
  • быстрого доступа к любому из элементов связного списка.
Ты можешь выполнять итерацию ("прохождение" через весь список) связного списка по одному элементу за раз, получить доступ к первому, последнему элементам, и даже вернуть случайно выбранный из списка элемент.
Также, в классе LinkedList экспонированы две дополнительные функции: ClearPointers и ClearPointer, которые созданы для удаления всех элементов списка или одного элемента соответственно. Что делает эти функции особенными, так это то, что они не уничтожают данные, хранящиеся в элементах. Это пригодится в тех случаях, когда есть связный список указателей, ссылающийся на данные, хранящиеся где-то в другом месте. Таким образом эти функции позволяют уничтожить связный список, не трогая данные.
Закрыть
noteОбрати внимание

Будь осторожен с функциями ClearPointers и ClearPointer. В случае их применения к связным спискам, действительно хранящим какие-либо данные, возможны утечки памяти (memory leaks).


Пример применения связных списков

Несмотря на то обилие возможностей, которое предоставляет класс LinkedList, пользоваться ими очень легко. Основная причина этого заключается в том, что вся подноготная LinkedList.h предельно прозрачна и доступна для понимания. Чтобы использовать класс LinkedList, тебе необходимо сначала создать на его основе класс с конкретным типом данных (Напомним, что LinkedList - это шаблонный класс!), добавить или удалить элементы и затем уничтожить его. Следующий пример демонстрирует использование класса LinkedList с данными типа float (прочитай и разберись в коде):
LinkedList<float> *list = new LinkedList<float>;

list->Add( new float(5.0f));
List->Add( new float(3.7f));

SAFE_DELETE(list;)


Интегрируем поддержку связных списков в движок

"Подключим" к Проекту Engine заголовок LinkedList.h .

Изменения в Engine.h (Проект Engine)

  • Добавь инструкцию #include "LinkedList.h" в файл Engine.h:
Фрагмент Engine.h
...
//-----------------
// DirectX Includes
//-----------------
#include <d3dx9.h>
#include <dinput.h>

//-----------------------------
// Engine Includes
//-----------------------------
#include "LinkedList.h"
...

  • Сохрани Решение (Файл -> Сохранить все).

Итоги главы

Класс LinkedList вовсе не ограничен использованием основных типов данных (например float и int). Он поддерживает любой тип данных, который ты укажешь (или сам создашь). Например, ты можешь создать связный список игроков в игре. Ты увидишь множество примеров использования связных списков по ходу разработки нашего движка. Более того, следующий компонент нашего движка - менеджер ресурсов (resource manager) - сам практически целиком состоит из связных списков.

ДАЛЕЕ ==> Кодим 3D FPS DX9. 1.4 Добавляем поддержку менеджеров ресурсов

Источники


1. Young V. Programming a Multiplayer FPS in DirectX 9.0. - Charles River Media, 2005


Последние изменения страницы Суббота 09 / Июль, 2022 03:50:53 MSK

Последние комментарии wiki

No records to display

Search Wiki Page

Точное совпадение

Категории

|--> C#
|--> C++