| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 935 人关注过本帖
标题:快速维护链表的方法
只看楼主 加入收藏
墨清扬
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:294
专家分:817
注 册:2011-10-4
结帖率:100%
收藏
已结贴  问题点数:100 回复次数:15 
快速维护链表的方法
假如有一个链表,链节为一个结构,已按某个成员的升序排好,对它有四种操作:
1、查询某个链节
2、增加一个链节,保持升序
3、删除一个链节,保持升序
4、按顺序输出全部链节的内容到屏幕

视野很重要,所以想知道有多少种实现办法,然后都有什么优缺点。

以下是我想到的:

1、全部遍历。
这个是最常规最低级的了
优点:易于实现,不易出错
缺点:链节多或者操作多的时候效率很低

2、树
构建一棵二叉树来维护链表,为避免退化还可以做成红黑树等等
优点:除输出外效率都不错
缺点:输出慢;遇到大量的极端数据,要么退化要么很慢(比如红黑树要转很多次)。

3、散列
将链节散列到多个地址,用拉链法保存散列值相同的链节
优点:增加和删除都快,一般情况下。
缺点:散列函数不好设计,设计得不好的话由占空间效率又低,跟没散列一样;输出的时候要重新组合在一起,时间复杂度至少是n,糟糕的散列函数可能会达到n^2。

4、懒惰标记
新建一个临时链表保存要添加的链节,直到删除和输出时才合并在一起(不知道删除也放在一个临时列表里效率会怎么样?)
优点:易于实现,连续的添加操作可以在O(n)完成
缺点:添加一次输出一次的话就变成跟第一种算法一样了。

5、类似标记排序法
用于排序的成员可能取值在一个不大的区间M内时,开辟一个M的数组,1表示有,0表示没有。
优点:输出为O(M),其它都是O(1)
缺点:只能在部分情况下使用


想到的就这么多了……效率都不高的样子……


搜索更多相关主题的帖子: 优缺点 二叉树 
2012-04-16 13:20
hellovfp
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:禁止访问
威 望:30
帖 子:2976
专家分:7697
注 册:2009-7-21
收藏
得分:25 
这个值得讨论,偶最近也在思考类似的问题。。
链表的还有一个问题就是malloc和free在分配节点内存时效率问题。偶的思考是采用内存池办法处理。
查询如果用树或是散列会大大加快查询的速度。
输出全部内容,用遍历。

其实这是大多数程序速度和空间的矛盾,想要快速,基本上拿空间来换,想要空间,拿速度来换。

[ 本帖最后由 hellovfp 于 2012-4-16 14:06 编辑 ]

我们都在路上。。。。。
2012-04-16 13:59
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:15 
我第一想到的是 链式堆 (二项堆,或者fib-heap)。
2012-04-16 14:08
hellovfp
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:禁止访问
威 望:30
帖 子:2976
专家分:7697
注 册:2009-7-21
收藏
得分:0 
看看DW大侠的提示,或许还有其它更好的数据结构。
几种堆(BinaryHeap, FibHeap, PairHeap)
any more??

[ 本帖最后由 hellovfp 于 2012-4-16 14:21 编辑 ]

我们都在路上。。。。。
2012-04-16 14:15
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:60 
链表本身就是为了方便插入和删除而设计的数据结构,现在的问题根本不在插入和删除上,与内存分配无关。他的麻烦主要是对链表的查询,因为要维护已排序状态,就必须找出新插入项应在什么位置,插入不是问题,找到这个位置才是问题,链表的查询比线性表慢。解决的办法,不妨另外做一份对应的线性表,按照排序项排好的,每个元素附带对应的链表项的实际指针。说白了就是用List的查询高效补充Link的查询低效,用Link的增删高效补充List的增删低效,两种结构综合了用。在面向对象的类设计中,封装这么一个综合功能,不是很难的事。
收到的鲜花
  • 绿茶盖儿2012-04-17 10:25 送鲜花  10朵   附言:我很赞同

授人以渔,不授人以鱼。
2012-04-16 14:21
墨清扬
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:294
专家分:817
注 册:2011-10-4
收藏
得分:0 
回复 2楼 hellovfp
按现在的硬件水平,时间应该比空间重要了,那么有什么快的算法吗

酱油实习生
2012-04-16 14:23
墨清扬
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:294
专家分:817
注 册:2011-10-4
收藏
得分:0 
回复 5楼 TonyDeng
嗯,也是……但是如果从零开始创建一个长链表呢?多久更新一次线性表合适?

酱油实习生
2012-04-16 14:26
hellovfp
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:禁止访问
威 望:30
帖 子:2976
专家分:7697
注 册:2009-7-21
收藏
得分:0 
回复 5楼 TonyDeng
Tong版说的,也是偶思考中的一个解决办法,用附加数组来解决链表的随机访问问题。

我们都在路上。。。。。
2012-04-16 14:28
hellovfp
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:禁止访问
威 望:30
帖 子:2976
专家分:7697
注 册:2009-7-21
收藏
得分:0 
回复 6楼 墨清扬
据说散列目前也有好几种比较不错的算法,ISBN就一种,md5也算一种,值得研究究。

我们都在路上。。。。。
2012-04-16 14:30
hellovfp
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:禁止访问
威 望:30
帖 子:2976
专家分:7697
注 册:2009-7-21
收藏
得分:0 
回复 7楼 墨清扬
我的思考是添加一个值,用来标识是否需要创建附加数组。1表示需要更新,0表示不需要。
在添加的时候可以重设这个值,直到用户添加完所有数据,第一次调用查询的时候,进行更新。

我们都在路上。。。。。
2012-04-16 14:31
快速回复:快速维护链表的方法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032759 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved