Реализация связанных списков с классами

Код определения класса

Перечень кода определения классов см. в dlnode Class Synopsis.

Чтобы использовать класс, создайте папку с именем @dlnode и сохраните dlnode.m в эту папку. Родительская папка @dlnode должен находиться на MATLAB^® путь. Кроме того, сохраните dlnode.m в папку с путем.

`dlnode` Классы Проекта

dlnode - класс для создания дважды связанных списков, в которых каждый узел содержит:

Массив данных
Указатель на следующий узел
Указатель на предыдущий узел

Каждый узел имеет методы, которые позволяют узлу быть:

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

Свойства класса

The dlnode класс реализует каждый узел как указатель объекта с тремя свойствами:

Data - Содержит данные для этого узла
Next - Содержит указатель на следующий узел в списке (SetAccess = private)
Prev - Содержит указатель на предыдущий узел в списке (SetAccess = private)

Эта схема показывает список с тремя узлами n1, n2, и n3. Также показано, как узлы ссылаются на следующий и предыдущий узлы.

Методы классов

The dlnode класс реализует следующие методы:

dlnode - Создайте узел и присвойте значение, переданное в качестве входов Data свойство
insertAfter - Вставить этот узел после указанного узла
insertBefore - Вставить этот узел перед указанным узлом
removeNode - Удалите этот узел из списка и снова соедините оставшиеся узлы
clearList - Эффективно удалять большие списки
delete - Частный метод, вызываемый MATLAB при удалении списка.

Создание списка с двойной связью

Создайте узел путем передачи данных узла в dlnode конструктор классов. Для примера эти операторы создают три узла со значениями данных 1, 2, и 3:

n1 = dlnode(1);
n2 = dlnode(2);
n3 = dlnode(3);

Создайте эти узлы в дважды связанный список с помощью методов класса, разработанных для этой цели:

n2.insertAfter(n1) % Insert n2 after n1
n3.insertAfter(n2) % Insert n3 after n2

Теперь три узла связаны:

n1.Next % Points to n2

ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

n2.Next.Prev % Points back to n2

ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

n1.Next.Next % Points to n3

ans = 

  dlnode with properties:

    Data: 3
    Next: []
    Prev: [1x1 dlnode]

n3.Prev.Prev % Points to n1

ans = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []

Почему класс Handle для связанных списков?

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

Для примера, объекта узла, node, содержит в своем Next свойство указателя на следующий объект узла, node.Next. Точно так же Prev свойство содержит указатель на предыдущий узел, node.Prev. Используя трехузловый связанный список, определенный в предыдущем разделе, можно продемонстрировать, что следующие операторы являются true:

n1.Next == n2
n2.Prev == n1

Теперь предположим, что вы присваиваете n2 на x:

x = n2;

Затем верны следующие два равенства:

x == n1.Next
x.Prev == n1

Но каждый образец узла уникален, поэтому в списке есть только один узел, который может удовлетворять условиям равного n1.Next и иметь Prev свойство, содержащее указатель на n1. Поэтому x должен указывать на тот же узел, что и n2.

Должен быть способ, чтобы несколько переменных ссылались на один и тот же объект. Система MATLAB handle класс предоставляет средство для обоих x и n2 для обращения к тому же узлу.

Класс handle задает eq метод (использование methods('handle') для перечисления методов класса handle), что позволяет использовать == оператор со всеми указателями объектов.

Связанная информация

Для получения дополнительной информации о классах handle, см. Сравнение классов handle и value.

`dlnode` Обобщение классов

В этом разделе описывается реализация dlnode класс.

Пример кода	Обсуждение
classdef dlnode < handle	dlnode Проект классов Почему класс Handle для связанных списков? Сравнение классов Handle и Value
properties Data end	dlnode Проект классов
properties (SetAccess = private) Next = dlnode.empty Prev = dlnode.empty end	Атрибуты свойств: `SetAccess`. Инициализируйте эти свойства в `empty` `dlnode` объекты. Общие сведения о свойствах см. в разделе Синтаксис свойств
methods	Для получения общей информации о методах см. Methods in Class Design
function node = dlnode(Data) if (nargin > 0) node.Data = Data; end end	Для создания отдельного узла (не связанного) требуются только данные. Общие сведения о конструкторах см. в Руководствах по конструкторам
function insertAfter(newNode, nodeBefore) removeNode(newNode); newNode.Next = nodeBefore.Next; newNode.Prev = nodeBefore; if ~isempty(nodeBefore.Next) nodeBefore.Next.Prev = newNode; end nodeBefore.Next = newNode; end	Вставьте узел в дважды связанный список после указанного узла или соедините два указанных узла, если еще нет списка. Присваивает правильные значения для `Next` и `Prev` свойства. Вставка узлов
function insertBefore(newNode, nodeAfter) removeNode(newNode); newNode.Next = nodeAfter; newNode.Prev = nodeAfter.Prev; if ~isempty(nodeAfter.Prev) nodeAfter.Prev.Next = newNode; end nodeAfter.Prev = newNode; end	Вставьте узел в двойной список перед указанным узлом или соедините два указанных узла, если еще нет списка. Этот метод присваивает правильные значения для `Next` и `Prev` свойства. См. Вставка узлов
function removeNode(node) if ~isscalar(node) error('Nodes must be scalar') end prevNode = node.Prev; nextNode = node.Next; if ~isempty(prevNode) prevNode.Next = nextNode; end if ~isempty(nextNode) nextNode.Prev = prevNode; end node.Next = = dlnode.empty; node.Prev = = dlnode.empty; end	Удалите узел и исправьте список так, чтобы оставшиеся узлы были правильно подключены. `node` аргумент должен быть скалярным. Если нет ссылок на узел, MATLAB удаляет его. Удаление узла
function clearList(node) prev = node.Prev; next = node.Next; removeNode(node) while ~isempty(next) node = next; next = node.Next; removeNode(node); end while ~isempty(prev) node = prev; prev = node.Prev; removeNode(node) end end	Избегайте рекурсивных вызовов деструктора в результате очистки переменной списка. Цикл через список, чтобы отсоединить каждый узел. Когда нет ссылок на узел, MATLAB вызывает деструктор классов (см. `delete` метод) перед его удалением.
methods (Access = private) function delete(node) clearList(node) end	Метод деструктора классов. MATLAB вызывает `delete` метод удаления узла, который все еще соединяется со списком.
end end	Конец частных методов и конец определения класса.

Разверните для кода класса

classdef dlnode < handle
   % dlnode A class to represent a doubly-linked node.
   % Link multiple dlnode objects together to create linked lists.
   properties
      Data
   end
   properties(SetAccess = private)
      Next = dlnode.empty
      Prev = dlnode.empty
   end
   
   methods
      function node = dlnode(Data)
         % Construct a dlnode object
         if nargin > 0
            node.Data = Data;
         end
      end
      
      function insertAfter(newNode, nodeBefore)
         % Insert newNode after nodeBefore.
         removeNode(newNode);
         newNode.Next = nodeBefore.Next;
         newNode.Prev = nodeBefore;
         if ~isempty(nodeBefore.Next)
            nodeBefore.Next.Prev = newNode;
         end
         nodeBefore.Next = newNode;
      end
      
      function insertBefore(newNode, nodeAfter)
         % Insert newNode before nodeAfter.
         removeNode(newNode);
         newNode.Next = nodeAfter;
         newNode.Prev = nodeAfter.Prev;
         if ~isempty(nodeAfter.Prev)
            nodeAfter.Prev.Next = newNode;
         end
         nodeAfter.Prev = newNode;
      end
      
      function removeNode(node)
         % Remove a node from a linked list.
         if ~isscalar(node)
            error('Input must be scalar')
         end
         prevNode = node.Prev;
         nextNode = node.Next;
         if ~isempty(prevNode)
            prevNode.Next = nextNode;
         end
         if ~isempty(nextNode)
            nextNode.Prev = prevNode;
         end
         node.Next = dlnode.empty;
         node.Prev = dlnode.empty;
      end
      
      function clearList(node)
         % Clear the list before
         % clearing list variable
         prev = node.Prev;
         next = node.Next;
         removeNode(node)
         while ~isempty(next)
            node = next;
            next = node.Next;
            removeNode(node);
         end
         while ~isempty(prev)
            node = prev;
            prev = node.Prev;
            removeNode(node)
         end
      end
   end
   
   methods (Access = private)
      function delete(node)
         clearList(node)
      end
   end
end

Свойства класса

Только dlnode методы класса могут задать Next и Prev свойства, поскольку эти свойства имеют доступ к частному набору (SetAccess = private). Использование доступа к частному набору препятствует выполнению клиентским кодом неправильной операции с этими свойствами. The dlnode методы класса выполняют все операции, которые разрешены на этих узлах.

