【数据结构(邓俊辉)学习笔记】向量03——常规向量

文章目录

  • 0.概述
  • 1.元素访问
  • 2.置乱器
  • 3.判等器与比较器
  • 4.无序查找
    • 4.1 判等器
    • 4.2 顺序查找
    • 4.3 实现
    • 4.4 复杂度
  • 5. 插入
    • 5.1 算法实现
    • 5.2 复杂度分析
  • 6. 删除
    • 6.1 区间删除
    • 6.2 单元删除
    • 6.3 复杂度
  • 7. 唯一化
    • 7.1 实现
    • 7.2 正确性
    • 7.3 复杂度
  • 8. 遍历
    • 8.1 实现
    • 8.2 复杂度
  • 9. 总结

0.概述

记录向量的元素访问、插入、区间删除、单元素删除、查找、唯一化、遍历算法。

1.元素访问

重载操作符"[]",使元素访问更加便捷。
在这里插入图片描述

template <typename T> T & Vector<T>::operator[] ( Rank r ) //重载下标操作符
{ return _elem[r]; } // assert: 0 <= r < _sizetemplate <typename T> const T & Vector<T>::operator[] ( Rank r ) const //仅限于做右值
{ return _elem[r]; } // assert: 0 <= r < _size

经重载后操作符“[]”返回的是对数组元素的引用,这就意味着它既可以取代get()操作(通常作为赋值表达式的右值),也可以取代set()操作(通常作为左值)。

2.置乱器

目标:借助操作符 “[]” 随机置乱向量,使各元素等概率出现于各位置。
策略:自后向前,依次将各元素与随机选取的某一前驱(含自身)做交换

template <typename T> void permute ( Vector<T>& V ) { //随机置乱向量,使各元素等概率出现于各位置for ( int i = V.size(); i > 0; i-- ) //自后向前swap ( V[i - 1], V[rand() % i] ); //V[i - 1]与V[0, i)中某一随机元素交换
}

从待置乱区间的末元素开始,逆序地向前逐一处理各元素。
在这里插入图片描述
注意,这里的交换操作swap(),隐含了三次基于重载操作符“[]”的赋值。

  • 通过反复调用 permute()算法,可以生成向量 V[0, n)的所有 n!种排列。
  • 由该算法生成的排列中,各元素处于任一位置的概率均为 1/n
  • 该算法生成各排列的概率均为 1/n!

3.判等器与比较器

算法思想:

  • 可比较或可比对的任何数据类型,而不必关心如何定义以及判定其大小或相等关系。
  • 将比对和比较操作的具体实现剥离出来,直接讨论算法流程本身。
  • 在定义对应的数据类型时,通过重载"<“和”=="之类的操作符,给出大小和相等关系的具体定义及其判别方法。
template <typename T> static bool lt ( T* a, T* b ) { return lt ( *a, *b ); } //less than
template <typename T> static bool lt ( T& a, T& b ) { return a < b; } //less than
template <typename T> static bool eq ( T* a, T* b ) { return eq ( *a, *b ); } //equal
template <typename T> static bool eq ( T& a, T& b ) { return a == b; } //equal

在一些复杂的数据结构中,内部元素本身的类型可能就是指向其它对象的指针;而从外部更多关注的,则往往是其所指对象的大小。若不加处理而直接根据指针的数值(即被指对象的物理地址)进行比较,则所得结果将毫无意义。

4.无序查找

4.1 判等器

Vector::find(e)接口,功能语义为“查找与数据对象e相等的元素”。这同时也暗示着,向量元素可通过相互比对判等,但未必支持比较的向量,称作无序向量(unsorted vector)

4.2 顺序查找

在这里插入图片描述
从末元素起自后向前,逐一取出各个元素并与目标元素e进行比对,直至发现与之相等者(查找成功),或者直至检查过所有元素之后仍未找到相等者(查找失败)。这种依次逐个比对的查找方式,称作顺序查找

4.3 实现

template <typename T> //在无序向量中顺序查找e:成功则返回最靠后的出现位置,否则返回lo-1
Rank Vector<T>::find ( T const& e, Rank lo, Rank hi ) const { //0 <= lo < hi <= _sizewhile ( ( lo < hi-- ) && ( e != _elem[hi] ) ); //从后向前,顺序查找return hi; //若hi < lo,则意味着失败;否则hi即命中元素的秩
}

细节:

  • 当同时有多个命中元素时,统一约定返回其中秩最大者
  • while循环的控制逻辑由两部分组成,首先判断是否已抵达lo,再判断当前元素与目标元素是否相等。得益于C/C++语言中逻辑表达式的短路求值特性,在前一判断非真后循环会立即终止,而不致因试图引用已越界的秩(-1)而出错。

