向量基础知识测验

好的，这是根据您提供的文本生成的学习笔记：

第2章 向量

• 数据结构是数据项的结构化集合，其结构性表现数据项之间的相互联系作用。
• 逻辑次序的复杂程度大致将各种数据结构划分为线性、半线性与非线性结构三大类。
• 线性结构中，各数据项按照一个线性次序构成一个整体，又被称为序列 (sequence)
• 根据数据项的逻辑次序与其物理存储地址的对应关系，序列可进一步区分为向量 (vector) 和列表 (list)。
• 向量中所有数据项的物理存放位置与其逻辑次序完全吻合；逻辑次序也称作秩 (rank)。
• 列表中逻辑相邻的数据项在物理上不一定相邻，而是采用间接定址相互引用。

数组

• C、C++ 和 Java 等程序设计语言，都将数组作为一种内置的数据类型。
• 集合 S 由 n 个元素组成，且具有线性次序，可存放于起始于地址 A、物理位置连续的一段存储空间，称为数组 (array)。
• 数组 A[] 中的每一元素唯一对应于某一下标编号，在多数高级程序设计语言中，一般从 0 开始编号，依次记作 0 号， 1 号， 2 号，...，n-1 号元素。
  • 记作: A = { a₀, a₁, ..., aₙ-₁ } 或者 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]的直接前驱 (intermediate predecessor)
• 对于任何i≤n-2,A[i+1]称作A[i]的直接后继 (intermediate successor)
• 任一元素的所有前驱构成其前缀 (prefix),所有后继构成其后缀 (suffix)。
• 采用唯一编号规范，可以使得每个元素都通过下标唯一指代，也可以直接访问到任一元素。
• “访问”包含读取、修改等基本操作，都可以在常数时间内完成。
• 数组的起始地址为A，且每个元素占用s个单位的空间，则元素A[i]对应的物理地址为: A+i×s
• 元素的物理地址与其下标之间满足线性关系，故亦称作线性数组 (linear array)。

向量

• 向量(vector)是线性数组的一种抽象与泛化，也是由具有线性次序的一组元素构成的集合。
  • V = { v₀, v₁, ..., vₙ-₁ }，其中的元素分别由秩相互区分。
• 各元素的秩(rank)互异，且均为[0, n)内的整数
  • 若元素 e 的前驱元素共计 r 个，则其秩就是 r
• "循秩访问(call-by-rank)": 通过秩亦可唯一确定元素。
• 向量元素不限定统一基本类型，本身可以是来自于更具一般性的某类的对象。
• 元素不见得同时具有某一数值属性，故不保证它们之间能够相互比较大小。

ADT 接口

• 向量对象应支持的操作接口：

• 引入秩的概念、并将外部接口与内部实现分离之后，无论采用何种具体的方式，符合统一外部接口规范的任一实现均可直接相互调用和集成。

操作示例（整数向量）

Vector 模板类

• 向量的ADT接口的代码定义
• typedef int Rank; //秩
• #define DEFAULT_CAPACITY 3 //默认的初始容量
• class Vector: 向量模板类
• protected: 规模、容量、数据区
• void copyFrom(const* A, Rank lo, Rank hi); //复制数组区间A[lo, hi)
• void expand();//空间不足时扩容
• void shrink();//装填因子过小时压缩
• bool bubble (Rank lo, Rank hi); //扫描交换
• void bubbleSort(Rank lo, Rank hi); //起泡排序算法
• Rank max(Rank lo, Rank hi); //选取最大元素
• void selectionSort(Rank lo, Rank hi) //选择排序算法
• void merge (Rank lo, Rank mi, Rank hi): //归并算法
• void mergeSort(Rank lo, Rank hi); //归并排序算法
• Rank partition (Rank lo, Rank hi); //轴点构造算法
• void quickSort(Rank lo, Rank hi); //快速排序算法
• void heapSort(Rank lo, Rank hi); //堆排序(稍后结合完全堆讲解)

构造与析构