The Data свойство имеет общий набор и получить доступ, что позволяет вам запросить и изменить значение Data по мере необходимости.

Вот как dlnode класс определяет свойства:

properties
   Data
end
properties(SetAccess = private)
   Next = dlnode.empty;
   Prev = dlnode.empty;
end

Создайте объект узла

Чтобы создать объект узла, укажите данные узла в качестве аргумента для конструктора:

function node = dlnode(Data)
   if nargin > 0
      node.Data = Data;
   end
end

Вставка узлов

Существует два метода вставки узлов в список - insertAfter и insertBefore. Эти методы выполняют аналогичные операции, поэтому этот раздел описывает только insertAfter в деталях.

function insertAfter(newNode, nodeBefore)
   removeNode(newNode);
   newNode.Next = nodeBefore.Next;
   newNode.Prev = nodeBefore;
   if ~isempty(nodeBefore.Next)
      nodeBefore.Next.Prev = newNode;
   end
   nodeBefore.Next = newNode;
end

Как insertAfter Работает. Во-первых, insertAfter вызывает removeNode метод, чтобы убедиться, что новый узел не соединен ни с какими другими узлами. Затем, insertAfter назначает newNode Next и Prev свойства для указателей на узлы, которые находятся после и перед newNode расположение в списке.

Например, предположим, что вы хотите вставить новый узел, nnew, после существующего узла, n1, в списке, содержащем n1—n2—n3.

Во-первых, создайте nnew:

nnew = dlnode(rand(3));

Далее звоните insertAfter для вставки nnew в список после n1:

nnew.insertAfter(n1)

The insertAfter метод выполняет следующие шаги для вставки nnew в списке между n1 и n2:

Задайте nnew.Next на n1.Next (n1.Next является n2):
```
nnew.Next = n1.Next;
```
Задайте nnew.Prev на n1
```
nnew.Prev = n1;
```
Если n1.Next не пуст, тогда n1.Next все еще n2, так n1.Next.Prev является n2.Prev, который установлен в nnew
```
n1.Next.Prev = nnew;
```
n1.Next теперь установлено значение nnew
```
n1.Next = nnew;
```

Удаление узла

The removeNode метод удаляет узел из списка и повторно соединяет оставшиеся узлы. The insertBefore и insertAfter методы всегда вызывают removeNode на вставляемом узле перед попыткой подключения его к связанному списку.

Вызывающие removeNode гарантирует, что узел находится в известном состоянии перед назначением его Next или Prev свойство:

function removeNode(node)
   if ~isscalar(node)
      error('Input must be scalar')
   end
   prevNode = node.Prev;
   nextNode = node.Next;
   if ~isempty(prevNode)
      prevNode.Next = nextNode;
   end
   if ~isempty(nextNode)
      nextNode.Prev = prevNode;
   end
   node.Next = dlnode.empty;
   node.Prev = dlnode.empty;
end

Например, предположим, что вы удаляете n2 из трехузлового списка (n1–n2–n3):

n2.removeNode;

removeNode удаляет n2 из списка и повторно соединяет оставшиеся узлы следующими шагами:

n1 = n2.Prev;
n3 = n2.Next;
if n1 exists, then
   n1.Next = n3;
if n3 exists, then
   n3.Prev = n1

Список вновь присоединен, потому что n1 соединяется с n3 и n3 соединяется с n1. Конечным шагом является обеспечение того, чтобы n2.Next и n2.Prev оба пусты (то есть n2 не подключен):

n2.Next = dlnode.empty;
n2.Prev = dlnode.empty;

Удаление узла из списка

Предположим, что вы создаете список с 10 узлами и сохраняете указатель на заголовок списка:

head = dlnode(1);
for i = 10:-1:2
   new = dlnode(i);
   insertAfter(new,head);
end

Теперь удалите третий узел (Data свойство присвоило значение 3):

removeNode(head.Next.Next)

Теперь третий узел в списке имеет значение данных 4:

head.Next.Next

ans = 

  dlnode with properties:

    Data: 4
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

И предыдущий узел имеет Data значение 2:

head.Next

ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

Удаление узла

Чтобы удалить узел, вызовите removeNode метод на этом узле. The removeNode метод отсоединяет узел и повторно соединяет список перед тем, как разрешить MATLAB уничтожить удаленный узел. MATLAB уничтожает узел после удаления ссылок на него другими узлами и повторного подключения списка.

