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

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

Для листинга кода определения класса см. dlnode Резюме Класса.

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

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

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

Массив данных
Обработайте к следующему узлу
Обработайте к предыдущему узлу

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

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

Class Properties

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

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

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

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

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. Используя связанный список с тремя узлами, заданный в предыдущем разделе, можно продемонстрировать, что следующие операторы верны:

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

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

x = n2;

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

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

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

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

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

Сопутствующая информация

Для получения дополнительной информации о классах Handle смотрите Сравнение Классов Указателя и Значения.

`dlnode` Резюме класса

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

Пример кода	Обсуждение
classdef dlnode < handle	дизайн Класса dlnode Почему класс Handle для связанных списков? Сравнение классов указателя и значения
properties Data end	дизайн Класса dlnode
properties (SetAccess = private) Next = dlnode.empty Prev = dlnode.empty end	Атрибуты свойств: `SetAccess`. Инициализируйте эти свойства к `empty` `dlnode` объекты. Для получения общей информации о свойствах, см. Синтаксис свойств
methods	Для получения общей информации о методах, seeMethods в Проекте Класса
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

Class Properties

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

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)

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 теперь установлен to nnew
```
n1.Next = nnew;
```

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

removeNode метод удаляет узел из списка и повторно подключает остающиеся узлы. 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 метод на том узле. removeNode метод отключает узел и повторно подключает список прежде, чем позволить MATLAB уничтожать удаленный узел. MATLAB уничтожает узел, если ссылки на него другими узлами удалены, и список повторно подключен.

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

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

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

Удалить Метод

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

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

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

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

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

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

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

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

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

Следующее определение класса показывает, как вывести 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

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: []

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