• 向量结构在内部维护一个数组_elem[]
  • 元素类型为T
  • 容量由私有变量_capacity指示；
  • 有效元素的数量 (即向量当前的实际规模) 由_size指示。
• 约定秩和物理地址具有如下关系：
  • 向量中秩为 r 的元素，对应于内部数组中的_elem[r]，其物理地址_elem + r
• 向量对象的构造与析构，将主要围绕初始化与销毁展开。

默认构造方法

• 向量在使用之前需要被系统创建 — 借助构造函数 (constructor) 做初始化 (initialization) 。
• 借助创建者指定的初始容量，向系统申请空间，以创建内部私有数组。
  • 容量未明确指定，则使用默认值DEFAULT_CAPACITY。
• 不包含任何元素，故将指示规模的变量_size初始化为 0。
• 整个过程顺序进行,共需常数时间。

基于复制的构造方法

• 以某个已有的向量 (vector) 或数组为蓝本，进行克隆。无论封装还是未封装，都可归于统一的 copyFrom() 方法。
• 先根据待复制区间的边界，换算出新向量的初始规模，再以双倍的容量，为内部数组申请空间；再通过一趟迭代，完成各元素的顺次复制。
• 基于复制的向量构造器的代码（以数组区间A[lo, hi)为蓝本复制向量）： 1 template <typename T> //元素类型 2 void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi) { //以数组区间A[lo,hi)为蓝本复制向量 3 _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0; 4 while (lo < hi) { //A[lo, hi)内的元素逐 - 5 _elem[_size++] = A[lo++]; //复制至 _elem[0, hi - lo) 6 }
• 运行时间应正比于区间宽度，即0(hi - lo) = 0(_size)。

析构方法

• 向量不再需要会被析构函数 (destructor) 及时清理 (cleanup)
  • 以释放其占用的系统资源。
• 向量对象的析构过程：只需释放内部数组_elem[],将其占用的空间交还操作系统,
• 若不计系统用于空间回收的时间，整个析构过程只需 Θ(1) 时间。
• 如果元素不是程序语言直接支持的基本类型，应该提前释放对应的空间。
• “谁申请谁释放”的原则。究竞应释放掉向量各元素所指的对象，还是需要保留这些对象，应由上层确定。

静态空间管理

• 内部数组所占物理空间的容量，若在向量的生命期内不允许调整，则称作静态空间管理策略。
  • 但空间效率难以保证。
  • 容量固定，总有可能在此后的某一时刻，无法加入更多的新元素 — 上溢 (overflow)。
  • 上溢是由于插入操作远多于删除操作造成的
  • 实际规模与其内部数组容量的比值(即_size / _capacity)，亦称作装填因子 (load factor)，它是衡量空间利用率的重要指标.

动态空间管理

• 如何保证向量的装填因子既不致于超过1, 也不致于太接近于0？需要改用动态空间管理策略，改用所谓的可扩充向量。

可扩充向量

• 当身体无法继续为其外壳所容纳，蝉就会蜕去外壳，同时换上一身更大的外壳。
• 扩充向量 (extendable vector) 的原理，与之相仿。
  • 内部数组仍有空余，则照常执行。
  • 每经一次插入 (删除) ，可用空间都会减少(增加)一个单元。
  • 一旦可用空间耗尽，就动态地扩大内部数组的容量，以另行申请一个容量更大的数组。
  • 将原数组中的成员集体搬迁至新的空间，此后方可在新数组中顺利插入。
  • 原数组所占的空间，需要及时释放并归还操作系统。
• 扩容算法expand()
  • 检查内部数组的可用容量。
  • 当前数据区已满 (_size == _capacity)，则将原数组替换为一个更大的数组。
• 不要直接引用数组，那样会导致野指针 (wild pointer)；而经封装为向量之后，即可继续准确地引用各元素,从而有效地避免野指针的风险。
• 新数组的容量总是取作原数组的两倍。

分摊分析

