数据结构-ch9

《数据结构-ch9》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第九章查找主要内容.静态查找表及查找算法：顺序查找折半查找.动态查找表及查找算法：二叉排序树.哈希表及查找算法9.1基本概念9.2静态查找9.3动态查找9.4哈希表9.1基本概念p查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。p静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中;（2）检索某个特定元素的各种属性。则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。p动态查找表若在查找过程

2、中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。p关键字（Key）是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。p查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于

3、某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。p查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构为存储结构的各种查找算

4、法。p查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。也称为平均查找长度。比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。平均查找长度ASL定义为：n=åASLPCiii1=9.1静态查找9.2.1顺序查找p顺序查找的基本思想p顺序表的类型描述和查找算法p顺序表查找示例p顺序表查找效率分析p顺序查找适用范围p基本思想顺序查找是一种最简单的查找方法。其基本 思想是将查找表作为一个线性表，可以是顺序表， 也可以是链表。从表的一端开始，逐个把每条记 录的

5、关键字值与给定值k进行比较。若某个记录 关键字值与给定值k相等，则查找成功，返回找 到的记录位置。反之，若已查找到表的另一端， 仍未找到关键字值与给定值相等的记录，则查找 不成功，返回查找失败标志。(21,37,88,19,92,05,64,56,80,75,13)p顺序表的类型描述和查找算法typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时 //按实际长度分配，0号单元留空intlength;//表中元素个数}SSTable;intSearch(SSTableST,KeyTypek){//在

6、顺序表ST中顺序查找其关键字等于k的数据元素， //若找到，则函数值为该元素在表中的位置，否则为0 ST.elem[0].key=k;//设置"哨兵"for(i=ST.length;ST.elem[i].key!=k;--i);//从后往前查找 returni;//找不到时，i为0}//Searchp顺序表查找示例 顺序表(21,37,88,19,92,05,64,56,80,75,13) (1)顺序查找64(2)顺序查找60ST.elemi21378819920564568075136401234567891011ST.Leng

7、thK＝64ST.elemi60213788199205645680751301234567891011ST.LengthK＝60p效率分析®容易看出，在顺序表中进行(顺序)查找查找成功的平均查找长度为：若查找表中每个记录的查找概率相等，即则等概率查找时顺序查找的平均查找长度为®在顺序表中进行(顺序)查找查找不成功的平均查找长度为：n＋1p适用范围在下列两种情况下，只能采用顺序查找：Ø线性表为无序表，不论采用顺序还是链式存储结构，只能用顺序查找；Ø即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。9.1折半(对分)查找p基

8、本要求p基本思想p折半查找过程示例p折半查找算法描述p折半查找完整算法p折半查找算法时间复杂度分析p基本要求折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。p基本思想首先