向量——dsa第二章

向量——dsa第二章

• 抽象数据类型
• • 接口与实现
  • 从数组到向量
  • • 数组vs向量
    • 向量的操作
  • 模板类
• 可扩充向量
• • 算法
  • 分摊
  • • 容量递增策略
    • 容量加倍策略
    • 平均分析vs分摊分析
• 无序向量
• • 基本操作
  • 查找
  • • 词条模版类entry
  • 去重
  • 遍历
• 有序向量
• • 唯一化
  • 二分查找A
  • Fibonacci查找
  • 通用策略
  • 二分查找B
  • 二分查找C
  • 插值查找
• 向量
• • 起泡排序
  • 归并排序
  • • 分而治之
    • 二路归并
    • 复杂度
• 位图
• • 数据结构
  • 典型应用
  • 快速初始化
• Reference

抽象数据类型

接口与实现

1. 抽象数据类型（ADT）：

• 定义：ADT是数据模型加上在该模型上定义的一组操作。
  抽象定义：ADT是一种定义，它描述了数据的外部逻辑特性，但不涉及具体的实现细节。
• 特点：ADT不考虑时间复杂度，即它不关心操作的效率问题，只关心操作的逻辑和语义。
• 存储方式：ADT不涉及数据的具体存储方式，它只定义了数据应该如何被操作。

2. 数据结构：

• 定义：数据结构是基于某种特定语言实现ADT的一整套算法。
• 具体实现：数据结构是ADT的具体实现，它涉及到数据的内部表示和实现方式。
• 特点：数据结构与复杂度密切相关，它需要考虑数据的具体存储机制，以及这些机制如何影响算法的效率。
• 多种实现：对于同一个ADT，可以有多种不同的数据结构实现。

3. 应用（Application）：

应用是使用ADT和数据结构的最终产品，它直接面向用户。

4. 接口（Interface）：

接口是ADT的表现形式，它定义了用户如何与数据结构进行交互

5. 实现（Implementation）：

实现是数据结构的具体代码，它包含了数据的存储和操作的具体细节

重要性

• ADT在数据结构的具体实现与实际应用之间提供了统一的规范，使得开发过程可以更加模块化和高效。
• 通过ADT，每种操作接口只需统一实现一次，这有助于缩短代码篇幅，增强安全性，并提高软件的复用度。

从数组到向量

数组vs向量

1. 数组的基本概念：

在C/C++中，数组元素与编号一一对应，例如：A[0], A[1], A[2], …, A[n-1]。
数组元素可以通过编号直接访问，这种特性使得数组也被称为线性数组（linear array）。

2. 数组的物理存储：

数组在内存中是连续存储的。如果每个元素占用的空间量为s（包括填充，padding），那么数组中第i个元素A[i]的物理地址可以通过公式 A + i * s 来计算，其中A是数组的起始地址。

3. 数组的访问方式：

数组支持循秩访问，即通过索引直接访问数组中的元素。这种访问方式是高效的，因为可以通过简单的算术运算直接计算出元素的内存地址

4.向量的定义：

向量是数组概念的抽象和泛化，它由一组元素按照线性次序组成。
向量中的每个元素都有一个唯一的秩（rank），这个秩在[0, n)范围内，其中n是向量中元素的数量。

5. 向量的表示：

使用A[]表示向量，其中0, 1, 2, 3, …, k, k+1, …, n-1是元素的秩。
向量的秩使用unsigned int类型表示，这是一种无符号整数类型，用于按秩访问元素。

6. 向量的优点：

向量提供了一种简化、统一且安全的方式来操作和管理元素。
与数组相比，向量的操作和维护更加灵活和方便。

7. 元素类型的灵活性：

向量的元素类型可以灵活选择，这使得向量可以用于构建复杂的数据结构。

// 定义PFCTree为字符类型的二叉树
using PFCTree = BinTree<char>;

// 定义PFCForest为存储PFCTree指针的向量
using PFCForest = Vector<PFCTree*>;

向量的操作

size() / empty()：

• 功能：报告向量中元素的总数或判定向量是否为空。
• 适用对象：向量。

get( r ) / put(r, e)：

• 功能：获取向量中秩（rank）为r的元素，或用e替换秩为r的元素的数值。
• 适用对象：向量。

insert(r, e) / insert(e)：

• 功能：将元素e作为秩为r的元素插入向量，或将e作为最后一个元素插入。
• 适用对象：向量。

