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

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

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

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

`дизайн Класса dlnode`

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

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

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

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

Class Properties

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

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

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

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

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

dlnode — Создайте узел и присвойте значение, переданное как вход свойству Data
insertAfter Вставьте этот узел после заданного узла
insertBefore Вставьте этот узел перед заданным узлом
removeNode — Удалите этот узел из списка и повторно подключите остающиеся узлы
clearList — Удалите большие списки эффективно
удаление Закрытый метод, вызванный 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: []

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