Удалить список

Когда вы создаете связанный список и назначаете переменную, которая содержит, например, заголовок или конец списка, очистка этой переменной заставляет деструктор рекурсивно просматривать весь список. При достаточно большом списке очистка переменной списка может привести к тому, что MATLAB превысит предел рекурсии.

The clearList метод избегает рекурсии и улучшает эффективность удаления больших списков путем закольцовывания по списку и отключения каждого узла. clearList принимает указатель на любой узел в списке и удаляет оставшиеся узлы.

function clearList(node)
   if ~isscalar(node)
      error('Input must be scalar')
   end
   prev = node.Prev;
   next = node.Next;
   removeNode(node)
   while ~isempty(next)
      node = next;
      next = node.Next;
      removeNode(node);
   end
   while ~isempty(prev)
      node = prev;
      prev = node.Prev;
      removeNode(node)
   end
end

Например, предположим, что вы создаете список со многими узлами:

head = dlnode(1);
for k = 100000:-1:2
   nextNode = dlnode(k);
   insertAfter(nextNode,head)
end

Переменная head содержит указатель на узел в заголовке списка:

head

head = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []

head.Next

ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

Можно вызвать clearList чтобы удалить весь список:

clearList(head)

Единственными узлами, которые не были удалены MATLAB, являются узлы, для которых существует явная ссылка. В этом случае эти ссылки head и nextNode:

head

head = 

  dlnode with properties:

    Data: 1
    Next: []
    Prev: []

nextNode

nextNode = 

  dlnode with properties:

    Data: 2
    Next: []
    Prev: []

Можно удалить эти узлы, очистив переменные:

clear head nextNode

Метод удаления

The delete метод просто вызывает clearList метод:

methods (Access = private)
   function delete(node)
      clearList(node)
   end
end

The delete метод имеет частный доступ, чтобы предотвратить вызов пользователями delete при намерении удалить один узел. MATLAB вызывает delete неявно при уничтожении списка.

Чтобы удалить один узел из списка, используйте removeNode способ.

Специализируйтесь на `dlnode` Класс

The dlnode класс реализует дважды связанный список и предоставляет удобную начальную точку для создания более специализированных типов связанных списков. Например, предположим, что вы хотите создать список, в котором каждый узел имеет имя.

Вместо копирования кода, используемого для реализации dlnode класс, а затем расширяясь на нем, можно вывести новый класс из dlnode (то есть подкласс dlnode). Можно создать класс, который имеет все функции dlnode а также определяет собственные дополнительные функции. А потому dlnode является классом handle, этот новый класс также является классом handle.

`NamedNode` Определение класса

Чтобы использовать класс, создайте папку с именем @NamedNode и сохраните NamedNode.m в эту папку. Родительская папка @NamedNode должен находиться в пути MATLAB. Кроме того, сохраните NamedNode.m в папку с путем.

Следующее определение класса показывает, как вывести NamedNode класс из dlnode класс:

classdef NamedNode < dlnode
   properties
      Name = ''
   end
   methods
      function n = NamedNode (name,data)
         if nargin == 0
            name = '';
            data = [];
         end
         n = n@dlnode(data);
         n.Name = name;
      end
   end
end

The NamedNode класс добавляет Name свойство для хранения имени узла.

Конструктор вызывает конструктор классов для dlnode класс, а затем присваивает значение Name свойство.

Использование `NamedNode` Создание вдвойне связанного списка

Используйте NamedNode класс, подобный dlnode класс, за исключением того, что вы задаете имя для каждого объекта узла. Для примера:

n(1) = NamedNode('First Node',100);
n(2) = NamedNode('Second Node',200);
n(3) = NamedNode('Third Node',300);

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

n(2).insertAfter(n(1))
n(3).insertAfter(n(2))

Один узел отображает его имя и данные, когда вы запрашиваете его свойства:

n(1).Next

ans = 

  NamedNode with properties:

    Name: 'Second Node'
    Data: 200
    Next: [1x1 NamedNode]
    Prev: [1x1 NamedNode]

n(1).Next.Next

ans = 

  NamedNode with properties:

    Name: 'Third Node'
    Data: 300
    Next: []
    Prev: [1x1 NamedNode]

n(3).Prev.Prev

ans = 

  NamedNode with properties:

    Name: 'First Node'
    Data: 100
    Next: [1x1 NamedNode]
    Prev: []

Документация