VBA编程技巧 之 遍历那点事儿

lee1892

本贴附件： 遍历那点儿事_By Lee1892.rar (28.74 KB, 下载次数: 892)

2014-12-5 17:35 上传

点击文件名下载附件

关于树形结构的遍历，做了个动画演示，共用了如下5种方法，希望能给初学者一些帮助。有人希望加注释吗？


1、深度优先，递归


2、深度优先，集合模拟堆栈


3、深度优先，数组模拟堆栈


4、广度优先，集合模拟队列


5、广度优先，数组模拟队列

feiren228

学习，收藏

EXCEL江湖

非常好的学习资料！但还是有很多地方看不懂，希望老师能够注解代码

aoe1981

只是看了看图形对象的变化，似乎这个可以懂……呵呵，惭愧……发现广度优先似乎有个“层”的概念在里头……

hyqzzs

大师，加个注释吧

qq348104184

大师就是大师 顶 要注释

lee1892

初始化部分的代码注释：

1. '|=====================================|'
   
2. '|            初始化过程               |'
   
3. '|-------------------------------------|'
   
4. '| 设置全局变量：                      |'
   
5. '| arrVisited 节点是否被访问数组       |'
   
6. '| strPath    访问路径字符串           |'
   
7. '| 重置各Shape颜色字体等               |'
   
8. '|=====================================|'
   
9. Private Sub Initialize()
   
10.     Dim i%
    
11.     ' 设置各Shape属性
    
12.     For i = 1 To Shapes.Count
    
13.         With Shapes(i)
    
14.             If Left(.Name, Len(STR_NODE)) = STR_NODE Then
    
15.                 With .TextFrame
    
16.                     With .Characters(1, .Characters.Count).Font
    
17.                         .Bold = False
    
18.                         .ColorIndex = 0
    
19.                     End With
    
20.                 End With
    
21.                 .Fill.ForeColor.SchemeColor = 9
    
22.             ElseIf Left(.Name, Len(STR_EDGE)) = STR_EDGE Then
    
23.                 With .Line
    
24.                     .EndArrowheadStyle = msoArrowheadNone
    
25.                     .ForeColor.SchemeColor = 0
    
26.                 End With
    
27.             End If
    
28.         End With
    
29.     Next
    
30.     ' 隐藏当前节点指示箭头
    
31.     Shapes("NODE_NOW").Visible = msoFalse
    
32.     ' 如果未设置节点数组全局变量，则读取树数据
    
33.     If intCount = 0 Then Call ReadTree
    
34.     ' 清空路径单元格，清空堆栈、队列演示单元格
    
35.     Range(RNG_PATH).ClearContents
    
36.     Range(RNG_STAK).CurrentRegion.ClearContents
    
37.     ' 初始化路径字符串
    
38.     strPath = ""
    
39.     ' 初始化节点是否被访问数组
    
40.     ReDim arrVisited(1 To intCount)
    
41.     Call WaitMoment(0.5)
    
42. End Sub
    
43. '|=====================================|'
    
44. '|         读取树数据过程              |'
    
45. '|-------------------------------------|'
    
46. '| 设置全局变量：                      |'
    
47. '| arrNodes 节点数组                   |'
    
48. '|  |-> Parent        父节点编号       |'
    
49. '|  |-> Children      子节点编号数组   |'
    
50. '|  |-> ChlidrenCount 子节点数量       |'
    
51. '| intCount 节点数量                   |'
    
52. '| intRoot  根节点编号，同节点数组下标 |'
    
53. '|=====================================|'
    
54. Private Sub ReadTree()
    
55.     Dim i%, nParent%, nChild%, sName$, aIDs, nShapeCount%
    
56.     intCount = 0
    
57.     ' 设置根节点编号为 1
    
58.     intRoot = 1
    
59.     nShapeCount = Shapes.Count
    
60.     ReDim arrNodes(1 To nShapeCount)
    
61.     For i = 1 To nShapeCount
    
62.         sName = Shapes(i).Name
    
63.         If Left(sName, Len(STR_NODE)) = STR_NODE Then
    
64.             ' 节点数量计数
    
65.             intCount = intCount + 1
    
66.         ElseIf Left(sName, Len(STR_EDGE)) = STR_EDGE Then
    
67.             ' 根据边，添加子节点
    
68.             aIDs = Split(sName, "-")
    
69.             nParent = aIDs(1)
    
