查找 ●查找就是在给定的DS中找出满足某种条件 的结点;若存在这样的结点,查找成功; 否则,查找失败。 ●找表是一组待查数据元素的集合。 ●静亦找是仅仅进行查询和检索操作,不 改变查找表中数据元素间的逻辑关系的查 找。 上一页 ●动态查找是除了进行查询和检索操作外,还对查 找表进行插入、删除操作的查找,动态地改变查找 停止放映 表中数据元素之间的逻辑关系。 页 第6页
下一页 上一页 停止放映 第 6 页 查找 ⚫ 查找 就是在给定的DS中找出满足某种条件 的结点；若存在这样的结点，查找成功； 否则，查找失败。 ⚫ 查找表 是一组待查数据元素的集合。 ⚫ 静态查找 是仅仅进行查询和检索操作，不 改变查找表中数据元素间的逻辑关系的查 找。 ⚫ 动态查找 是除了进行查询和检索操作外，还对查 找表进行插入、删除操作的查找，动态地改变查找 表中数据元素之间的逻辑关系
平均查找长度 平均查找长度( ASL-Average Search Length) 在查找过程中,对每个结点记录中的关键字要进行反复 比较,以确定其位置。因此,与关键字进行比较的平 均次数,就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ●对含有n个数据元素的查找表,查找成功时的平均查找 长度为: ASL=∑Pi米Ci 上一页 其中: 停止放映 Ci为查找第i个数据元素时需比较的次数=1 Pi为查找表中第i个数据元素的概率,且∑ 页 显然,C随查找过程及DS的不同而各异。 第7页
下一页 上一页 停止放映 第 7 页 平均查找长度 ⚫ 平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复 比较，以确定其位置。因此，与关键字进行比较的平 均次数，就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ⚫ 对含有n个数据元素的查找表，查找成功时的平均查找 长度为： ASL = Pi * Ci 其中： Pi 为查找表中第i个数据元素的概率，且 Pi = 1 Ci为查找第i个数据元素时需比较的次数。 显然，Ci随查找过程及DS的不同而各异。 i=1 n i=1 n
、主要查找算法 顺序查找 折半查找 分块查找 树表查找 上一页 哈希查找 停止放映 页 第8页
下一页 上一页 停止放映 第 8 页 二、主要查找算法 •顺序查找 •折半查找 •分块查找 •树表查找 •哈希查找
1、顺序查找 ●顺序查找是最简单、最普通的查找方法。 ●查找步骤: stepl从第1个元素开始查找; step2用待查关键字值与各结点(记录)的 关键字值逐个迸行比较;若找到相等的结点, 则查找成功;否则,查找失败。 ●查找表的存储结构: 上一页 既适用于顺序存储结构 停止放映 也适用于链式存储结构 页 第9页
下一页 上一页 停止放映 第 9 页 1、顺序查找 ⚫ 顺序查找是最简单、最普通的查找方法。 ⚫ 查找步骤： –step1 从第1个元素开始查找； –step2 用待查关键字值与各结点（记录）的 关键字值逐个进行比较；若找到相等的结点， 则查找成功；否则，查找失败。 ⚫ 查找表的存储结构： –既适用于顺序存储结构 –也适用于链式存储结构
顺序查找算法3-1 seg search(item, n, key int *item, n, key int 1=0 while(i<n&& item[i]!=key 1+t if (item[i]== key printf(“查找成功!n”); return(i);} 上一页 e⊥se 停止放映 printf(“查找失败!ln”); return(-1);} 页 第10页
下一页 上一页 停止放映 第 10 页 顺序查找算法3-1 seq_search(item , n , key ) int *item ,n , key ; { int i=0 ; while ( i < n && item[i] != key ) i++; if (item[i]= = key ) { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1);} }