返回信息流简单的链表结构拥有很好的插入 删除节点性能, 但随机定位(获取链表第n个节点)操作性能不佳, 请你设计一种改进型的链表结构优化随机定位操作的性能, 给出设计思路及其改进后随机定位操作的时间复杂度
这是一条镜像帖。来源：北邮人论坛 / cpp / #44306同步于 2010/9/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
向大牛求助，一道去年网易的笔试题！
yinghan
2010/9/28镜像同步9 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
方案一：
增加一个数组 记录所有节点的指针情况 这样随机访问时间为O(1)
缺点是：链表插入删除后对该数组的更新代价高，而且数据静态分配，有大小限制
改进方案二：
用BST记录所有节点的指针情况，当然了能用平衡的BST最好了
这样， 随机访问的时间O(logn)
但却避免了方案一的缺点
ps. 网易啥时候笔试的？ 日 我咋忘了投了呢 悲剧。。。
【 在 jmpesp 的大作中提到: 】
: 方案一：
: 增加一个数组 记录所有节点的指针情况 这样随机访问时间为O(1)
: 缺点是：链表插入删除后对该数组的更新代价高，而且数据静态分配，有大小限制
: ...................
这是以前的笔试题，我挖坟挖出来的。。。
网易今天晚上7点的笔试，网申截止的早导致很多人都忘了投
【 在 jmpesp 的大作中提到: 】
: 方案一：
: 增加一个数组 记录所有节点的指针情况 这样随机访问时间为O(1)
: 缺点是：链表插入删除后对该数组的更新代价高，而且数据静态分配，有大小限制
: ...................
哦。BST是二叉树的意思么。。大牛google笔的咋样
Binary Search Tree
二叉搜索树
【 在 xiecaiji 的大作中提到: 】
: : 方案一：
: : 增加一个数组 记录所有节点的指针情况 这样随机访问时间为O(1)
: : 缺点是：链表插入删除后对该数组的更新代价高，而且数据静态分配，有大小限制
: ...................
改进方案二有点主次颠倒了，为了改进一个简单链表，居然大动干戈弄出一棵树，莫不如在树里做插入、删除、搜索、定位呢。
【 在 jmpesp 的大作中提到: 】
: 方案一：
: 增加一个数组 记录所有节点的指针情况 这样随机访问时间为O(1)
: 缺点是：链表插入删除后对该数组的更新代价高，而且数据静态分配，有大小限制
: ...................
那不就是直接的链式哈希了？
【 在 braveheart 的大作中提到: 】
: 哈希表
: --
: 只有心的强大才是真正的强大
: ...................
我的算法：基本思想是来源于分块排序索引表：
定义一个索引表：索引表格式如下： 0 d 2d .... nd
*p1 *p2 *p3 ..... *pn
*pn 为指向链表第n个节点的指针
当 要定位链表第m项时，先在索引表中查找离目标节点最近的指针，索引表第一行元素是有序等差数列，可以用二分查找算法实现，然后用得到的指针操作链表，平均时间复杂度为lg(n/d) + d/2
因为索引表第一行元素是有序等差数列，可以用精算点算法查找，基本可以一次定位，具体方法是在二分查找中mid改为mid = low + (k - R[low].key)*(high-low)/(R[high].key -R[low].key])+0.5//加0.5是四舍五入，即使不能一次定位，mid也已经在待查元素附近，在用顺序查找，很快可以查到目标