remove(lo, hi) / remove®：

• 功能：删除向量中秩为r的元素或区间[lo, hi)内的元素。
• 适用对象：向量。

disordered() / sort(lo, hi) / unsort(lo, hi)：

• 功能：检测向量是否整体有序 / 对向量整体进行排序 / 将向量整体置乱。
• 适用对象：向量。

find(e, lo, hi) / search(e, lo, hi)：

• 功能：在指定区间[lo, hi)内查找目标元素e。
• 适用对象：向量或有序向量。

dedup() / uniquify()：

• 功能：剔除向量中相等的元素，使得向量中的元素唯一。
• 适用对象：向量或有序向量。

traverse(visit())：

• 功能：遍历向量，对所有元素统一执行visit()函数。
• 适用对象：向量。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v; // an empty vector of integers

    vector<int> s(289, 7); // { 7, 7, 7, ..., 7 }

    s.insert(s.begin() + 7, 2024); // { 7, 7, 7, 7, 7, 7, 7, 2024, 7, 7, ..., 7 }

    s.erase(s.end() - 280, s.end()); // { 7, 7, 7, 7, 7, 7, 7, 2024, 7, 7, ..., 7 }

    for (int i = 0; i < s.size(); i++)
        cout << s[i] << endl;

    return 0;
}

模板类

1. 结构

向量类的结构，包括私有数据成员（_elem, _size, _capacity）和公有接口（构造函数、析构函数、insert, remove, traverse）

1. template <typename T> class Vector：
   定义了一个名为Vector的模板类，其中T是模板参数，代表向量中元素的类型。

2. 私有成员：
   private: Rank _size;：表示向量中元素的数量，即当前向量的规模。
   Rank _capacity;：表示向量的最大容量，即向量在不重新分配内存的情况下能够存储的元素数量。
   T* _elem;：指向向量数据区的指针，存储向量中的元素。

3. 保护成员：
   protected:：
   保护成员可以被派生类访问，这里可能包含一些内部函数，用于实现向量类的核心功能。

4. 公有接口：
   public:：
   公有接口是类对外提供的操作，包括：

   • 构造函数：用于初始化向量对象。
   • 析构函数：用于销毁向量对象，释放分配的内存。
   • 只读接口：允许访问向量中的元素，但不能修改它们。
   • 可写接口：允许修改向量中的元素。
   • 遍历接口：允许对向量中的元素进行迭代访问。

2. 构造函数&析构函数

#define DEFAULT_CAPACITY 3 // 默认初始容量（实际应用中可设置为更大）

// 默认构造函数
Vector(int c = DEFAULT_CAPACITY) {
    _elem = new T[_capacity = c]; // 分配内存并设置容量
    _size = 0; // 初始化规模为0
}

// 数组区间复制构造函数
Vector(T const * A, Rank lo, Rank hi) {
    copyFrom(A, lo, hi); // 调用copyFrom函数执行复制
}

// 向量区间复制构造函数
Vector(Vector<T> const & V, Rank lo, Rank hi) {
    copyFrom(V._elem, lo, hi); // 调用copyFrom函数执行复制
}

// 向量整体复制构造函数
Vector(Vector<T> const & V) {
    copyFrom(V._elem, 0, V._size); // 调用copyFrom函数复制整个向量
}

// 析构函数，用于释放内部空间
~Vector() {
    delete[] _elem; // 释放分配的内存
}

3. copyfrom函数

template <typename T> // T为基本类型，或已重载赋值操作符'='
void Vector<T>::copyFrom(T const * A, Rank lo, Rank hi) { // A中元素不致被篡改
    // 分配空间，容量至少为默认容量或所需容量的两倍
    _elem = new T[_capacity = max(DEFAULT_CAPACITY, (hi - lo) * 2)];
    // 初始化向量规模为0
    _size = 0;
    // 复制A[lo, hi)内的元素至_elem[0, hi-lo)
    for (; lo < hi; _size++, lo++) {
        _elem[_size] = A[lo]; // 逐一复制元素
    }
    // 时间复杂度为O(n)，其中n为复制的元素数量
}

O(n)

可扩充向量

算法

1. 静态空间管理

内部数组_elem[]的容量_capacity是固定的。

问题：

