（期末考试prepare）数据结构（C语言版）第七章——查找（顺序表、树表、哈希表）·附习题

绝地灬酷狼 2023-02-16 00:52 2阅读 0赞

**数据结构期末复习系列【陆续更新】**  
内部排序：https://blog.csdn.net/qq\_45832958/article/details/106542994

### 查找 ###

*  一、顺序表
 *   *  1.顺序表(静态查找)表示
     *  2.顺序查找
     *  3.折半查找（二分查找）
     *  4.分块查找
 *  二、树表
 *   *  1.二叉排列树的查找
     *  2.平衡二叉树(AVL树)
     *  3.B-树（B树）
 *  三、Hash（散列）表查找

# 一、顺序表 #

## 1.顺序表(静态查找)表示 ##

typedef struct{
    KeyType key;//关键字（数据项）
    InfoType info;//数据元素的其他属性，为简化算法通常忽略此数据项
    }ElemType;//数据类型
    
    typedef struct{
    ElemType *elem;//数据元素储存基址，0号单元留空
    int length;
    }STable;//顺序表

## 2.顺序查找 ##

顺序表或者链表都适合

int SeqSearch(STable ST,KeyTpe key){
    ST.elem[0]=key;//设置0号为监视哨，就不用了多次比较i是不是越界，因为在最后0号哨上一定能配对成功。所以比较时候要从后往前
    for(i=ST.length;;i- -){
    if(ST.elem[i].key=key) return i;
    }
    }

对n个元素顺序查找，若查找成功，则比较关键字的次数最多为（n）次；  
当使用监视哨时，若查找失败，则比较关键字的次数为（n+1）

## 3.折半查找（二分查找） ##

必为有序表first,且顺序表（链表no）  
时间复杂度O(log2n)  
平均查找长度：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70]

int BinSearch(STable ST,KeyType key){
    low=1;
    high=ST.length;
    while(low<=high){
    mid=(low+high)/2;
    if(key==ST.elem[mid].key) return mid;
    else if(key<ST.elem[mid].key) high=mid-1;
    else low=mid+1;
    }
    return 0;
    }

该算法的递归也很好写：

int BinSearch(STable ST,int low,int high,KeyType key){
    low=1;
    high=ST.length;
    if(low>high) return 0;
    else{
    mid=(high+low)/2;
    if(key==ST.elem[mid].key) return mid;
    else if(key<ST.elem[mid].key) 
    return BinSearch(ST,low,mid-1,key);
    else return BinSearch(ST,mid+1;high,key);
    }
    }

ps:如果考试的时候让写这种算法，能写成递归的形式就写成递归的形式，那个看起来太简单了。  
记得上学期期末考试老师好像说输入时候用scanf和for循环逐个输入也可以，但是肯定得分会低。而用特定的函数gets就可以拿满分。  
赶脚是一个道理。

## 4.分块查找 ##

原理：  
每一块中所有元素的关键字均小于（大于）其后面块中的所有元素，并对块建立索引表。  
查找表的每一块都可以由索引表中的索引项决定。  
索引项包括：  
1.关键字（存放对应块中最大/最小关键字）  
2.起始地址（存放对应块的其实下标），索引表按关键字递增/递减排序

每块最佳长度：√n

查找步骤：  
1.在索引表中检测索引项（用key比对），确定待查记录的所在块  
2.在块中顺序查找  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 1]

typedef struct{
    KeyType index;//索引关键字
    int indexaddr;//所在块的起始地址
    }InElemType;//查找表（逻辑上按块划分）
    
    typedef struct{
    InElemTyep *elem;//索引项的存储空间基址
    int length;//索引表表长
    }IndexTable;//索引表
    
    int BlockSearch(STable ST,IndexTable IT,KeyType key){
    //在查找表ST（0号单元未用）中分块查找关键字为指定值key的数据元素
    //折半查找其索引表IT
    low=1;high=IT.length;
    while(low<=high){
    mid=(low+high)/2;
    if(key==IT.elem[mid].index) {i=mid;break;}//找到元素对应的块
    else if(key<IT.elem[mid].index) high=mid-1;
    else low=mid+1;
    }
    if(low>high) i=low;//在low索引的块中
    if(i= =IT.length) return 0;//key大于索引表中所有关键字，查找失败
    
    //在ST表（查找表）中
    l=IT.elem[i].indexaddr;//查找下界
    if(i==IT.length-1) h=ST.length;
    else h=IT.elem[i+1].indexaddr-1;//上界
    while(h>1){
    if(key= =ST.elem[l].key)
    break;
    else l++;
    }
    if(l<h) return 1;//查找成功
    else return 0;
    }

