数据结构(第二版) 郑泳 方风波 第九章 查找新.pptVIP

第九章 查找 知识教学目标 查找的有关概念，平均查找长度 顺序查找、二分查找、分块查找、二叉排序树上的查找 散列表的有关概念和查找运算 能力培养目标 平均查找长度的概念和求解分析 顺序查找、二分查找和分块查找的运算 二叉排序树的查找、插入和删除操作 散列函数的构造方法及冲突的处理方法 9.1 基本概念 1．查找表 由同一类型的数据元素（或记录）构成的集合称为查找表。 2．关键字 数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；反之，把可以标识若干记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。 3．查找 查找是指在查找表中查找一个其关键字值等于某一给定值的数据元素（或记录）。若表中存在这样一个数据元素（或记录），则称查找成功；若表中不存在关键字值等于给定值的数据元素（或记录），则称查找失败，此时查找的结果可能给出一个“空”记录或“空”指针。 4．平均查找长度 对于不同的数据结构，有不同的查找方法，也有不同的查找效率。而在查找中，要衡量一种查找算法的优劣，主要是看要查找的值与关键字的比较次数。因此，通常把查找过程中对关键字的比较次数作为衡量一个查找算法效率优劣的标准，并称平均比较次数为平均查找长度。其计算公式定义为： 9.2线性表的查找 9.2.1 顺序查找 顺序查找是一种最简单也是最基本的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K进行比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败 。 顺序查找的线性表结构定义如下： ＃define MAXITEM 100 typedef struct { keytype key; DataType data; } NodeType; typedef NodeType SeqList[MAXITEM]; 【算法9.1】 顺序查找。 int SeqSearch( SeqList r,int k,int n) { i=1; while(r[i].key!=k i=n) i++; if(in) i=0; return (i); } 9.2.2 二分查找 二分查找又称为折半查找，它是一种效率较高的查找方法。但二分查找有一定的条件限制：要求线性表必须采用顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）。 【算法9.2】 二分查找。 int BinSearch(SeqList r,Datatype k) { int low=1,high=n; while ( lowhigh ) { int mid=(low+high)/2; //取区间中点 if (r[mid].key==k) return mid; //查找成功 else if (r[mid].keyk) high=mid-1; else low=mid+1; } returb 0; } 9.2.3 分块查找 分块查找又称为索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。分块查找必须先建立索引表，其索引表是一个有序表，故可以用二分查找来代替顺序查找实现索引表的快速查找。 具体实现如下：将一个含有n个元素的主表分成m个子表，但要求子表之间元素是按关键字有序排列的，而子表中元素可以是无序的，然后建立索引表，索引表中索引域的值用每个子表最大关键字代替，则可以按索引查找思想找到表中的元素。 9.3 树上的查找 1. 二叉排序树的定义 二叉排序树又称为二叉查找树，它是一种特殊结构的二叉树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树： 1) 它的左子树非空，则左子树上所有结点的值均小于根结点的值； 2) 它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3) 左、右子树本身又各是一棵二叉排序树。 2. 二叉排序树的查找 根据二叉排序树的性质，在二叉排序树中进行查找，将要查找的值从树根开始比较，若与根的关键值相等，则查找成功；若比根的关键值小，则到左子树找；若比根的关键值大，则到右子树找；直到查找成功或查找子树空（查找失败）。若查找成功，则返回查找到结点的地址；若查找失败，则返回空指针。这里使用二叉链表作为二叉树的存储结构。 【算法9.4】 二叉排序树的查找递归算法。 NODE *search(int x