《数据结构》课程PPT教学课件（2012）第9章 查找 9.1 基本概念 9.2 静态查找表

数据结构课程的内容 线性结构（线性表、栈、队、串、数组） 逻辑结构 树结构 非线性结构 图结构 颜序结构 链式结构 数据结构： 物理（存储）结构 索引结构 散列结构 插入运算 删除运筧 数据运算 修改运算 查拢运算 排序运算 习

1 数据结构课程的内容

第9章查找 9.1基本概念 9.2静态查找表 9.3动态查找表 9.4哈希表 教材第8、11和12章省略，因《操作系统》课程会涉及

2 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 第9章 查找 教材第8、11和12章省略，因《操作系统》课程会涉及

9.1基本概念 是一种数据结构 查找表 由同一类型的数据元素（或记录)构成的集合。 查找 查询(Searching)特定元素是否在表中。 查找成功 若表中存在特定元素，称查找成功，应输出该记录； 查找不成功 否则，称查找不成功（也应输出失败标志或失败位置） 静态查找 只查找，不改变集合内的数据元素。 动态查找 既查找，又改变（增减）集合内的数据元素。 关键字 记录中某个数据项的值，可用来识别一个记录 (预先确定的记录的某种标志) 主关键字 可以唯一标识一个记录的关键字 例如“学号” 次关键字 识别若干记录的关键字 例如“女

3 9.1 基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志) ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” 是一种数据结构 ——识别若干记录的关键字

讨论： 讨论1：查找的过程是怎样的？ 给定一个值K,在含有个记录的文件中进行搜索，寻找 个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 讨论2：对查找表常用的操作有哪些？ “特定的”=关键 必 查询某个“特定的”数据元素是否在表中 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 冬.从查找表中删除一元素。 讨论3：有哪些查找方法？ 例如查字典 查找方法取决于表中数据的排列方式 针对静态查找表和动态查找表的查找方法也有所不同

4 讨论2：对查找表常用的操作有哪些？ ❖ 查询某个“特定的”数据元素是否在表中； ❖ 查询某个“特定的”数据元素的各种属性； ❖ 在查找表中插入一元素； ❖ 从查找表中删除一元素。 讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式; 讨论： 讨论1：查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找 一个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键 字

讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 ∑sc Average Search Length 其中： 统计意义上的 n是文件记录个数； 数学期望值 P是查找第i个记录的查找概率（通常取等概率，即P,=1/n); C是找到第个记录时所经历的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每 元素所需的比较次数之总和再取平均，即为 显然，ASL值越小，时间效率越高

5 讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 = =  n i ASL Pi Ci 1 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 统计意义上的 数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一 元素所需的比较次数之总和再取平均，即为 ASL。 显然，ASL值越小，时间效率越高。 Average Search Length

9.2静态查找表 针对静态查找表的查找算法主要有： 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找） 四、静态树表的查找 ADT StaticSearchTable 静态查找表的定义 数据对象D: (抽象数据类型) 参见教材P216 数据关系R: 基本操作P: ADT StaticSearchTable

6 针对静态查找表的查找算法主要有： 9.2 静态查找表 静态查找表的定义 （抽象数据类型） 参见教材P216 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找） 四、静态树表的查找 ADT StaticSearchTable { 数据对象D: 数据关系R： 基本操作P： } ADT StaticSearchTable

顺序查找(Linear search,又称线性查找) 顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直 接的办法。 冬对顺序结构如何线性查找？ 见下页之例或教材P216 ÷对单链表结构如何线性查找？ 从头指针始“顺藤摸瓜” 冬对非线性树结构如何顺序查找？ 借助各种遍历操作！ (1)顺序表的机内存储结构： typedef struct ElemType *elem; /表基址，0号单元留空。表容量为全部元素 int length;/表长，即表中数据元素个数 SSTable;

7 一、顺序查找（ Linear search，又称线性查找 ） （1）顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable; 顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直 接的办法。 ❖ 对顺序结构如何线性查找？ ❖ 对单链表结构如何线性查找？ ❖ 对非线性树结构如何顺序查找? 见下页之例或教材P216 从头指针始 “顺藤摸瓜” 借助各种遍历操作！

(2)算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”)， 这样可以加快执行速度。 例：若将待查找的特定值key存入顺序表的首部（如0号单 元)，并从后向前逐个比较，就不必担心“查不到”。 int Search_Seq(SSTable ST,KeyType key ) ST.elem[0/在顺序表ST中，查找关键字与key相同的元素； 若成二a甘位置信息否训返回0 for(=ST/设立哨兵，可免去查找过程中每一步都要检 还查找完毕。当n>1000时，查找时间将 测 return减 /不要用for(i=l;i0;-i 找得到=成功，返回值正好代表所我元素的位置！

8 int Search_Seq( SSTable ST , KeyType key ){ ST.elem[0].key =key; for( i=ST.length; ST.elem[ i ].key!=key; - - i ); return i; } // Search_Seq （2）算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”）， 这样可以加快执行速度。 例：若将待查找的特定值key存入顺序表的首部（如0号单 元），并从后向前逐个比较,就不必担心“查不到” 。 //在顺序表ST中，查找关键字与key相同的元素； 若成功，返回其位置信息，否则返回0 //设立哨兵，可免去查找过程中每一步都要检 测是否查找完毕。当n>1000时，查找时间将 减少一半。 //找不到=不成功，返回值必为i=0； 找得到=成功，返回值i正好代表所找元素的位置。 //不要用for(i=1; i0; - -i)

讨论1：查找失败怎么办？ 返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”， 就是将关键字送入未地址sT.elem[0].key使之结束，并返回i=0。 讨论2：查找效率怎样计算？ 用平均查找长度ASL衡量。 讨论3：如何计算ASL? 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； 未考虑查找不成功的情况：查 找哨兵所需的比较次数为n+1 查找第n个元素所需的比较次数为n; 总计全部比较次数为：1+2+.+n=(1+n)n/2 若求某一个元素的平均查找次数，还应当除以（等概率）， 即：ASL=(1+n)2,时间效率为O() 这是查找成功的情况

9 ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵” ， 就是将关键字送入末地址ST.elem[0].key使之结束，并返回 i=0。 讨论2：查找效率怎样计算？ ——用平均查找长度ASL衡量。 讨论1：查找失败怎么办？ 讨论3：如何计算ASL？ 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； . 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋.＋n = (1+n)n/2 未考虑查找不成功的情况：查 找哨兵所需的比较次数为n+1 这是查找成功的情况 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL＝（1＋n）/2 ，时间效率为O(n)

讨论4：顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL太大，时间效率太低。 如何改进？ 二、折半查找（又称二分查找或对分查找） 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将ky 与正中元素相比，若key小，则缩小至右半部内查找；再取其中 值比较，每次缩小1/2的范围，直到查找成功或失败为止。 冬对顺序表结构如何编程实现折半查找算法？ 见下页之例，或见教材（P219) ?·对单链表结构如何折半查找？ 无法实现！因全部元素的定位只能从头指针head开 始 冬对非线性（树）结构如何折半查找？ 可借助叉排序树来查找（属动态查找表形式）

10 二、折半查找（又称二分查找或对分查找） 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL 太大，时间效率太低。 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key 与正中元素相比，若key小，则缩小至右半部内查找；再取其中 值比较，每次缩小1/2的范围，直到查找成功或失败为止。 ❖ 对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P219） ❖ 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开 始 ❖ 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。 讨论4：顺序查找的特点： 如何改进？