ps：分块查找由于只要求索引表有序，不要求块内部有序，所以很能适应结点动态变化的要求，而且查找速度较快。

三种顺序表查找方式查找长度的比较：  
（二分<分块<顺序）  
二分最短；  
顺序最长；  
分块是在索引表（有序）用二分，块内（无序）用顺序，所以期间介于二者之间

# 二、树表 #

**前序**遍历得出的结点序列是从小到大  
N个结点的二叉排序树有多种，其中树高最小的二叉排序树是较好的

## 1.二叉排列树的查找 ##

typedef struct BiTNode{
    ElemType elem;//数据元素
    struct BiTNode *lchild,*rchild;//左右孩子指针
    }BiTNode,*BiTree;//二叉树结点，指针类型
    
    BiTree BSTSearch(BiTree BT,KeyType key,BiTree &q){
    //若找到key，返回指向它的指针p，指针q指向其父结点
    p=BT;//p一直指向待比较的结点
    q=NULL;
    while(p){
    if(key==p->elem.key) return p;
    else if(key>p->elem.key){ q=p;p=p->rchild;}
    else {q=p;p=p->lchild; }
    return p;
    }
    }

改成递归：

BiTree BSTSearch(BiTree BT,KeyType key){
    if((!BT)||key==BT->elem.key) return BT;
    else if(key<BT->elem.key) return (BSTSearch(BT->lchild,key));
    else return(BSTSearch(BT->rchild,key));
    }

哇用递归能少写好多代码~

二叉排序树构造的代码也可以简单一看，很简单，就是申请一个新结点然后找位置插进去就行了。二叉树删除的代码也太长了，应该不会考⑧。。。

二叉排列树习题：  
①以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(**C**)  
A（100，80， 90， 60， 120，110，130）  
B（100，120，110，130，80， 60， 90）  
C（100，60，80， 90， 120，110，130）  
D (100，80， 60， 90， 120， 130，110)  
**析**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 2]

②将元素\{38，27,64,12,61,83,19\}插入生成二叉排序树，查找值为61的结点所需要比较次数：3  
**析**：从某种程度上来说，二叉排列树的查找方式很类似于二分  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 3]  
③二叉排序树删除一个结点后，仍是二叉排序树  
**析**：这句话是出的判断，答案是√ 但我感觉只是说叶子结点吧，还要考虑根结点情况，对非叶子、非根结点删除它和它子树比较合适叭。赶脚不太严谨

④二叉查找树的效率与（树型）有关，当（呈单枝树）时效率最低。  
所以才提出了底下平衡二叉树的概念

## 2.平衡二叉树(AVL树) ##

**定义**：高度平衡的二叉排列树 （填空）

为了降低二叉排序树的平均查找长度，使得每个结点的两个子树深度不要太大，而引入平衡二叉树，即左子树和右子树的深度之差绝对值小于1.  
结点的平衡因子（BT）（该结点的左子树深度减去右子树深度）只能为0、-1、1

插入新结点后构建：LL型，RR型，LR型，RL型

## 3.B-树（B树） ##

前面所讨论的查找对象都是可以全部保存在内存中的数据结构，比如二叉排列树、平衡二叉树等。  
当数据量增大后，一般会以文件的形式存储在外存（如硬盘）上。这样，执行查找操作时，必须多次访问硬盘。  
与内存相比，硬盘的存取速度很低。应用B-树这种多路平衡查找树，可以提高查找效率，减少查找过程中对磁盘的存取次数。  
所以B-树是一种适合在磁盘等直接存取设备上组织动态的查找表。

B+树  
既能索引查找 也能顺序查找

讲真课本的老大一大串概念定义都没大看懂ε=(´ο｀\*)))唉，找不出啥考点，先pass掉叭

# 三、Hash（散列）表查找 #

每个关键字通过哈希函数f（自己规定）的变换，搞出一个唯一的存储地址  
因为是1vs1的，so可快速插入、删除，时间复杂度可达常数级O(1)

负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。  
Hash表的平均查找长度不随表中结点数目的增加而增加，而与装填因子有关。  
理解一下基本概念，搞两道习题凑活下吧。这块应该只能出选择填空⑧

散列函数有一个共同的性质，即函数值应当以(**同等概率**)取其值域的每个值

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020060910014766.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609094852261.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200609110924481.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200609113416866.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200609095126963.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200609095256598.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70