4.4 复杂度

最坏情况 查找终止于首元素_elem[lo],运行时间为O(hi - lo) = O(n)。
最好情况 查找命中于末元素_elem[hi - 1],仅需O(1)时间。
对于规模相同、内部组成不同的输入,渐进运行时间却有本质区别,故此类算法也称作输入敏感的算法

5. 插入

5.1 算法实现

算法思想:插入之前必须首先调用expand()算法,核对是否即将溢出。

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

在这里插入图片描述
为保证数组元素物理地址连续的特性,随后需要将后缀_elem[r, _size)(如果非空)整体后移一个单元(图©)。这些后继元素自后向前的搬迁次序不能颠倒,否则会因元素被覆盖而造成数据丢失。在单元_elem[r]腾出之后,方可将待插入对象e置入其中(图(d))。

5.2 复杂度分析

时间主要消耗于后继元素的后移,线性正比于后缀的长度,故总体为O(_size - r + 1)。
r取最大值_size时为最好情况,只需O(1)时间;r取最小值0时为最坏情况,需要O(_size)时间。

若插入位置等概率分布,则平均运行时间为O(_size) = O(n)

运行时间主要来自于后继元素顺次后移的操作。因此对于每个插入位置而言,对应的移动操作次数恰好等于其后继元素(包含自身)的数目。不难看出它们也构成一个等差数列(数学期望O( n 2 n^2 n2) m为后继元素数目),故在等概率的假设条件下,其均值(数学期望)应渐进地与其中的最高项同阶,为O(n)。

6. 删除

应将单元素删除视作区间删除的特例,并基于后者来实现前者

6.1 区间删除

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

在这里插入图片描述
设[lo, hi)为向量(图(a))的合法区间(图(b)),则其后缀[hi, n)需整体前移hi - lo个单元(图©)。与插入算法同理,后继元素自前向后的移动次序也不能颠倒。

  • 若以自后向前得次序逐个前移后继元素,位置靠前的元素,可能被位置靠后(优先移动)的元素覆盖,从而造成数据的丢失。
    在这里插入图片描述
    V.remove(0, 2)以删除其中的前两个元素,可见,原数据元素V[2] = 2并未顺利转移至输出向量中的V[0],即出现数据的丢失现象。

6.2 单元删除

重载即可实现如下另一同名接口remove®。

template <typename T> T Vector<T>::remove( Rank r ) { //删除向量中秩为r的元素,0 <= r < sizeT e = _elem[r]; //备份被删除元素remove( r, r + 1 ); //调用区间删除算法,等效于对区间[r, r + 1)的删除return e; //返回被删除元素
}

6.3 复杂度

remove(lo, hi)的计算成本,主要消耗于后续元素的前移,线性正比于后缀的长度,总体不过O(m + 1) = O(_size - hi + 1)。
结论

区间删除操作所需的时间,应该仅取决于后继元素的数目,而与被删除区间本身的宽度无关。

被删除元素在向量中的位置越靠后(前)所需时间越短(长),最好为O(1),最坏为O(n) = O(_size)。

7. 唯一化

所谓向量的唯一化处理,就是剔除其中的重复元素。

7.1 实现

template <typename T> Rank Vector<T>::dedup() { //删除无序向量中重复元素(高效版)Rank oldSize = _size; //记录原规模for ( Rank i = 1; i < _size; ) //自前向后逐个考查_elem[1,_size)if ( -1 == find(_elem[i], 0, i) ) //在前缀[0,i)中寻找与[i]雷同者(至多一个),O(i)i++; //若无雷同,则继续考查其后继elseremove(i); //否则删除[i],O(_size-i)return oldSize - _size; //被删除元素总数
}

该算法自前向后逐一考查各元素_elem[i],并通过调用find()接口,在其前缀中寻找与之雷同者。若找到,则随即删除;否则,转而考查当前元素的后继。

7.2 正确性

在while循环中,在当前元素的前缀_elem[0, i)内,所有元素彼此互异
在这里插入图片描述

7.3 复杂度

随着循环的不断进行,当前元素的后继持续地严格减少

这里所需的时间,主要消耗于find()和remove()两个接口。

find()时间应线性正比于查找区间的宽度,即前驱的总数;
remove()时间应线性正比于后继的总数。因此,每步迭代所需时间为O(n),总体复杂度应为O( n 2 n^2 n2)。

8. 遍历

8.1 实现

