【数据结构周周练】025 查找算法详解及顺序查找算法实现

àì夳堔傛蜴生んèń 2021-06-11 15:13 436阅读 0赞

# 前言 #

从今天开始就给大家分享有关于查找的算法啦，查找是数据结构算法中比较重要的部分，我们在很多软件中都能接触到查找，包括我们从小查词典的过程，就是查找的过程，那个时候，我们有拼音查，有笔画查，偏旁部首查等等。那个时候或许我们并没有查找效率的概念，但是我们都会考虑到，怎样查找，我们查的最快。其实那个时候，分块查找以及如何提升查找效率的应用已经被我们所熟练掌握。

# 一、查找 #

## 1、什么是查找？ ##

在计算机科学中定义为：在一些（有序的 / 无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。查找的结果有两种，**查找失败**与**查找成功**。

## 2、查找表 ##

用于查找的数据的集合称为查找表，它由同类型属于元素组成。对于查找表一般有如下四种操作：

1.查询某特定元素是否在查找表中；

2.检索该特定元素的各种属性；

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

4.从查找表中删除某个数据元素。

## 3、静态查找表与动态查找表 ##

在查找过程中，如果我们只需要对查找表进行前两个操作，即查找某个特定元素是否存在于查找表中并检索其属性，我们称这种查找为**静态查找表**；如果我们除了查询操作，还需要进行剩余两个操作即插入或删除某个数据元素，我们称之为**动态查找表**。

适合静态查找表的查找方法有：顺序查找、折半查找、散列查找等。

适合动态查找表的查找方法有：二叉排序树的查找、散列查找等。除此之外，我们还会讲到二叉平衡树和B树，这两个都是二叉排序树的改进，也适合动态查找表。

## 4、关键字 ##

数据元素中**唯一标识**该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

例如，在一个班级中，有学生的学号，姓名，性别，座位号等；学生的学号和座位号是唯一确定的（不考虑换座位现象），即一个学号或者一个座位号对应一个学生，这个时候，学号或者座位号可以唯一标识一个学生；但是姓名和性别不可以，因为姓名可能会有重复，性别一定会有重复，一个班级中不可能只有两个学生，学生人数＞=3时，性别只有男女之分（双性人等特殊情况不予考虑），根据抽屉原理，至少男生，或者女生不只一个人，所以不能作为标识。班级中也会出现同名现象，所以姓名也不可以。

所以关键字中，最主要的是唯一标识，如果查找不是通过关键字查找，例如我们查找数组中值为某个数的数组下标，我们查找到的是数组中第一个值为我们查找的值的下标。

## 5、平均查找长度 ##

我的中文名字叫平均查找长度，我的英文名字叫 “ Average Search Length ”， 简称 “ASL” 。这个简称很重要，经常我们会遇到，所以希望大家能够记住。

在查找过程中**一次查找的长度是指需要比较的关键字的次数**，**平均查找长度是指所有查找过程中进行关键字的比较次数的平均值**。其数学定义为：

![2018110721064834.png][]

其中，Pi是查询第i个数据的概率，一般情况下，我们认为每个数据元素查找的概率都是相同的即Pi = 1/n；Ci是找到第i个数据的比较次数。**平均查找长度是衡量查找算法的最主要指标**。

# 二、顺序查找 #

## 1、顺序查找概念 ##

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。查找时，对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

给定一个数据，判断该数据是否为二叉排序树中的数据并求其所在层数。其中圆角矩形内为结点数据，旁边数字为结点编号，箭头指向的结点为箭尾的孩子结点。

## 2、示例及代码 ##

给定一组数据，数据内容如下：

numData[] = { 12,31,25,67,80,51,77,32 };

用户指定查询内容，判断该组数据中是否有用户指定数据。算法实现如下：

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    int numData[] = { 12,31,25,67,80,51,77,32 };
    int length = sizeof(numData) / sizeof(int);
    
    int SequentialSearch(int numData[],int searchElem) {
    	for (int i = 0; i < length; i++)
    	{
    		if (numData[i] == searchElem)
    			return i;
    	}
    
    	return -1;
    }
    
    void main() {
    	int se;
    	cout << "Please input the data that you want to inquire : ";
    	cin >> se;
    	int k = SequentialSearch(numData, se);
    	if (k == -1)
    		cout << "There is no data that you want to query in this array. " << endl;
    	else
    		cout << "The number of the data that you inquiring is : " << k << endl;
    }

## 3、实现效果 ##

![20181107211521629.png][]

![20181107211625373.png][]

[2018110721064834.png]: /images/20210516/02c13cae5b7c47959e53f5018b71e248.png
[20181107211521629.png]: /images/20210516/9bd50256f02a4b84b80846530ef222c1.png
[20181107211625373.png]: /images/20210516/929fba10a295423497e0db278885855b.png