gpt4 book ai didi

algorithm - 从 Excel 导入中查找包含的边界区域

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:35:02 25 4
gpt4 key购买 nike

我正在从具有各种表格布局的 Excel 中导入大量数据。我有足够好的表格检测例程和合并单元格处理,但在处理边框时遇到了问题。即性能。其中一些文件中的边界区域是有意义的。

数据设置:
我使用 VB6 和 MSXML 直接从 Office Open XML 导入。数据从 XML 解析为单元格数据字典。这非常棒,与在 Access 中使用 docmd.transferspreadsheet 一样快,但返回的结果要好得多。每个单元格都包含一个指向样式元素的指针,样式元素包含一个指向定义每个边框的可见性和权重的边框元素的指针(这也是数据在 OpenXML 中的结构)。

挑战:
我想要做的是找到包含在边界内的每个区域,并创建该区域内的单元格列表。

我做了什么:
我最初创建了一个 BFS(广度优先搜索)填充例程来查找这些区域。这对于“正常”大小的电子表格非常有效且快速,但对于导入到数千行中来说太慢了。一个问题是 Excel 中的边框可能存储在您正在检查的单元格中或相邻单元格中的相反边框。没关系,我可以在导入时合并该数据以减少所需的检查次数。

我想做的一件事是创建一个单独的图形,使用边框作为我的边来勾勒出单元格的轮廓,并使用图形算法以这种方式找到区域,但我在弄清楚如何实现该算法时遇到了麻烦。我过去曾使用过 Dijkstra,并认为我可以用它做类似的事情。因此,我可以不使用端点展开来搜索整个图,如果我遇到一个封闭节点,我知道我只是找到了一个封闭区域,但我怎么知道我找到的路线是否是最佳路线?我想我可以将其标记为对找到的封闭节点运行单独的检查,以忽略前一个节点的边缘。

这可以工作,但在密集图上的性能不会更好。其他人可以建议更好的方法吗?感谢您花时间阅读本文。

最佳答案

你的问题很复杂,但听起来好像你需要一个算法来找到一个图的连通分量(连通分量 = 一组节点都相互连接但没有连接到其他节点),这可以在通过重复遍历的线性时间。伪代码:

FindComponents(G):
For all vertices v in G:
Let C be a mutable empty collection
Traverse(G, C, v)
If C is nonempty, then it is a connected component

Traverse(G, C, v):
If v has not been visited:
Mark v as visited
Add v to C
For each neighbor w of v in G:
Traverse(G, C, w)

Traverse 的迭代变体:

Traverse(G, C, r):
Let S be an empty stack
Push r onto S
While S is not empty:
Pop the top element v of S
If v is not marked as visited:
Mark v as visited
Add v to C
For each neighbor w of v in G:
Push w onto S

关于algorithm - 从 Excel 导入中查找包含的边界区域,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2439768/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com