VBA编程技巧 之 浅谈数据结构 （不定期持续更新，最后更新130411）

lee1892

引言

    还是一个心血来潮的东西，先是看到不少关于Bill Of Material（BOM）材料清单的帖子，于是写了个用字典链接构造链表的代码。而后又试着用数组、自定义数据类型改写。突然意识到论坛里有不少高深算法的帖子（代表性的法师的一系列算法帖，一直怀疑这家伙是学应用数学之类的）、有大量介绍各种对象的、有列出或利用诸多系统API函数而随心所欲的做出各种功能的，貌似没人介绍最基本的数据结构。所以就想试着写些，套个俗话：权当抛砖引玉了。

    VBA作为Visual Basic的一个子集，可以非常便捷的帮助我们实现一些原有软件不能做到的功能。虽说它是一个简化了的工具，但究其实质还是一个完整的计算机程序语言。那么要用好VBA，势必需要我们了解计算机程序语言一些最基本的概念。而无论你学习任何一种程序语言，数据结构必然是最基础的。

    那么什么是数据结构呢，可以从两方面来理解。当我们使用数据来描述现实世界中一样或一类事物时，这些数据本身之间的相互内在关系就是数据结构需要表达的。所以我们可以理解为数据结构是描述数据之间的逻辑关系得，即逻辑结构，比如门牌号码系统就是天然的树形数据结构。而另一方面，在计算机世界中，数据是要进行存储和取用的即所谓的存取，如何组织存储数据就决定了取用时实现的方法，比如是链表顺序存储还是使用索引随机存储，所以我们可以理解为数据结构是指数据的存储结构，即物理结构。作为软件的使用者，我们显然不需要对后者有过多的了解，所以这里只聊聊前者。

    至于为什么要了解数据结构，这是因为数据结构在某种程度上决定了算法的难易程度，也决定了程序的执行效率。

    Pascal 之父 Niklaus Wirth 的一本著名著作就叫《算法 + 数据结构 = 程序》

（会是一个长贴吗......？ By Lee1892, 2012.12.21）

目录

楼层	标题	附件
02楼	VBA提供的数据类型
05楼	迭代（Iteration）与递归（Recursion）
07楼	迭代与递归的使用	迭代循环查询 | 递归循环查询
08楼	队列（Queue）和堆栈（Stack）
10楼	队列与堆栈的使用
13楼	使用队列和堆栈获得正确的顺序
18楼	链表（Linked List）
19楼	使用链表构建树形结构	单向链表构建树形结构
20楼	树（Tree）和二叉树（Binary Tree）
22楼	二叉查找树（Binary Searching Tree）的 向左走、向右走
25楼	也谈排序
27楼	字典（Dictionary）和散列表（Hash Table）
29楼	n叉树转为二叉树的示例	n叉树转二叉树示例
32楼	使用案例-两棵树的比较	两棵树的比较
37楼	堆（Heap）、二叉堆（Binary Heap）、优先队列（Priority Queue）	二叉堆的类代码演示
42楼	使用正确的数据结构的例子（一）	彭希仁的汇总表
43楼	使用正确的数据结构的例子（二）	地理信息的网格查找示例 | 及其改进
87楼	使用正确的数据结构的例子（三）	发货明细统计
94楼	使用正确的数据结构的例子（四）由28秒到2秒！	水样监测_使用数据结构加速

====================================================================================
Original Post:

下午没事，逛论坛。。。
貌似不少BOM的东西，估计都是从ERP之类的软件导出来的数据，数据完全没有组织，每个条目仅有所属部件/产品的编号和自身的编号。
大致翻了一下相关的帖子，没看到什么好的方案，所以动手写了一段字典套字典的。

供参考~~

补充内容 (2013-4-15 11:08):
本来还存了些有趣的案例，傻了吧叽的论坛不让编辑了，这个贴子也就到此为止不再更新了。只能说有病~

lee1892

VBA提供的数据类型

VBA中的基本数据类型有：字节（Byte）、整型（Integer）、长整型（Long）、单精度（Single）、双精度（Double）、货币型（Currency）、字符串（String）、布尔型（Boolean）、日期（Date）、Object（对象）、变体（Variant）、用户自定义类型

其中的用户自定义类型是用 Type 在申明部分显式申明的，可以将一系列相关数据组织到一起，从而仅使用一个变量就可以获得这些数据。使用方式如：
Private Type 美女
    胸围 As Single
    腰围 As Single
    臀围 As Single
End Type
Public Sub 查找美女()
    Dim Girl as 美女
    Girl.胸围 = ...
    ...
End Sub

再有就是数组了，就物理结构而言，数组是顺序存储的由多个元素组成的表状数据结构，其中的元素则可以是任何数据类型。由于VBA不能像正经的程序语言如C之类的直接读写内存，所以我们会经常使用数组来模拟实现其它数据结构。

Collection 集合对象，VBA中原生的可以用关键字（字符串）索引的数据类型，由多个元素构成的顺序存储的表状数据结构，元素可以是任何数据类型。Excel内的大量对象都是通过它来封装的，如 Ranges、Cells、Rows、Columns 等都是Range对象的集合封装。值得注意的是，VBA中的集合对象是支持插入操作的，其Add方法允许定义Before或After参数。

Dictionary 字典对象，VBS中的可以用关键字（任何数据类型）索引的数据类型，猜测存储方式也是顺序的，但内键了某种机制（据猜测是散列表，一称哈希表，Hashing），使得能够快速的将关键字转化为存储地址而获得其索引的数据，元素可以是任何数据类型。

类，一种特殊的自定义数据类型，其不仅包含了静态的数据，同时也包含了其内部的过程，并可捕获事件以激发某个过程，从而使得其脱离了前述各种静态数据类型的范畴，而将 数据结构、算法 融于一体，实现所谓的面向对象。

以上，是我们使用的工具。

=====================================================
Original Post （字典构造双向链表的ParseData代码，删，详见1楼附件）

947100086

{:soso_e179:}学习了

guojianlin1985

做的挺好，就是不具备通用性。估计这段代码给其他人改起来也是超费劲的

lee1892

迭代（Iteration）与递归（Recursion）

在我们讲数据结构之前，先作一下思维训练。经常看到有人说什么递归算法，严格来说递归不能称为算法，只能说是一种思维方式。

从数学角度而言，所谓迭代可以指函数迭代的过程，即反复的运用同一函数计算，前一次迭代得到的结果被用于作为下一次迭代的输入。而在计算机世界中，迭代是程序中对一组指令（或一步骤）的重复。

而递归是指在函数或过程的定义中使用函数自身的方法。很显然，作为前述第一种意义下的迭代，递归实质上是迭代的一种特例。我一直认为，递归的思维逻辑是和数学中的归纳法一样的，比如证明由1至n的连续自然数的和的计算公式。

以计算等差数列的和为例，使用迭代的函数可以是这样的：
[code=vb]
Function Sum_Iteration&(n&)
    Dim i&
    Sum_Iteration= 0
    For i = 1 to n
        Sum_Iteration = Sum_Iteration + i
    Next
End Function
[/code]
而使用递归的函数：
[code=vb]
Function Sum_Recursion&(n&)
    If n = 1 Then
        Sum_Recursion = 1
    Else
        Sum_Recursion = n + Sum_Recursion(n - 1)
    End If
End Function
[/code]
非常有趣的是，上述递归代码在计算 n > 5835 时会报“溢出堆栈空间”的错误。
========================================================
Original Post:

guojianlin1985 发表于 2012-12-18 15:23
做的挺好，就是不具备通用性。估计这段代码给其他人改起来也是超费劲的

嗯嗯，我个人意见以为恰恰相反。
只要是符合我对原始数据描述的，基本只需要改改几个常量就可以了。。。

哼哼~~~

kuangben8

呵呵，各人的想法不同，思路不同，但是只要结果是正确的就好！

hehex

好帖啊，好好学习。佩服楼主扎实的数据结构基本功和算法知识。厉害{:soso_e179:}{:soso_e179:}

lee1892

迭代与递归的使用

1、本贴使用案例的原始数据分析：

此贴中所使用的案例是一个BOM清单，每一条记录反映了一个 产品/部件 所需要的一种 材料 的信息，包括如名称、规格、数量等。

该案例的最初的功能述求是取得某个 产品 所需的全部 部件 和 材料 信息，并罗列出来。显然这些数据的内在关联是一种树形结构，每个产品是一棵树，其根是产品，部件则是分支节点，材料则是叶子。

注：本贴所有代码，均假设原始数据中没有产生循环。
       本贴中使用aData数组来缓存原始数据，作为数据存储的模拟，行号则模拟了储存地址，列号对应的是储存的不同信息。

让我们分别使用迭代和递归的思维逻辑来作这个查询。