70.             nChild = aIDs(2)
    
71.             arrNodes(nChild).Parent = nParent
    
72.             With arrNodes(nParent)
    
73.                 ' 初始化子节点编号数组
    
74.                 If .ChildrenCount = 0 Then ReDim .Children(1 To nShapeCount)
    
75.                 ' 子节点数量计数
    
76.                 .ChildrenCount = .ChildrenCount + 1
    
77.                 ' 添加子节点
    
78.                 .Children(.ChildrenCount) = nChild
    
79.             End With
    
80.         End If
    
81.     Next
    
82.     ReDim Preserve arrNodes(1 To intCount)
    
83.     For i = 1 To intCount
    
84.         With arrNodes(i)
    
85.             If .ChildrenCount > 0 Then ReDim Preserve .Children(1 To .ChildrenCount)
    
86.         End With
    
87.     Next
    
88. End Sub

复制代码

lee1892

1、深度优先递归 的代码注释：

1. Private Sub 深度优先_递归_Click()
   
2.     ' 初始化
   
3.     Call Initialize
   
4.     ' 调用递归函数，由根节点开始遍历
   
5.     Call DFS_Recursive(intRoot)
   
6. End Sub
   
7. '|=====================================|'
   
8. '|         深度优先递归过程            |'
   
9. '|-------------------------------------|'
   
10. '| 参数：                              |'
    
11. '|     nInd 访问节点编号               |'
    
12. '| 伪代码：                            |'
    
13. '|     访问输入节点                    |'
    
14. '|     对输入节点所有子节点循环        |'
    
15. '|         经过输入节点到其子节点的边  |'
    
16. '|         递归调用其子节点            |'
    
17. '|     循环结束退出程序                |'
    
18. '|=====================================|'
    
19. Private Sub DFS_Recursive(ByVal nInd%)
    
20.     Dim i%
    
21.     ' 访问输入节点
    
22.     Call VisitNode(nInd)
    
23.     With arrNodes(nInd)
    
24.         ' 对输入节点所有子节点循环
    
25.         For i = 1 To .ChildrenCount
    
26.             ' 经过输入节点到其子节点的边
    
27.             Call PassEdge(nInd, .Children(i))
    
28.             ' 递归调用其子节点
    
29.             Call DFS_Recursive(.Children(i))
    
30.             ' 动画演示用，实际不需要
    
31.             Call VisitNode(nInd)
    
32.         Next
    
33.     End With
    
34. End Sub

复制代码

lee1892

2、深度优先集合模拟堆栈的代码注释：

1. '|==============================================|'
   
2. '|             深度优先集合模拟堆栈             |'
   
3. '|----------------------------------------------|'
   
4. '| 伪代码：                                     |'
   
5. '|     初始化                                   |'
   
6. '|     根节点及子节点序号0压入堆栈              |'
   
7. '|     循环直到堆栈为空                         |'
   
8. '|         调出堆栈顶的节点作为当前节点         |'
   
9. '|         删除堆栈顶数据                       |'
   
10. '|         访问当前节点                         |'
    
11. '|         如果子节点序号不是其最后一个子节点   |'
    
12. '|             则当前节点及下一个子节点序号压栈 |'
    
13. '|             下一个子节点及其子节点序号0压栈  |'
    
14. '|             经过当前节点到下一个子节点的边   |'
    
15. '|     循环结束退出程序                         |'
    
16. '|==============================================|'
    
17. Private Sub 深度优先_集合堆栈_Click()
    
18.     Dim cStack As New Collection
    
19.     Dim nChildInd%, nInd%, nChild%, aInds
    
20.     ' 初始化
    
21.     Call Initialize
    
22.     With Range(RNG_STAK)
    
23.         ' 根节点及子节点序号0压入堆栈
    
24.         cStack.Add intRoot & "-" & 0
    
25.         .Offset(cStack.Count - 1, 0) = intRoot
    
26.         .Offset(cStack.Count - 1, 1) = 0
    
27.         Call WaitMoment(0.5)
    
28.         ' 循环直到堆栈为空
    
29.         Do While cStack.Count > 0
    
30.             ' 调出堆栈顶的节点作为当前节点
    
31.             aInds = Split(cStack(cStack.Count), "-")
    
32.             nInd = aInds(0)
    
33.             nChildInd = aInds(1)
    
34.             ' 删除堆栈顶数据
    
