免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 5824 | 回复: 21

[算法] 数据结构和算法设计,请高手指点 [复制链接]

论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 12:51 |显示全部楼层
如题,C语言,4层结构
1. 每一层均为指针数组
2. 数组最大长度均为512,最小长度为4
3. 每个数组元素,即指针均指向下一层级的数组起始位置

问题:遍历该4层结构,需执行的循环次数太多(512*512*512*512?),且查找的效率不高
怎样设计一种数据结构,可以在程序开始执行时,仅执行一次遍历,然后将遍历的结果保存到该数据结构中,后面的查询直接对该数据结构进行操作?

请各位不吝赐教,多谢。


论坛徽章:
323
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2017-06-13 15:43 |显示全部楼层
你是要提升查找性能?一般可以用哈希或者二分之类的,具体可以根据数据特点来设计

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-06-13 16:03 |显示全部楼层
本帖最后由 yulihua49 于 2017-06-13 16:06 编辑
superwujc 发表于 2017-06-13 12:51
如题,C语言,4层结构
1. 每一层均为指针数组
2. 数组最大长度均为512,最小长度为4

这就是M树啊,按有序平衡树组织。遍历次数不可能少,检索速度本身就挺快的。
数据插入时就自动建立树。
不过,平衡M树的程序够难写的。主要是插入和删除。检索比较简单。

论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 16:05 |显示全部楼层
回复 2# hellioncu

是的,因为数组的查找涉及到遍历,程序运行期间,每一次查找都要遍历至少1层,最多4层
最坏的场景是这样的:
第1层指针数组,每一个指针元素指向1个第2层的指针数组
第2层指针数组,每一个指针元素指向1个第3层的指针数组
第3层指针数组,每一个指针元素指向1个第4层的指针数组

每一层级的数组最大长度为512,因此若查找位于第4层级数组的元素的话,遍历需要执行太多循环

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-06-13 16:08 |显示全部楼层
本帖最后由 yulihua49 于 2017-06-13 16:15 编辑
superwujc 发表于 2017-06-13 16:05
回复 2# hellioncu

是的,因为数组的查找涉及到遍历,程序运行期间,每一次查找都要遍历至少1层,最多4 ...

有序树的查找不用遍历。看看二叉树查找,很简单的递归过程。当然M树要稍复杂些,原理是一样的。
你这个题目改一改就是二叉树:每层两个数据。再加一条,小左大右。层数不限。
所以你这个就是二叉树推广,跟B+树差不多。但是B+树程序挺复杂的。
B+树的规则是有序,最小节点是最大节点的1/2。层数不限。

论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 16:14 |显示全部楼层
回复 5# yulihua49

其实我想的是用散列表。。。

对于每一层数组,符合条件的索引和对应的值作为key-value,不用哈希函数

只不过需要创建4个哈希表

论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 16:16 |显示全部楼层
回复 5# yulihua49

程序运行开始,首先执行一次大循环,将每一层级数组中,符合条件的索引和值添加到一个哈希表中
可以确定的是,数组的值是唯一的,所以无需计算索引的哈希值,直接将索引作为key

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-06-13 16:18 |显示全部楼层
本帖最后由 yulihua49 于 2017-06-13 16:25 编辑

回复 6# superwujc
估计不是题目的原意。如果能用hash做索引,何不用一维数组?


论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 16:24 |显示全部楼层
回复 8# yulihua49

哈希表可能不是最好的方式

首先执行一次嵌套4层的循环,把结果保存到哈希表,后面每一次查找只需按层级的顺序指定索引,就可以查找出对应的值,无需再次遍历

论坛徽章:
11
摩羯座
日期:2013-09-29 17:39:09白羊座
日期:2014-11-13 09:38:14技术图书徽章
日期:2014-01-17 15:07:36狮子座
日期:2013-12-25 14:01:52技术图书徽章
日期:2013-12-17 11:33:22技术图书徽章
日期:2013-12-03 10:27:57天秤座
日期:2013-11-08 15:47:19申猴
日期:2013-10-29 13:16:32未羊
日期:2013-10-12 22:28:56辰龙
日期:2013-10-09 14:39:5515-16赛季CBA联赛之山东
日期:2016-07-25 10:23:00
发表于 2017-06-13 16:44 |显示全部楼层
回复 8# yulihua49

1. 对于每一层级的数组元素,需要首先检查有效性,只有符合要求的,才将索引和值作为key-value插入到哈希表
2. 需要得到每个层级数组中的每个有效元素,用于不断输出调试,而不是简单的按特定索引进行查找,因此哈希表可以避免每一次需要输出时都必须执行循环

能力有限,目前能想到的最好解决方式就是哈希表了

不知m树可以怎样更好的解决这个问题?求教。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP