《数据结构》课程电子教案（PPT课件讲稿，C语言版）第09章 检索

第9章检索 >检索的基本概念 >线性表的检索 >二叉排序树 >丰满树和平衡树 >最佳二叉排序树和 Huffman树 >B-树 散列表检索

第9章 检索 ➢检索的基本概念 ➢ 线性表的检索 ➢最佳二叉排序树和Huffman树 ➢散列表检索 ➢二叉排序树 ➢B-树 ➢丰满树和平衡树

91检索的基本概念 检索是确定数据元素集合中是否存在数据元素 等于特定元素或是否存在元素满足某种给定特征的 过程。 要进行检索,必须知道待检索对象的特征,也 就是要知道待检索数据元素的关键字。 我们将能唯一标识一个数据元 素的关键字称为主关键字,而 其它关键字称为辅助关键字或 从关键字

9.1 检索的基本概念 检索是确定数据元素集合中是否存在数据元素 等于特定元素或是否存在元素满足某种给定特征的 过程。 要进行检索，必须知道待检索对象的特征，也 就是要知道待检索数据元素的关键字。 我们将能唯一标识一个数据元 素的关键字称为主关键字，而 其它关键字称为辅助关键字或 从关键字

静态检索表:检索的前后不会改变查找表的内容。 动态检索表:检索过程中可能会改变数据元素的存储 位置。 检索算法的评价标准:平均查找长度ASL( Average Search Length),也就是为确定某一结点在数据集 合中的位置,给定值与集合中的结点关键字所需进行 的比较次数。 对于具有n个数据元素的集合,查找某元素成功的平 均查找长度为 ASL= ∑

静态检索表：检索的前后不会改变查找表的内容。 动态检索表：检索过程中可能会改变数据元素的存储 位置。 检索算法的评价标准：平均查找长度ASL（Average Search Length），也就是为确定某一结点在数据集 合中的位置，给定值与集合中的结点关键字所需进行 的比较次数。 对于具有n个数据元素的集合，查找某元素成功的平 均查找长度为： =  n i Pi Ci 1 ASL＝

92线性表的检索 线性结构是数据元素间最常见的数据结构,基 于线性表的检索运算在各类程序中应用非常广泛 本节介绍三种在线性表上进行检索的方法,它们分 别是顺序检索、二分法检索与分块检索。为简化问 题,本节所介绍的检索方法均视为是基于静态查找 表上的操作

9.2 线性表的检索 线性结构是数据元素间最常见的数据结构，基 于线性表的检索运算在各类程序中应用非常广泛， 本节介绍三种在线性表上进行检索的方法，它们分 别是顺序检索、二分法检索与分块检索。为简化问 题，本节所介绍的检索方法均视为是基于静态查找 表上的操作

921顺序检索 从表的一端开始,顺序(逐个)扫描线性表, 依次将扫描到的结点关键字和给定值Key相比较,若 当前扫描到的结点关键字与Key相等,则检索成功; 若扫描结束后,仍未找到关键字等于Key的结点,则 检索失败。 存储结构:顺序存储或链式存储 本节介绍基于顺序表的顺序检索算法

9.2.1顺序检索 从表的一端开始，顺序（逐个）扫描线性表， 依次将扫描到的结点关键字和给定值Key相比较，若 当前扫描到的结点关键字与Key相等，则检索成功； 若扫描结束后，仍未找到关键字等于Key的结点，则 检索失败。 存储结构：顺序存储或链式存储 本节介绍基于顺序表的顺序检索算法

大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 /线性表检索用的头文件* /*文件名 seqlist. h #include # define maxsize100/预定义最大的数据域空间* typedef int datatype;/假设数据类型为整型 ty pede struct datatype data[maxsize];/此处假设数据元素只包含一个整 型的关键字域 nten;/线性表长度 } seqlist;/^预定义的顺序表类型*

/************************************/ /* 线性表检索用的头文件 */ /* 文件名:seqlist.h */ /************************************/ #include #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[maxsize]; /*此处假设数据元素只包含一个整 型的关键字域*/ int len; /*线性表长度*/ } seqlist; /*预定义的顺序表类型*/

