数据结构（C语言描述） 马秋菊 第8章查找

《数据结构（C语言描述） 马秋菊 第8章查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.1基本概念与术语8.2静态查找表8.3动态查找表8.4哈希表查找8.5小结与习题第八章查找1本章主要内容本章主要学习静态查找和动态查找方法。静态查找包括顺序查找、二分查找和分块索引查找等，动态查找包括二叉排序树、B树等。作为重点内容本章还介绍了哈希查找及相关知识。查找是数据结构中的重要操作，好的查找方法会大大提高执行效率。通过本章学习，应掌握以下内容：查找的有关概念；静态查找；动态查找；哈希查找。2查找就是指在给定的一组数据中对某个数值进行查询的过程。关键字是数据元素（或记录）中某个项或组合项的数值，它可以标识一个数据元素或记录。主关键字将能唯一确定一个数

2、据元素（或记录）的关键字。查找表是由具有相同类型的数据元素（或记录）组成的集合。分为静态查找表和动态查找表两大类。如果查找表中能够找到满足条件的记录，称为查找成功，否则称为查找不成功。8.1基本概念与术语3静态查找表：在对查找表进行操作时，不改变表的结构，只进行查找操作；动态查找表：在对查找表进行操作时，可以改变该查找表的结构，既可以进行查找操作，又可以进行插入、删除等操作。8.2静态查找表8.2.1静态查找表结构静态查找表是由数据元素组成的线性表。其存储结构分为顺序存储和链式存储两种。可以用顺序表或线性链表来表示静态查找表。48.2.1静态查找表结构type

3、defintKeyType;typedefstruct{KeyTypekey;………}ElemType;typedefstruct{ElemTypeelem[MAXSIZE+1]；intlength；}SST；typedefstructNODE{ElemTypedata；/*结点的数据域*/structNODE*next；/*指针域*/}NodeType；静态查找表的顺序存储结构定义静态查找表的链式存储结构定义58.2.2顺序查找顺序查找又称线性查找，它思路简单、容易实现，是一种最基本的查找方法。其查找过程为：从查找表的一端开始，逐个进行关键字与查找值的比较，

4、若某个记录的关键字值与给定值相等，则查找成功，给出数据元素在查找表中的位置；若将整个表查找完，仍未找到与给定值相同的关键字，则查找失败，给出提示信息。6【算法8.1】顺序查找intSearch_Seq(SSTST，KeyTypex){ST.elem[0].key=x;/*设置监护哨*/i=ST.length;while(ST.elem[i].key!=x)i--;/*返回找到记录的下标或者0(查找不成功)*/returni;}/*Search_Seq*/将查找过程中给定值和关键字比较的次数称为查找长度。通常用平均查找长度ASL来衡量查找算法的优劣。算法分析：7

5、平均查找长度：在查找成功时，平均查找长度ASL是指为确定数据元素在表中位置所进行关键字比较次数的期望值。对一个含n个数据元素的表，查找成功时ASL=Pi*Cin∑i=1Pi为表中第i个数据元素的查找概率，Ci为表中第i个数据元素的关键字与给定值x相等时，需要比较的次数。设查找表长度为n，查找元素x和表中第i个元素关键字相等时，需要比较的次数为n-i+1，则平均查找长度为：ASL=Pi*（n-i+1）n∑i=18设查找表中各元素的查找概率相等，即Pi=1/n，则上面的式子表示为：n∑i=1ASL=（n-i+1）=１─ｎｎ＋１───２当查找成功时，顺序查找的时间复

6、杂度就是O(n)。当查找失败时，关键字与给定值的比较次数总是n+1次。8.2.3二分查找二分查找，也称为折半查找，是对有序表进行的一种高效率的线性查找。有序表是指数据元素按给定的关键字已经是升序（或者是降序）的查找表。9假设各记录的关键字是由小到大排序的，算法的实现过程为：在待查找的有序表中，将中间元素首先与给定值进行比较，若相等，则表示查找成功；若给定值小于中间元素的关键字，则在左边的区域中继续查找；若给定值大于中间元素的关键字，则在右边的区域中继续查找。重复上述过程，直到查找成功或者查找失败，查找的过程随之结束。例在给定的序列A={6，13，17，20，2

7、4，28，30，36，39，44，48，51，55}中查找给定值13和52这两个数据。⑴查找关键字为13的过程106131720242830363944485155第一次low=1mid=7high=13因x<30，下一步继续在左半区查找，即：012345678910111213第二次low=1mid=3high=6因x<17，下一步继续在左半区查找，即：0123456789101112136131720242830363944485155613172024283036394448515511因x>6，下一步继续在右半区查找。此时，low=2,high=2,m

8、id=(2+2)/2=2。由于x=13