计算机专业基础课《数据结构》课程PPT教学课件（3/3，9-12章）

第9章查找(5~6学时 静态查找表 顺序表的查找 有序表的查找 索引顺序表的查找 动态查找表 二叉排序树 平衡二叉树 散列表

第9章 查找（5～6学时） ◼ 静态查找表 顺序表的查找 有序表的查找 索引顺序表的查找 ◼ 动态查找表 二叉排序树 平衡二叉树 ◼ 散列表

第9章查找 基本概念 查找:根据给定的某个值,在査找表中确定个其关键字等于给定 值的记录或数据元素。 关键字:是记录或数据元素中某个数据项的值 (主关键字:唯标识;次关键字:标识若干个。) 查找成功:若表中存在这样的一个记录 查找不成功:若表中不存在关键字等于给定值的记录。 查找表:由同一类型的数据元素构成的集合。 静态查找表:若对查找表只作査找操作,则此类査找表称为静态査 找表。 边态查找表:若在査找的过程中同时迸行插入或删除,则此类表称 为动态查找表

第9章 查找 ◼ 基本概念 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定 值的记录或数据元素。 关键字：是记录或数据元素中某个数据项的值。 （主关键字：唯一标识；次关键字：标识若干个。） 查找成功：若表中存在这样的一个记录。 查找不成功：若表中不存在关键字等于给定值的记录。 查找表：由同一类型的数据元素构成的集合。 静态查找表：若对查找表只作查找操作，则此类查找表称为静态查 找表。 动态查找表：若在查找的过程中同时进行插入或删除，则此类表称 为动态查找表

第9章查找 平均查找长度ASL( Average Search Length): 为确定记录在查找表中的位置,需和给定值进 行比较的关键字个数的期望值称为查找算法在成功 时的平均查找长度。 ASL=ΣpC j=1~n 其中:n:结点个数 ρ查找第个结点的概率(等概率) G找到第个结点所需要的比较次数 以其关键字和给定值进行过比较的记录个数的平均值作为衡量查找 算法好坏的依据)

第9章 查找 平均查找长度ASL(Average Search Length)： 为确定记录在查找表中的位置，需和给定值进 行比较的关键字个数的期望值称为查找算法在成功 时的平均查找长度。 ASL=∑pici i=1～n 其中：n：结点个数 pi :查找第i个结点的概率（等概率） ci :找到第i个结点所需要的比较次数 (以其关键字和给定值进行过比较的记录个数的平均值作为衡量查找 算法好坏的依据)

静态查找表 顺序表的查找 基本思想:从表的一端开始,顺序扫描线性表,依次将扫描到的结 点关键字和给定值相比较,若当前扫描到的结点关键字 与相等,则查找成功;若扫描结束后,仍未找到关键字 等于的结点,则查找不成功。(该法可用于顺序存储结 构或链式存储结构) (参见:P216算法9.1) 查找成功的平均查找长度 ASLss-2p =1/n2(n-i+1)=(n+1)2 顺序查找的平均查找长度 ASL=1/(2n)Σ(n-i+1)+n(n+1))=3/4·(n+1)

静态查找表 ◼ 顺序表的查找 基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结 点关键字和给定值相比较，若当前扫描到的结点关键字 与相等，则查找成功；若扫描结束后，仍未找到关键字 等于的结点，则查找不成功。（该法可用于顺序存储结 构或链式存储结构） （参见：P216-算法9.1） 查找成功的平均查找长度： ASLss=∑pici=1/n∑(n-i+1)=(n+1)/2 顺序查找的平均查找长度： ASL=1/(2n)(∑(n-i+1)+n(n+1))=3/4· (n+1)

静态查找表 顺序查找的特点 优点:算法简单,对表的结构或关键字是否有序无任 何要求。 缺点:查找效率低

静态查找表 ◼ 顺序查找的特点 优点：算法简单，对表的结构或关键字是否有序无任 何要求。 缺点：查找效率低

静态查找表 有序表的查找 折半查找(二分查找):先确定待查记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。 (条件:(1)表中数据的关键字有序 (2)表是顺序存储结构) (参见:P219)

静态查找表 ◼ 有序表的查找 折半查找（二分查找）：先确定待查记录所在的范围， 然后逐步缩小范围直到找到或找不到该记录为止。 （条件： （1）表中数据的关键字有序 （2）表是顺序存储结构 ） （参见：P219）

静态查找表 折半查找的算法 int Search Bin(SSTable St, Key Type key) i low=l; high-STlength; while(low<high i mid=(low+high)/2 if (eQ(key, STelem(mid].key)) return mid Ise if(t(key, STelem[mid]. key)) high=mid-1 else low=mid+1

静态查找表 ◼ 折半查找的算法 int Search_Bin(SSTable ST, KeyType key) { low=1; high=ST.length; while (low<high) { mid=(low+high)/2; if (EQ(key, ST.elem[mid].key)) return mid; else if(LT(key, ST.elem[mid].key)) high=mid-1; else low=mid+1; } }

静态查找表 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为log2n+1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过|og2n+1 成功平均查找长度: ASL=Σpc=1n2j.21=(n+1)n*og2(n+1)-1 (当n>50时) ASlbs=log2(n+1)-1

静态查找表 ◼ 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为 log2n +1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过 log2n +1 成功平均查找长度： ASLbs= ∑pici=1/n∑j.2j-1=(n+1)/n*log2 (n+1)-1 （当n>50时） ASLbs=log2 (n+1)-1

静态查找表 索引顺序表的查找(分块查找) (是顺序查找的一种改进。在此查找方法中,除表本身外,尚需 建立一个索引表。索引表按关键字有序。) 索引表 关键字项:其值为该子表内的最大关键字。 指针项:指示该子表的第一个记录在表中位置。 (参见:P225-图96) 分块查找过程 (1)先确定待查记录所在的块(子表),可采用顺序查找或折 半查找 (2)然后在块中顺序查找

静态查找表 ◼ 索引顺序表的查找（分块查找） （是顺序查找的一种改进。在此查找方法中，除表本身外，尚需 建立一个索引表。索引表按关键字有序。） ◼ 索引表 关键字项：其值为该子表内的最大关键字。 指针项：指示该子表的第一个记录在表中位置。 （参见：P225-图9.6） 分块查找过程： （1）先确定待查记录所在的块（子表），可采用顺序查找或折 半查找。 （2）然后在块中顺序查找

静态查找表 分块查找的算法即为折半查找或顺序查找的简单组合。 分块查找的平均查找长度为 aslbs=lb 其中:Lb:为査找索引表确定所在块的平均查找长度。 为在块中查找元素的平均查找长度。 若用顺序查找确定所在块,则 ASLb=(b+1)/2+(s+1)2=(n/s+s)/2+1 若用分块查找确定所在块,则 ASLbslog (n/s+1)+s/2 -般情况下:b=「ns

静态查找表 分块查找的算法即为折半查找或顺序查找的简单组合。 分块查找的平均查找长度为： ASLbs=Lb+Lw 其中： Lb：为查找索引表确定所在块的平均查找长度。 Lw：为在块中查找元素的平均查找长度。 若用顺序查找确定所在块，则： ASLbs=(b+1)/2+(s+1)/2=(n/s+s)/2+1 若用分块查找确定所在块，则： ASLbs≈log2 (n/s+1)+s/2 一般情况下：b= n/s s=√n