数据结构之查找（期末复习）

淩亂°似流年 2023-02-21 01:51 106阅读 0赞

**【知识框架】**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]

# 一、查找的基本概念 #

### 1、查找表 ###

**查找表**是由同一类的数据元素（或记录）构成的集合。集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

### 2、关键字 ###

**关键字**是数据结构（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。  
**主关键字**：关键字可以唯一标识一个记录；（不同的记录，主关键字不同）  
**次关键字**：用以识别若干记录的关键字；

### 3、查找 ###

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在该数据，则查找成功；否则查找不成功；

### 4、动态、静态查找表 ###

动态查找表：在查找的过程中对表进行修改（插入、删除）；  
静态查找表：在查找过程中不做修改；

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

可以用平均平均查找长度来衡量查找算法的性能；

# 二、线性表的查找 #

## 1、顺序查找 ##

顺序表的定义

typedef struct{
        
     ElemType *R;  //储存空间基地址
     int length;   //表长度
    }SSTable;

【算法描述】

int Search_Seq(SSTable ST,KeyType key)
    {
        
     for(i=ST.length;i>=1;--i)
     {
        
      if(ST.R[i].key==key)return i;
     }
     return 0;
    }

设置监视哨的顺序查找

int Search_Seq(SSTable ST,KeyType key)
    {
        
     ST.R[0].key=key;
     for(i=ST.length;ST.R[i].key!=key;--i);
     return i;
    }

【特点】  
算法简单，对表结构无任何要求，但查找效率低；  
【适用情况】  
任何结构的线性表，不经常做插入和删除；

## 2、折半查找（二分查找） ##

要求：线性表必须采用顺序存储结构，且元素有序排列；  
例如：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]  
**【代码示例】**

#include<iostream>
    using namespace std;
    typedef struct 
    {
        
    	int R[100];
    	int length;
    }SSTable;
    //折半法查找元素
    void Search_Bin(SSTable ST,int key)
    {
        
    	int mid;
    	int low = 1;
    	int hight = ST.length;
    	while (low <= hight)
    	{
        
    		mid = (low + hight) / 2;
    		if (key == ST.R[mid])
    		{
        
    			cout << "查找元素在第" << mid << "位置";
    			break;
    		}
    		else if (key < ST.R[mid])hight = mid - 1;
    		else if (key > ST.R[mid])low = mid + 1;
    	}
    	if (low > hight)cout << "不存在该查找数";
    }
    int main()
    {
        
    	SSTable ST;
    	int len;
    	cout << "请输入数组长度：";
    	cin >> len;
    	ST.length = len;
    	cout << "请输入数组元素：";
    	for (int i = 1; i <= len; i++)
    	{
        
    		cin >> ST.R[i];
    	}
    	int key;
    	cout << "请输入要查找的数：";
    	cin >> key;
    	Search_Bin(ST, key);
    	cout << endl;
    	return 0;
    }

**【运行结果】**  
![在这里插入图片描述][20200628201642516.png] ![在这里插入图片描述][20200628201632628.png]  
【特点】  
对表结构要求较高，查找效率高；  
【适用情况】  
有序的顺序表，不经常做插入和删除；

## 3、分块查找（索引顺序查找） ##

首先需要建立一个**索引表**，索引表的每个块包含两部分：**关键字项**（该块内的最大关键字），**指针项**（该块第一个记录在表中的位置）。

【查找过程】  
先确定待查记录所在的块，然后在块中顺序查找（或折半查找）。  
【特点】  
对表结构由一定要求，查找效率介于折半查找和顺序查找之间；  
【适用情况】  
块间有序、块内无序的顺序表，经常做插入和删除；

# 三、树表的查找 #

## 1、二叉排序树（二叉查找树） ##

【定义】  
二叉排序树可以是一棵空树，或者是满足下列条件的树：  
（1）若它的左子树非空，则左子树上所有节点均小于它的根结点；  
（2）若它的右子树非空，则右子树上所有节点均大于它的根结点；  
（3）它的左右子树也为二叉排序树；

【二叉排序树的递归查找算法描述】  
（1）若树为空，则查找失败；  
（2）若树非空：将查找值与树根结点比较：  
a、若两值相等，则输出根结点的地址；  
b、若查找值<根结点，则在左子树进行查找，重复（1）（2）步骤；  
c、若查找值>根结点，则在右子树进行查找，重复（1）（2）步骤；

【二叉排序树的插入、创建、删除】

