Для листинга кода определения класса см. dlnode Резюме Класса.
Чтобы использовать класс, создайте папку под названием @dlnode
и сохраните dlnode.m
к этой папке. Родительская папка @dlnode
должен быть на пути MATLAB®. В качестве альтернативы сохраните dlnode.m
к папке path.
dlnode
Проект классаdlnode
класс для создания двунаправленных связанных списков, в которых каждый узел содержит:
Массив данных
Обработайте к следующему узлу
Обработайте к предыдущему узлу
Каждый узел имеет методы, которые позволяют узлу быть:
Вставленный перед заданным узлом в связанный список
Вставленный после определенного узла в связанный список
Удаленный из списка
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: []
Каждый узел уникален в этом, никакие два узла не могут быть до или рядом с тем же узлом.
Например, объект узла, 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
| |
properties Data end | дизайн Класса dlnode |
properties (SetAccess = private) Next = dlnode.empty Prev = dlnode.empty end | Атрибуты свойств: Инициализируйте эти свойства к Для получения общей информации о свойствах, см. Синтаксис свойств |
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 | Вставьте узел в двунаправленный связанный список после заданного узла или соедините два заданных узла, если уже нет списка. Присваивает правильные значения для |
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 | Вставьте узел в двунаправленный связанный список перед заданным узлом или соедините два заданных узла, если уже нет списка. Этот метод присваивает правильные значения для Смотрите вставляют узлы |
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 | Удалите узел и зафиксируйте список так, чтобы остающиеся узлы были правильно соединены. Однажды нет никаких ссылок на узел, 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 вызывает деструктор класса (см. |
methods (Access = private) function delete(node) clearList(node) end | Метод деструктора класса. MATLAB вызывает |
end end | Конец закрытых методов и конец определения класса. |
Только 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: []