软件技术基础第03章查找.pptVIP

思考问题 数据存放在计算机中如何查找？ 查找方法有所不同吗？不同方法的查找效率有区别吗？ 基本的查找方式有几种？ 教学目标 了解有关查找的 基本概念 查找的主要算法 教学要求 通过本单元的学习，了解、掌握有关查找的： 基本概念 查找、平均查找长度 主要查找算法 顺序查找、折半查找、分块查找 哈希查找 本单元涉及的内容 第3章 3.1 基本的查找技术 3.2 哈希表技术 一、基本概念 查找 查找表 静态查找 动态查找 平均查找长度 查找 查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。 查找表 是一组待查数据元素的集合。 静态查找 是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。 动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。 平均查找长度 平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。 它是用来评价一个算法好坏的一个依据。 对含有n个数据元素的查找表，查找成功时的平均查找长度为： 基本的查找技术 顺序查找 折半查找 分块查找 1.顺序查找 算法思想： 最古老的算法。从第1个元素到最后1个元素，逐个进行比较。 查找表的存储结构 既适用于顺序存储结构 也适用于链式存储结构 算法描述 算法讨论 算法描述 查找操作步骤： step1 从第1个元素开始查找； step2 用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。 顺序查找算法 seq_search(int *item ,n , key ) { int i=0 ; while ( i n item[i] != key ) i++; /* 查找key的循环 */ if (item[i]= = key ) { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1);} } 顺序查找算法（改进算法） seq_search_adv(int *item ,n , key ) { int i=0 ; item[n]=key ; /* 设置哨兵 */ while ( item[i]!= key ) i++; /* 查找key */ if ( i n ) /* 如果 i = n，没找到 */ { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1); } } 注: 设置哨兵目的在于免去查找过程中每一步都要检测整个表是否查完 顺序查找算法中,执行频率最高的是while语句,改进后,可以节省近一半的时间 顺序查找算法主程序 #include “stdio.h” #define n 7 main() ｛　int key,loc=0; int a[10]={43,15,21,37,2,5,82}; printf(“Input key:”); scanf(“%d”,key); loc=s_search_adv(a,n,key); if (loc 0) printf(“loc=%d,key=%d\n”,loc,key); } 算法讨论 平均查找长度ASL在等概率的情况下 2.折半查找 算法思想： 将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 即通过一次比较，将查找区间缩小一半。 二分查找的先决条件是查找表中的数据元素必须有序。 算法描述 算法步骤： step1 首先确定整个查找区间的中间位置， mid = （ left + right ）/ 2 step2 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功； 若大于，则在后半区域继续进行二分查找； 若小于，则在前半区域继续进行二分查找。 对确定的缩小区域再按二分公式，重复上述步骤； 最后，得到结果： 要么，查找成功， 要么，查找失败。 存储结构 用一维数组存放。 折半查找算法举例 对给定数列（有序）{ 3，5，