//插入
    void InsertBST(BSTree &T,ElemType e)
    {
        
     if(!T)   //如果是空树
     {
        
      S=new BSTNode;    //生成新结点*S
      S->data=e;        //将结点*S的数据域置为e
      S->lchild=S->rchild=NULL;   //*S为叶子结点
      T=S;              //把结点*S链接到已找到的插入位置
     }
     else if(e.key<T->data.key)  //关键字小于根结点的值
     InsertBST(T->lchild,e);     //往左子树中插入
     else if(e.key>T->data.key)  //关键字大于根结点的值
     InsertBST(T->rchild,e);     //往右子树中插入
    }

//创建
    void CreatBST(BSTree &T)
    {
        
     T=NULL;
     cin>>e;
     while(e.key!=ENDFLAG)
     {
        
      InsertBST(T,e);
      cin>>e;
     }
    }

【删除的三种类型】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]

## 2、平衡二叉树 ##

【定义】  
二叉排序树可以是一棵空树，或者是满足下列条件的树：  
（1）左子树和右子树的深度之差的绝对值不超过1；  
（2）左子树和右子树也是平衡二叉树；  
**平衡因子**：该结点的左子树与右子树之差，（平衡因子只可能是-1，0，1）若不是这三个值，则该树不平衡。  
【平衡调整方法】  
（1）LL型  
进行一次向右的顺时针旋转操作  
（2）RR型  
进行一次向左的逆时针旋转操作  
（3）LR型  
需进行两次旋转操作，第一次逆时针旋转变为LL型，再顺时针旋转恢复平衡  
（4）RL型  
需进行两次旋转操作，第一次顺时针向右旋转，第二次逆时针向左旋转

## 3、B-树 ##

【定义】  
一棵m阶B-树可以是一棵空树，或者是满足下列条件的m叉树：  
（1）树中每个结点至多有m棵子树；  
（2）若根结点不是叶子结点，则至少有两棵子树；  
（3）除根之外的所有非终端结点至少有\[m/2\]棵子树；  
（4）所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点；  
（5）所有的非终端结点最多有m-1个关键字；  
【查找】  
B-树是一种平衡的多叉查找树，是一种在外存文件系统中常用的动态索引技术。查找过程与二叉排序树类似，是一个顺指针查找结点和在结点内的关键字中查找交叉进行的过程。

## 4、B+树 ##

【特点】  
（1）有n棵子树的结点中含有n个关键字；  
（2）所有的叶子结点中包含了全部关键字信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；  
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大关键字；  
【查找】  
若非终端结点上的关键字等于给定值，查找并不终止，而是继续向下直到叶子结点。  
【插入和删除】  
插入和删除仅发生在叶子结点上。

# 四、散列表的查找 #

## 1、散列表的基本概念 ##

**散列查找法**：如果能在元素的存储位置和其关键字之间建立某种直接关系，按照这种关系直接由关键字找到相应的记录。  
**散列函数、散列地址**：在记录的存储位置p和关键字key之间建立一种确定的对应关系H，使p=H（key）;对应关系H称为散列函数，p称为散列地址。  
**散列表**：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。  
**冲突**：对于不同的关键字可能得到同一散列地址；  
**同义词**：具有相同函数值的关键字对该散列函数来说称作同义词；

## 2、散列函数的构造方法 ##

#### 1、数字分析法 ####

适用情况：实现必须明确知道所有的关键字每一位上各种数字的分布情况。

#### 2、平方取中法 ####

适用情况：不能事先了解关键字的所有情况，或难于直接从关键字中找到取值较分散的几位。

#### 3、折叠法 ####

适用情况：适合于散列地址的位数较少，而关键字的位数较多，且难于直接从关键字中找到取值较分散的几位。

#### 4、除留余数法 ####

适用范围广，这个方法的关键是选取适当的p，一般情况下，可以选p为小于表长的最大质数。

## 3、处理冲突的方法 ##

#### 1、开放地址法 ####

将记录都存储在散列表数组中，若发生冲突，采取合适方法计算得到另一个地址，如果还是冲突，再算地址，直到不再冲突为止.（探测方法有：线性探测法、二次探测法、伪随机探测法）

#### 2、链地址法 ####

把具有相同散列地址的记录放在同一个单链表中，称为同义词链表，依次计算各个关键字的散列地址，然后根据散列地址将关键字插入到相应的链表中。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628100622415.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629090948404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[20200628201642516.png]: https://img-blog.csdnimg.cn/20200628201642516.png
[20200628201632628.png]: https://img-blog.csdnimg.cn/20200628201632628.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200630095332785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70