基础扩展 | 18. 静态链表

学习Excel技术，关注微信公众号：

excelperfect

通常，我们使用指针来构建链表。然而，对于没有指针的的编程语言来说，还可以使用数组来构建链表。可以让每个数组元素由两个元素项组成：data和cur，data用来存放数据，cur用来存放该数组元素的后继元素在数组中的下标。这种用数组描述的链表叫做静态链表。

本文以《大话数据结构》第3章3.12节为基础，讲解用VBA代码实现静态链表。具体的实现原理请参阅这本书。

初始化静态链表

下面是作为静态链表的数组的初始化状态。数组的第一个和最后一个元素不存储数据，数组的第一个元素即下标为0的元素的cur存放着备用链表（即数组中未使用的第一个元素）的下标，数组的最后一个元素的cur存放第一个有数值的元素的下标，相当于链表中的头结点，当链表为空时为0，如下图1所示。

图1

实现上图1的代码如下：

'自定义类型

Public Type MyStruct

data As String

cur As Long

End Type

'指定数组大小

Const MAXSIZE = 999

'声明数组

Dim StaticLinkList(MAXSIZE) As MyStruct

'初始化数组元素的cur值

Sub InitList()

Dim i As Long

For i = 0 To MAXSIZE - 1

StaticLinkList(i).cur= i + 1

Next i

StaticLinkList(MAXSIZE).cur = 0

End Sub

下面的代码将数据存储到数组中：

'在数组中存储data值

Sub InitValue()

Dim num As Long

num = 6

StaticLinkList(StaticLinkList(0).cur).data = "甲"

StaticLinkList(StaticLinkList(1).cur).data= "乙"

StaticLinkList(StaticLinkList(2).cur).data = "丁"

StaticLinkList(StaticLinkList(3).cur).data = "戊"

StaticLinkList(StaticLinkList(4).cur).data = "己"

StaticLinkList(StaticLinkList(5).cur).data = "庚"

StaticLinkList(num).cur =0

StaticLinkList(0).cur =num + 1

StaticLinkList(MAXSIZE).cur = 1

End Sub

结果如下图2所示。

图2

静态链表的数据个数

下面的代码返回静态链表中包含data的元素的个数：

'获取链表数组的长度

Function ListLength() As Long

Dim i As Long

Dim j As Long

i =StaticLinkList(MAXSIZE).cur

j = 0

Do While i <> 0

i =StaticLinkList(i).cur

j = j + 1

Loop

ListLength = j

End Function

静态链表的插入操作

将所有未被使用过的及已被删除的数组元素用cur链接成一个备用链表，每当插入元素时，从备用链表上取得第一个节点作为待插入的新节点。如下图3所示，要插入“丙”，则插入到备用链表的第一个节点即下标为7的数组元素。然后，对数据链表中的cur值进行调整，使之前后相连并符合前面所描述的组成链表的规则，以便下次再进行插入、删除或遍历等操作。

下面的代码将数据“丙”插入到链表的第3个元素：

'插入数据

Sub ListInsert()

'要插入的位置

Dim i As Long

'要插入的元素数据值

Dim e As String

i = 3

e = "丙"

'其他声明

Dim j As Long

Dim k As Long

Dim n As Long

'最后一个元素下标

k = MAXSIZE

'备用链表第一个节点下标

j = Malloc

If j Then

'赋给节点data值

StaticLinkList(j).data = e

'找到第i个元素之前的位置

For n = 1 To i - 1

k =StaticLinkList(k).cur

Next n

'将第i个元素之前的cur赋给新元素的cur

StaticLinkList(j).cur= StaticLinkList(k).cur

'将新元素的下标赋值给第i个元素之前的元素的cur

StaticLinkList(k).cur= j

End If

End Sub

'获取备用链表的第1个节点

Function Malloc() As Long

Dim i As Long

i = StaticLinkList(0).cur

If StaticLinkList(0).curThen

StaticLinkList(0).cur= StaticLinkList(i).cur

End If

Malloc = i

End Function

插入元素“丙”后的链表如下图3所示。

图3

静态链表的删除操作

如下图4所示，删除链表中的元素“甲”，代码如下：

'删除数据

Sub ListDelete()

'要删除的位置

Dim i As Long

i = 1

'其他声明

Dim j As Long

Dim k As Long

'最后一个元素下标

k = MAXSIZE

StaticLinkList(i).data =""

'找到第i个元素之前的位置

For j = 1 To i - 1

k =StaticLinkList(k).cur

Next j

'调整cur

j = StaticLinkList(k).cur

StaticLinkList(k).cur =StaticLinkList(j).cur

'回收删除的节点到备用链表

StaticLinkList(i).cur =StaticLinkList(0).cur

StaticLinkList(0).cur = i

End Sub

图4

实现静态链表是一种非常巧妙的思考方式，详细的原理请参见《大话数据结构》第3章3.12节。