算法9.1给出了基于顺序查找表的顺序检索方法。 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 顺序检索算法文件名 s search.c* /函数名: seqsearch10、 seqsearch20 大大大大火大大大大大大大大大大大大大大大大大大大大★大大大大大大火大大大大大大大大大大大大大大大大大 include"seqlist. h /-顺序查找的非递归实现--* int seqsearch 1(seqlist L, datatype key) i int k=L. len-1 while(k>=0 & I data[k!=key)k return (k);

算法9.1给出了基于顺序查找表的顺序检索方法。 /***************************************************/ /* 顺序检索算法 文件名:s_search.c */ /* 函数名: seqsearch1()、seqsearch2() */ /***************************************************/ #include "seqlist.h" /*--------顺序查找的非递归实现------*/ int seqsearch1(seqlist l,datatype key) { int k=l.len-1; while (k>=0 && l.data[k]!=key ) k--; return(k); }

-顺序查找的递归实现-- int seqsearch2 (seqlist I, int n, datatype key) int k=0 else if (I data[n]=key)k=n else k=seqsearch2(, n-1, key) return(k) 算法9.1线性表的顺序检索(顺序存储)

/*-------------顺序查找的递归实现----------*/ int seqsearch2(seqlist l,int n,datatype key) { int k=0; if (n==-1) k=-1; else if (l.data[n]==key) k=n; else k=seqsearch2(l,n-1,key); return(k); } 算法9.1 线性表的顺序检索（顺序存储）

算法分析 顺序检索的缺点是查找时间长。假设顺序表中每个 记录的查找概率相同,即P=1/n(i=0,1,…,n-1), 查找表中第个记录所需的进行的比较次数C=n-。因 此,顺序查找算法查找成功时的平均查找长度为 n-1 n-1 ASL seg ∑P.C1=∑=(n-1)=(n+1) 0 查找失败时,算法的平均查找长度为 ASI .n= n seg

顺序检索的缺点是查找时间长。假设顺序表中每个 记录的查找概率相同，即Pi=1/n（i=0，1，…，n-1）， 查找表中第i个记录所需的进行的比较次数Ci=n-i。因 此，顺序查找算法查找成功时的平均查找长度为： 算法分析：   − = − =  =  − = + 1 0 1 0 ( ) ( 1) / 2 1 n i n i i i n i n n ASLseq= P C 查找失败时，算法的平均查找长度为： n n n n i   = − = 1 0 1 ASLseq =

9.2.2二分法检索 分法检索又称为折半查找,采用二分法检索可以 大大提高查找效率,它要求线性表结点按其关键字从小 到大(或从大到小)按序排列并采用顺序存储结构。 采用二分搜索时,先求位于搜索区间正中的对象的 下标mid,用其关键码与给定值x比较: I[mid].Key=X,搜索成功; [mid].Key>ⅹ,把搜索区间缩小到表的前半 阝分,再继续进行对分搜索 I[mid].Key<ⅹ,把搜索区间缩小到表的后半 部分,再继续进行对分搜索

9.2.2二分法检索 二分法检索又称为折半查找，采用二分法检索可以 大大提高查找效率，它要求线性表结点按其关键字从小 到大（或从大到小）按序排列并采用顺序存储结构。 采用二分搜索时，先求位于搜索区间正中的对象的 下标mid，用其关键码与给定值x比较: ➢ l[mid]. Key = x，搜索成功； ➢ l[mid]. Key > x，把搜索区间缩小到表的前半 部分，再继续进行对分搜索； ➢ l[mid]. Key < x，把搜索区间缩小到表的后半 部分，再继续进行对分搜索