数据结构（C语言）下ppt课件.ppt

《数据结构（C语言）下ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言）下第8章查找（时间：3次课，6学时）第8章查找教学提示：前几章介绍了基本数据结构线性表、树和图结构，并讨论了这些结构的存储方式，以及定义在这些结构上的基本运算。本章将讨论数据结构中的另一种常用的重要技术——查找表。在非数值运算中，数据存储量很大，为了在大量信息中找到某些数据，需要用到查找技术。在数据处理过程中，查找的效率直接影响到算法的优劣，因而查找是数据处理中重要的基本运算之一。教学目标：本章将针对数据的不同组织形式来讨论几种常用的查找方法，用户应学会根据查找算法进行分析，比较各种查找技术的效率，并掌握各种查找算法的使用方法。第8章查找8.1查找的基

2、本概念8.2线性表的查找8.3树结构的查找8.4散列技术8.5上机实习8.6习题8.1查找的基本概念查找表是一种以集合为逻辑结构，以查找运算为基本操作的数据结构。下面给出有关查找的基本概念。集合：具有相同类型的数据元素(或记录)构成的整体，被称为集合。查找表：由同一类型的数据元素(或记录)构成的集合，可以利用任意存储结构表示。关键字：数据元素中某个数据项的值，用它可以标识列表中的一个或一组数据元素。查找：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素或记录，并返回该数据元素在查找表中的位置。对查找表经常进行的操作有：①查找某个“特定的”数据元素是否

3、在查找表中；②检索某个“特定的”数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删除某个数据元素。1．抽象数据类型静态查找表的定义数据对象D：D是具有相同特性的数据元素(或记录)的集合、各个数据元素均含有类型相同、可惟一标识数据元素的关键字。数据关系R：数据元素(或记录)同属一个集合。8.1查找的基本概念(2)基本操作：Create(ST，n)：构造一个含有n个数据元素的静态查找表。Destroy(ST)：当静态查找表ST存在时，销毁表ST。Search(ST,key)：静态查找表ST存在。2．抽象数据类型动态查找表的定义数据对象D：D是具有相同特性的数据

4、元素(或记录)的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。数据关系R：数据元素(或记录)同属一个集合。基本操作：InitDSTable(DT)：构造一个空的动态查找表。DestroyDSTable(DT)：当动态查找表DT存在时，销毁表DT。SearchDSTable(DT,key)：动态查找表DT存在。InsertDSTable(DT,e)：动态查找表DT存在，e为待插入的数据元素，若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(DT,key)：动态查找表DT存在。8.1查找的基本概念(3)3．平均查找长

5、度为确定数据元素在查找表中的位置，需与给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度(AverageSearchLength)，简称ASL。8.2线性表的查找8.2.1顺序查找8.2.2二分查找8.2.3分块查找8.2.1顺序查找顺序查找法的查找特点是，用所给关键字与线性表中各元素的关键字逐个比较。下面给出顺序结构有关数据类型的定义：#definemaxsize100;/*查找表的最大容量*/typedefstruct{KeyTypekey;/*关键字*/ElemTypedata;/*其他数据*/}rec;typedefstruct{reci

6、tem[maxsize-1];intlengh;/*最后一个数据元素的下标*/}SqTable;顺序查找的实现过程：从表中最后一个记录开始，从后向前逐个进行记录的关键字与给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。8.2.1顺序查找(2)查找过程的算法(算法8.1)描述如下:intSeqSearch(SqTableL,keytypek);{L.item[0].key=k;i=L.length;while(L.item[i].key!=k)i--;ret

7、urn(i);}这里使用“监视哨”，即L.item[0].key=k以便控制循环最多执行到数组中下标为0的元素位置，可以起到防止越界的作用，从而提高查找效率。8.2.2二分查找二分查找法又称为折半查找法。这种方法要求待查找的查找表必须是按关键字大小有序排列的顺序表。查找的基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，进一步查找前子表，否则进一步查找后子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为