【免费】DSAinC++11-查找算法1资源-CSDN文库

需积分: 0 43 浏览量 2022-08-04 13:41:43 上传评论收藏 750KB PDF 举报

资源详情

资源评论

资源推荐

第11章查找算法

电子信息学院

王文伟 WangWenwei,Dr.‐Ing.

Tel:189‐71562600

Email:wwwang@aliyun.com

课程QQ群:珞珈EIS数据结构与算法

，

668792335

第11章查找算法

TableofContents

电子信息学院

本章介绍查找操作

的基本概念，讨论

若干种经典的查找

技术；此外还将讨

论各种查找算法所

适用的数据存储结

构，以及分析、比

较各算法的效率。

TableofContents

本

章

位

置

第1章绪论

第2章 C++编程基础

第3章遍历、迭代与递归

第4章字符串

第5章排序算法

第6章线性表

第7章栈与队列

第8章数组和广义表

第9章树和二叉树

第10章图

第11章查找算法

TableofContents

电子信息学院

11.0简介

11.1查找与查找表

11.2线性表的查找

11.3二叉查找树及其查找算法

12.4哈希查找

第11章查找算法

11.0Introduction

 search：查找操作是指在特定的数据集合中寻

找满足某种给定条件的数据元素的过程，按内

容寻找数据对象。查找是数据处理中经常使用

的一种重要运算，也是程序设计中的一项重要

的基本技术。生活中经常用到查找，如在字典

中查找单词，在电话簿中查找电话号码等。

 本章介绍“查找”相关的基本概念，讨论多种

经典查找技术，包括线性表的顺序、折半和分

块查找算法，二叉排序树的查找算法以及哈希

查找算法。

第11章查找算法

11.1查找与查找表

11.1.1查找操作相关基本概念

11.1.2C++内建数据结构中的查找操作

第11章查找算法

1.关键字、查找操作、查找表与查找结果



关键字：是数据元素类型中用于识别不同元素的某

个域（字段）。

能唯一地标识数据元素的关键字，称为“主关键字”。

若某关键字标识若干而不是唯一元素，称为 “次关键

字”。



查找:是在特定的数据结构中寻找满足某种给定条件

的数据元素的过程。一般是指根据给定的某个值，

在数据集合中找到其关键字等于给定值的数据元素

（或记录）。



查找表（searchtable）即被实施查找操作的数据集

合，是由同一类型的数据元素(或记录)构成的集合。

第11章查找算法

查找操作与查找结果



查找操作也可以说是按关键字的内容找到数据元

素。



若查找表中存在满足条件的数据元素（记录），

则称“查找成功”，查找结果：给出整个记录的

信息，或指示该记录在查找表中的位置；



否则称“查找不成功”，查找结果：给出“空记

录”或“空指针”。



对查找表经常进行的操作:

查询某个“特定的”数据元素是否在查找表中；

检索某个“特定的”数据元素的各种属性；

在查找表中插入一个数据元素；

从查找表中删去某个数据元素。

第11章查找算法

2.静态查找表与动态查找表

静态查找表（staticsearchtable）:

仅作查询和检索操作的查找表，不需要对查找

表进行插入、删除操作。例如，字典是一个静

态查找表。

动态查找表（dynamicsearchtable）：需要对

一个查找表进行插入、删除操作。有时在查询

之后，还需要将查询结果为“不在查找表中”

的元素插入到查找表中；或者，从查找表中删

除查询结果为“在查找表中”的数据元素。例

如，电话簿是一个动态查找表。

第11章查找算法

3.如何进行查找？(查找方法)



数据元素在查找表中所处的存储位置与它的内容无关，

那么按照内容查找某个数据时不得不进行一系列值的

比较操作。顺序查找是基本方法，要提高查找效率，

需要特定的查找方法。



查找方法一般因数据的逻辑结构及存储结构的不同而

变化。如果数据元素之间不存在明显的组织规律，则

不便于查找。为了提高查找的效率，需要在查找表

的元素之间人为地附加某种确定的关系，亦即改变查

找表的结构，如先将数据元素按关键字值的大小排序，

就可以实施高效的二分查找算法。

第11章查找算法

查找方法



查找表的规模也会影响查找方法的选择：

 数据量较小的线性表，可以采用顺序查找算法。例如个人电

话簿。

 数据量较大时，采用分块查找算法。例如在字典中查找单词。



顺序查找是在数据集合中查找满足特定条件的数据元

素的基本方法，要提高查找效率，可先将数据按一定

方式整理存储，如排序、分块索引等。所以完整的查

找技术包含存储（又称造表）和查找两个方面。总之，

要根据不同的条件选择合适的查找方法，以求快速高

效地得到查找结果。本章将讨论若干种经典的查找技

术。

第11章查找算法

4.查找算法的性能评价



查找的效率直接依赖于数据结构和查找算法。查找过

程中的基本运算是关键字的比较操作。



衡量查找算法效率的最主要标准是平均查找长度

（AverageSearchLength,ASL）。 ASL是指查找过程所

