Связные списки в разработке компьютерных игр. Часть 1
Дата создания: 2009-05-19 12:03:11
Последний раз редактировалось: 2012-02-08 06:41:31
- Дальнейшие уроки:
- Связные списки. Часть 2. Перейти.
До сих пор (смотрите материал из раздела C++) для хранения нескольких значений мы использовали массивы. Связные списки (или просто списки) также предназначены для хранения нескольких значений. Но хранение данных в массивах и списках организовано по разному.
Основная проблема с массивами заключается в том, что нельзя быстро вставить новый элемент в середину массива. Да и просто увеличить массив не получится. Для этого придётся создавать новый массив и копировать туда содержимое старого.
Элементы массива располагаются в памяти друг за другом. В списках же, два соседних элемента могут находиться в разных участках памяти. Посмотрим на код (и массив и список пусть хранят int):
array + 4; // Массив. Четыре элемета вперёд (16 байтов).
list + 4; // Список. Здесь нельзя прибавить 16 байтов,
// элементы расположены в разных участках памяти
Вторая строка некорректна.
Элементы связного списка называются узлами (node). Для того чтобы обеспечить связь между элементами, в каждом элементе помимо значения, нужно хранить указатели на соседние элементы.
Благодаря вот этим особенностям, можно легко вставлять новые узлы в любое место списка, что в массивах делать довольно сложно.
Сначала мы рассмотрим ситуацию, когда в узлах хранится указатель только на следующий узел. Такие списки называются односвязными или однонаправленными (singly linked list).
Односвязные списки (однонаправленные)
В узлах связных списков мы будем хранить значения типа int.
Односвязные списки редко используют в реальных программах. Но они просты в реализации, поэтому мы начнём с них.
Каждый узел односвязного списка состоит из двух переменных. В первой хранится значение. Вторая представляет из себя указатель на следующий узел.
Самый простой список можно реализовать с помощью всего лишь одного класса, который будет представлять узлы:
class SListNode // SListNode - название класса, представляющего
{ // узел односвязного списка
public:
int data; // целая переменная хранит данные узла
SListNode* next; // указатель на следующий узел списка
};
Класс хранит переменную целого типа и укзатель на следующий узел (узел - node).
Уже можно написать программу использующую списки:
SListNode* list = new SListNode; list->data = 0; list->next = new SListNode; // создание следующего узла list->next->data = 1; list->next->next = new SListNode; list->next->next->data = 2;
При этом мы создаём указтель на первый узел и через него получаем доступ ко всем следующим узлам.
Данная реализация списка очень примитивна. При увеличении односвязного списка становится очень сложно вставлять новые узлы и получать доступ к существующим. Представьте, какой код нужно написать, чтобы получить доступ к данным хранящимся в двадцатом узле списка!
Для реализации более продвинутого односвязного списка, нам понадобится три класса. Первый будет представлять узлы списка (мы уже начали его писать - SListNode), второй - сам односвязный список (SLinkedList) а третий - итератор списка (SListIterator).
Добавим конструктор к класс Node, который будет инициализировать поля класса:
SListNode();
SListNode::SListNode ()
{
data = 0;
next = NULL;
}
Примечание: во всех примерах я буду указывать прототип функции и определение функции.
Тут всё просто, полю data, которое хранит значение узла, присваивается ноль. А полю next, в котором хранится указатель на следующий узел, присваивается NULL. NULL - это такой ноль для указателей.
Кроме конструктора, в классе Node будет одна функция. Назовём её InsertAfter (вставить после). Её задачей будет вставка нового элемента списка после текущего:
void InsertAfter(int);
void SListNode::InsertAfter( int d)
{
SListNode* new_node = new SListNode; // Создаём указатель на узел.
new_node->data = d; // Заполняем поле data.
new_node->next = next; // Заполняем поле next. Этому полю присваиваем
// значение поля next текущего элемента
next = new_node; // Меняем поле next текущего элемента. Теперь, текущий
} // узел указывает на вновь созданный
Функция принимает один аргумент - значение, которое будет вставлено в поле data.
Вставляемый узел должен указывать на следующий, а указатель текущего узла необходиом направить на вновь создваваемый элемент списка.
На этом реализация класса SListNode закончена. Приступим непосредственно к созданию списка.
Класс односвязного списка SLinkedList
class SLinkedList
{
public:
SListNode* head; // первый элемент списка
SListNode* tail; // последний элемент списка
int count;
};
В списке будет хранится три переменные. Два указателя на узлы: на первый (head) и на последний (tail) и переменная целого типа count, в которой будет храниться количество элементов (узлов) связного списка.
Конструктор односвязного списка
Конструктор списка в нашей реализации довольно прост:
SLinkedList();
SLinkedList::SLinkedList () : count(0), head(NULL), tail(NULL)
{}
Здесь полям класса присваиваются инициализирующие значения. count - 0, а head и tail - NULL.
Деструктор списка
В данном примере у нас впервые возникает потребность в деструкторе класса. Деструктор класса - это функция вызываемая при уничтожении класса. Также как и конструктор, деструктор не нужно вызывать явно. Имя деструктора совпадает с именем класса (а соответсвенно и с именем конструктора), но перед именем стоит знак тильда ~ (обычно расположен на месте буквы ё в английской расскладке):
~SLinkedList();
SLinkedList::~SLinkedList()
{
SListNode* delNode = head;
SListNode* temp;
while (delNode != NULL)
{
temp = delNode->next;
delete delNode;
delNode = temp;
}
}
Необходимость деструктора обусловлена там, что при уничтожении класса SLinkedList, также необходимо уничтожить и все объекты класса SListNode, являющимися узлами списка. Но между этими классами нет никакой связи, и автоматически узлы не уничтожатся. В результате чего может возникнуть утечка памяти.
В функции нам необходимы два указателя на узлы: который мы будем сейчас удалять, и указатель на следующий узел, чтобы не потеряться.
В цикле идёт проверка значения текущего элемента списка. Если в укзателе содержится NULL, значит список кончился.
Если в списке ещё есть узлы, то мы сохраняем указатель на следующий узел во временном узле temp. Затем удаляем текущий узел операцией delete. Теперь мы не можем указать на следующий узел с помощью текущего узла:
delNode->next; // этот код не работает!!!
Память выделенную под delNode мы уже отпустили, а указатель теперь указывает на совершенно другую область памяти. Именно для этого нам и нужна была вспомогательная переменная temp. Если бы её не было, мы бы потеряли все следующие узлы. Теперь указателю delNode присваивается next и в следующей итерации цикла всё повторяется.
Метод добавления элемента в конец списка
void PushBack (int);
void SLinkedList::PushBack (int d)
{
if (count == 0) // В списке нет элементов.
{
head = tail = new SListNode;
head->data = d;
}
else // В списке есть хотя бы один элемент
{
tail->InsertAfter(d);
tail = tail->next;
}
count++;
}
При добавлении узла в конец списка, возможны два варианта: в списке совсем нет элементов или в списке есть хотя бы один элемент. Эти условия мы проверяем с помощью поля count, хранящей количество элементов списка.
Так вот, если в списке нет элементов, то мы создаём новый узел, а указателям tail и head присваиваем адрес этого элемента.
Если же в списке есть хотя бы один элемент, то мы создаём узел после узла tail, а затем передвигаем tail вперёд (чтобы этот указатель указывал на новый элемент).
Конечно же, в функции PushBack нужно не забыть увеличить переменную count, так как количество узлов увеличилось.
Теперь, когда у нас есть функция добавления узла в конец списка, неплохо было бы научить наш список добавлять элементы в начало.
Метод добавления узлов в начало связного списка
void PushFront (int);
void SLinkedList::PushFront (int d)
{
if (count == 0)
{
head = tail = new SListNode;
head->data = d;
}
else
{
SListNode* new_node = new SListNode;
new_node->data = d;
new_node->next = head;
head = new_node;
}
count++;
}
Также как и в функции PushBack, здесь возможны два варианта: список пустой или в списке уже есть хотя бы один узел.
В случае если список пуст, мы делаем то же самое, что и в функции PushBack.
Если же в списке есть элементы, мы создаём новый узел. Полю next нового узла присваиваем head. А затем меняем значение head, чтобы он указывал на новый узел.
Теперь наш список умеет добавлять узлы в конец и в начало. Кроме того, список корректно уничтожается с помощью деструктора. Неплохо было бы иметь возможность удалять узлы из списка во время выполнения програмы. В рамках класса SLinkedLIst мы можем удалить элементы из начала и из конца. Удаление элементов из середины, в данном классе реализовать невозможно. Поэтому удаление элементов из середины списка мы рассмотрим позже, когда будем рассматривать итераторы. А сейчас:
Функция удаления первого элемента списка
Тут всё очень просто:
void PopFront();
void SLinkedList::PopFront()
{
if (count != 0)
{
SListNode* temp = head;
head = head->next;
delete temp;
count--;
if (head == NULL) // в списке был один элемент
tail = head;
}
}
Удалять элемент имеет смысл, если список не пустой. Поэтому мы проверяем переменную count.
В фунции используется временная переменная, также как в деструкторе. Только в данном случае нам нужно удалить только один элемент. Затем мы уменьшаем количество элементов в переменной count.
Если в списке был один элемент (head == tail == "корректный адрес", а поля head->next == tail->next == NULL), нам нужно изменить значение указателя tail.
Метод удаления последнего узла списка
Эта функция сложнее предыдущей. Мы не можем просто так удалить узел, на который указывает tail. tail нужно передвинуть на один элемент назад. Для того чтобы узнать адрес предпоследнего элемента нам нужно "пройти" по всем узлам от начала списка.
void PopBack();
void SLinkedList::PopBack()
{
if (count == 1)
{
delete tail;
head = tail = NULL;
count--;
}
if (count > 1)
{
SListNode* temp = new SListNode;
temp = head;
while (temp->next != tail)
temp = temp->next;
tail = temp;
delete temp->next;
tail->next = NULL;
count--;
}
}
Когда в списке один элемент, мы просто удаляем его, а указателям head и tail присваиваем NULL. Конечно же не забываем и про переменную count.
Если же в списке больше одного элемента, то мы создаём временную переменную, которая будет "пробегать" все элементы. Такие переменные называются итераторами. В деструкторе, кстати, тоже был итератор. Но об итераторах позже.
Временному узлу мы присваиваем адрес первого элемента списка. Далее в цикле происходит проверка поля next временного узла с адресом последнего узла tail. Цикл прекратит выполняться, когда временный узел будет содержать адрес предпоследнего элемента.
После цикла мы передвигаем узаатель tail назад. А затем удаляем последний узел. Обратите внимание, что делается это с помощью поля next предпоследнего узла. Теперь, когда последний элемент удалён, поле next предпоследнего узла указывает в "пустоту", поэтому мы присваиваем этому полю значение NULL.
Вот, в общем-то, почти готовы два класса. Теперь работать со связными списками стало полегче.
SLinkedList list; SListNode* node; list.PushBack(25); list.PushBack(12); list.PushBack(3); list.PushFront(1); list.PushFront(2); node = list.head; node = node->next; node = node->next; cout << node->data << "\n"; // 25
При этом переменная node используется для путешествия по узлам. node в данном случае является итератором. Чтобы ещё больше расширить функциональность списков для итераторов необходимо создать свой класс. Чем мы и займёмся в следующий раз.
To be continued... T.е. оставшуюся часть реализации односвязного списка рассмотрим чуть-чуть позже.