数据结构和算法设计，请高手指点

yulihua49

superwujc 发表于 2017-06-13 16:44
回复 8# yulihua49

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

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


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

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

cokeboL

你们累不累。。。
一、map/unordered_map套map/unordered_map套map/unordered_map套map/unordered_map
二、可以把1、2层合并成一个key，3、4层合并成一个key，这样只要套两层map/unordered_map

superwujc

回复 12# cokeboL

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

sditmaner

回复 2# hellioncu

yulihua49

superwujc 发表于 2017-06-14 10:16
回复 12# cokeboL

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

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

wlmqgzm

我这边的设计是:

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

如果只做一个大hash表, 那么就存在锁冲突太大, 每次hash表扩容或者收缩的时候, 拷贝数据的时间也太长, 时延不稳定, 问题很多.

superwujc

回复 16# wlmqgzm

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

lxyscls

回复 13# superwujc

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

shang2010

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

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

superwujc

回复 19# shang2010

就是这样的

4层数组，每层数组最大包含512个元素，最小包含非0个元素，每个元素的类型均为指针
例如数组arrp0, arrp1, arrp2, arrp3