没有合适的资源?快使用搜索试试~ 我知道了~
第33章章列表§3.1 从向量刡列表第3章 列表66上一章介绍的向量结构中,各数据项的物理存放位置与逻辑次序完全对应,故可通过秩直接访问对应的元素,此即所谓“循
资源详情
资源评论
资源推荐
第
第
3
3
章
章
列表
§3.1 从向量刡列表 第3章 列表
66
上一章介绍的向量结构中,各数据项的物理存放位置与逻辑次序完全对应,故可通过秩直接
访问对应的元素,此即所谓“循秩访问”(call-by-rank)。这种访问方式,如同根据具体的
城市名、街道名和门牌号,直接找到某人。本章将要介绍的列表,与向量同属序列结构的范畴,
其中的元素也构成一个线性逻辑次序;但与向量极为不同的是,元素的物理地址可以任意。
为保证对列表元素访问的可行性,逻辑上互为前驱和后继的元素之间,应 维护某种索引关系。
这种索引关系,可抽象地理解为被索引元素的位置(position),故列表元素是“循位置访问”
(call-by-position)的;也可形象地理解为通往被索引元素的链接(link),故亦称作“循
链接访问”(call-by-link)。这种访问方式,如同通过你的某位亲朋,找到他/她的亲朋、亲
朋的亲朋、...。注意,向量中的秩同时对应于逻辑和物理次序,而位置仅对应于逻辑次序。
本章的讲解,将围绕列表结构的高效实现逐步展开,包括其ADT接口规范以及对应的算法。
此外还将针对有序列表,系统地介绍排序等经典算法,并就其性能做一分析和对比。
§3.1 从向量到列表
不同数据结构内部的存储与组织方式各异,其操作接口的使用方式及时空性能也不尽相同。
在设计或选用数据结构时,应从实际应用的需求出发,先确定功能规范及性能指标。比如,引入
列表结构的目的,就在于弥补向量结构在解决某些应用问题时,在功能及性能方面的不足。二者
之间的差异,表面上体现于对外的操作方式,但根源则在于其内部存储方式的不同。
3.1.1 从静态到动态
数据结构支持的操作,通常无非静态和动态两类:前者仅从中获取信息,后者则会修改数据
结构的局部甚至整体。以第2章基于数组实现的向量结构为例,其size()和get()等静态操作均
可在常数时间内完成,而insert()和remove()等动态操作却都可能需要线性时间。究其原因,
在于“各元素物理地址连续”的约定此即所谓的“静态存储”策略。
得益于这种策略,可在O(1)时间内由秩确定向量元素的物理地址;但反过来,在添加(删
除)元素之前(之后),又不得不移动O(n)个后继元素。可见,尽管如此可使静态操作的效率
达到极致,但就动态操作而言,局部的修改可能引起大范围甚至整个数据结构的调整。
列表(list)结构尽管也要求各元素在逻辑上具有线性次序,但对其物理地址却未作任何
限制此即所谓“动态存储”策略。具体地,在其生命期内,此类数据结构将随着内部数据的
需要,相应地分配或回收局部的数据空间。如此,元素之间的逻辑关系得以延续,却不必与其物
理次序相关。作为补偿,此类结构将通过指针或引用等机制,来确定各元素的实际物理地址。
例如,链表(linked list)就是一种典型的动态存储结构。其中的数据,分散为一系列称
作节点(node)的单位,节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点,
只需在局部,调整少量相关节点之间的指针。这就意味着,采用动态存储策略,至少可以大大降
低动态操作的成本。
第3章 列表 §3.2 接口
67
3.1.2 由秩到位置
改用以上动态存储策略之后,在提高动态操作效率的同时,却又不得不舍弃原静态存储策略
中循秩访问的方式,从而造成静态操作性能的下降。
以采用动态存储策略的线性结构(比如链表)为例。尽管按照逻辑次序,每个数据元素依然
具有秩这一指标,但为了访问秩为r的元素,我们只能顺着相邻元素之间的指针,从某一端出发
逐个扫描各元素,经过r步迭代后才能确定该元素的物理存储位置。这意味着,原先只需O(1)时
间的静态操作,此时的复杂度也将线性正比于被访问元素的秩,在最坏情况下等于元素总数n;
即便在各元素被访问概率相等的情况下,平均而言也需要O(n)时间。
对数据结构的访问方式,应与其存储策略相一致。此时,既然继续延用循秩访问的方式已非
上策,就应更多地习惯于通过位置,来指代并访问动态存储结构中的数据元素。与向量中秩的地
位与功能类似,列表中的位置也是指代各数据元素的一个标识性指标,借助它可以便捷地(比如
在常数时间内)得到元素的物理存储地址。各元素的位置,通常可表示和实现为联接于元素之间
的指针或引用。因此,基于此类结构设计算法时,应更多地借助逻辑上相邻元素之间的位置索引,
以实现对目标元素的快速定位和访问,并进而提高算法的整体效率。
3.1.3 列表
与向量一样,列表也是由具有线性逻辑次序的一组元素构成的集合:
L = { a
0
, a
1
, ..., a
n-1
}
列表是链表结构的一般化推广,其中的元素称作节点(node),分别由特定的位置或链接
指代。与向量一样,在元素之间,也可定义前驱、直接前驱,以及后继、直接后继等关系;相对
于任意元素,也有定义对应的前缀、后缀等子集。
§3.2 接口
如上所述,作为列表的基本组成单位,列表节点除需保存对应的数据项,还应记录其前驱和
后继的位置,故需将这些信息及相关操作组成列表节点对象,然后参与列表的构建。
本节将给出列表节点类与列表类的接口模板类描述,稍后逐一讲解各接口的具体实现。
3.2.1 列表节点
ADT接口
作为一种抽象数据类型,列表节点对象应支持以下操作接口。
表3.1 列表节点ADT支持癿操作接口
操 作 接 口
功 能
data()
弼前节点所存数据对象
pred()
弼前节点前驱节点癿位置
succ()
弼前节点后继节点癿位置
insertAsPred(e)
揑入前驱节点,存入被引用对象e,迒回新节点位置
insertAsSucc(e)
揑入后继节点,存入被引用对象e,迒回新节点位置
§3.2 接口 第3章 列表
68
ListNode模板类
按照表3.1所定义的ADT接口,可定义列表节点模板类如代码3.1所示。出于简洁与效率的考
虑,这里并未对ListNode对象做封装处理。列表节点数据项的类型,通过模板参数T指定。
1 typedef int Rank; //秩
2 #define ListNodePosi(T) ListNode<T>* //列表节点位置
3
4 template <typename T> struct ListNode { //列表节点模板类(以双向链表形式实现)
5 // 成员
6 T data; ListNodePosi(T) pred; ListNodePosi(T) succ; //数值、前驱、后继
7 // 极造函数
8 ListNode() {} //针对header和trailer癿极造
9 ListNode ( T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s = NULL )
10 : data ( e ), pred ( p ), succ ( s ) {} //默讣极造器
11 // 操作接口
12 ListNodePosi(T) insertAsPred ( T const& e ); //紧靠弼前节点乀前揑入新节点
13 ListNodePosi(T) insertAsSucc ( T const& e ); //紧随弼前节点乀后揑入新节点
14 };
代码3.1 列表节点模板类
①
每个节点都存有数据对象data。为保证叙述简洁,在不致歧义的前提下,本书将不再区分
节点及其对应的data对象。此外,每个节点还设有指针pred和succ,分别指向其前驱和后继。
为了创建一个列表节点对象,只需根据所提供的参数,分别设置节点内部的各个变量。其中
前驱、后继节点的位置指针若未予指定,则默认取作NULL。
3.2.2 列表
ADT接口
作为一种抽象数据类型,列表对象应支持以下操作接口。
表3.2 列表ADT支持癿操作接口
操 作 接 口
功 能
适 用 对 象
size()
报告列表弼前癿觃模(节点总数)
列表
first()、last()
迒回首、末节点癿位置
列表
insertAsFirst(e)
insertAsLast(e)
将e弼作首、末节点揑入
列表
insertA(p, e)
insertB(p, e)
将e弼作节点p癿直接后继、前驱揑入
列表
①
请注意,返里所“定丿”癿ListNodePosi(T)幵非真正意丿上“列表节点位置”类型。
巧合癿是,就在本书第1版即将付印乀际,C++.0x标准终亍被ISO接纳。
新标准所拓展癿特性乀一,就是对模板删名(template alias)等语法形式癿支持。因此可以期望在丌丽癿将来,
C++编译器将能够支持如下更为直接和简明癿描述和实现:
template <typename T> typedef ListNode<T>* ListNodePosi;
剩余19页未读,继续阅读
BJWcn
- 粉丝: 28
- 资源: 294
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0