Реализация односвязных и двусвязных списков. Часть 2
Дата создания: 2009-06-11 01:59:25
Последний раз редактировалось: 2012-02-08 06:50:22
Класс итераторов для односвязных списков
После того, как мы написали классы узла и непосредственно списка, нужно добавить класс итераторов. Итераторы используются для перемещения по списку. Концепция итераторов широко распространена и используется со многими структурами данных.
class SListIterator
{
public:
SListNode* node;
SLinkedList* list;
};
В классе две переменные: указатель на текущий узел списка и указатель на сам список. Указатель на список используется, чтобы определить, к какому списку принадлежит данный итератор.
Методы класса итераторов
Все методы класса чрезвычайно просты.
Класс Iterator содержит конструктор с двумя аргументами.
SListIterator(SListNode*,SLinkedList*);
SListIterator::SListIterator(SListNode* n, SLinkedList* l)
{
node = n;
list = l;
}
В конструктор передаются указатели на узел и список. Заполняются соответствующие поля.
Когда итератор добегает до конца списка, что должно происходить? Итератор не может вернуться в предыдущий элемент. Нужно уничтожать итератор и создавать новый? Вместо этого мы создадим функцию в которой итератор вернётся в начало списка.
void Start();
void SListIterator::Start()
{
node = list->head;
}
Тут всё просто, полю node мы присваиваем поле head переменной list. Здесь и list, и node являются членами класса Iterator.
Следующая функция передвигает итератор в следующий узел.
void Forward();
void SListIterator::Forward()
{
if (node != NULL)
node = node->next;
}
Обратите внимание на проверку условия. Мы можем продвинуть итератор вперёд на один узел дальше узла tail списка. Этот узел содержит значение NULL.
Следующая функция возвращает значение текущего узла.
int& Item();
int& SListIterator::Item()
{
return node->data;
}
Метод возвращает значение по ссылке.
И последняя функция итератора проверяет его значение. Если в итераторе содержится NULL (список закончился или в нём нет элементов), то функция вернёт 0. Если в итераторе содержится корректное значение, то функция вернёт 1.
bool Valid();
bool SListIterator::Valid()
{
return (node != NULL);
}
Теперь перепишем программу. Итератор может добавлять значение, обращаясь к своему полю node. Кроме того, теперь очень легко вывести все элементы списка.
SLinkedList list;
list.PushBack(5);
list.PushBack(6);
list.PushBack(7);
list.PushFront(3);
list.PushFront(2);
SListIterator itr(list.head, &list);
itr.Forward();
itr.node->InsertAfter(4);
for (itr.Start(); itr.Valid(); itr.Forward())
{
cout << itr.Item() << ", ":
}
Вывод:
2, 3, 4, 5, 6, 7,
Хотя, с помощью итераторов и можно добавлять узлы к списку (метод InsertAfter класса SListNode), делается это чудовищно криво. Если итератор указывает на последний узел, и мы вызываем функцию InsertAfter, то список испортится, так как в InsertAfter никак не обрабатывается проверка tail списка. Поэтому для итераторов более правильным решением будет написать собственную функцию. Причём лучше эту функцию сделать не для итераторов а для списков, а итераторы можно передавать в функцию в виде аргументов:
void SLinkedList::Insert(SListIterator&, int);
void Insert( SListIterator& itr, int d)
{
if (itr.Valid())
{
itr.node->InsertAfter(d);
if (itr.node == tail)
{
tail = itr.node->next;
}
count++;
}
}
Мы делаем проверку, на что указывает итератор. Если он указывает на NULL, то ничего не происходит. Если же в итераторе содержится корректное значение, то мы добавляем узел с помощью функции InsertAfter. И теперь нужно проверить, если мы добавили узел после последнего, нужно передвинуть tail.
И последняя функция которую мы рассмотрим: функция удаления узла из связного списка:
void Remove(SListIterator&);
void SLinkedList::Remove(SListIterator& itr)
{
SListNode* temp = head;
if (itr.node == head)
{
itr.Forward();
PopFront();
}
else
{
while (temp->next != itr.node)
temp = temp->next;
itr.Forward();
if (temp->next == tail)
tail = temp;
delete temp->next;
temp->next = itr.node;
}
count--;
}
Данный метод похож на метод удаления последнего элемента списка, здесь также используется временная переменная для хранения указателя на элемент списка.
Двусвязные (двунаправленные) списки
В двусвязных списках (doubly linked list) к узлам добавляется ещё один указатель - на предыдущий узел. Это существенно повышает гибкость структуры данных по сравнению с односвязными списками.
Большинство функций реализующих двунаправленные списки аналогичны тем, что используются для реализации однонаправленных списков. Поэтому мы не будем их подробно рассматривать.
В узле двусвязного списка содержатся два указателя. Помимо указателя на следующий узел, есть указатель и на предыдущий. Это резко увеличивает функциональность двусвязного списка по сравнению с односвязным.
Во-первых следует заметить, что для создания методов двусвязного списка требуется немного больше усилий, та как теперь нужно менять два указателя в отличие от односвязных списков.
Как я уже написал выше, рассматривать методы двусвязных списков мы не будем. Классы необходимые для реализации двусвязных списков вы можете посмотреть здесь. Это заголовочный файл, поэтому достаточно добавить его к проекту и вы сможете пользоваться двусвязными списками.
Пожалуйста, внимательно изучите все классы представленные в файле. Именно на основе этой реализации списков в дальнейшем будут создаваться многие структуры данных. Я постарался как можно сильнее упростить код (в коде почти нет комментариев, и так всё понятно), надеюсь, получилось. Кроме того, обязательно выполните упражнения для двусвязных списков.
Единственное важное отличие данной реализации двусвязных списков, от реализации односвязных, которую мы рассматривали до сих пор - использование шаблонных классов. Если вы ещё не знаете что это такое, то перед рассмотрением кода двусвязных списков изучите шаблонные классы.
Ещё один вид списков (частный случай двусвязного списка) - замкнутый или ещё встерачающееся название - кольцевой или закольцованный список. Это, кстати, наиболее полезный и часто встречающийся вариант связных списков. При этом у последнего элемента списка в поле next хранится head, а у первого элемента в поле previous - tail.
Заключение.
Ну, вот в общем-то, по спискам и всё. Несколько заключительных слов:
Сильная сторона списков заключается в том, что с их помощью можно без проблем добавлять и удалять элементы, что гораздо труднее делать с помощью массивов.
Также можно без проблем изменить размер списков, добавив/удавлив новые узлы.
У списков есть конечно же и слабые стороны. Получить доступ к какому-либо элементу не так просто. Необходимо пройти до этого элемента от начала списка, в то время как в массивах доступ к любому элементу можно получить с помощью индекса.
Кроме того, для хранения списков требуется больше памяти.
В списках удобно хранить объекты больших сложных классов. Если у вас множество мелких объектов, будет эффективнее сохнанить их в массиве. Кроме того, доступ к элементам списков происходит медленнее чем к элементам массива, так как узлы списков хранятся в разных участках памяти.
Мы ещё вернёмся к связным спискам когда будем рассматривать создание игрового ландшафта на основе клеток.
На сегодня всё.
Упражнения (односвязные списки):
1. Для односвязного списка реализуйте интерфейс взаимодействия с пользователем. Примерно как на картинке:
Пользователь вводит какую-нибудь команду, и программа должна корректно обработать эту команду.
Во время выполнения программы, загляните в отладчик и понаблюдайте значения переменных, хранящих список и итераторы.
Во время написания данной программы вы увидите все слабости данной реализации односвязных списков. Откровенно говоря, данная реализация написана довольно паршиво.
Упражнения (двусвязные списки):
1. Напишите два метода класса DListIterator: Start и End. Первый метод устанавливает итератор в начало списка, второй - в конец. Для реализации этих методов необходимо добавить в класс итераторов дополнительное поле - указатель на список.
2. Напишите программу аналогичную программе для связных списков. Набор команд выберите самостоятельно.