35.             .Offset(cStack.Count - 1, 0).ClearContents
    
36.             .Offset(cStack.Count - 1, 1).ClearContents
    
37.             cStack.Remove cStack.Count
    
38.             ' 访问当前节点
    
39.             Call VisitNode(nInd)
    
40.             ' 如果子节点序号不是其最后一个子节点
    
41.             If nChildInd + 1 <= arrNodes(nInd).ChildrenCount Then
    
42.                 nChildInd = nChildInd + 1
    
43.                 nChild = arrNodes(nInd).Children(nChildInd)
    
44.                 ' 则当前节点及下一个子节点序号压栈
    
45.                 cStack.Add nInd & "-" & nChildInd
    
46.                 .Offset(cStack.Count - 1, 0) = nInd
    
47.                 .Offset(cStack.Count - 1, 1) = nChildInd
    
48.                 Call WaitMoment(0.5)
    
49.                 ' 下一个子节点及其子节点序号0压栈
    
50.                 cStack.Add nChild & "-" & 0
    
51.                 .Offset(cStack.Count - 1, 0) = nChild
    
52.                 .Offset(cStack.Count - 1, 1) = 0
    
53.                 ' 经过当前节点到下一个子节点的边
    
54.                 Call PassEdge(nInd, nChild)
    
55.             End If
    
56.         Loop
    
57.     End With
    
58.     Set cStack = Nothing
    
59. End Sub

复制代码

lee1892

4、广度优先 集合模拟队列 的代码注释：

1. '|==============================================|'
   
2. '|             广度优先集合模拟队列             |'
   
3. '|----------------------------------------------|'
   
4. '| 伪代码：                                     |'
   
5. '|     初始化                                   |'
   
6. '|     根节点进入队列                           |'
   
7. '|     循环直到队列为空                         |'
   
8. '|         调出队列前端的节点作为当前节点       |'
   
9. '|         删除队列前端数据                     |'
   
10. '|         如果当前节点不是根节点               |'
    
11. '|             则经过当前节点的父节点到其的边   |'
    
12. '|         访问当前节点                         |'
    
13. '|         循环当前节点的所有子节点             |'
    
14. '|             子节点进入队列末端               |'
    
15. '|         循环结束                             |'
    
16. '|     循环结束退出程序                         |'
    
17. '|==============================================|'
    
18. Private Sub 广度优先_集合队列_Click()
    
19.     Dim cQueue As New Collection
    
20.     Dim i%, nInd%
    
21.     ' 初始化
    
22.     Call Initialize
    
23.     With Range(RNG_STAK)
    
24.         ' 根节点进入队列
    
25.         cQueue.Add intRoot
    
26.         .Offset(0, 0) = intRoot
    
27.         Call WaitMoment(0.5)
    
28.         ' 循环直到队列为空
    
29.         Do While cQueue.Count > 0
    
30.             ' 调出队列前端的节点作为当前节点
    
31.             nInd = cQueue(1)
    
32.             ' 删除队列前端数据
    
33.             cQueue.Remove 1
    
34.             .Resize(cQueue.Count, 2).ClearContents
    
35.             For i = 1 To cQueue.Count
    
36.                 .Offset(i - 1, 0) = cQueue(i)
    
37.             Next
    
38.             If cQueue.Count > 0 Then .Offset(cQueue.Count - 1, 1) = "<－队列末端"
    
39.             ' 如果当前节点不是根节点 则经过当前节点的父节点到其的边
    
40.             If arrNodes(nInd).Parent > 0 Then Call PassEdge(arrNodes(nInd).Parent, nInd)
    
41.             ' 访问当前节点
    
42.             Call VisitNode(nInd)
    
43.             ' 循环当前节点的所有子节点
    
44.             For i = 1 To arrNodes(nInd).ChildrenCount
    
45.                 ' 子节点进入队列末端
    
46.                 .Offset(cQueue.Count - 1, 1) = ""
    
47.                 cQueue.Add arrNodes(nInd).Children(i)
    
48.                 .Offset(cQueue.Count - 1, 0) = arrNodes(nInd).Children(i)
    
49.                 .Offset(cQueue.Count - 1, 1) = "<－队列末端"
    
50.                 Call WaitMoment(0.5)
    
51.             Next
    
52.         Loop
    
53.     End With
    
54.     Set cQueue = Nothing
    
55. End Sub

复制代码