• 上溢（Overflow）：当_elem[]不足以存放所有元素时，即使系统有足够的空间，也会导致上溢。
• 下溢（Underflow）：当_elem[]中的元素很少时，会浪费空间。
• 装填因子（Load Factor）：λ = _size / _capacity，理想情况下应远小于50%。
• 在一般的应用环境中，难以准确预测空间的需求量。
  2. 动态空间管理

向量在即将上溢时，适当扩大内部数组的容量。

过程：

• 向量即将上溢。
• 向量已满。
• 分配新的更大的空间。
• 将旧数据复制到新空间。
• 释放旧空间。

template <typename T>
void Vector<T>::expand() {
    if (_size < _capacity) return; // 无需扩容
    T* oldElem = _elem; // 记下原数据区
    copyFrom(oldElem, 0, _capacity); // 容量加倍后，复制原数据
    delete[] oldElem; // 释放原空间
}

分摊

容量递增策略

1. 策略描述：在向量空间不足时，通过增加一个固定的INCREMENT来扩容。
2. 最坏情况：从初始容量0开始，连续插入n = m * I个元素，其中I是INCREMENT的值。
3. 扩容次数：在第1, I+1, 2I+1, 3I+1, 4I+1, …次插入时，都需要扩容。
4. 时间成本：各次扩容的时间成本依次为0, I, 2I, 3I, 4I, …，形成算术级数。
5. 总体耗时：O(n^2)，每次insert/remove操作的分摊成本为O(n)。

容量加倍策略

1. 策略描述：在向量空间不足时，将容量加倍来扩容。
2. 最坏情况：从初始容量1开始，连续插入n = 2^m个元素。
3. 扩容次数：在第1, 2, 4, 8, 16, …次插入时，都需要扩容。
4. 时间成本：各次扩容的时间成本依次为1, 2, 4, 8, 16, …，2^m,形成几何级数。2^m=n
5. 总体耗时：O(n)，每次insert/remove操作的分摊成本为O(1)。

平均分析vs分摊分析

• 平均分析：
  根据操作出现概率分布，加权平均成本。
  作为独立事件考查，忽略操作间的相关性和连贯性。
  可能无法准确评判数据结构和算法的真实性能。
• 分摊分析：
  考虑连续多次操作的总体成本，分摊至单次操作。
  从实际角度整体考量操作序列，更真实地刻画操作序列。
  更精准地评判数据结构和算法的真实性能。

无序向量

基本操作

1. 元素访问

• 目的：提供一种更便捷和直观的方式来访问向量中的元素，类似于数组的访问方式。
• 实现：通过重载下标操作符[]来实现。这包括两个重载：
  T& operator[](Rank r)：可作为左值，允许修改向量中的元素。
  const T& operator[](Rank r) const：仅限于右值，用于获取向量中的元素而不修改它。
• 注意：这里采用了简易的方式处理意外和错误，例如，入口参数约定为0 <= r < _size。实际应用中，应采用更为严格的方式。

template <typename T>
class Vector {
public:
    // 可作为左值，允许修改向量中的元素
    T& operator[](Rank r) { return _elem[r]; }

    // 仅限于右值，用于获取向量中的元素而不修改它
    const T& operator[](Rank r) const { return _elem[r]; }
};

2. 插入操作

• 目的：在向量的指定位置插入一个新元素。
• 实现：insert(Rank r, T const& e)函数首先检查是否需要扩容，然后从后向前移动元素以为新元素腾出空间，最后将新元素插入并返回新元素的位置。

template <typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
    if (_size == _capacity) {
        expand(); // 如必要，先扩容
    }
    for (Rank i = _size; r < i; --i) {
        _elem[i] = _elem[i - 1]; // 后继元素顺次后移一个单元
    }
    _elem[r] = e; _size++; return r; // 置入新元素，更新容量，返回秩
}

3. 区间删除

• 目的：从向量中删除指定区间的元素。
• 实现：remove(Rank lo, Rank hi)函数首先检查区间是否退化（即lo == hi），然后通过前移操作将被删除区间后的元素移动到前面，更新规模，并在必要时调用shrink()函数来缩小容量。

template <typename T>
Rank Vector<T>::remove(Rank lo, Rank hi) {
    if (lo == hi) return 0; // 出于效率考虑，单独处理退化情况
    while (hi < _size) _elem[lo++] = _elem[hi++]; // 后缀[hi,n)前移
    _size = lo; shrink(); // 更新规模，如必要，则缩容
    return hi - lo; // 返回被删除元素的数目
}

4. 单元素删除

