数据结构--查找

发布于：2025-02-27 ⋅ 阅读:(9) ⋅ 点赞:(0)

查找

查找：根据给定的某个值，在查找表中确定一个其关键字等于其查找的数据元素或记录（主关键字/次关键字）

查找的目的：

  1. 查询某个特定的数据元素是否在查找表中
  2. 检索某个特定的数据元素的各种属性
  3. 在查找表中插入一个数据元素
  4. 删除查找表中的某个数据元素

查找的分类：

  • 静态查找表
  • 动态查找表

查找算法的评价指标–关键字的平均比较次数（平均查找长度）（关键字比较次数的期望值）

查找过程中我们要研究查找表的各种组织方法及其查找过程的实施，为设法提高查找表的查找效率，一个办法时在构造查找表的时候，在集合的数据元素之间认为的加上某种确定的约束关系

线性表的查找–线性存储结构

顺序查找（线性查找）

#include<stdio.h>
#include<limits.h>
typedef struct{
    int *data;
    int length;
}SSTable;//Sequential search table
SSTable ST;
void Init(SSTable *S){
    printf("请输入数组长度:\n");
    scanf("%d",&S->length);
    if (S->length <= 0) { // 检查长度是否有效
        printf("数组长度必须大于0！\n");
        exit(1);
    }
    S->data = (int *)malloc((S->length+1)*sizeof(int));
    if(S->data==NULL){
        printf("创建失败");
        exit(1);
    }
    S->data[0]=INT_MAX;
    for(int i=1;i<S->length+1;i++){     //0号位置空出，从第一个开始存储
        printf("请输入第%d个元素:",i);
        scanf("%d",&S->data[i]);
    }
}
int Search_Seq1(SSTable S,int key){
    for(int i=S.length;i>0;i--){
        if(S.data[i]==key)  return i;
    }
    return -1;
}
int Search_Seq2(SSTable S,int key){
    int i;
    for(i=S.length;S.data[i]!=key&&i>0;i--);
    return i>0?i:-1;
}

上述这种方法每执行一次都要比较两次，能否改进？

  • 改进：把关键字作为“监视哨”存储在第0号位置，每次不需要比较是否检查完成，加快速度
int Search_Seq3(SSTable S,int key){
    if(key==INT_MAX){
        return -1;
    }
    int temp = S.data[0];
    S.data[0]=key;
    int i;
    for(i=S.length;S.data[i]!=key;i--);
    S.data[0]=temp;
    return i>0?i:-1;
}

  • 查找的次数取决于key,查找第i个元素需要n-i+1次，所以时间复杂度为O(n)

  • 数组的大小为length + 1，其中length是用户输入的数组长度。这个空间是用于存储数据的，而不是额外空间 ；在查找过程中，我们使用了几个基本变量（如i和temp），这些变量占用的空间是常数级别的，所以空间复杂度为O(1)

  • 假设个记录查找概率相同，则查找成功时的平均查找长度为:(n+1)/2

特点：

  • 优点：算法简单，逻辑次序无要求，且不同存储结构均适用
  • 缺点：ASL太长，时间效率低

折半查找（二分查找）+ 插值查找

定义：每次将待查记录所在区间缩小只原来的一半(要求该区间上的必须是有序的)

int Search_Bin(SSTable S,int key){  //该算法要求该数组是升序的
    int low=1,high=S.length;
    while(low<=high){
        int mid=(low+high)/2;
        if(key==S.data[mid])    return mid;
        else if(key>S.data[mid])    low=mid+1;
        else    high=mid-1;
    }
    return -1;
}

特点：

  • 优点：效率高，时间复杂度为O(lgn)
  • 缺点：只适用于有序表，而且必须是顺序存储结构

改进:我们不直接折半，而是根据要查找的关键字key和查找表中最大最小记录的关键字比较后的查找方法，得到了插值查找，也就是把mid=1/2（low+high)换成mid=(key-a[low])/(a[high]-a[low]),其他均不变，时间复杂度为O(logn)

所以对于表长较长有比较均匀的查找表来说性能更好，极端表未必合适

分块查找

条件：

  1. 将表分为几块，且表或者有序，或者分块有序
  2. 建立“索引表”(索引就是把一个关键字与它对应记录相关联的过程)

查找过程：先确定待查记录所在快（顺序/折半），再在块内查找（顺序）

假设表长n,平均每块为s，一共m块，显然n=ms