2、迭代：
具体代码见一楼附件：BOM查询-不构造任何数据结构，迭代循环查询
其中获得材料信息函数GetBOMList不作详细介绍，着重讲迭代过程，代码如下：
[code=vb]
Private Sub GetChildren(sNo$, aRows, nCount&, iLayer&)
    ' sNo: 产品/部件 的编号，对应于 GC 列，过程内改变值，应定义为 ByRef
    ' aRows: 二维数组，用于保存查找的结果，第二维对应的是查找到的项目数量，第一维有2个元素分别对应该项的层数和地址，过程内改变，应定义为 ByRef
    ' nCount: 查找得到结果的数量，过程内改变，应定义为 ByRef
    ' iLayer: 查找得到结果的层数，由于是迭代过程，这个参数实际为内部变量，为不改变其它代码，故作保留
    ' 以上参数中，aRows实际上是返回值。
    Dim i&, nCurrent&
    iLayer = 1 ' 初始化层数为 1
    Do
    ' 循环查找，退出机制使用Exit Do方式设于循环内部
        For i = 2 To UBound(aData)
        ' 遍历数据，进行查找。递归的结束是查找完全部数据。
            If sNo = aData(i, nParentCol) Then
            ' 于GC列，找到 产品/部件 的编号
                nCount = nCount + 1 ' 找到的项目数量 +1
                aRows(1, nCount) = iLayer ' 在返回数组中记录该项目的层数
                aRows(2, nCount) = i ' 在返回数组中记录该项目的地址
            End If
        Next
        nCurrent = nCurrent + 1 ' 在查找到的结果中，下次循环查找项目指针 +1
        If nCurrent > nCount Then Exit Do ' 如果下次查找项目指针大于已经找到的项目数量，则完成全部查询，退出
        sNo = aData(aRows(2, nCurrent), nItemCol) ' 获得下次查询的 部件/材料 编号
        iLayer = aRows(1, nCurrent) + 1 ' 下次查询的层数 是 本次查询的层数 +1
    Loop
End Sub
[/code]
由于上述迭代查询代码的限制，显示的查询结果是按层数排列的，即总是低层的在前面。

3、递归：
具体代码见一楼附件：BOM查询-不构造任何数据结构，递归循环查询
[code=vb]
Private Sub GetChildren(sNo$, aRows, nCount&, iLayer&)
    ' sNo: 产品/部件 的编号，对应于 GC 列，过程内不改变值，可定义为 ByVal
    ' aRows: 二维数组，用于保存查找的结果，第二维对应的是查找到的项目数量，第一维有2个元素分别对应该项的层数和地址，过程内改变，应定义为 ByRef
    ' nCount: 查找得到结果的数量，过程内改变，应定义为 ByRef
    ' iLayer: 查找得到结果的层数，过程内改变，应定义为 ByRef
    ' 以上参数中，aRows实际上是返回值。
    Dim i&, sItemNo$ ' , nRow&, nChildNodeNo& 这俩变量忘删了...
    For i = 2 To UBound(aData)
    ' 遍历数据，进行查找。递归的结束是查找完全部数据。
        If sNo = aData(i, nParentCol) Then
        ' 于GC列，找到 产品/部件 的编号
            iLayer = iLayer + 1 ' 层数 +1
            nCount = nCount + 1 ' 找到的项目数量 +1
            aRows(1, nCount) = iLayer ' 在返回数组中记录该项目的层数
            aRows(2, nCount) = i ' 在返回数组中记录该项目的地址
            sItemNo = aData(i, nItemCol) ' 获得该项目的 部件/材料 编号
            Call GetChildren(sItemNo, aRows, nCount, iLayer) ' 对该项目的 部件/材料 编号进行查找
        End If
    Next
    iLayer = iLayer - 1 ' 本次数据遍历查找结束，层数 -1
End Sub
[/code]
由于采用递归的方法，每次查询树的分支情况时，总是在到达叶子后才返回，所以查询得到的结果是也是同样的顺序，即按 部件/材料 的从属关系排列的。
=======================================================
Original Post （原有用数组构造双向链表的ParseData代码，删，详见1楼附件）

改写成用数组构造双向链表，貌似初始化的速度快了很多啊，而且内存占用也很小
看来字典多重嵌套不是什么好办法，应该尽量少用。。。
附件在1楼

lee1892

队列（Queue）和堆栈（Stack）

队列是指遵循先进先出原则的线性表。队列只允许在末端进行插入操作、在前端进行删除操作。
[code=vb]'│队列末端│
'├────┤
'│       │
'├────┤
'│       │
'├────┤
'│队列前端│
[/code]

打印机的打印工作流就是一个队列，当一个打印工作被添加时，位于打印工作记录表的末端，而当一个打印工作结束后，该打印工作从打印工作记录表的前端删除，并进行下一项打印工作。现实世界中有大量的例子，比如排队、零件加工工序、仓库财务报表的先进先出原则等等。

堆栈是指遵循后进先出原则的线性表。堆栈只允许在末端进行插入槽作、在末端进行删除操作。[code=vb]
'│堆栈末端│
'├────┤
'│       │
'├────┤
'│       │
'├────┤
'│堆栈前端│
'└────┘
[/code]

集装箱的装箱卸载过程就是一个很好的例子，最先被装入的货物位于箱底（即前端），最后被装入的货物位于靠门处（即末端），当取出货物时，只能从其末端开始取出。

=================================================
Original Post （使用自定义数据类型构造双向列表的ParseData代码，删，详见1楼附件）
继续改，用自定义数据类型，同前贴上ParseData代码

ctp_119

好好学习一下，，，还看的我稀里糊涂的。。。