• 目的：删除向量中的单个元素。
• 实现：remove(Rank r)函数通过备份要删除的元素，然后调用区间删除函数remove(r, r+1)来删除单个元素，并返回被删除的元素。
• 将单元素删除视为区间删除的特例，if反过来，通过反复调用remove( r )来实现remove(lo, hi)的复杂度，可能导致总体O(n^2)的复杂度。

template <typename T>
T Vector<T>::remove(Rank r) {
    T e = _elem[r]; // 备份
    remove(r, r+1); // “区间” 删除
    return e; // 返回被删除元素
}

查找

template <typename T> // 0 <= lo < hi <= size
Rank Vector<T>::find( T const & e, Rank lo, Rank hi ) const { // O(hi-lo)
    while ( (lo < hi--) && (e != _elem[hi]) ); // 从后向前，顺序查找
    return hi; // 最靠后的命中者，或lo-1示意失败（lo == 0时呢？）
}

最好情况下时间复杂度为 O(1)，最坏情况下为 O(n)。

词条模版类entry

template <typename K, typename V> struct Entry { // 词条模板类
    K key; V value; // 关键码、数值

    // 默认构造函数，使用默认初始化方式初始化 key 和 value
    Entry(K k = K(), V v = V()) : key(k), value(v) {}

    // 克隆构造函数，通过另一个 Entry 实例来初始化当前实例
    Entry(Entry<K, V> const& e) : key(e.key), value(e.value) {}

    // 重载操作符 '=='，用于比较两个 Entry 实例的关键码是否相等
    bool operator==(Entry<K, V> const& e) { return key == e.key; }

    // 重载操作符 '!='，用于比较两个 Entry 实例的关键码是否不等
    bool operator!=(Entry<K, V> const& e) { return key != e.key; }

    // 重载操作符 '<'，用于比较两个 Entry 实例的关键码大小
    bool operator<(Entry<K, V> const& e) { return key < e.key; }

    // 重载操作符 '>'，用于比较两个 Entry 实例的关键码大小
    bool operator>(Entry<K, V> const& e) { return key > e.key; }
};

去重

template<typename T>
Rank Vector<T>::dedup() { // 剔除相等的元素
    Rank oldSize = _size; // 保存原始大小

    for (Rank i = 1; i < _size; ) { // 遍历向量中的每个元素
        if (-1 == find(_elem[i], 0, i)) // 检查当前元素是否之前已存在
            i++; // 如果已存在，跳过当前元素
        else
            remove(i); // 否则，删除当前元素
    }

    return oldSize - _size; // 返回删除的元素数量
}

• 该函数的时间复杂度为O(n²)，因为在最坏情况下，每个元素都可能触发一次find()操作，而find()操作本身在最坏情况下需要O(n)时间。如果find()在最坏情况下每次都要遍历到当前索引，那么总的时间复杂度将是O(n²)。
• 每次find()操作不是最坏情况（即查找成功）时，remove()函数将被执行，这进一步确认了时间复杂度的分析。

遍历

目的：对向量中的每个元素执行统一的操作。

template <typename T>
void Vector<T>::traverse(void (* visit )(T &)) {
    for (Rank i = 0; i < _size; i++) {
        visit(_elem[i]);
    }
}

template <typename T> template <typename VST>
void Vector<T>::traverse(VST & visit) {
    for (Rank i = 0; i < _size; i++) {
        visit(_elem[i]);
    }
}

举例：所有元素均加一

template <typename T>
struct Increase { // 函数对象：通过重载操作符 "()" 实现
    virtual void operator()(T & e) { e++; } // 加一
};

template <typename T>
void increase(Vector<T> & V) {
    V.traverse(Increase<T>()); // 即可以之作为基本操作，遍历向量
}

有序向量

唯一化

1. 有序性的检查
   提供了一个 checkOrder 函数，它通过遍历向量来统计逆序对的数量，从而评估向量的有序程度。
   如果存在逆序对，函数会打印出逆序对的数量；如果没有，会打印 “Sorted”。

template<typename T>
void checkOrder(Vector<T>& V) {
    int unsorted = 0;
    V.traverse(CheckOrder<T>(unsorted, V[0]));
    if (0 < unsorted)
        printf("Unsorted with %d adjacent inversion(s)\n", unsorted);
    else
        printf("Sorted\n");
}