ASL=L1+L2≈(1+2+…+m)/m+s+1/2 //在查找索引表确定块的时候，可以用折半/插值来提高效率

​ =(m+t)/2

特点（块内无序，块间有序）：

  • 优点：插入和删除比较容易，无需进行大量移动
  • 缺点：要增加一个索引表的存储空间并对初始空间进行排序运算
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;       
    int length;      
} SSTable;

typedef struct {
    int *index;      // 索引表，存储每个块的最大值
    int *blockStart; // 每个块的起始位置
    int blockSize;   // 每个块的大小
    int indexSize;   // 索引表大小
} BlockTable;
//省略初始化过程...
int Search_Block(SSTable S, BlockTable B, int key) {
    // 在索引表中查找目标块
    int i;
    for (i = 0; i < B->indexSize && B->index[i] < key; i++);

    if (i == 0) {
        i = 0;
    } else {
        i--; 
    }

    // 在目标块内顺序查找
    int start = B->blockStart[i];
    int end = ((start + B->blockSize) < S.length) ? start + B->blockSize : S.length;
    for (int j = start; j < end; j++) {
        if (S.data[j] == key) {
            return j; // 找到目标值，返回索引
        }
    }

    return -1; // 未找到目标值
}

树表的查找–树形存储结构

当表插入、删除操作频繁时，为了维护表的有序性，需要西东表中很多记录，那么有没有一种既可以使得插入和删除效率不错，又可以比较高效率的实现查找的算法呢？

  • 改用动态查找表–几种特殊的树

二叉排序树（二叉搜索树):要么是空树，要么满足下面条件

  1. 若其左子树飞快，则左子树上所有结点的值均小于根结点的值
  2. 若其右子树飞快，则右子树上所有结点的值均大于根结点的值
  3. 其左右子树本身又各是一棵二叉排序树

二叉排序树的性质：

  • 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列

首先，给出一个基本的树形结构，我们将在这上面进行操作

typedef struct{
    int data;
    struct BiTNode* lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;

二叉排序树的操作–查找

算法思路:

  1. 若二叉排序树为空，则查找失败，返回NULL
  2. 若二叉排序树非空，则将key==T->data进行比较
    1. 如果=，则查找成功，返回根结点地址
    2. 如果<，则递归查找其左子树
    3. 如果>，则递归查找其右子树
BiTree Search_BST(BiTree T,int key){
    if(!T){
        printf("空树");
        return NULL;
    }
    if(key==T->data)    return T;
    else if(key<T->data)    return Search_BST(T->lchild,key);
    else return Search_BST(T->rchild,key);
}

查找分析：

  • 比较的关键字次数=此结点所在层次数 最多的比较次数=树的深度
  • 二叉排序树的评卷查找长度和树的形态有关，最好情况树的深度O(log2n)+1，时间复杂度为O(log2n);最坏情况变成单支树，查找效率与顺序查找情况相同，ASL=(n+1)/2,时间复杂度O(n)

二叉排序树操作–插入

算法思路：

  • 若二叉排序树为空，则插入结点作为根结点
  • 否则，继续在左右子树上寻找
    • 如果已有，不再插入
    • 没有，查找直至某个叶子结点的左子树或右子树为空时为止，则插入该结点为该叶子结点的左孩子或右孩子
BiTree Insert(BiTree T,int value){
    if(T==NULL){
        BiTree S=(BiTNode*)malloc(sizeof(BiTNode));
        if(S==NULL){
            printf("内存分配失败");
            return NULL;
        }
        S->data=value;
        S->lchild=NULL;
        S->rchild=NULL;
        return S;
    }
    if(T->data>value)   T->lchild=Insert(T->lchild,value);
    else if(T->rchild<value)    T->rchild=Insert(T->rchild,value);
    return T;
}

二叉排序树的操作–删除

在二叉排序树删除结点，不能把该结点所在的根全部删掉，只能删掉该结点，并且还要保证删完后的仍然还是一个二叉排序树

算法分析:

  1. 删除的是叶子结点，则直接删掉即可
  2. 删除的结点只有左子树或者右子树的时候，直接用左子树或者右子树替换至原位置即可
  3. 删除的结点既有左子树，又有右子树
    1. 以其中序前驱值替换之，然后再删除该前驱结点。前驱是左子树中最大的结点
    2. 也可以用其后继替换之，删除该后继结点。后继是右子树中最小的结点
BiTree findmin(BiTree T){
    if(T==NULL) return NULL;
    while(T->lchild!=NULL){
        T=T->lchild;
    }
    return T;
}
BiTree Delete(BiTree T,int value){
    if(T==NULL){
        printf("未找到该结点");
        return NULL;
    }
    if(T->data>value){
        T->lchild=Delete(T->lchild,value);
    }
    else if(T->data<value){
        T->rchild=Delete(T->rchild,value);
    }
    else{
        if(T->lchild==NULL&&T->rchild==NULL){
            free(T);
            return NULL;
        }
        if(T->lchild==NULL){
            BiTree S=T->rchild;
            free(T);
            return S;
        }
        if(T->rchild==NULL){
            BiTree S=T->lchild;
            free(T);
            return S;
        }

        BiTree minNode=findmin(T->rchild);
        T->data=minNode->data;
        T->rchild=Delete(T->rchild,minNode->data);
    }
    return T;
}

平衡二叉树

前面我们了解到了二叉排序树的平均查找长度与树的形态有关，那么如何提高形态不均衡的二叉排序树的查找效率呢？

解决办法:做"平衡化处理"，尽量使二叉树平衡化

平衡二叉树（AVL树)：要么是空树，要么满足下列性质

  • 左子树和右子树的高度差的绝对值<=1
  • 左右子树也是平衡二叉排序树