算法思想:

  1. 借助函数指针*visit()指定某一函数,该函数只有一个参数,其类型为对向量元素的引用,故通过该函数即可直接访问或修改向量元素。
  2. 也可以函数对象的形式,指定具体的遍历操作。这类对象的操作符“()”经重载之后,在形式上等效于一个函数接口,故此得名。
    在这里插入图片描述
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> void increase ( Vector<T> & V ) //统一递增向量中的各元素
{  V.traverse ( Increase<T>() );  } //以Increase<T>()为基本操作进行遍历

8.2 复杂度

遍历操作本身只包含一层线性的循环迭代,故除了向量规模的因素之外,遍历所需时间应线性正比于所统一指定的基本操作所需的时间。故这一遍历的总体时间复杂度为O(n)。

9. 总结

  1. 置乱算法 permute() 从待置乱区间的末元素开始,逆序地向前逐一处理各元素。时间复杂度为O(n)
  2. 顺序查找算法 find() 从末元素起自后向前,逐一取出各个元素并与目标元素进行比对,时间复杂度应线性正比于查找区间的宽度,即前驱的总数。
  3. 插入算法insert() ,时间复杂度线性正比于后缀的长度为
  4. 删除算法remove() ,时间复杂度应该仅取决于后继元素的数目
  5. 唯一化算法deduplicate(),主要消耗于find()和remove()两个接口,时间复杂度O( n 2 n^2 n2)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2980735.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【树莓派学习】开发环境配置

【树莓派学习】开发环境配置 ​ Raspberry Pi OS作为基于Linux的系统&#xff0c;其默认网络配置在国内的网络环境下容易出现访问慢甚至无法连接等问题&#xff0c;不便于我们的学习&#xff0c;同时&#xff0c;树莓派上C/C的使用需要单独安装WiringPi。本文主要介绍如何更改…

探索开源的容器引擎--------------Docker容器操作

目录 一、Docker 容器操作 1.1容器创建 1.2查看容器的运行状态 1.3启动容器 1.4创建并启动容器 1.4.1当利用 docker run 来创建容器时&#xff0c; Docker 在后台的标准运行过程是&#xff1a; 1.4.2在后台持续运行 docker run 创建的容器 1.4.3创建容器并持续运行容器…

PYTHON用[邻接列表]及[邻接矩阵]来存储无向图

# 图可以根据边的性质进行分类&#xff1a;# 有向图&#xff08;Directed Graph&#xff09;&#xff1a;在有向图中&#xff0c;边是有方向性的&#xff0c;从一个节点指向另一个节点。这意味着从节点 A 到节点 B 的边与从节点 B 到节点 A 的边可以是不同的&#xff0c;或者根…

parallels desktop19出来了吗?2024最新版本有哪些新功能

Parallels Desktop 19已经发布。以下是关于Parallels Desktop 19的相关信息&#xff1a; 发布时间&#xff1a;Parallels Desktop 19是在近期发布的一款虚拟机软件&#xff0c;具体发布时间为2023年下半年。 功能特点&#xff1a; 针对搭载苹果芯片的Mac进行了优化&#xff0c…

微信小程序webview和小程序通讯

1.背景介绍 1.1需要在小程序嵌入vr页面&#xff0c;同时在vr页面添加操作按钮与小程序进行通信交互 1.2 开发工具&#xff1a;uniapp开发小程序 1.3原型图 功能&#xff1a;.点击体验官带看跳转小程序的体验官带看页面 功能&#xff1a;点击立即咨询唤起小程序弹窗打电话 2.…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别 一、简单介绍 二、简单进行车牌检测和识别实现原理 …

Jmeter之Beanshell详解

一、 Beanshell概念 Beanshell: BeanShell是一种完全符合Java语法规范的脚本语言,并且又拥有自己的一些语法和方法;BeanShell是一种松散类型的脚本语言(这点和JS类似);BeanShell是用Java写成的,一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器,具有对象脚本语言特性…

[Algorithm][前缀和][模板 一维前缀和][模板 二维前缀和][寻找数组中心下标][除自身以外数组的乘积] + 前缀和原理 + 前缀和模板

目录 0.原理讲解1.[模板]一维前缀和1.题目链接2.模板代码实现 2.[模板]二维前缀和1.题目链接2.算法原理讲解3.模板代码实现 3.寻找数组的中心下标1.题目链接2.算法原理详解3.代码实现 4.除自身以外数组的乘积1.题目链接2.算法原理详解3.代码实现 0.原理讲解 前缀和&#xff1a;…

Esp8266 - USB开关分享(开源)

文章目录 简介推广自己gitee项目地址:嘉立创项目地址&#xff1a;联系我们 功能演示视频原理图嘉立创PCB开源地址原理图PCB预览 固件烧录代码编译烧录1. 软件和驱动安装2. 代码编译1. 安装所需要的依赖库文件2. 下载源代码3. 烧录代码 使用说明1. 设备配网2. 打开设备操作页面3…

