Flyingis

Talking and thinking freely !
Flying in the world of GIS !
随笔 - 156, 文章 - 16, 评论 - 589, 引用 - 0
数据加载中……

数据结构中避免数据项的重复

抽象数据类型(ADT)是一种只能通过接口访问的数据类型,它是字段与基于字段的操作所构成的集合。这里的接口不是interface,而是访问数据的途径,接口把数据的表示和操作方法的实现完全分离开来。两种最基本的ADT是堆栈和队列,并且根据我们的需要,可以构建更为复杂的ADT,例如可以对数据项进行计数,检查数据项是否存在重复等等。

在很多实际应用中,我们都不允许存在数据项重复的情况,需要对用户提交的重复数据进行合适的处理。让用户保证不提交重复的数据可以避免这种情况的发生,但显然这种方法并不实际,既然使用ADT就是为了给使用它的程序员提供简单明了的数据类型解决方案,那么我们就应该在ADT中来解决这个问题。以队列为例,一般可以通过两种策略来处理这个问题:

1.        放弃新输入的数据项:当最新放入队列中的数据项已经在队列中时,放弃当前输入的数据项。

2.        放弃旧的数据项,保存新输入的数据项:当最新放入队列中的数据项已经在队列中时,放弃已经存在于队列中的数据项,保存当前放入的数据项。

    对于第一种处理方式,在一种特殊的情况下,数据项存储的数据是0~N-1之间的整数,那么可以通过增加一个新的数组a[i]或链表来储存boolean类型数据,当队列中第i个位置上已经存在数据i(i<=N-1),设置a[i]=boolean,那么可以通过a[i]来判断数据i是否已经存在于队列中。第二种处理方式比第一种更为复杂一些,如果有必要,还可以让用户去选择采取哪种策略来避免重复的数据项。但不管怎么样,我们可以通过构建不同类型的ADT,并在ADT中实现某些我们所需要的功能,将能极大限度地保证数据结构和算法的灵活性与清晰的结构,使基于ADT的实现能满足各种不同的具体应用,并方便类的重构。

posted on 2006-01-30 00:34 Flyingis 阅读(961) 评论(2)  编辑  收藏 所属分类: Algorithm

评论

# re: 数据结构中避免数据项的重复  回复  更多评论   

不许重复的数据项,听上去想是集合的概念.java collection framework 里的Set,你看是不是解决你说的问题呀. 当然set有不同数据结构实现的子类
2006-02-01 18:35 | 集合

# re: 数据结构中避免数据项的重复  回复  更多评论   

Set的确实现了类似的功能,但不能满足任何情况下功能上的需要;有时对于特定的数据,需要考虑程序的运行效率.这两种情况下都需要自己重新设计数据结构.即只设计自己需要的功能,并在特定情况下满足效率上的需要.
2006-02-01 22:31 | Flyingis

只有注册用户登录后才能发表评论。


网站导航: