[工学]第7章 查找.pptVIP

第7章 查找 7.1 基本概念 7.2 线性表的查找 7.3 二叉排序树的查找 7.4 哈希表的查找 7.5 典型题例 7.6 实训例题 7．1 基本概念 查找——也称为检索，就是要在大量的数据中找到“特定”的数据。 查找表——大量的数据组织为某种数据结构，这种数据结构就称为查找表，它由若干记录即数据元素构成，每个记录由若干数据项构成，“特定”的数据是由关键字标识的。 关键字——唯一标识一个记录的一个或一组数据项。在本章，假定关键字由单个数据项构成。 静态查找 ——若找到了，返回该记录的相关信息，否则给出“没找到”的信息。这样的查找称为静态查找，相应的查找表称为静态查找表。 动态查找 ——若找到了，对该记录做相应的操作（例如修改某些数据项的值、删除该记录等），否则，将该记录插入到查找表中。这样的查找称为动态查找，相应的查找表称为动态查找表。 7．2 线性表的查找 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表 针对静态查找表的查找算法主要有 顺序查找（线性查找） 折半查找（二分查找） 分块查找（索引顺序查找） 7．2．1 顺序查找 顺序查找是最简单、最常用的一种查找方法。在这种查找方法中，把所有数据组织为一个顺序表，其类型说明为： #define MaxSize 表长 typedef struct { KeyType key； /*关键字域*/ …； /*其他域*/ }RecordType[MaxSize]； 基本思想： 从顺序表的一端开始，把给定的值与顺序表的每个数据元素的关键字的值依次进行比较，若找到，返回该元素在顺序表中的序号，否则返回-1。 为提高查找效率，在顺序查找时，从最后一个位置开始向前查找，并且下标为0的位置不存放有用数据，而是存放给定的值，这个位置称为“监视哨”。 算法描述如下： int SeqSearch(RecordType r, int n, KeyType k) { /*返回关键字值等于k的数据元素在表r中的位置，n为表中元素的个数*/ i=n； r[0].key=k； /*监视哨*/ while (r[i]. key!=k) i--； if (i0) return （i）； /*查找成功*/ else return （-1）； /*查找失败*/ }/* SeqSearch */ 算法分析： MSL=n+1 7．2．2 折半查找（二分查找） 适用条件：采用顺序存储结构的有序表 基本思想 ：首先找到所有数据的中间位置mid，把给定的值k与中间位置的数据元素的关键字的值r[mid].key比较，若相等，则查找成功，返回中间元素的位置mid；若kr[mid].key，由于查找表是有序的（假设由小到大有序），要查找的元素如果存在，一定在表的前半部分，于是，在表的前半部分（左子表）继续进行折半查找；若kr[mid].key，要查找的元素如果存在，一定在表的后半部分（右子表），于是，在表的后半部分继续进行折半查找。这样把表的范围一半一半地缩小，直到找到，或找不到（此时表的范围为0）。 假设给定的一组关键字为（3，6，12，23，30，43，56，64，78，85，98），要查找的值k为23，其折半查找过程如下。 初始，low=1，high=11，mid=(1+11)/2=6。 k与r[mid].key进行比较。由于k43，待查元素若存在，必在表的前半部分，即在区间[1，mid-1]范围内，令high=mid-1，此时，low=1，hig=5，重新求得mid=(1+5)/2=3。 k再与r[mid].key进行比较，由于k12，待查元素若存在，必在当前查找范围的后半部分，即在区间[mid+1，high]范围内，令low=mid+1，此时，low=4，high=5，重新求得mid=(4+5)/2=4。 k再与r[mid].key进行比较，由于k=23，查找成功。所查找的记录在表中位置为4。 折半查找算法描述如下： int BinSearch(RecordType r, int n, KeyType k) { /*在有序表r中折半查找关键字值等于k的数据元素*/ int low,high,mid; low=1；high=n； while (low=high) {