【数据结构——查找的基本概念和线性表的查找（静态查找表）】

谁借莪１个温暖的怀抱￠ 2022-12-23 00:56 143阅读 0赞

### 查找 ###

*  一、查找的基本概念
 *   *   *  1、查找的基本概念
         *  2、查找的目的
         *  3、查找表的分类
         *  4、平均查找长度ASL（Average Search Length）
 *  二、静态查找表（基于线性表的查找法）
 *   *  (一）顺序查找
     *   *  1、实例
         *  2、顺序查找算法
         *  3、改进
         *  4、顺序表查找的性能分析
         *  5、顺序查找方法的特点
     *  （二）折半查找
     *   *  1、实例
         *  2、折半查找（非递归算法）
         *  3、递归算法描述
         *  4、折半查找的性能分析-判定树
         *  5、折半查找的优缺点
     *  （三）分块查找
     *   *  1、条件
         *  2、分块查找的过程
         *  2、分块查找的性能分析

# 一、查找的基本概念 #

### 1、查找的基本概念 ###

**查找表：是由同一类型的数据元素（或记录）构成的集合  
关键字：是数据元素中某个数据项的值，它可以标识一个数据元素  
主关键字：可以唯一标识一个记录的关键字**  
**查找：也称检索，是根据给定的关键字，在查找表中确定一个关键字等于给定值的记录或数据元素。**

### 2、查找的目的 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

### 3、查找表的分类 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

### 4、平均查找长度ASL（Average Search Length） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

# 二、静态查找表（基于线性表的查找法） #

## (一）顺序查找 ##

**查找过程：从表的一端开始，依次将查找表中记录的关键字与给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。  
适用条件：顺序存储或链式存储的静态查找表均可。**

### 1、实例 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]

### 2、顺序查找算法 ###

//数据元素类型的定义
    typedef struct
    {
        
    	keyType key;					//关键字域
    	InfoType otherInfo;				//其他域
    }ElemType;
    //静态查找表的顺序存储结构
    typedef struct
    {
        
    	ElemType* R;					//数据元素存储空间基地址，建表时按实际长度分配，0号单元留空
    	int length;						//表长度
    }SSTable;
    SSTable ST;							//定义顺序表ST
    //设元素从ST.R[1]开始向后顺序存放，ST.R[0]不用
    int Search_Seq(SSTable ST, keyType key)
    {
        
    	for (int i = ST.length;i >= 1;--i)
    		if (ST.R[i].key == key)
    			return i;				//从后往前找
    	return 0;
    }

### 3、改进 ###

**改进：把待查关键字key存入表头("哨兵“)，从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。**  
![在这里插入图片描述][20201122091352938.png_pic_center]

int Search_Seq(SSTable ST, keyType key)
    {
         //若成功返回其位置信息，否找返回0
    	ST.R[0].key = key;				//哨兵
    	for (i = ST.length;ST.R[i].key != key;--i)
    		return i;
    	//不用for (int i = ST.length;i >= 1;--i)
    }

### 4、顺序表查找的性能分析 ###

**空间复杂度：一个辅助空间  
时间复杂度：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]

### 5、顺序查找方法的特点 ###

**（1）对表结构为有序表、无序表均可适用  
（2）算法简单，对表结构没有任何要求（顺序和链式）  
（3）n很大的查找效率较低，适合于短表，方法简单  
（4）改进措施：非等概率查找时，可按照查找概率进行排序**

## （二）折半查找 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

### 1、实例 ###

![在这里插入图片描述][20201122093324979.png_pic_center]

### 2、折半查找（非递归算法） ###

**设表长为n,low,high,mid分别指向待查元素所在区间的上界、下界和中点，key为要查找的值。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

//顺序表定义
    typedef struct
    {
        
    	ElemType* R;
    	int length;
    }SSTable;
    //折半查找
    int Search_Bin(SSTable ST, KeyType key)
    {
        
    	//若找到，则函数值为该元素在表中的位置，否则为0
    	low = 1;high = ST.length;
    	while (low < high)
    	{
        
    		mid = (low + high) / 2;
    		if (key == ST.R[mid].key)
    			return mid;
    		else if (key < ST.R[mid].key)
    			high = mid - 1;			//前一子表查找
    		else
    			low = mid + 1;			//后一子表查找
    	}
    	return 0;						//表中不存在待查元素
    }

### 3、递归算法描述 ###

//顺序表定义
    typedef struct
    {
        
    	ElemType* R;
    	int length;
    }SSTable;
    //折半查找
    int Search_Bin_re(SSTable ST, KeyType key,int low,int high)
    {
        
    	//若找到，则函数值为该元素在表中的位置，否则为0
    	if (low > high)
    		return 0;					//表中不存在待查元素
    	mid = (low + high) / 2;
    	if (key == ST.R[mid].key)
    		return mid;
    	else if (key < ST.R[mid].key)
    		return Search_Bin_re(ST, key, low, mid - 1);
    	else
    		return Search_Bin_re(ST, key, mid + 1, high);
    }

### 4、折半查找的性能分析-判定树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]

### 5、折半查找的优缺点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]

## （三）分块查找 ##

### 1、条件 ###

**（1）分块有序，即分成若干子表，要求每个子表的数值都比后一块中的数值小（但子表内部未必有序）  
（2）建立“索引表”，索引表包括：  
关键字项目：各子表中的最大关键字  
指针项：指示该子表的起始地址。**

![在这里插入图片描述][20201122100626187.png_pic_center]

### 2、分块查找的过程 ###

**分两步：  
（1)先确定待查记录所在块：对索引表使用折半查找法（因为索引表是有序表）  
（2）确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 10]

### 2、分块查找的性能分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 11]  
**比较：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/eda1acaefeb547e9962e123383714457.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/9d48b796565244278d60c0ede4b05e6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/64a54bc7ac4242d196ffe0d52b83bca0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/e2f49d4b39c8458c8f050f5a8589bdf5.png
[20201122091352938.png_pic_center]: /images/20221120/8f00154c402241a8a08bc481ba21511b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/90ce1c219cdf443db8f842bf7c5fc10b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/49177238497b4920adeb277c0553b688.png
[20201122093324979.png_pic_center]: /images/20221120/b8b6babaab9749b19f0d855ff1751103.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/77f931d4a10a46beae3b33eba4519bb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/0cf4046f2a2d45f690e6c3ff20df37ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/3081bdb3379d4c46a053ab172bf5194b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/fc24e6c5cc65488e93925273d15dd4b8.png
[20201122100626187.png_pic_center]: /images/20221120/f0126eb17fa14ffc8164096ef6cf9714.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221120/018c5558500f4541a44844115fbe9b19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221120/79c5cd43ec534c1eb0a0aefbaa9b4459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20201122101922849.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center