数据结构 教学课件作者 戴敏8

数数 据据 结结 构构第第8章章b查查 找找本章目标本章目标8.1 查找的基本概念查找的基本概念8.2 线性表的查找线性表的查找8.3 树表的查找树表的查找8.4 散列表的查找散列表的查找 3 38.1 查找的基本概念查找的基本概念集合的定义和表示集合的定义和表示b前面几章中我们已经学习了前面几章中我们已经学习了3种数据结构种数据结构线性结构、树、图线性结构、树、图b从本章起，我们学习最后一种数据结构从本章起，我们学习最后一种数据结构集合结构集合结构5 5b集合集合(collection)是由同一类型的数据元素是由同一类型的数据元素(或纪录或纪录)组成的群集组成的群集b由于集合中的数据元素之间存在着松散的关由于集合中的数据元素之间存在着松散的关系系(松耦合关系松耦合关系)，因此集合是一种灵活的数，因此集合是一种灵活的数据结构据结构集合的定义和表示集合的定义和表示 线性结构中的数据元素是一对一的关系线性结构中的数据元素是一对一的关系 树中的数据元素是一对多的关系树中的数据元素是一对多的关系 图中的数据元素是多对多的关系图中的数据元素是多对多的关系 集合中的数据元素仅存在着集合中的数据元素仅存在着“同属一个集合同属一个集合”的关的关系系6 6集合的表示集合的表示 集合在数学中常用右图表示，集合在数学中常用右图表示，其中的每个圆点代表一个数其中的每个圆点代表一个数据元素。这里的数据元素可据元素。这里的数据元素可以是一个简单的数据类型，以是一个简单的数据类型，如如int、char等，但更经常的是复杂数据类型，如等，但更经常的是复杂数据类型，如class、struct等。等。在实际应用中，数据元素通常是数据库中的纪在实际应用中，数据元素通常是数据库中的纪录录(records)，而集合则是这些记录的集合，即而集合则是这些记录的集合，即数据库中的表数据库中的表(tables)。7 7集合的表示集合的表示b一个数据元素可由若干个数据项一个数据元素可由若干个数据项(data items)组成。数据项组成。数据项是数据的不可分割的最小单位是数据的不可分割的最小单位。例如，每个学生纪录由若。例如，每个学生纪录由若干列干列(columns)组成，列就是学生纪录的数据项，每一列组成，列就是学生纪录的数据项，每一列描述了学生某一方面的特征或属性描述了学生某一方面的特征或属性学号学号 姓名姓名 性别性别 籍贯籍贯 电电 话话 通通 讯讯 地地 址址 01 张三张三 男男 长沙长沙 8639000 麓山南路麓山南路327号号 02 李四李四 男男 北京北京 23456789 学院路学院路435号号 03 王五王五 女女 广州广州 30472589 天河路天河路478号号 04 赵六赵六 男男 上海上海 41237568 南京路南京路1563号号 05 钱七钱七 女女 南京南京 5013472 南京大学南京大学 06 刘八刘八 女女 武汉武汉 61543726 武汉大学武汉大学 07 朱九朱九 男男 昆明昆明 4089651 云南大学云南大学 08 孙十孙十 女女 杭州杭州 6154372 西湖路西湖路635号号 8 8集合的存储结构集合的存储结构b集合这种数据结构在计算机中如何表示？它采用什么集合这种数据结构在计算机中如何表示？它采用什么样的存储结构？样的存储结构？b由于计算机中数据的存储结构只有两种：顺序存储结由于计算机中数据的存储结构只有两种：顺序存储结构和链式存储结构。因此集合的存储结构也不外乎这构和链式存储结构。因此集合的存储结构也不外乎这两种两种b我们已经学习了顺序表，线性链表（如单链表），树我们已经学习了顺序表，线性链表（如单链表），树的二叉链表等存储结构。应该说这些存储结构都可以的二叉链表等存储结构。应该说这些存储结构都可以作为集合来存放数据元素。所以，我们没有必要再寻作为集合来存放数据元素。所以，我们没有必要再寻求一种新的存储结构存放集合中的元素求一种新的存储结构存放集合中的元素b换句话说，换句话说，顺序表、线性链表、二叉链表等存储结构顺序表、线性链表、二叉链表等存储结构从广义上讲都是集合，其中每个元素或结点代表一条从广义上讲都是集合，其中每个元素或结点代表一条纪录纪录9 9关键字与查找关键字与查找b查找是按关键字进行的查找是按关键字进行的b所谓关键字所谓关键字(key)是数据元素是数据元素(或记录或记录)中的某个数中的某个数据项或某些数据项的组合，用它可以据项或某些数据项的组合，用它可以唯一标识唯一标识一一个数据元素个数据元素(或纪录或纪录)b任意两个数据元素的关键字都不能相同任意两个数据元素的关键字都不能相同b例如一条学生记录包含学号、姓名、性别、籍贯、例如一条学生记录包含学号、姓名、性别、籍贯、电话、通讯地址等数据项。有些数据项不能唯一电话、通讯地址等数据项。有些数据项不能唯一标识一个数据元素，而有的则可以。例如，姓名标识一个数据元素，而有的则可以。例如，姓名就不能唯一标识一条纪录就不能唯一标识一条纪录(因有同名的人因有同名的人)，而学，而学号则可以唯一标识一条纪录号则可以唯一标识一条纪录(每个学生学号是唯一每个学生学号是唯一的，不能相同的，不能相同)1010查找的定义查找的定义b查找查找(find)，也称为检索也称为检索(retrieve)或搜索或搜索(search)，就是根据给定值就是根据给定值k，在一个集合在一个集合(或表或表)中查找出其中查找出其关键字等于关键字等于k的数据元素的数据元素(或纪录或纪录)，若集合中有这样，若集合中有这样的元素，则查找成功，并返回整个数据元素的元素，则查找成功，并返回整个数据元素(或纪录或纪录)或指出该元素在表中的位置；若表中不存在这样的记或指出该元素在表中的位置；若表中不存在这样的记录，则称查找失败，并作相应处理录，则称查找失败，并作相应处理b动态集合动态集合(dynamic collection)在对集合中的元素进在对集合中的元素进行查找时，若集合中不存在给定值行查找时，若集合中不存在给定值k，那么我们就要那么我们就要将它插入集合中；也可以执行删除元素的操作，这样将它插入集合中；也可以执行删除元素的操作，这样的集合叫动态集合的集合叫动态集合b静态集合静态集合(static collection)对集合只能做查找，不对集合只能做查找，不能做插入或删除元素的操作，只返回查找成功还是失能做插入或删除元素的操作，只返回查找成功还是失败的结果，这样的集合叫静态集合败的结果，这样的集合叫静态集合1111平均查找长度平均查找长度(ASL)b查找运算的基本操作是关键字的比较，所以，通查找运算的基本操作是关键字的比较，所以，通常把查找过程中对关键字执行的平均比较次数常把查找过程中对关键字执行的平均比较次数(也也称为称为平均查找长度平均查找长度 average search length)作作为衡量一个查找算法效率优劣的标准为衡量一个查找算法效率优劣的标准b对于一个含有对于一个含有n个元素的集合个元素的集合(或表或表)，查找成功时，查找成功时的平均查找长度可表示为的平均查找长度可表示为=niiicpASL1b其中其中pi为查找第为查找第i个元素的概率，且个元素的概率，且 =1。一般。一般情形下我们认为查找每个元素的概率相等，即情形下我们认为查找每个元素的概率相等，即p1=p2=pn=,ci为查找到第为查找到第i个元素所用的比较次数个元素所用的比较次数12128.2 线性表的查找线性表的查找8.2.1 无序表的查找无序表的查找顺序查找顺序查找b静态集合中的元素在初次建表时建立，不再改变静态集合中的元素在初次建表时建立，不再改变b顺序查找是最基本的查找方法之一。所谓顺序查找，顺序查找是最基本的查找方法之一。所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找又称线性查找，主要用于在线性结构中进行查找b顺序查找的基本思想是：从表的一端开始，顺序扫描顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的元素的关键字和待找的值线性表，依次将扫描到的元素的关键字和待找的值k作比较，若相等，则查找成功；若整个表扫描完毕，作比较，若相等，则查找成功；若整个表扫描完毕，仍未找到其关键字等于仍未找到其关键字等于k的元素，则查找失败的元素，则查找失败b以顺序表或线性链表表示的静态集合可以采用顺序查以顺序表或线性链表表示的静态集合可以采用顺序查找找b顺序查找的表中的元素可以是无序的顺序查找的表中的元素可以是无序的1414顺序查找的算法实现顺序查找的算法实现b若返回值为若返回值为0表示查找不成功，否则查找成功。函表示查找不成功，否则查找成功。函数中查找的范围从数中查找的范围从recordn到到record1（即从后即从后向前），向前），record0作为监视哨，保存要找的值，作为监视哨，保存要找的值，查找时若遇到它，表示查找不成功查找时若遇到它，表示查找不成功1typedef struct 2 KeyType key;3 OtherType other;4 ElemType;5int search_seq(ElemType record,KeyType k)6 record0.key=k;7 for(int i=n;recordi.key!=k;-i);8 return i;91515顺序查找的性能分析顺序查找的性能分析b假设在每个位置查找的概率相等，即假设在每个位置查找的概率相等，即pi=，由于查找由于查找是从后往前扫描，则有每个位置的查找比较次数是从后往前扫描，则有每个位置的查找比较次数cn=1,，c2=n-1，c1=n，于是，查找成功的平均搜索长度于是，查找成功的平均搜索长度为为=niiicpASL1=ni 1=(n-i+1)=b即它的时间复杂度为即它的时间复杂度为O(n)。这就是说，查找成功的平这就是说，查找成功的平均比较次数约为表长的一半。从均比较次数约为表长的一半。从ASL可知，当可知，当n较大时，较大时，ASL值较大，查找的效率较低值较大，查找的效率较低b有时，表中各结点的查找概率并不相等。因此若事先有时，表中各结点的查找概率并不相等。因此若事先知道表中各结点查找概率的分布情况，则可将表中结知道表中各结点查找概率的分布情况，则可将表中结点按查找概率从小到大排列，即点按查找概率从小到大排列，即p1p2pn，以便提以便提高顺序查找的效率高顺序查找的效率1616顺序查找的优缺点顺序查找的优缺点b优点：算法简单，对表结构无任何要求，无优点：算法简单，对表结构无任何要求，无论是用数组还是用线性链表来存放数据元素，论是用数组还是用线性链表来存放数据元素，也无论元素之间是否按关键字有序或无序，也无论元素之间是否按关键字有序或无序，它都同样适用。而且它都同样适用。而且对于线性链表，只能顺对于线性链表，只能顺序查找序查找b缺点：查找效率低，当缺点：查找效率低，当n较大时，不宜采用较大时，不宜采用顺序查找，而必须寻求更好的查找方法顺序查找，而必须寻求更好的查找方法17178.2.2 有序表的查找有序表的查找折半查找折半查找b折半查找折半查找(或二分法搜索，或二分法搜索，binary search)是一种高效的查找方法是一种高效的查找方法b折半查找有两个条件限制折半查找有两个条件限制要求表必须采用顺序存储结构，即顺序表要求表必须采用顺序存储结构，即顺序表表中元素必须按关键字有序表中元素必须按关键字有序(升序或降序升序或降序)排排列列1818折半查找举例折半查找举例b给定有序表中关键字为给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，查找，查找k=17的情况的情况 8 17 25 44 68 77 98 100 115 125 lowhigh(a)初始情形初始情形 8 17 25 44 68 44 98 100 115 125low high mid(b)经过一次比较后的情形经过一次比较后的情形1919折半查找举例折半查找举例b查找查找k=20的情况的情况 8 17 25 44