需进行的关键字比较次数的期望值。

ASL







是要查找的数据元素出现在位置i处的概率，c

是查

找相应数据元素需进行的关键字比较次数。考虑等概

率情况。查找成功和查找不成功的平均查找长度通常

不同，分别用ASL

成功

和ASL

不成功

表示。

第11章查找算法

11.1.2C++内建数据结构中的查找操作



数组和C++标准库的vector、list及map等集合类型支持

较为方便地实施查找，标准库中的algorithm模块包含

了高效、实用的查找算法实现。



一般意义下的查找指找到满足一定条件的元素。



algorithm模块提供多种重载(overloaded)形式的find( )

或find_if( )模板函数实现查找操作。

[first,last)

Iterator find(Iterator first, Iterator last, const T& k);

Iterator find_if(Iterator first, Iterator last,

Pred mat);

vector<int>v{1,2,3,4,5,6,7,8,9};

autore=find_if(begin(v),end(v),[](inti){returni%2==0;});

autos=find_if(begin(t),end(t),[](Student&x){returnx.id==9;});

function<bool(const T&)>

第11章查找算法

推荐设计index函数与其他语言的IndexOf方法一致



C#/Java的IndexOf方法实现查找操作，返回给定数

据在指定范围内首次出现的索引。

template <typename IIt, typename T>

int index(IIt first, IIt last, const T& k) {

// call <algorithm> std::find()

auto p = find(first, last, k);

if (p == last) {return -1; }

else{ return (int)(p - first);}

}

inti =index(begin(v),end(v),10);

第11章查找算法

二分查找binary_search函数



对于已按关键字值排序的集合，可用更高效的二分

查找技术：

bool binary_search(It

first,

last,

const

k);

在范围[first, last)中应用二分查找算法查找具有指定值k的

元素，如果找到，则返回 true；否则，返回 false。

{29365356707379799999} 50

r=‐3=>i=2

ar[~r - 1] < k < ar[~r]

int BinarySearch<T>(T[] ar, T k); C#/Java

返回给定数据k在数组ar指定范围内首次出现位置。如果找到k，则

返回其索引。如果找不到k，则返回一个负数r，它的反码 ~r =i=

-r-1 正好是将k插入数组ar并保持其排序的正确位置。

第11章查找算法

IEnumerable<Robot> qv =

from r in robots

where r.Name.Contains(textBox1.Text)

select r;

foreach(var r in qv) {

listBox1.Items.Add(“名字：”+ r.Name+

“ ID：”+ r.ID + " 智商：" + r.IQ);

}

C#语言集成了高级的LINQ查询模块

第11章查找算法

C++标准库中的关联容器map



关联容器是表示<键，值>对（Key-Value Pair）的容

器类，这些<键，值>对根据键的哈希码进行组织。提

供了从一组键到一组值的映射，键的作用类似于数组

中的下标，可以通过键来索引集合内的元素。通过键

来检索值的速度非常快，时间效率接近于O(1)。



在C#、Java和Python等编程语言中，map这种类型称为

字典Dictionary。

第11章查找算法

11.2线性表查找技术

11.2.1顺序查找

11.2.2折半查找

11.2.3分块查找

要根据不同的条件选择合

适的查找方法，以求快速

高效地得到查找结果。

顺序查找是在数据集合中查找满足特

定条件的数据元素的基本方法，针对

线性表的查找操作有三种基本方法：

顺序查找，二分查找和分块查找。

第11章查找算法

11.2.1顺序查找



顺序查找(sequential search)又称线性查找(linear

search)，是一种最基本的查找算法。对于给定

查找关键字值k，从线性表的指定位置开始，

依次与每个数据元素的关键字进行比较，直到

查找成功，或到达线性表的指定边界时仍没有

找到这样的数据元素，则查找不成功。

剩余11页未读，继续阅读

评论收藏

内容反馈

鸣泣的海猫

粉丝: 21
资源: 293

DSAinC++11-查找算法1

评论0

最新资源

DSAinC++11-查找算法1

评论0

DSAinPython:Python中数据结构和算法的不同实现以及一些现实生活中的应用程序项目

dsa-in-cpp：C ++中的数据结构和算法问题的实现

DSAinC++5-排序算法1

DSAinC++10-图1

DSAinC++1-绪论1

DSAinC++6-线性表1

DSAinC++2-C++编程基础1

DSAinC++9-树与二叉树1

DSAinC++7-栈与队列1

DSAinC++3-遍历迭代与递归1

DSAinC++8-数组与广义表1

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

禅道项目管理系统身份认证绕过漏洞(QVD-2024-15263)POC

安全认证cisp教材全套

STM32F103C8T6核心板-电路原理图1.PDF

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

goby红队&社区版-win-64-2.4.7

软件工程导论(第六版)课后习题答案1

全面的安全基线核查清单

OpenVAS离线资源

CISP、NISP二级、CISE题库最新版（2024年1月更新）

2023年最全最精简wifi密码字典(2.6G)

hackbar2.1.3-master安装包

最新资源