忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 视频 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: superwujc

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

论坛徽章:
13
射手座
日期:2014-11-29 19:22:4915-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:252015年迎新春徽章
日期:2015-03-04 09:50:282015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-06-13 22:15 |显示全部楼层
本帖最后由 yulihua49 于 2017-06-13 22:42 编辑
superwujc 发表于 2017-06-13 16:44
回复 8# yulihua49

1. 对于每一层级的数组元素,需要首先检查有效性,只有符合要求的,才将索引和值作 ...

树的查找不会?
1.树是在插入时按键值顺序排序的,这个插入程序比较复杂。
2.按深度查找。不需要遍历整个树。你这个树只需4次就可以找到指定节点。
3.在节点内可进行二分查找。


插入程序大致这样:
先分配一个节点。
然后接受数据。数据按键值大小次序放入节点。
当数据达到512,分裂成两个节点各256.同时生成新的根节点,两个指针分别指向两个“块”。每个指针都要表明其中数据的键的最大和最小值。
依此类推直到生成全部数据树。

我估计你没有那么多的数据足以填满4层的512叉树。要么就是没有足够的内存。
查找就很简单了,从根节点开始,看看键值在哪个节点,然后递归到下一个节点。最多4次就到底了。

论坛徽章:
34
子鼠
日期:2013-08-28 22:23:292015亚冠之柏太阳神
日期:2015-10-26 18:08:17黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03
发表于 2017-06-14 09:08 |显示全部楼层
你们累不累。。。
一、map/unordered_map套map/unordered_map套map/unordered_map套map/unordered_map
二、可以把1、2层合并成一个key,3、4层合并成一个key,这样只要套两层map/unordered_map

论坛徽章:
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-14 10:16 |显示全部楼层
回复 12# cokeboL

。。。google了一下unordered_map,发现这个是c++的概念
不知纯c可否实现?

论坛徽章:
2
综合交流区版块每日发帖之星
日期:2016-07-06 06:20:00综合交流区版块每日发帖之星
日期:2016-08-16 06:20:00
发表于 2017-06-14 11:23 |显示全部楼层
回复 2# hellioncu

论坛徽章:
13
射手座
日期:2014-11-29 19:22:4915-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:252015年迎新春徽章
日期:2015-03-04 09:50:282015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-06-14 11:25 |显示全部楼层
superwujc 发表于 2017-06-14 10:16
回复 12# cokeboL

。。。google了一下unordered_map,发现这个是c++的概念

作为算法,与语言无关。作为实现,目前没有C的实现。几年前有人在本坛发过CSTL。

论坛徽章:
9
程序设计版块每日发帖之星
日期:2015-10-18 06:20:00程序设计版块每日发帖之星
日期:2015-11-01 06:20:00程序设计版块每日发帖之星
日期:2015-11-02 06:20:00每日论坛发贴之星
日期:2015-11-02 06:20:00程序设计版块每日发帖之星
日期:2015-11-03 06:20:00程序设计版块每日发帖之星
日期:2015-11-04 06:20:00程序设计版块每日发帖之星
日期:2015-11-06 06:20:00数据库技术版块每周发帖之星
日期:2015-12-02 15:02:47数据库技术版块每日发帖之星
日期:2015-12-08 06:20:00
发表于 2017-06-18 15:29 |显示全部楼层
我这边的设计是:

采用2层hash表结构, 第1层是固定容量,  里面装着指向第2层的智能指针, 第1层中有读写锁, 访问第2层需要加锁, 第2层是动态容量hash, 随时根据容量大小自动扩容和收缩,
只需要计算2次hash值, 分别对应1层和2层

如果只做一个大hash表, 那么就存在锁冲突太大, 每次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-19 10:31 |显示全部楼层
回复 16# wlmqgzm

多谢,有个问题请教,4层结构实现为2层hash表,怎样解决索引的冲突啊?

论坛徽章:
12
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15摩羯座
日期:2014-07-21 10:11:2815-16赛季CBA联赛之八一
日期:2017-04-12 14:26:28
发表于 2017-06-19 10:39 |显示全部楼层
回复 13# superwujc

unordered_map就是hash,你只要不需要泛型,用C实现就没什么问题,不行还有个void *

论坛徽章:
129
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2017-06-20 14:16 来自手机 |显示全部楼层
本帖最后由 shang2010 于 2017-06-20 16:34 编辑

弱弱地问一下,四层数组说的是四维数组么

这个指针结构已经足够复杂了——说实话,我是一点没读懂楼主到底想设计一个什么具体点的数据结构,
算法貌似就用到两个,hash和二分查找(最终算不算tree结构)

论坛徽章:
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-27 13:54 |显示全部楼层
回复 19# shang2010

就是这样的

4层数组,每层数组最大包含512个元素,最小包含非0个元素,每个元素的类型均为指针
例如数组arrp0, arrp1, arrp2, arrp3
hahaha.jpg
您需要登录后才可以回帖 登录 | 注册

本版积分规则

SACC2017购票6.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月2日前

活动链接>>
  

北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP