美文网首页
数据结构(七)查找

数据结构(七)查找

作者: AdRainty | 来源:发表于2021-08-23 10:16 被阅读0次

7.1 查找的基本概念

查找:在数据集合中寻找满足某种条件的数据元素的过程

查找表:用于查找的顺序集合 查找表不是一个新的数据结构

关键字:数据元素中唯一标识该元素的某个数据项的值 唯一、不重复

平均查找长度(ASL):所有查找过程中进行关键字的比较次数的平均值
ASL= \sum_{i=1}^{n}{P_iC_i}

7.2 顺序查找和折半查找

7.2.1 顺序查找

typedef struct{ // 查找表的数据结构
    ElemType elem; // 动态数组基址
    int TableLen;   // 表的长度
}SSTable;

int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0; i<ST.TableLen && ST.elem[i]!=key; ++i);
    return i==ST.TableLen?-1:i;
}

ASL_{成功}= \sum_{i=1}^{n}\frac{i}{n}=\frac{n+1}{2}

ASL_{失败}=n+1

若表是有序表
ASL_{失败}=\frac{n}{2}+\frac{n}{n+1}

7.2.2 折半查找

折半查找又称二分查找,仅适用于有序的顺序表

int Binary_Search(SSTable L,ElemType key){
    int low=0, high=L.TableLen-1, mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key) return mid;
        else if(L.elem[mid]>key) high=mid-1;
        else low=mid+1;
    }
    return -1;
}

ASL_{成功}= log_2{(n+1)}-1

7.2.3 分块查找

特点:块内无序,块间有序

将长度为n的查找表平均分为b块,每块有s个元素,则
ASL=L_i+L_s=\frac{s^2+2s+n}{2s}
s=\sqrt{n}时最小,若对索引表采用折半查找,则
ASL=\lceil \log_2{(b+1)} \rceil +\frac{s+1}{2}

7.3 B树和B+树

7.3.1 B树及其基本操作

B树又称多路平衡查找树,其特性如下

  • 树中每个结点至多有m颗子树,即至多含有m-1个关键字
  • 若根结点不是终端结点,则至少有两颗子树
  • 除根结点外所有非叶子结点至少有\lceil m/2 \rceil颗子树,即至少含有\lceil m/2 \rceil -1个关键字

对一颗含有n个关键字的m阶B树

  • 最小高度h \ge \log_m{(n+1)}
  • 最大高度h \le \log_{\lceil m/2 \rceil}{\frac{n+1}{2}}+1
  • n个关键字的B树必有n+1个叶子结点
B树.png

插入:

  • 需要关键字个数\lceil m/2\rceil-1\le n \le m-1
  • 新元素一定是插入到终端结点,插入依据查找
  • 若超过上限,则从中间位置\lceil m/2\rceil分为两部分,当前结点放入父结点中

删除:

  • 对终端结点删除,关键字未达下限则直接删除
  • 对根结点删除,用直接前驱/直接后继代替
  • 删除终端结点后小于下限,若右结点有多余,则从当前结点后继和后继的后继或者是前驱和前驱的前驱借用
  • 若左右结点都无多余,则将关键字删除后与左兄弟或右兄弟结点中关键字合并

7.3.2 B+树的基本概念

  • 每个分支结点最多有m棵子树(孩子结点)。
  • 非叶根结点至少有两棵子树,其他每个分支结点至少有\lceil m/2 \rceil棵子树。
  • 结点的子树个数与关键字个数相等。
  • 所有叶结点包含全部关键字及指向相应记录的指针.
  • 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
B+树.png

7.4 散列表

7.4.1 散列表的基本概念

散列表又称哈希表,是一种数据结构,特点是数据元素的关键字与其存储地址直接相关

散列函数:一个把查找表中的关键字映射成该关键字对应地址的函数
Hash(key)=Addr

7.4.2 处理冲突的办法

7.4.2.1 拉链法

把所有的同义词存储在同一个链表中

查找:

  • Addr=Hash(key)
  • 查找Addr上是否有记录

装填因子\alpha定义为一个表的装满长度
\alpha = \frac{表中记录数n}{散列表长度m}

7.4.2.2 开放定址法

可存放新表项的空闲地址即可向同义词表项开放,又向非同义词开放
H_i = (H(key)+d_i) \% m
求di的方法:

  • 线性探测法:发生冲突时,看下一个单元是否为空
  • 平方探测法:只有表长=4j+3才能探测到所有位置
  • 伪随机序列法

7.4.3 散列函数的构造方法

  • 直接定址法 H(key)=a*key+b
  • 除留余数法 H(key)=key%p,取一个不大于m但最接近m的质数p
  • 数字分析法
  • 平方取中法

相关文章

  • 数据结构(七)查找

    7.1 查找的基本概念 查找:在数据集合中寻找满足某种条件的数据元素的过程 查找表:用于查找的顺序集合 查找表不是...

  • 数据结构实验之查找七:线性之哈希表

    数据结构实验之查找七:线性之哈希表 Time Limit: 1000MS Memory Limit: 65536K...

  • 音视频开发之旅(27) 算法序列 - 二叉查找树

    目录 常见的查找数据结构和算法介绍 二叉查找树 资料 收获 一、常见的查找数据结构和算法介绍 1.1 链表(顺序查...

  • 06-查找

    在已有的数据结构中查找数据是否存在。 1. 什么是查找 在已有的数据结构中,查找数据是否存在。 2. 分类 线性查...

  • 常见数据结构

    参考文档数据结构中的树Bit-map空间压缩和快速排序去重浅谈算法和数据结构: 七 二叉查找树Java遍历树(深度...

  • 索引

    排好序的快速查找数据结构 定义:数据本身之外,数据库还维护着一个满足特定查找算法的数据结构,这些数据结构以某种方式...

  • 2019-02-23 普林斯顿大学 数据结构课程笔记

    一、 数据结构:基本数据结构:栈、队列、背包、优先队列 排序:排序、归并排序、堆排序、基数排序 查找:二叉查找树、...

  • 数据结构之查找

    数据结构之查找 查找概论 查找表 定义 查找表(Search Table)是同一类型的数据元素(或记录)的集合。 ...

  • redis skiplist

    skiplist数据结构 查找操作 插入操作 删除操作

  • 数据结构实验之查找六:顺序查找

    数据结构实验之查找六:顺序查找 Time Limit: 1000MS Memory Limit: 65536KB ...

网友评论

      本文标题:数据结构(七)查找

      本文链接:https://www.haomeiwen.com/subject/nmiciltx.html