【深度学习】YOLOv5,烟雾和火焰,目标检测,防火检测,森林火焰检测

文章目录 数据收集和数据标注查看标注好的数据的脚本下载yolov5创建 dataset.yaml训练参数开始训练yolov5n训练训练后的权重下载gradio部署 数据收集和数据标注 搜集数据集2w张。 pip install labelme labelme 然后标注矩形框和类别。 下载数据请看这里&#xff1a; https:…

【SpringCloud】Consul-服务注册中心及配置中心快速入门

【SpringCloud】Consul-服务注册中心及配置中心快速入门 文章目录 【SpringCloud】Consul-服务注册中心及配置中心快速入门1. 下载安装及启动2. 服务注册2.1 引入依赖2.2 yml配置2.3 启动类配置2.4 测试 3. 服务配置3.1 引入依赖3.2 yml配置3.3 创建配置文件3.4 动态刷新配置3.…

2024深圳杯(东三省)数学建模挑战赛D题:音板的振动模态分析与参数识别思路代码成品论文分析

​ 更新完整代码和成品完整论文 《2024深圳杯&东三省数学建模思路代码成品论文》↓↓↓ https://www.yuque.com/u42168770/qv6z0d/zx70edxvbv7rheu7?singleDoc# 问题重述 深圳杯&#xff08;东三省&#xff09;数学建模挑战赛2024D题&#xff1a;音板的振动模态分析与…

Docker常用命令(镜像、容器、网络)

一、镜像 1.1 存出镜像 将镜像保存成为本地文件 格式&#xff1a;docker save -o 存储文件名 存储的镜像docker save -o nginx nginx:latest 1.2 载入镜像 将镜像文件导入到镜像库中 格式&#xff1a;docker load < 存出的文件或docker load -i 存出的文件…

WordPress自动采集发布AutoPostPro汉化版插件

WP-AutoPostPro 是一款极为出色的WordPress自动采集发布插件&#xff0c;其显著优势在于能够从任何网站抓取内容并自动将其发布到你的WordPress网站上。它实现了对任何网页内容的自动采集和发布&#xff0c;整个采集过程完全自动化&#xff0c;无需手动操作。 项 目 地 址 &…

Docker学习(二十五)构建 Arthas 基础镜像

目录 一、简介二、构建基础镜像2.1 下载 Arthas2.2 编写 Dockerfile2.3 构建镜像2.4 创建容器2.5 测试 一、简介 Arthas 是一款由 阿里巴巴 开发的 线上监控诊断工具。通过全局视角实时查看应用负载、内存、GC、线程等信息&#xff0c;能在不修改代码的情况下&#xff0c;对业…

【结构型模型】享元模式

一、享元模式概述 享元模式定义&#xff1a;又叫蝇量模式&#xff0c;运用共享技术有效地支持大量细粒度对象的复用。系统只使用少量的对象&#xff0c;而这些对象都很相似&#xff0c;状态变化很小&#xff0c;可以实现对象的多次复用。由于享元模式要求能够共享的对象必须是细…

Microsoft SPY++ 使用教程及实操

Spy介绍 Spy (SPYXX.EXE) 是一个基于 Win32 的实用工具&#xff0c;提供系统进程、线程、窗口和窗口消息的图形视图。 Spy 有两个版本 第一个版本&#xff0c;名为 Spy (spyxx.exe)&#xff0c;用于显示发送到在 32 位进程中运行的窗口的消息。 例如&#xff0c;在 32 位进程…

立即刷新导致请求的response没有来得及加载造成的this request has no response data available

1、前端递归调用后端接口 const startProgress () > {timer.value setInterval(() > {if (progress.value < 100) {time.value--;progress.value Math.ceil(100 / wait_time.value);} else {clearInterval(timer.value);progress.value 0;timer.value null;time.…

设计模式-00 设计模式简介之几大原则

设计模式-00 设计模式简介之几大原则 本专栏主要分析自己学习设计模式相关的浅解&#xff0c;并运用modern cpp 来是实现&#xff0c;描述相关设计模式。 通过编写代码&#xff0c;深入理解设计模式精髓&#xff0c;并且很好的帮助自己掌握设计模式&#xff0c;顺便巩固自己的c…

【UE5.1 C++】VS2022下载安装

目录 步骤 一、Visual Studio下载安装 二、Visual Studio Integration Tool插件安装 先看一下UE和VS的兼容性 &#xff08;虚幻5&#xff1a;为虚幻引擎C项目设置Visual Studio开发环境&#xff09; &#xff08;虚幻4&#xff1a;设置虚幻引擎的Visual Studio&#xff0…