2. 勤奋的低效算法
   uniquify 的函数，用于从向量中移除重复元素，但这种方法效率较低。
   算法通过比较相邻元素来检查重复，并在发现重复时移除它们。这可能导致多次不必要的元素移动。
   这种方法的时间复杂度较高，因为它在每次迭代中都可能进行元素的移除操作。

template<typename T>
int Vector<T>::uniquify() {
    int oldSize = _size;
    int i = 1;
    while (i < _size) {
        if (_elem[i-1] == _elem[i]) {
            remove(i);
        } else {
            i++;
        }
    }
    return oldSize - _size;
}

3. 懒惰的高效算法
   Two-Pointer Technique
   更高效的 uniquify 算法，使用两个指针（i 和 j）来遍历向量。
   i 指针用于跟踪最后一个已知非重复元素的位置，而 j 指针用于检查当前元素是否与 i 位置的元素不同。
   如果不同，j 位置的元素会被复制到 i+1 的位置，并且 i 指针递增。这种方法减少了不必要的元素移动，提高了效率。

template<typename T>
int Vector<T>::uniquify() {
    Rank i = 0, j = 0;
    while (++j < _size) {
        if (_elem[i] != _elem[j]) {
            _elem[++i] = _elem[j];
        }
    }
    _size = ++i;
    shrink();
    return j - i;
}

二分查找A

统一接口
提供了一个 search 函数，它是查找算法的统一接口，可以等概率地随机选择二分查找算法或 Fibonacci 查找算法。

template <typename T>
Rank Vector<T>::search(T const& e, Rank lo, Rank hi) const {
    return (rand() % 2) ?
        binSearch(_elem, e, lo, hi) : // 二分查找算法
        fibSearch(_elem, e, lo, hi); // Fibonacci 查找算法
}

1. 有序向量中，每个元素都是轴点，用于分割查找区间。通过与轴点 x 的比较，可以将查找区间分为三部分：[lo, mi)、[mi] 和 (mi, hi)。根据目标元素 e 与轴点 x 的比较结果，可以确定下一步的查找区间。

2. 减而治之
   如果 e < x，则在左侧子区间 [lo, mi) 继续查找；如果 e > x，则在右侧子区间 (mi, hi) 继续查找；如果 e == x，则查找成功。
   如果轴点 mi 取作中点，每次比较后，查找区间将缩减一半。

3. 实现
   binSearch 函数通过循环，不断将查找区间折半，直到找到目标元素或区间为空。
   mi 是通过 lo 和 hi 计算得到的中点索引。
   如果找到目标元素，函数返回其索引；如果查找失败，返回 -1。

template <typename T>
static Rank binSearch(T * S, T const& e, Rank lo, Rank hi) {
    while (lo < hi) {
        Rank mi = (lo + hi) >> 1;
        if (e < S[mi]) hi = mi;
        else if (S[mi] < e) lo = mi + 1;
        else return mi;
    }
    return -1;
}

成功查找 / 失败查找。
成功查找的平均比较次数（ASL_succ）和失败查找的平均比较次数（ASL_fail）都接近于 O(log n)。

4. 关键字的比较次数与平均查找长度（Average Search Length, ASL）

   • 成功查找（ASL_succ）：从根节点到某个叶节点的路径长度，表示成功找到某个关键字所需的比较次数。
     ex：一个包含8个关键字（0到7）的有序序列的搜索树。每个关键字被搜索时，路径长度不同，例如搜索关键字3的路径长度为2（经过根节点和第二个分支），搜索关键字5的路径长度为3（经过根节点、第二个分支和第四个分支）。

   • 失败查找（ASL_fail）：如果查找的关键字不在序列中，那么最长的路径将结束于一个空子节点，表示查找失败。失败查找的路径长度取决于搜索树的最深路径。

   • 平均查找长度（ASL）：成功查找的平均查找长度是所有成功路径长度的平均值，失败查找的平均查找长度是所有失败路径长度的平均值。成功和失败查找的平均查找长度的公式：ASL succ=O(1.50⋅logn) 和 ASL fail=O(1.50⋅logn)，其中 n 是序列中元素的数量。

   ，二分查找的决策树并不是完全填充的，特别是在底部。因此，实际的平均比较次数会略高于完全填充树的理论值。这个额外的因子就是1.50（或者更精确地说，是
   

   标签：lo,元素,Rank,查找,hi,第二章,向量,dsa
   From： https://blog.csdn.net/yaoyc23/article/details/144760911