数据结构第9章VIP免费

9.1查找的基本概念9.2静态查找表——基于线性表的查找法9.3动态查找表——基于树表的查找法9.4哈希表——计算式查找法第9章查找查找和排序是数据处理系统中最重要的两个操作；其次是插入、删除操作；讨论查找、排序，不可避免要涉及文件、记录、关键字等概念。文件——查找表，是由同一类型的数据元素(记录)构成的集合记录——构成文件的数据元素，是文件中可存取的数据的基本单位字段——数据项，数据的最小单位关键字——某个可以用来标识记录的数据项主关键字——某个可以用来唯一标识记录的数据项次关键字——可以用来识别若干记录的数据项D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01严蔚敏数据结构001………………………课程号课程名教师课程类别课程安排表文件记录数据项主关键字次关键字对文件经常进行的操作有:1)查询某个“特定”的数据元素是否存在4)对数据元素进行排序2)插入某个数据元素3)删除某个数据元素查找算法排序算法不管何种操作，都遵循一个重要的性质:都是对主关键字操作查找表由同一类型的数据元素（记录）构成的集合。查找的定义给定一个值key，在含有n个记录的表中找出关键字等于key的记录。若找到,则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。1.查找的基本概念采用何种查找方法?(1)使用哪种数据结构来表示“表”,即表中记录是按何种方式组织的。(2)表中关键字的次序。是对无序集合查找还是对有序集合查找?静态查找表(StaticSearchTable)：查询某个特定的元素是否在表中；检索某个特定的元素的各种属性。动态查找表(DynamicSearchTable)：若在查找的同时对表做修改运算(如插入和删除)。2.查找操作的性能分析基本操作：将记录的关键字和给定值进行比较。平均查找长度ASL(AverageSearchLength)：为确定数据元素在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。n1iiicpASLPi为查找表中第i个记录的概率，Ci为找到第i个记录时，和给定值已经进行过比较的关键字个数。在表的组织方式中,线性表是最简单的一种。三种在线性表上进行查找的方法：(1)顺序查找(2)折半查找（二分查找）(3)索引顺序表查找（分块查找）。因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的。9.1静态查找表1.顺序查找顺序查找法的特点：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。开始:39158106724第1次比较:39158106724i=0第2次比较:39158106724i=1第3次比较:39158106724i=2第4次比较:39158106724i=3第5次比较:39158106724i=4查找成功,返回序号4例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为8的元素。typedefstruct{ElemType*elem;intlength;}SSTable;intSearch_Seq(SStableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}for(i=ST.length;i>0&&!EQ(ST.elem[i].key,key);--i);111111(1)(1)2nnnSSiiiiiiASLPCCninnn顺序查找的平均查找长度ASL：假设表长度为n，那么查找到第i个记录时，和给定值已进行过比较的关键字个数为n-i+1，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：1113(1)(1)(1)224nSSiASLninnnnn查找不成功时的平均查找长度：假设查找成功和不成功的可能性相等，且每个记录的查找概率也相等，即Pi=1/(2n)，则2.折半查找法（二分法查找法）要求待查找的表必须是按关键字大小有序排列的顺序表。折半查找的思想：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。折半查找5，13，19，21，37，56，64，75，80，88，92lowh...