《数据结构》课件(c语言)第09章

《《数据结构》课件(c语言)第09章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第九章查找第九章查找内容和要求查找的概念，顺序查找、二分法查找、分块查找的概念和方法，二叉排序树、平衡二叉树的查找，哈希表查找。要求获得有关静态和动态环境下几种基本的查找方法和技术知识。掌握顺序、二分法和分块查找的方法；了解哈希表是一种基本的存储结构、哈希表的背景和基本思路。掌握哈希表处理冲突的方法。重点二分法查找方法；哈希表的动态查找。2查找表由同一类型的数据元素（或记录）构成的集合基本概念静态查找表仅作查询与检索（统称为查找）工作的查找表。动态查找表除作查询与检索之外，还需作诸如插入、删除之类更新操作的查找表。查找在一个含有众多数据元素（或记录）的查找表中找出某个“

2、特定的”数据元素（或记录）的过程。关键字能够标识一个数据元素（或记录）的某个数据项的值。当数据元素只有一个数据项时，其关键字即为该数据元素的值。主关键字能唯一地标识一个记录的关键字。给定一个值k，在含有n个记录(或数据元素)的表中找出关键字等于给定值k的记录，若找到，则查找成功，查找结果为给出整个记录的信息，或指示该记录在查找表中的位置；若找不到，则查找不成功，查找结果为NULL值或值0。3查找操作主要是关键字的比较，故通常把查找过程中对关键字需要执行的平均比较次数（亦称平均查找长度）作为衡量一个查找算法效率优劣的标准。基本概念平均查找长度为了确定记录在查找表中的位置，需和给定值进

3、行比较的关键字个数的期望值(平均值)称为查找算法在查找成功时的平均查找长度(AverageSearchLength)。对于含有n个记录的表，查找成功时的平均查找长度为(9-1)其中Pi：表中第i个记录被查找的概率，有；Ci：找到表中其关键字与给定值相等的第i个记录时，所需要的比较次数。若无特别声明，均认为表中每个记录的概率均相等，即4约定和宏定义宏定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))注：宏定义随不同的数据类型，有所不同。51、静态查找表静态查找表的ADT静态查找表是一种最简

4、单的查找表。SpecificationADTStatic_Search_TableElements：查找表中的数据元素类型相同，每一数据元素都存在一个能唯一标识该元素的关键字Structure：查找表中的n个数据元素具有相同类型，属于同一集合。数据元素之间不存在结构关系Operation：Create(ST,n)生成操作：产生一个含用户给定的n个数据元素的表ST。Search(ST,K)查找函数:若表ST中存在其关键字等于给定值K的数据元素，则函数值为该元素在表中的位置；否则函数值为“空”。Traverse(ST)输出操作：按某种次序输出表ST中所有数据元素。6顺序(线性)表的查找

5、——顺序查找顺序（线性）表的查找是一种最简单的查找方法。它的算法基本思想是：从表的一端开始，顺序地扫描线性表，依次将扫描到的关键字和给定值相比较，若当前扫描到的记录的关键字与给定值相等，则查找成功，找到所查记录；若直至扫描结束，仍未找到其关键字与给定值相等的记录，则查找不成功。既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。若使用单链表作存储结构时，扫描必须从第一个结点开始。若以向量作存储结构，则可从前往后或从后往前进行扫描。7顺序表的查找算法描述typedefstruct{ElemTypeelem[];intLength;}SSTable;顺序（线性）表的查找ints

6、eqsearch(SSTablest,keytypek){/*K为给定值，返回i为关键字等于K的记录在表st中的序号，i值为零表明查找不成功*/st.elem[0].key=K;//设置监视哨for(i=st.length;!EQ(st.elem[i].key,key);i--)//从表尾开始向前扫描returni;//返回找到的位置}//算法9.18算法性能分析若查找每个记录时是等概率，则有ASLss=(n+1)/2顺序（线性）表的查找(9-2)9如果考虑到不成功的查找，则查找算法的平均查找长度应是查找成功时的平均长度与查找不成功时的平均查找长度之和。若假设查找成功与不成功的可能

7、性相同，对每个记录的查找概率也相等，即。由于查找不成功的比较次数总是n+1，故顺序查找的平均查找长度为顺序（线性）表的查找10(2)当表中各个记录的查找概率互不相等时，为了提高查找效率，宜将诸记录先按查找概率由小到大进行排列（式(9-2)在P1≤P2≤···≤Pn-1≤Pn时达到极小值）；说明：(1)顺序查找算法简单，且对表的结构无任何要求（无论按向量还是链表结构，无论记录间是否按关键字有序排列），故此算法适应面广。但当n>>1时，查找效率随n越大而越低。顺序（线性）