第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)
静态查找表 顺序查找的特点 优点:算法简单,对表的结构或关键字是否有序无任 何要求。 缺点:查找效率低
静态查找表 ◼ 顺序查找的特点 优点：算法简单，对表的结构或关键字是否有序无任 何要求。 缺点：查找效率低