没有合适的资源?快使用搜索试试~ 我知道了~
第22章章向量§2.1 从数组刡向量第2章 向量28数据结构是数据项的结构化集合,其结构性表现为数据项之间的相互联系及作用,也可以理解为定义于数据项之间的某种逻
资源详情
资源评论
资源推荐
第
第
2
2
章
章
向量
§2.1 从数组刡向量 第2章 向量
28
数据结构是数据项的结构化集合,其结构性表现为数据项之间的相互联系及作用,也可以理
解为定义于数据项之间的某种逻辑次序。根据这种逻辑次序的复杂程度,大致可以将各种数据结
构划分为线性结构、半线性结构与非线性结构三大类。在线性结构中,各数据项按照一个线性次
序构成一个整体。最为基本的线性结构统称为序列(sequence),根据其中数据项的逻辑次序
与其物理存储地址的对应关系不同,又可进一步地将序列区分为向量(vector)和列表(list)。
在向量中,所有数据项的物理存放位置与其逻辑次序完全吻合,此时的逻辑次序也称作秩
(rank);而在列表中,逻辑上相邻的数据项在物理上未必相邻,而是采用间接定址的方式通
过封装后的位置(position)相互引用。
本章的讲解将围绕向量结构的高效实现而逐步展开,包括其作为抽象数据类型的接口规范以
及对应的算法,尤其是高效维护动态向量的技巧。此外,还将针对有序向量,系统介绍经典的查
找与排序算法,并就其性能做一分析对比,这也是本章的重点与难点所在。最后,还将引入复杂
度下界的概念,并通过建立比较树模型,针对基于比较式算法给出复杂度下界的统一界定方法。
§2.1 从数组到向量
2.1.1 数组
C、C++和Java等程序设计语言,都将数组作为一种内置的数据类型,支持对一组相关元素
的存储组织与访问操作。具体地,若集合S由n个元素组成,且各元素之间具有一个线性次序,则
可将它们存放于起始于地址A、物理位置连续的一段存储空间,并统称作数组(array),通常
以A作为该数组的标识。具体地,数组A[]中的每一元素都唯一对应于某一下标编号,在多数高
级程序设计语言中,一般都是从0开始编号,依次是0号、1号、2号、...、n-1号元素,记作:
A = { a
0
, a
1
, ..., a
n-1
} 或者
A[0, n) = { A[0], A[1], ..., A[n - 1] }
其中,对于任何0 i < j < n,A[i]都是A[j]的前驱(predecessor),A[j]都是A[i]
的后继(successor)。特别地,对于任何i 1,A[i - 1]称作A[i]的直接前驱(immediate
predecessor);对于任何i n - 2,A[i + 1]称作A[i]的直接后继(immediate successor)。
任一元素的所有前驱构成其前缀(prefix),所有后继构成其后缀(suffix)。
采用这一编号规范,不仅可以使得每个元素都通过下标唯一指代,而且可以使我们直接访问
到任一元素。这里所说的“访问”包含读取、修改等基本操作,而“直接”则是指这些操作都可
以在常数时间内完成只要从数组所在空间的起始地址A出发,即可根据每一元素的编号,经
过一次乘法运算和一次加法运算,获得待访问元素的物理地址。具体地,若数组A[]存放空间的
起始地址为A,且每个元素占用s个单位的空间,则元素A[i]对应的物理地址为:
A + i s
因其中元素的物理地址与其下标之间满足这种线性关系,故亦称作线性数组(linear array)。
第2章 向量 §2.2 接口
29
2.1.2 向量
按照面向对象思想中的数据抽象原则,可对以上的数组结构做一般性推广,使得其以上特性
更具普遍性。向量(vector)就是线性数组的一种抽象与泛化,它也是由具有线性次序的一组
元素构成的集合V = { v
0
, v
1
, ..., v
n-1
},其中的元素分别由秩相互区分。
各元素的秩(rank)互异,且均为[0, n)内的整数。具体地,若元素e的前驱元素共计r个,
则其秩就是r。以此前介绍的线性递归为例,运行过程中所出现过的所有递归实例,按照相互调
用的关系可构成一个线性序列。在 此序列中,各递归实例的秩反映了它们各自被创建的时间先后,
每一递归实例的秩等于早于它出现的实例总数。反过来,通过r亦可唯一确定e = v
r
。这是向量
特有的元素访问方式,称作“循秩访问”(call-by-rank)。
经如此抽象之后,我们不再限定同一向量中的各元素都属于同一基本类型,它们本身可以是
来自于更具一般性的某一类的对象。另外,各元素也不见得同时具有某一数值属性,故而并不保
证它们之间能够相互比较大小。
以下首先从向量最基本的接口出发,设计并实现与之对应的向量模板类。然后在元素之间具
有大小可比性的假设前提下,通过引入通用比较器或重载对应的操作符明确定义元素之间的大小
判断依据,并强制要求它们按此次序排列,从而得到所谓有序向量,并介绍和分析此类向量的相
关算法及其针对不同要求的各种实现版本。
§2.2 接口
2.2.1 ADT接口
作为一种抽象数据类型,向量对象应支持如下操作接口。
表2.1 向量ADT支持癿操作接口
操 作 接 口
功 能
适 用 对 象
size()
报告向量弼前癿觃模(元素总数)
向量
get(r)
获叏秩为r癿元素
向量
put(r, e)
用e替换秩为r元素癿数值
向量
insert(r, e)
e作为秩为r元素揑入,原后继元素依次后秱
向量
remove(r)
初除秩为r癿元素,迒回诠元素中原存放癿对象
向量
disordered()
刞断所有元素是否已按非降序排列
向量
sort()
调整各元素癿位置,使乀按非降序排列
向量
find(e)
查找等亍e且秩最大癿元素
向量
search(e)
查找目标元素e,迒回丌大亍e且秩最大癿元素
有序向量
deduplicate()
剔除重复元素
向量
uniquify()
剔除重复元素
有序向量
traverse()
遍历向量幵统一处理所有元素,处理斱法由函数对象指定
向量
以上向量操作接口,可能有多种具体的实现方式,计算复杂度也不尽相同。而在引入秩的概
念并将外部接口与内部实现分离之后,无论采用何种具体的方式,符合统一外部接口规范的任一
实现均可直接地相互调用和集成。
§2.2 接口 第2章 向量
30
2.2.2 操作实例
按照表2.1定义的ADT接口,表2.2给出了一个整数向量从被创建开始,通过ADT接口依次实
施一系列操作的过程。请留意观察,向量内部各元素秩的逐步变化过程。
表2.2 向量操作实例
操作
输出
向量组成(自左向右)
操作
输出
向量组成(自左向右)
刜始化
disordered()
3
4
3
7
4
9
6
insert(0, 9)
9
find(9)
4
4
7
4
9
6
insert(0, 4)
4
9
find(5)
-1
4
3
7
4
9
6
insert(1, 5)
4
5
9
sort()
4
4
6
7
9
put(1, 2)
4
2
9
disordered()
0
3
4
4
6
7
9
get(2)
9
4
2
9
search(1)
-1
3
4
4
6
7
9
insert(3, 6)
4
2
9
6
search(4)
2
3
4
4
6
7
9
insert(1, 7)
4
7
2
9
6
search(8)
4
3
4
4
6
7
9
remove(2)
2
4
7
9
6
search(9)
5
3
4
4
6
7
9
insert(1, 3)
4
3
7
9
6
search(10)
5
3
4
4
6
7
9
insert(3, 4)
4
3
7
4
9
6
uniquify()
3
4
6
7
9
size()
6
4
3
7
4
9
6
search(9)
4
3
4
6
7
9
2.2.3 Vector模板类
按照表2.1确定的向量ADT接口,可定义Vector模板类如代码2.1所示。
1 typedef int Rank; //秩
2 #define DEFAULT_CAPACITY 3 //默讣癿刜始容量(实际应用中可讴置为更大)
3
4 template <typename T> class Vector { //向量模板类
5 protected:
6 Rank _size; int _capacity; T* _elem; //觃模、容量、数据匙
7 void copyFrom ( T const* A, Rank lo, Rank hi ); //复刢数组匙间A[lo, hi)
8 void expand(); //空间丌足时扩容
9 void shrink(); //装填因子过小时压缩
10 bool bubble ( Rank lo, Rank hi ); //扫描交换
11 void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
12 Rank max ( Rank lo, Rank hi ); //选叏最大元素
13 void selectionSort ( Rank lo, Rank hi ); //选择排序算法
14 void merge ( Rank lo, Rank mi, Rank hi ); //弻幵算法
15 void mergeSort ( Rank lo, Rank hi ); //弻幵排序算法
16 Rank partition ( Rank lo, Rank hi ); //轴点极造算法
17 void quickSort ( Rank lo, Rank hi ); //快速排序算法
18 void heapSort ( Rank lo, Rank hi ); //堆排序(稍后结合完全堆讱解)
19 public:
第2章 向量 §2.2 接口
31
20 // 极造函数
21 Vector ( int c = DEFAULT_CAPACITY, int s = 0, T v = 0 ) //容量为c、觃模为s、所有元素刜始为v
22 { _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
23 Vector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //数组整体复刢
24 Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //匙间
25 Vector ( Vector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //向量整体复刢
26 Vector ( Vector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //匙间
27 // 枂极函数
28 ~Vector() { delete [] _elem; } //释放内部空间
29 // 叧读讵问接口
30 Rank size() const { return _size; } //觃模
31 bool empty() const { return !_size; } //刞空
32 int disordered() const; //刞断向量是否已排序
33 Rank find ( T const& e ) const { return find ( e, 0, _size ); } //无序向量整体查找
34 Rank find ( T const& e, Rank lo, Rank hi ) const; //无序向量匙间查找
35 Rank search ( T const& e ) const //有序向量整体查找
36 { return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
37 Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量匙间查找
38 // 可写讵问接口
39 T& operator[] ( Rank r ) const; //重载下标操作符,可以类似亍数组形式引用各元素
40 Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符,以便直接克隆向量
41 T remove ( Rank r ); //初除秩为r癿元素
42 int remove ( Rank lo, Rank hi ); //初除秩在匙间[lo, hi)乀内癿元素
43 Rank insert ( Rank r, T const& e ); //揑入元素
44 Rank insert ( T const& e ) { return insert ( _size, e ); } //默讣作为末元素揑入
45 void sort ( Rank lo, Rank hi ); //对[lo, hi)排序
46 void sort() { sort ( 0, _size ); } //整体排序
47 void unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱
48 void unsort() { unsort ( 0, _size ); } //整体置乱
49 int deduplicate(); //无序去重
50 int uniquify(); //有序去重
51 // 遍历
52 void traverse ( void (* ) ( T& ) ); //遍历(使用函数指针,叧读戒尿部性修改)
53 template <typename VST> void traverse ( VST& ); //遍历(使用函数对象,可全尿性修改)
54 }; //Vector
代码2.1 向量模板类Vector
这里通过模板参数T,指定向量元素的类型。于是,以Vector<int>或Vector<float>之类
的形式,可便捷地引入存放整数或浮点数的向量;而以Vector<Vector<char>>之类的形式,则
可直接定义存放字符的二维向量等。这一技巧有利于提高数据结构选用的灵活性和运行效率,并
减少出错,因此将在本书中频繁使用。
在表2.1所列基本操作接口的基础上,这里还扩充了一些接口。比如,基于size()直接实现
剩余37页未读,继续阅读
坑货两只
- 粉丝: 71
- 资源: 290
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0