【精品数据结构】检索结构.PPTVIP

第 8 章 检索结构 §8.1 概述 检索也称查找 检索是指在数据元素（记录）集合中求出满足某给定条件的记录 数据元素（记录）中确定某特定数据字段的值与给定值相匹配的记录 关键字字段（简称关键字） 检索成功与不成功 在某此问题中，当检索不成功时要插入不存在的数据记录，或在某种情况下删除所找到的记录 检索算法（方法） : 按检索操作是否全部在内存进行： 内检索 外检索 按是否增删元素 静态检索 动态检索 检索算法（方法） : 按是否进行比较操作 比较式检索 非比较式检索 按关键字是否变化 原词检索 变词检索 为了提高检索效率，要专门为检索操作设置数据结构 若按数据元素集合中元素间结构关系分类 线性结构（含线性链结构） 线性索引结构 树形结构 散列（杂凑）结构 按检索结构中数据元素是否会增加或减少分类 静态检索结构：操作中不增加或减少元素 动态检索结构：操作中可能增加元素或减少元素 检索算法的空间复杂度分析 在现有结构上进行检索的算法 实现检索算法而构造专门的数据结构的算法 检索算法的时间复杂度分析 以关键字的比较次数为主度量算法的时间复杂度 待查关键字的位置对算法本身而言是个随机量，所以要综合测定算法的检索次数，需使用检索次数的数学期望 将检索算法的检索次数的数学期望称为平均检索长度ASL（Average Search Length） 对检索成功（关键字在表中）情况其计算式为： ASL= 检索不成功的情况（关键字不在数据元素集中），平均检索长度即为检索失败对应的比较次数。 检索算法的总的平均检索长度应为检索成功与失败两种情况的平均检索长度的数学期望。 判定树中每个结点表示被查数据元素集中的一个元素（常用元素编号表示） 从树根到某一结点的路径，就表示检索该结点所经历的过程，路径上各结点为检索中测试（比较）过的结点 树结点的各个儿子，表示从该结点起下步检索的各选择分枝 对无儿子结点，表示检索过程进行到它（即与它比较）后，不能继续进行，应终止 判定树的构造方法 若某检索算法A在数据元素集D上进行检索，则A对D的（检索）判定树定义为： 若D=空，则A对D的判定树为空 若第1次是与元素i1比较（测试），则令i1为判定树的根 若与i1比较后，下一步的检索操作是在数据集D1,...,Dm 之一中进行（即可能在D1,...,Dm中任意一个上进行），则令算法A的其余部分对D1,...,Dm的判定树（子树）为根结点i1的各子树，这里，D1,...,Dm应为(D-{i1})的一个划分。 （即D1∪...∪Dm=D-{i1}，且Dj∩Dk=空，j≠k，j, k∈{1,...,m}） 判定树的深度就表示检索算法的最大比较次数 树的分枝数越大（即数据集分块越多），树深度就越小 检索某结的比较次数，就是从树根到该结点的路径上的结点个数 外结点 增设了外结点的判定树为完全二叉树 增设了外结点的判定树为完全二叉树 判定树的内路径长定义为该树中各内结点的路径长（从根到某结点的路径长定义为该结点的内径长）之和 外路径长定义为树中各外结点的路径长之和 设I与E分别代表判定树的内与外路径长，则有 　　　 E=I+2n 这里n为内结点数目 实际中，各关键被查概率可能不同，为此，引入加权内外路径长 设wi与li分别为结点i的权值与在树中的层次数（即结点i的路径长），则定义wi与li的积为i的加权路径长 加权内路径长I= 加权外路径长E= 属于静态检索 算法简单，但速度不高 主要用在对小型数据集的检索 一般的线性表有两种存贮结构：连续式与链式 对它们的检索，一般采用顺序有哪些信誉好的足球投注网站的方式──称为顺序查找 若元素已按关键字排序，则可采用更高效的检索法──折半查找 (一)算法 long SeqSearch(int a[], long n, int key) { /*连续存储结构的线性表的顺序查找 a[ ]——输入量.一维数组，充当线性表，n为元素个数。 序号为0的位置不使用 key——待查关键字 返回——成功时返回key在表中的序号，否则返回0*/ ? long i; a[0]=key; //设置监视哨 i=n;; while(a[i]!=key) i--; return i; } (二)平均检索长度 检索成功时的平均检索长度 ASL=∑1/n(n-i+1)=1/n (n-i+1)=(n+1)/2=O(n) ASL总=q0(n+1)+q1(n+1)/2 若它们是等概率的 ASL总=1/2(n+1)+1/2·(n+1)/2=3/4(n+1)