• 常规数组实现相比，可扩充向量更加灵活，只要系统尚有可用空间，其规模将不再受限于初始容量。但是，扩增是要花费额外时间的。
• 对可扩充向量的足够多次连续操作，并将其间所消耗的时间，分摊至所有的操作
  • 单次操作的时间成本,称作分摊运行时间(amortized running time)。
• 分摊复杂度可以针对计算成本和效率，做出更为客观而准确的估计。

静态空间管理

• 内部数组所占物理空间的容量,若在向量的生命期内不允许调整,则称作静态空间管理策略。
  • 但空间效率难以保证
  • 既然容量固定,总有可能在此后的某一时刻, 无法加入更多的新元素————上溢 (overflow)。
  • 上溢是由于插入操作远多于删除操作造成的
  • 实际规模与其内部数组容量的比值(即_size/_capacity)
    • 亦称作装填因子 (load factor) + 是衡量空间利用率的重要指标

• 如何才能保证向量的装填因子既不致于超过1, 也不致于太接近于0？——需要改用动态空间管理策略

动态空间管理

• 导致低效率的另一情况是，向量的实际规模可能远远小于内部数组的容量。装填因子低于某一阈值时，称数组发生了下溢 (underflow)。 尽管下溢不属于必须解决的问题，但在格外关注空间利用率的场合，发生下溢时也有必要适当缩减内部数组容量。代码 2.5 给出了一个动态缩容 shrink()算法。

常规向量

• 既可以通过下标访问元素，比如数组形式 (形如“A[i]“)，也可沿用数组的访问方式

直接引用元素

1 template <typename T> T& Vector<T>::operator[](Rank r) const //重载下标操作符 2 { return _elem[r]; } // assert: 0 <= r < _size

置乱器

• 借助重载后的操作符“[]”返回的是数组元素的引用， 这就意味着它既可以取代get()操作 ,也可以取代操作
• 利用置乱算法可以在各元素等概率出现于每一位置

判等器和比较器

• 用来区别对待数值类型
• 本书将主要采用后一方式，为节省篇幅，这里只给出涉及到的比较和判等操作符，读者可以根据实际需要，参照给出的代码加以扩充。 在一些复杂的数据结构中,内部元素本身的类型可能就是指向其它对象的指针;而从外部更多关注的,则往往是其所指对象的大小。若不加处理而直接根据指针的数值(即被指对象的物理地址)进行比较,则所得结果将毫无意义。

无序查找

• 在无序向量中查找任意指定元素e时，因为没有更多的信息可以借助，故在最坏情况下 一 只有在访遍所有元素之后，才能得出查找结论；称为顺序查找。
• **查找接口find()：**返回最后一个元素 e 的位置
• 复杂度：最好情况仅需要 0(1) 时间，最坏情况下 O(n)

插入

• 整体实现的代码：

1 template <typename T> //将 作为秩为 元素插入 2 Rank Vector<T>::insert(Rank r，T const& e) { //assert: 0 <= r <= _size 3 expand(); //若有必要,扩容 4 for (inti = size; i > r; i--)_elem[i] = _elem[i - 1];//后继元素顺次后移个单元 5 _elem[r] = e;_size++; //置入新元素并更新容量 6 return r;//返同 7 }

• 时间主要消耗于后继元素的后移，线程正比于后缀的长度。故总体0（_size - r - 1)。

删除

• 两个接口：
  • (remove(lo, hi)用以删除区间[lo, hi)内的元素)
  • (remove(r)用以删除秩为r的单个元素)
• 代码: 同样, 向量中的元素可能不是程序语言直接支持的基本类型。 比如，可能是指向动态分配对象的指针，或引用。
• 需要根据具体的要求来定制策略。

无序去重

• 借助 remove 只能删除单个元素
• 算法自前向后逐一考查各元素 _elem[i]， 并通过调用 find()接口， 在其前缀中寻找与之雷问者 算法的正确性： 在 while 循环中，在当前元素 的前缀 _elem[0, i) 内，所有元素彼此互异