用类实现链表- MATLAB & Simulink万博1manbetx - 万博1manbetx,s manbetx 845,万博尤文图斯

用类实现链表

类定义代码

有关类定义代码清单，请参见dlnode类简介．

要使用类，请创建一个名为@dlnode并保存dlnode.m到这个文件夹。的父文件夹@dlnode必须在MATLAB中^®路径。另外,保存dlnode.m到路径文件夹。

`dlnode`类的设计

dlnode是用于创建双链表的类，其中每个节点包含:

数据数组
下一个节点的句柄
上一个节点的句柄

每个节点都有方法使节点:

插入到链表中的指定节点之前
插入到链表中的特定节点之后
从列表中删除

类属性

的dlnode类将每个节点实现为具有三个属性的句柄对象:

数据—包含该节点的数据
下一个-包含列表中下一个节点的句柄(SetAccess = private）
上一页-包含列表中前一个节点的句柄(SetAccess = private）

该图显示了一个包含三个节点的列表n1,n2,n3．它还显示了节点如何引用下一个和上一个节点。

双链表中的三个节点

类方法

的dlnode类实现以下方法:

dlnode构造一个节点并将作为输入传递的值赋给数据财产
insertAfter—将该节点插入到指定节点后
方法—将该节点插入到指定节点之前
removeNode—将该节点从列表中移除，并重新连接其他节点
clearList-有效地删除大型列表
删除-删除列表时由MATLAB调用的私有方法。

创建双链表

方法来创建节点，方法是将节点的数据传递给dlnode类的构造函数。例如，这些语句用数据值创建了三个节点1,2,3.:

N1 = dlnode(1);N2 = dlnode(2);N3 = dlnode(3);

使用为此目的设计的类方法将这些节点构建到双链表中:

n2.insertAfter (n1)在n1后面插入n2n3.insertAfter (n2)在n2之后插入n3

现在这三个节点是相连的:

n1。下一个%指向n2

ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]

n2.Next.Prev%指向n2

ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]

n1.Next.Next%指向n3

ans = dlnode with properties: Data: 3 Next: [] Prev: [1x1 dlnode]

n3.Prev.Prev%指向n1

ans = dlnode with properties: Data: 1 Next: [1x1 dlnode] Prev: []

为什么是链表的句柄类?

每个节点都是唯一的，因为没有两个节点可以在同一个节点的前面或后面。

例如，一个节点对象，节点，包含在其下一个属性下一个节点对象的句柄，节点。下一个．类似地,上一页属性包含上一个节点的句柄，节点。上一页．使用前一节中定义的三节点链表，你可以证明以下语句是正确的:

n1。下一步== n2Prev == n1

现在假设你分配n2来x:

X = n2;

以下两个等式成立:

X == n1。下一个x．Prev == n1

但是每个节点的实例都是唯一的，所以列表中只有一个节点可以满足等于的条件n1。下一个有一个上一页属性的句柄n1．因此,x必须指向相同的节点n2．

必须有一种方法让多个变量引用同一个对象。MATLAB处理类为两者提供了一种手段x而且n2引用相同的节点。

句柄类定义情商(使用方法方法(处理)来列出句柄类方法)，这样就可以使用= =所有句柄对象的运算符。

`dlnode`课程简介

介绍方法的实现dlnode类。

示例代码	讨论
classdefDlnode < handle	dlnode类设计为什么是链表的句柄类? 句柄类和值类的比较
属性数据结束	dlnode类设计
属性(SetAccess = private)下一步= dlnode。empty Prev = dlnode.empty结束	属性的属性:`SetAccess`．将这些属性初始化为`空dlnode`对象。有关属性的一般信息，请参见属性的语法
方法	有关方法的一般信息，请参见课堂设计方法
函数node = dlnode(数据)如果(nargin > 0)节点。数据=数据;结束结束	创建单个节点(未连接)只需要数据。有关构造函数的一般信息，请参见建造商指引
函数insertAfter(newNode, nodeBefore) remove (newNode);newNode。下一个= nodeBefore.Next; newNode.Prev = nodeBefore;如果~isempty(nodeBefore.Next) nodeBefore.Next. prev = newNode;结束nodeBefore。下一个= newNode;结束	在指定节点之后插入节点到双链表中，或者如果还没有列表，则链接两个指定节点。为指定正确的值`下一个`而且`上一页`属性。插入节点
函数insertBefore(newNode, nodeAfter);newNode。下一个= nodeAfter; newNode.Prev = nodeAfter.Prev;如果~isempty(nodeAfter.Prev)结束nodeAfter。上一页= newNode;结束	在指定节点之前插入节点到双链表中，如果没有链表，则连接两个指定节点。此方法为指定正确的值`下一个`而且`上一页`属性。看到插入节点
函数removeNode(节点)如果~ isscalar(节点)错误(“节点必须是标量”）结束prevNode = node.Prev;nextNode = node.Next;如果~ isempty (prevNode) prevNode。Next = nextNode;结束如果~ isempty (nextNode) nextNode。Prev = prevNode;结束节点。下一个= = dlnode.empty; node.Prev = = dlnode.empty;结束	删除节点并修复列表，以使其余节点正确连接。`节点`参数必须为标量。一旦没有对节点的引用，MATLAB就会删除它。移除节点
函数clearList(node) prev = node. prev;next = node.Next;removeNode(节点)而~isempty(next)节点= next;next = node.Next;removeNode(节点);结束而~isempty(prev)节点= prev;prev = node.Prev;removeNode(节点)结束结束	避免由于清除列表变量而对析构函数进行递归调用。遍历列表以断开每个节点。当没有对节点的引用时，MATLAB调用类析构函数(参见`删除`方法)，然后删除它。
方法(Access = private)函数删除(节点)clearList(节点)结束	类析构函数方法。MATLAB调用`删除`方法删除仍然连接到列表的节点。
结束结束	私有方法结束，类定义结束。

扩展类代码

类属性

只有dlnode类方法可以设置下一个而且上一页属性，因为这些属性具有私有集访问权限(SetAccess = private)．使用私有集访问可以防止客户端代码对这些属性执行任何不正确的操作。的dlnode类方法执行这些节点上允许的所有操作。

的数据属性具有公共设置和获取访问权限，允许您查询和修改的值数据是必需的。

以下是如何dlnode类定义属性:

属性数据结束属性(SetAccess = private) Next = dlnode.empty;Prev = dlnode.empty;结束

构造节点对象

要创建一个节点对象，将节点的数据指定为构造函数的参数:

函数node = dlnode(数据)如果Nargin > 0节点。数据=数据;结束结束

插入节点

在列表中插入节点有两种方法-insertAfter而且方法．这些方法执行类似的操作，因此本节仅介绍insertAfter在细节。

函数insertAfter(newNode, nodeBefore) remove (newNode);newNode。下一个= nodeBefore.Next; newNode.Prev = nodeBefore;如果~isempty(nodeBefore.Next) nodeBefore.Next. prev = newNode;结束nodeBefore。下一个= newNode;结束

如何insertAfter的工作原理。首先,insertAfter调用removeNode方法以确保新节点未连接到任何其他节点。然后,insertAfter分配的newNode下一个而且上一页属性的前后节点句柄newNode列表中的位置。

例如，假设你想插入一个新节点，nnew，在现有节点后，n1，在包含n1-n2-n3．

首先,创建nnew:

Nnew = dlnode(rand(3));

接下来,调用insertAfter插入nnew进入之后的列表n1:

nnew.insertAfter (n1)

的insertAfter方法执行以下步骤来插入nnew在列表中n1而且n2:

集nnew。下一个来n1。下一个（n1。下一个是n2)：
```
nnew。下一个= n1.Next;
```
集nnew。上一页来n1
```
nnew。上一页= n1;
```
如果n1。下一个不是空的，那么n1。下一个仍然是n2,所以n1.Next.Prev是n2。上一页，设置为nnew
```
n1.Next.Prev= nnew;
```
n1。下一个现在设置为nnew
```
n1。Next = nnew;
```

新节点插入双链表

移除节点

的removeNode方法从列表中删除节点并重新连接其余节点。的方法而且insertAfter方法总是调用removeNode在尝试将其连接到链表之前，在要插入的节点上。

调用removeNode属性之前，确保节点处于已知状态下一个或上一页属性:

