数据结构第15,16次课-查找A,B.pptVIP

数据结构课程的内容 第8章 查找 (4)评估查找方法优劣的标准 8.2 静态查找 1.顺序查找（又称线性查找） 1、顺序查找（ Linear search，又称线性查找 ） （2）算法的改进： 讨论① 查不到怎么办？ 二、折半查找（又称二分查找或对分查找） 讨论① 若关键字不在表中，怎样得知和停止？ 平均每个数据的查找时间还要除以n，所以： 折半查找效率分析法2 三、静态树表的查找（自学） 四、分块查找（索引顺序查找） 查找步骤分两步进行： * 数据结构 计算机与信息学院 姜敏 8.1 基本概念 8.2 静态查找 8.3 动态查找 8.4 哈希查找 8.1 基本概念 定义 查找－查询特定元素是否在查找列表中。 (3) 目的 提高查找效率 (2) 实质 关键字的比较或匹配。 猜价格游戏：已知物品价格为1至9之间的整数，请按两种不同方式来猜物品价格。 6 一般用查找次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。 静态查找——只查找，不改变查找表的数据元素。 动态查找——既查找，又改变查找表内的数据元素。 (5) 分类 静态查找算法主要有： 1、顺序查找（线性查找） 2、二分查找（折半或对分查找） 3、分块查找（索引顺序查找） 4、静态树表的查找 定义：用逐一比较的办法顺序查找关键字。 i 例 1 2 3 4 5 6 7 8 9 10 11 5 63 59 21 17 56 64 45 80 38 92 找64 i i i i 顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？见下页之例; 对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性树结构如何顺序查找?可借助各种遍历操作！ 　 （1） 　已知顺序表元素存储在a [1-n] 中，要在其中查找关键字为k的某元素的位置，该如何编程？(找到返回位置，找不到返回0） int seqsrch( int a[], int n, int k ) { 　for(int i=1; i=n ;i++) 　 if( k == a[i] ) return i; 　return 0; } //每次循环比较两次 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。 i 例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数=5 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1 将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！ int Search_Seq( SSTable ST , KeyType key ){ //在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n很大时，查找时间将减少一半。 for( i=ST.length; ST.elem[ i ].key!=key; - - i ) ; //不要用for(i=n; i0; - -i) 或 for(i=1; i=n; i++) return i; //若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。 } // Search_Seq （2）改进算法： ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论② 查找效率怎样计算？ ——用平均查找长度ASL衡量。 讨论③ 如何计算ASL？ 分析： 查找第1个元素所需的