数据结构》 第九章查找
《数据结构》 第九章 查找
第九章查找 第九章查找 内容和要求 査找的概念,顺序査找、二分法查找、分块查 找的概念和方法,二叉排序树、平衡二叉树的 查找,哈希表查找。要求获得有关静态和动态 环境下几种基本的查找方法和技术知识。掌握 顺序、二分法和分块查找的方法;了解哈希表 是一种基本的存储结构、哈希表的背景和基本 思路。掌握哈希表处理冲突的方法 重点 分法查找方法;哈希表的动态查找 第2页
第九章 查找 第2页 第九章 查 找 内容和要求 查找的概念，顺序查找、二分法查找、分块查 找的概念和方法，二叉排序树、平衡二叉树的 查找，哈希表查找。要求获得有关静态和动态 环境下几种基本的查找方法和技术知识。掌握 顺序、二分法和分块查找的方法；了解哈希表 是一种基本的存储结构、哈希表的背景和基本 思路。掌握哈希表处理冲突的方法。 重点 二分法查找方法；哈希表的动态查找
基本概念 第九章查找 査找表由同一类型的数据元素(或记录)构成的集合 静态査找表仅作查询与检索(统称为查找)工作的查找 表 动态査找表除作査询与检索之外,还需作诸如插入、删 除之类更新操作的查找表 查找在一个含有众多数据元素(或记录)的查找表中找出某个 “特定的”数据元素(或记录)的过程 关键字能够标识一个数据元素(或记录)的某个数据项的值。 当数据元素只有一个数据项时,其关键字即为该数据元素的值。 主关键字能唯一地标识一个记录的关键字 给定一个值k,在含有n个记录(或数据元素)的表中找出关键字等 于给定值k的记录,若找到,则査找成功,查找结果为给出整个 记录的信息,或指示该记录在查找表中的位置;若找不到,则查 找不成功,查找结果为NULL值或值0
第九章 查找 第3页 查找表 由同一类型的数据元素（或记录）构成 的集合 基本概念 静态查找表 仅作查询与检索（统称为查找）工作的查找 表。 动态查找表 除作查询与检索之外，还需作诸如插入、删 除之类更新操作的查找表。 查找 在一个含有众多数据元素（或记录）的查找表中找出某个 “特定的”数据元素（或记录）的过程。 关键字 能够标识一个数据元素（或记录）的某个数据项的值。 当数据元素只有一个数据项时，其关键字即为该数据元素的值。 主关键字 能唯一地标识一个记录的关键字。 给定一个值k，在含有n个记录(或数据元素)的表中找出关键字等 于给定值k的记录，若找到，则查找成功，查找结果为给出整个 记录的信息，或指示该记录在查找表中的位置；若找不到，则查 找不成功，查找结果为NULL值或值0
基本概念 第九章查找 查找操作主要是关键字的比较,故通常把查找过程中对关键一 字需要执行的平均比较次数(亦称平均査找长度)作为衡量 个查找算法效率优劣的标准。 平均査找长度为了确定记录在查找表中的位置,需和给定值进 行比较的关键字个数的期望值(平均值)称为查找算法在查找成功 时的平均查找长度( Average Search Length) 对于含有n个记录的表,查找成功时的平均查找长度为 ASL (9-1) 其中 P P:表中第个记录被查找的概率,有 找到表中其关键字与给定值相等的第个记录时,所需 要的比较次数 若无特别声明,均认为表中每个记录的概率均相等,即 P= P P
第九章 查找 第4页 查找操作主要是关键字的比较，故通常把查找过程中对关键 字需要执行的平均比较次数（亦称平均查找长度）作为衡量一 个查找算法效率优劣的标准。 基本概念 平均查找长度 为了确定记录在查找表中的位置，需和给定值进 行比较的关键字个数的期望值(平均值)称为查找算法在查找成功 时的平均查找长度(Average Search Length)。 对于含有n个记录的表，查找成功时的平均查找长度为 (9-1) 其中 Pi：表中第i个记录被查找的概率，有 ； Ci：找到表中其关键字与给定值相等的第i个记录时，所需 要的比较次数。 若无特别声明，均认为表中每个记录的概率均相等，即
约定和宏定义 第九章查找 宏定义 tdefine Eo( a b)((a)==(b)) #define lT( a b)((a)<(b)) #define Lo( a, b)((a) (y)) 注:宏定义随不同的数据类型,有所不同
第九章 查找 第5页 约定和宏定义 宏定义 #define EQ( a, b ) ((a) == (b)) #define LT( a, b ) ((a) < (b)) #define LQ( a, b ) ((a) <= (b)) 注：宏定义随不同的数据类型，有所不同
1、静态查找表 第九章查找 静态查找表的ADT 静态查找表是一种最简单的查找表 Specification ADT Static Search Table Elements:査找表中的数据元素类型相同,每一数据元素 都存在一个能唯一标识该元素的关键字 Structure:查找表中的n个数据元素具有相同类型,属于一 同一集合。数据元素之间不存在结构关系 Operation: Create(ST,n)生成操作:产生一个含用户给定的n个数据 元素的表ST Search(ST,K)查找函数:若表ST中存在其关键字等于给 定值K的数据元素,则函数值为该元素在表中的位 置;否则函数值为“空”。 Traverse(ST)输出操作:按某种次序输出表ST中所有数 据元素
第九章 查找 第6页 1、静 态 查 找 表 静态查找表的ADT 静态查找表是一种最简单的查找表。 Specification ADT Static_Search_Table Elements：查找表中的数据元素类型相同，每一数据元素 都存在一个能唯一标识该元素的关键字 Structure：查找表中的n个数据元素具有相同类型，属于 同一集合。数据元素之间不存在结构关系 Operation： Create(ST,n) 生成操作：产生一个含用户给定的n个数据 元素的表ST。 Search(ST,K) 查找函数: 若表ST中存在其关键字等于给 定值K的数据元素，则函数值为该元素在表中的位 置；否则函数值为“空”。 Traverse(ST) 输出操作：按某种次序输出表ST中所有数 据元素
+顺序(线性)表的查找一顺序查找 第九章查找 顺序(线性)表的查找是一种最简单的查找方法。它的 算法基本思想是: 从表的一端开始,顺序地扫描线性表,依次将扫描到的 关键字和给定值相比较,若当前扫描到的记录的关键字 与给定值相等,则查找成功,找到所查记录;若直至扫 描结束,仍未找到其关键字与给定值相等的记录,则查 一找不成功。 既适用于线性表的顺序存储结构,也适用于线性表的链 式存储结构。若使用单链表作存储结构时,扫描必须从第 一个结点开始。若以向量作存储结构,则可从前往后或从一 后往前进行扫描
第九章 查找 第7页 顺序(线性)表的查找——顺序查找 顺序（线性）表的查找是一种最简单的查找方法。它的 算法基本思想是： 从表的一端开始，顺序地扫描线性表，依次将扫描到的 关键字和给定值相比较，若当前扫描到的记录的关键字 与给定值相等，则查找成功，找到所查记录；若直至扫 描结束，仍未找到其关键字与给定值相等的记录，则查 找不成功。 既适用于线性表的顺序存储结构，也适用于线性表的链 式存储结构。若使用单链表作存储结构时，扫描必须从第 一个结点开始。若以向量作存储结构，则可从前往后或从 后往前进行扫描
顺序(线性)表的查找 第九章查找 顺序表的查找算法描述 typedef struct i ElemType elem[li int Length }ssTab1e; nt8 research(s9ab1est, keytype k)中的序号,i值为零表明查 /*K为给定值,返回为关键字等于K的记录在表st 找不成功*/ st,e1em[01.key=K;//设置监视赠 for( i=st length; !EQ( st elem[i]. key, key )il-- /从表尾开始向前扫描 七urni //返回找到的位置 }//算法9.1
第九章 查找 第8页 顺序表的查找算法描述 typedef struct { ElemType elem[]; int Length; }SSTable; 顺序（线性）表的查找 int seqsearch( SSTable st, keytype k ) {/*K为给定值，返回i为关键字等于K的记录在表st中的序号，i值为零表明查 找不成功*/ st.elem[0].key = K; //设置监视哨 for( i = st.length; !EQ( st.elem[i].key, key ); i--) //从表尾开始向前扫描 return i; //返回找到的位置 } //算法 9.1
顺序(线性)表的查找 第九章查找 算法性能分析 ASL=∑PC ASLsS=nP+(n-DP+.+2P-+P (9-2 若查找每个记录时是等概率,则有ASLs(n+1)2
第九章 查找 第9页 算法性能分析 ASLSS = nP1 + n − P2 + + 2Pn−1 + Pn ( 1) 若查找每个记录时是等概率，则有 ASLss=(n+1)/2 顺序（线性）表的查找 (9-2)
顺序(线性)表的查找 第九章查找 如果考虑到不成功的查找,则查找算法的平均查找长度应是 查找成功时的平均长度与查找不成功时的平均查找长度之和。若 假设查找成功与不成功的可能性相同,对每个记录的查找概率也 相等,即p=1。由于查找不成 功的比较次数总是n+1,故顺序查找的平均查找长度为 ASD Ss ∑(n-t+1)+n·(n+1) 2n j 72 n+1n+1 4 3 (n+1) 9-4) 4 第10页
第九章 查找 第10页 如果考虑到不成功的查找，则查找算法的平均查找长度应是 查找成功时的平均长度与查找不成功时的平均查找长度之和。若 假设查找成功与不成功的可能性相同，对每个记录的查找概率也 相等，即 。由于查找不成 功的比较次数总是n+1，故顺序查找的平均查找长度为 顺序（线性）表的查找