如何对一组动态长度的随机数定位中间元素、1/4、3/4元素

wwwjek

有一组动态长度的随机数（已排好序），如何定位到该组数据的中间元素或者第1/4、3/4等个元素？用什么算法好些。

mik

硬实现倒没什么好办法吧


那是架构设计的问题，例如：当初排好序时，已记录下数据长度等等，整体框架已设计好

wwwjek

结构体可以设计成：
{
  编号；     //顺序编号
数据内容；
所在位置；//   编号/随机数个数
}

wwwjek

单链表

yulihua49

有一组动态长度的随机数（已排好序），如何定位到该组数据的中间元素或者第1/4、3/4等个元素？用什么算法好 ...
wwwjek 发表于 2010-04-02 22:32

    所有数据插入平衡二叉树。
树根是1/2，下面一层是1/4,3/4,再下边一层是 1/8,3/8,5/8,7/8。。。。。。

ubuntuer

所有数据插入平衡二叉树。
树根是1/2，下面一层是1/4,3/4,再下边一层是 1/8,3/8,5/8,7/8。。。。 ...
yulihua49 发表于 2010-04-04 10:44

这个方法不错.....

还有个就是排序的时候 记录总长度.... 上面的兄弟也说过的

progliker

回复 5# yulihua49


你说的这是完全二叉树， 现在不知道有什么方法构造， 对于AVL和红黑树，它们并不是完全二叉树， 不满足你说的性质。

yulihua49

回复  yulihua49


你说的这是完全二叉树， 现在不知道有什么方法构造， 对于AVL和红黑树，它们并不是完 ...
progliker 发表于 2010-04-08 09:41

是要求完全平衡树，程序在下：

    http://blog.chinaunix.net/u3/92831/showart_2166582.html

yulihua49

这个方法不错.....

还有个就是排序的时候 记录总长度.... 上面的兄弟也说过的
ubuntuer 发表于 2010-04-04 13:04

节点插入树时自动排序、平衡，不需要你做。至于节点数，自己记录吧，