函数removeNode(节点)如果~ isscalar(节点)错误(输入必须是标量）结束prevNode = node.Prev;nextNode = node.Next;如果~ isempty (prevNode) prevNode。Next = nextNode;结束如果~ isempty (nextNode) nextNode。Prev = prevNode;结束节点。下一个= dlnode.empty; node.Prev = dlnode.empty;结束

例如，假设你移除n2从三个节点的列表(n1-n2-n3)：

n2.removeNode;

从双链表中删除节点后断开链接

removeNode删除n2，并按以下步骤重新连接其余节点:

n1 = n2.Prev;n3 = n2.Next;如果N1存在，那么N1。Next = n3;如果N3存在，那么N3。Prev = n1

重新加入列表是因为n1连接到n3而且n3连接到n1．最后一步是确保这一点n2。下一个而且n2。上一页都是空的(即，n2没有连接):

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

从列表中移除节点

假设你创建了一个有10个节点的列表，并将句柄保存到列表的头部:

Head = dlnode(1);为I = 10:-1:2 new = dlnode(I);负责人insertAfter(新);结束

现在删除第三个节点(数据属性的值。3.)：

removeNode (head.Next.Next)

现在列表中的第三个节点的数据值为4:

head.Next.Next

ans = dlnode with properties: Data: 4 Next: [1x1 dlnode] Prev: [1x1 dlnode]

前一个节点有a数据的价值2:

头。下一个

ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]

删除节点

要删除节点，调用removeNode方法。的removeNode方法在允许MATLAB销毁被删除的节点之前断开节点并重新连接列表。一旦删除了其他节点对该节点的引用，并重新连接该列表，MATLAB就会销毁该节点。

从双链表中删除节点后重新连接链接

删除列表

当创建链表并为包含链表头部或尾部的变量赋值时，清除该变量将导致析构函数递归遍历整个链表。对于足够大的列表，清除列表变量会导致MATLAB超出其递归限制。

的clearList方法通过遍历列表并断开每个节点来避免递归并提高删除大型列表的性能。clearList接受列表中任何节点的句柄，并删除其余节点。

函数clearList(节点)如果~ isscalar(节点)错误(输入必须是标量）结束prev = node.Prev;next = node.Next;removeNode(节点)而~isempty(next)节点= next;next = node.Next;removeNode(节点);结束而~isempty(prev)节点= prev;prev = node.Prev;removeNode(节点)结束结束

例如，假设你创建了一个有很多节点的列表:

Head = dlnode(1);为nextNode = dlnode(k);insertAfter (nextNode头)结束

的变量头包含列表头节点的句柄:

头

head = dlnode with properties: Data: 1 Next: [1x1 dlnode] Prev: []

头。下一个

ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]

你可以打电话clearList删除整个列表:

clearList(头)

MATLAB唯一没有删除的节点是那些存在显式引用的节点。在本例中，这些引用是头而且nextNode:

头

head = dlnode with properties: Data: 1 Next: [] Prev: []

nextNode

nextNode = dlnode with properties: Data: 2 Next: [] Prev: []

你可以通过清除变量来移除这些节点:

清晰的头nextNode

删除方法

的删除方法只调用clearList方法:

方法(Access = private)函数删除(节点)clearList(节点)结束结束

的删除方法具有私有访问权限，以防止用户调用删除当打算删除单个节点时。MATLAB调用删除当列表被销毁时，隐式地。

若要从列表中删除单个节点，请使用removeNode方法。

专门化`dlnode`类

的dlnode类实现了双链表，并为创建更专门的链表类型提供了方便的起点。例如，假设您想要创建一个列表，其中每个节点都有一个名称。

而不是复制用于实现的代码dlnode类，然后对其进行扩展，您可以从中派生一个新类dlnode(即子类dlnode)．的所有特性都可以创建一个类dlnode并且还定义了它自己的附加特性。因为dlnode是句柄类，这个新类也是句柄类。

`NamedNode`类定义

要使用类，请创建一个名为@NamedNode并保存NamedNode.m到这个文件夹。的父文件夹@NamedNode必须在MATLAB路径上。另外,保存NamedNode.m到路径文件夹。

类的定义说明如何派生NamedNode类的dlnode类:

classdefNamedNode < dlnode属性Name =”结束方法函数n = NamedNode (name,data)如果Nargin == 0 name =”；数据= [];结束N = n@dlnode(数据);n.名字;结束结束结束

的NamedNode类添加的名字属性存储节点名称。

类的类构造函数dlnode类，然后将值赋给的名字财产。

使用`NamedNode`创建一个双重链表

使用NamedNode类，比如dlnode类，除非您为每个节点对象指定一个名称。例如:

n(1) = NamedNode(的第一个节点, 100);n(2) = NamedNode(“第二个节点”, 200);n(3) = NamedNode(“第三个节点”, 300);

现在使用继承自的插入方法dlnode要构建列表:

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

单个节点在查询属性时显示其名称和数据:

n(1)。下一个

ans =带有属性的NamedNode:名称:“第二个节点”数据:200下一步:[1x1 NamedNode]前视:[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属性:名称:'第一个节点'数据:100下一个:[1x1 NamedNode]前一个:[]