Войти
Nebula CommunityСтатьи

Разбор кода Nebula Device2. Часть3. Контейнеры (статья 2 - Списки. Практическое использование)

Автор:

Списки. Практическое использование


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

Начнем с нодов. Узел списка (нод) описан классом nNode. Класс nNode имеет член типа указателя на void, поэтому, вы можете поместить в объект типа nNode адрес одного объекта любого типа.

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


Пример:
nNode node; // все члены класса обнуляются
struct Dummy{}dummy;
nNode node2(&dummy); /* член-указатель на void инициализируется адресом объекта структуры Dummy*/

Можно поместить адрес внешнего объекта на хранение в объект типа nNode и после его создания при помощи операции SetPtr() и получить его после при помощи операции GetPtr():

nNode n;
struct Dummy{}dummy;
n.SetPtr(&dummy); // помещаем в нод адрес объекта dummy
n.GetPtr(); // получаем адрес объекта dummy

Метод GetSucc() возвращает нод, который идет за данным нодом в списке или нуль, если данный нод является последним в списке (стоит перед хвостом). GetPred() действует аналогично, возвращая нод, стоящий перед данным нодом в списке или нуль, если этот нод - первый (стоит после головы списка).

Теперь о классе списка nList.Чтобы проверить, есть ли элементы в списке, нужно вызвать метод IsEmpty() списка, который возвращает true, если список не содержит ни одного элемента. Элементы, играющие роль головы и хвоста списка  (головного и хвостового элементов соответственно), при этом не учитываются, потому что это ненастоящие ноды, а форматированный участок памяти, как я описал в предыдущей статье.

Метод AddHead() добавляет нод в позицию сразу за головой списка, метод AddTail() добавляет нод перед хвостом списка.

Методы GetHead() списка возвращает указатель на нод, стоящий сразу за головой списка или нуль, если список пуст. Список считается пустым, если он содержит только голову и хвост, являющиеся форматированным участком памяти. Метод GetTail() возвращает указатель на нод, сразу перед хвостом списка или нуль, если список пуст.

Типичная операция перебора нодов в списке выглядит следующим образом:

for (nNode* n = list.GetHead(); n != 0; n = n->GetSucc())
    {
      Some* some = (Some*)n->GetPtr();
      // Что-то делаем с some
    }

Чтобы убрать нод из списка, в котором он находится, применяется операция Remove(). Она связывает элементы списка, идущие перед и за нодом, и обнуляет члены-указатели самого нода на его предыдущий и его следующий элементы в списке. Но для удаления нодов из списка, как правило, применяются методы RemHead() и RemTail().

Метод RemHead() вызывает операцию Remove() для нода, стоящего сразу за головой списка и возвращает указатель на него. Если же список пуст, то просто возвращается нуль. Метод RemTail() действует аналогично, но по отношению к элементу, стоящему перед хвостом списка. Возвращение нода при его удалении из списка может быть удобным, например, когда нужно удалить нод, который был создан динамически:

nNode* n = new nNode;
nList list;
list.AddHead(n);
delete list.RemHead();

Удобный и, думаю, самый практичный способ очистки списка, это использование цикла while, следующий:

nList list;
// Добавляем ноды
while (!list.IsEmpty())
    {
      nNode* n = list.RemHead();
      // удаляем нод из памяти, если он был создан динамически
    }

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

+ Показать

6 мая 2016