欢迎来到天天文库
浏览记录
ID：70408811
大小：2.95 MB
页数：90页
时间：2021-11-22
《数据结构第九章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9章查找学习目的与要求：1．熟练掌握顺序表和有序表的查找方法；2．熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；3．熟练掌握二叉排序树的构造和查找方法；4．掌握平衡树二叉的平衡方法；5．理解B-树和B+树的特点以及它们的建树过程；6．熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；7．掌握计算各种查找方法在等概率情况下查找成功时的平均查找长度。基本概念1、查找表：是由同一类型的数据元素（或记录）构成的集合。对查找表经常进行的操作：（1）查询某个“特定的”数据元素是否在表中；（2）检索某个“特定的”元素
2、的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删除某个数据元素。2、静态查找表：对查找表只作前两种操作的查找表，称作~。4、关键字：是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字可以惟一地标识一个记录，则称此关键字为主关键字；反之，称用以识别若干记录的关键字为次关键字。3、动态查找表：若在查找过程中同时插入表中不存在的数据元素，或删除表中的某个数据元素，这样的查找表称作~。5、查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在一个这样的记录，则称查找是成功
3、的，否则称查找不成功。基本内容一、静态查找表二、动态查找表三、哈希表四、本章小结一、静态查找表1.顺序表的查找(SequentialSearch)顺序存储结构的定义：typedefstruct{ElemType*elem;//建表时按实际长度分配,0号单元留空intlength;//表长度}SSTable;顺序查找的查找过程：从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，给出该元素在表中的位置；否则，若直到第一个（或最后一个）记录，其关键字和给定值比较都不等，则查找不成功。
4、算法描述如下：intSearch_Seq(SSTableST,KeyTypekey){//在顺序ST中查找关键字等于key的数据元素。inti；ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key);--i);returni;//返回0则查找失败}0单元作为监视哨作用：减少判断，提高查找效率位置：低下标或高下标处。特点：算法简单且适用面广。对表的结构无要求：顺序存储或链表存储都可以对关键字是否有序无要求缺点：平均查找长度较大性能分析：衡量算法好坏的量度时间复杂度空间复杂度其它性能：平均查找长
5、度平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度（ASL）。对n个记录进行查找时，平均查找长度为：
此文档下载收益归作者所有