性质：

  • 为了方便起见，我们还引入了平衡因子的概念，即左子树与右子树的高度差
  • 对于一棵有n个结点的AVL树，其高度保持在O(log2n),ASL也保持在O(log2n)
  • 如果在一棵AVL树中插入一个新结点造成失衡，则必须重新调整树的结构，使之恢复平衡

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

具体平衡二叉树的调整示例

主要遵循两个原则:降低高度，保持二叉树性质

哈希表的查找–散列存储结构

[一个视频讲解散列表（哈希表）](散列表(哈希表) - 散列函数, 冲突处理, 平均查找长度(ASL)_哔哩哔哩_bilibili)

基本定义

  • 基本思想:记录的存储位置与关键字之间存在对应关系（哈希关系）

  • 优点：查找效率非常高

  • 缺点：空间效率低

  • 散列方法

    • 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放
    • 查找时，由同一个函数对给定值k计算地址，将k与地址单元张元素关键码进行比较，确定是否成功

  • 散列函数：散列方法中使用的转换函数

  • 散列表：按上述思想构造的表

  • 冲突：不同的关键码映射到同一个散列地址，即key1≠key2,但H(key1)=H(key2)

  • 同义词:具有相同函数值的多个关键字

散列函数的构造方法

使用散列表要解决好两个问题：

  • 构造好的散列函数
    • 所选函数尽可能简单，以便提高转换速度
    • 所选函数对关键码计算出的地址，应在散列地址集中均匀分布，以减少空间浪费
  • 制定一个好的解决中途的方案
    • 查找时，如果从散列函数计算出的地址中查不到关键码，应该依据解决冲突的规则，有规律的查询其他相关单元

构造散列函数需要考虑的因素;

  1. 执行速度
  2. 关键字的长度
  3. 散列表的大小
  4. 关键字的分布情况
  5. 查找频率

散列表解决冲突方法

开放定址法（开地址法）

链地址法（拉链法）

基本思想：相同散列地址的记录链成一个单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构

优点：

  • 非同义词不会冲突，无“聚集”现象
  • 链表结点空间动态申请，更适合于表长不确定的情况

散列表的查找及其性能分析

使用平均查找长度ASl来衡量查找算法。ASL取决于：

  • 散列函数
  • 处理冲突的方法
  • 散列表的装填因子a

a=表中填入的记录数/哈希表的长度

几点结论：

  1. 散列表奇数具有很好的平均性能，优于一般的传统奇数
  2. 链地址法优于开地址法
  3. 除留余数法作散列函数优于其他类型函数
    存储起来，形成一个动态的结构

优点：

  • 非同义词不会冲突，无“聚集”现象
  • 链表结点空间动态申请，更适合于表长不确定的情况

散列表的查找及其性能分析

使用平均查找长度ASl来衡量查找算法。ASL取决于：

  • 散列函数
  • 处理冲突的方法
  • 散列表的装填因子a

a=表中填入的记录数/哈希表的长度

几点结论：

  1. 散列表奇数具有很好的平均性能，优于一般的传统奇数
  2. 链地址法优于开地址法
  3. 除留余数法作散列函数优于其他类型函数

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布