【VB】基于数组的内存管理

天马座

众所周知VB没有指针对象,很多语言也没有指针对象，导致编写链式存储结构很麻烦,但是VB有数组，并且一般情况编写链式存储结构的数据类型的成员都是固定的完全可以使用数组实现，那么数组的索引就相当于内存地址,
比如一个树的节点可以写成如下形式

Dim mem() As TreeNode
debug.print mem(p).key '索引相当于地址 mem数组相当于整个内存

那么我们只需要对数组的规模和索引进行有效的管理就可以了
如果还是不明白可以参考 算法导论 第10章 10.3 指针和对象实现
下面是我封装好的一个类，大家可以直接拿去使用，类外绑定一下数据类型就可以
手机打字有点费劲 例子就不写了，自行脑补

1. Private Const START_HEADER = 0
2. Private header As Long, allocCount As Long, last As Long
3. Private nextFree() As Long
4. Private Sub Class_Initialize()
5.     Call clear
6. End Sub
7. Private Sub Class_Terminate()
8.     Erase nextFree
9. End Sub
10. Public Property Get count() As Long
11.     count = allocCount
12. End Property
13. Public Property Get capacity() As Long
14.     capacity = last - START_HEADER
15. End Property
16. Public Sub clear()
17.     allocCount = 0
18.     header = START_HEADER
19.     last = START_HEADER + 1
20.     ReDim nextFree(START_HEADER To last - 1)
21.     nextFree(header) = last
22. End Sub
23. Public Function alloc() As Long
24.     '分配一个自由的索引
25.     If header = last Then
26.         Call doubleCapacity
27.     End If
28.     Dim result As Long
29.     result = header
30.     header = nextFree(header)
31.     nextFree(result) = START_HEADER - 1
32.     allocCount = allocCount + 1
33.     alloc = result
34. End Function
35. Public Function free(ByVal p As Long) As Boolean
36.     '把索引标记成自由
37.     If p < START_HEADER Or p >= last Then
38.         free = False
39.         Exit Function
40.     End If
41.     If nextFree(p) >= START_HEADER Then
42.         free = False
43.         Exit Function
44.     End If
45.     nextFree(p) = header
46.     header = p
47.     allocCount = allocCount - 1
48.     free = True
49. End Function
50. Private Sub doubleCapacity()
51.     last = START_HEADER + (last - START_HEADER) * 2
52.     ReDim Preserve nextFree(START_HEADER To last - 1)
53.     Dim i As Long
54.     For i = header To last - 1
55.         nextFree(i) = i + 1
56.     Next
57. End Sub

复制代码

0xAA55

VB没有“指针对象”，C语言和C++也没有。

但，VB有对象，有类，使用对象和类可以实现链式结构，并不麻烦。并且还自带引用计数，就像C++的智能指针shared_ptr一样。

参考我使用VB6实现AVL二分查找树：
https://www.0xaa55.com/thread-25770-1-1.html

天马座

0xAA55 发表于 2020-11-7 23:52
VB没有“指针对象”，C语言和C++也没有。

但，VB有对象，有类，使用对象和类可以实现链式结构，并不麻烦。 ...

用类编写代码有点丑 判空和赋值 有点啰嗦
比如查找最小节点，数组版代码如下，更加接近c风格

1. Private Function getFirstEntry() As Long
2.     Dim p As Long
3.     p = root
4.     If p <> NULL_PTR Then
5.         Do While leftChild(p) <> NULL_PTR
6.             p = leftChild(p)
7.         Loop
8.     End If
9.     getFirstEntry = p
10. End Function

复制代码