首页
社区
课程
招聘
[旧帖] [讨论]关于树结构与数组 0.00雪花
发表于: 2009-5-12 18:52 3424

[旧帖] [讨论]关于树结构与数组 0.00雪花

2009-5-12 18:52
3424
"数组"是我们最常用到的一种对象, 很多编程语言都支持数组.
而通常数组是以数字进行索引的, 于是就出现了各种类似于数组并以文本的方式索引的对象.

最近在用Asp写一个无限级的树结构,

第一种最简单的莫过于用Access SQL命令不断的递归查询并返回结果

第二种编写MS SQL函数, 与第一种一样, 也是用递归, 只是将程序的递归过程转移到MS SQL上而已, 但速度会比第一种快, 好像是由于MS Sql比Access SQL更高效的原因, 也还有另一原因是因为使用了MS SQL编程, (对MS SQL不太熟悉, 只认识这么多)

第三种是使用Asp的Directory字典对象或是使用C#.net的HashTable对象, 这两个对象最大的特点是可以用文本进行索引

第四种则是使用数组. 这是跟大家讨论的一种思路, 不谈语言的具体写法, 本人比较菜, 望高手赐教!

数组, 以索引号进行索引, 而如何取得或者说是定位这个"索引号"
我想可以在填充数据的时候, 构建一个字符串, 以达到数组的效果
如以JavaScript为例:

var index="";
var abc = [["a","a值"],["b","b值"],["c","c值"],["d","d值"],["e","e值"],["f","f值"]];
for(var i=0;i<abc.length;i++)
{
    index +="#" + abc[i][0] + "#"; //此处的#为特殊符号, 可以使用其它字符代替或其它算法代替
}

function arr_index(val)
{
        var r_val = index.indexOf("#"+val+"#");
        if(r_val>0) return r_val/3;  //此处的3 为#a#的长度, 如果这里使用了#ab#则会索引错误, 可通过改善代码解决这个问题
        return 0;
}
document.write(abc[arr_index("e")][1]);

通过更完善的算法, 可以使这个结构更加强大, 我使用asp的vbscript, 完成了使用数组实现无限级树结构.

只是使用indexOf定位字符串位置返回数组的索引位位置
相对于for循环来定位索引位置, 不知道哪个速度更快呢?

[课程]Android-CTF解题方法汇总!

收藏
免费 1
支持
分享
最新回复 (8)
雪    币: 339
活跃值: (10)
能力值: ( LV9,RANK:260 )
在线值:
发帖
回帖
粉丝
2
不是太明白楼主的意思。

对于定位索引位置,我认为就是一个查找算法,典型实现可以采用“排序、二分查找”的方式;不过就特殊的实际问题可能有更有效的解决办法。

而且貌似跟“树结构”没有太大的关系,期待楼主把问题阐明。
2009-5-13 09:42
0
雪    币: 205
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
不好意思, 写得不太好理解, 其实我是想说如何使用数组来建立树结构,
而树结构最重要的是弄清楚每个节点之间的关系,
要使用数组来建立树结构的, 最频繁用到的就是如何快速定位到所要查找的内容上.
所以这里讲的是使用什么样的算法来进行快速定位

理论上, 我觉得indexOf字符串搜索相对于for搜索来说, 会更快一点, 只是我不知道具体是否是这样
2009-5-13 10:47
0
雪    币: 205
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
你学习C的吗?
假说要在1000000的数组中, 检索值为"1000000", 当然, 这是有规则的, 我们假设它是无规则的类型
除了使用for(int i=0;i<=1000000;i++) 循环1百万次才能找到我们要的索引值之外, 还有啥比这高效的吗?
相对于使用indexOf, 哪个更快一点呢?
2009-5-13 10:55
0
雪    币: 339
活跃值: (10)
能力值: ( LV9,RANK:260 )
在线值:
发帖
回帖
粉丝
5
(1)如果你要用数组来实现树结构,推荐使用Haffman方式,便于查找
(2)如果在有1000000个数据的数组中通过索引的方式查找,假设,我是说假设数组一般不变动或者变动不大,可以对索引值使用某种哈希算法计算hash值,对该值排序、二分查找,我相信查找效率应该高一些

C语言是基础,以前学了,现在用着,以后也会深入地去理解与使用
2009-5-13 11:03
0
雪    币: 205
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
谢谢, 学习了.
2009-5-13 14:59
0
雪    币: 87
活跃值: (25)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
7
楼主可以去看一下数据结构,严蔚敏的那本教材。有关树的存储方式里面讲的还是蛮详细的。

看你3楼问题,貌似不是编程语言的问题,而是数据结构上的选取问题。
2009-5-13 15:55
0
雪    币: 205
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
不是编程的问题啊, 我只是想采用哪种方式更高效, 谢谢你推荐的那本数据结构的教材, 学习中
2009-5-15 00:03
0
雪    币: 141
活跃值: (25)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
9
用链接结构就行了  数组比较适合完全二叉树
2009-5-17 12:22
0
游客
登录 | 注册 方可回帖
返回
//