第8章查找 数据结构(C++描述)
第8章 查找 数据结构（C++描述）
目录 81查找的基本概念 8.2线性表的查找 8.3树表查找 8.4散列查找 退出
目录 8．4 散列查找 8．3 树表查找 8.1 查找的基本概念 8．2 线性表的查找 退出
8,1查找的基本概念 查找,也称为检索。在我们日常生活中,随处可见查找 的实例。如查找某人的地址、电话号码;查某单位45岁 以上职工等,都属于查找范畴。本书中,我们规定查找 是按关键字进行的,所谓关键字(key)是数据元素(或记 录)中某个数据项的值,用它可以标识(或识别)一个数据 元素。例如,描述一个考生的信息,可以包含:考号 姓名、性别、年龄、家庭住址、电话号码、成绩等关键 字。但有些关键字不能唯一标识一个数据元素,而有的 关键字可以唯一标识一个数据元素。如刚才的考生信息 中,姓名不能唯一标识一个数据元素(因有同名同姓的 人),而考号可以唯一标识一个数据元素(每个考生考号 是唯一的,不能相同)。我们将能唯一标识一个数据元素 的关键字称为主关键字,而其它关键字称为辅助关键字 或从关键字
8.1 查找的基本概念 查找，也称为检索。在我们日常生活中，随处可见查找 的实例。如查找某人的地址、电话号码；查某单位45岁 以上职工等，都属于查找范畴。本书中，我们规定查找 是按关键字进行的，所谓关键字(key)是数据元素(或记 录)中某个数据项的值，用它可以标识(或识别)一个数据 元素。例如，描述一个考生的信息，可以包含：考号、 姓名、性别、年龄、家庭住址、电话号码、成绩等关键 字。但有些关键字不能唯一标识一个数据元素，而有的 关键字可以唯一标识一个数据元素。如刚才的考生信息 中，姓名不能唯一标识一个数据元素(因有同名同姓的 人)，而考号可以唯一标识一个数据元素(每个考生考号 是唯一的，不能相同)。我们将能唯一标识一个数据元素 的关键字称为主关键字，而其它关键字称为辅助关键字 或从关键字
它洧了主关键字及关键字后,我们可以给查找下一个完整 的定义。所谓査找,就是根据给定的值,在一个表中查 找出其关键字等于给定值的数据元素,若表中有这样的 y元素,则称查找是成功的,此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置;若表中不 存在这样的记录,则称查找是不成功的,或称查找失败, 并可给出相应的提示 入因为查找是对已存入计算机中的数据所进行的操作,所 以采用何种查找方法,首先取决于使用哪种数据结构来 表示“表”,即表中结点是按何种方式组织的。为了提 髙査找速度,我们经常使用某些特殊的数据结构来组织 表。因此在研究各种査找算法时,我们首先必须弄清这 些算法所要求的数据结构,特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内 存进行,则称这样的查找为内查找;反之,若在查找过 程中还需要访问外存,则称之为外查找。我们仅介绍内 查找
有了主关键字及关键字后，我们可以给查找下一个完整 的定义。所谓查找，就是根据给定的值，在一个表中查 找出其关键字等于给定值的数据元素，若表中有这样的 元素，则称查找是成功的，此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置；若表中不 存在这样的记录，则称查找是不成功的，或称查找失败， 并可给出相应的提示。 因为查找是对已存入计算机中的数据所进行的操作，所 以采用何种查找方法，首先取决于使用哪种数据结构来 表示“表” ，即表中结点是按何种方式组织的。为了提 高查找速度，我们经常使用某些特殊的数据结构来组织 表。因此在研究各种查找算法时，我们首先必须弄清这 些算法所要求的数据结构，特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内 存进行，则称这样的查找为内查找；反之，若在查找过 程中还需要访问外存，则称之为外查找。我们仅介绍内 查找
它要衡量一种查找算法的优劣,主要是看要找的值与关键字 的比较次数,但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个査找算法好坏的标准,对于一个含 有个元素的表查找成功时的斗均查找长度可示为 般情形下我们认为查找每个元素的概率相等,Ci为查找 第个元素所用到的比较次数 要衡量一种查找算法的优劣,主要是看要找的值与关键字 的比较次数,但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个査找算法好坏的标准,对于一个含 有n个元素的表,查找成功时的平均查找长度可表示为 ASL 其中Pi为査找第i个元素的概率,且=1。一般情 形下我们认为查找每个元素的概率相等,Ci为查找第个 元素所用到的比较次数
要衡量一种查找算法的优劣，主要是看要找的值与关键字 的比较次数，但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准，对于一个含 有n个元素的表，查找成功时的平均查找长度可表示为 ASL= ，其中Ｐi为查找第i个元素的概率，且 =1。 一般情形下我们认为查找每个元素的概率相等，Ｃi为查找 第i个元素所用到的比较次数。 要衡量一种查找算法的优劣，主要是看要找的值与关键字 的比较次数，但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准，对于一个含 有n个元素的表，查找成功时的平均查找长度可表示为 ASL= ，其中Ｐi为查找第i个元素的概率，且=1。一般情 形下我们认为查找每个元素的概率相等，Ｃi为查找第i个 元素所用到的比较次数。 = n i i i p c 1 = n i i p 1
8.2线性表的查找 821顺序查找 工顺查找的基本思想 顺序查找是一种最简单的查找方法,它的基本思想是: 从表的一端开始,顺序扫描线性表,依次将扫描到的 结点关键字和待找的值K相比较,若相等,则查找成 功,若整个表扫描完毕,仍末找到关键字等于K的元 素,则查找失败 顺序查找既适用于顺序表,也适用于链表。若用顺序 表,查找可从前往后扫描,也可从后往前扫描,但若 采用单链表,则只能从前往后扫描。另外,顺序查找 的表中元素可以是无序的 下面以顺序表的形式来描述算法
8．2 线性表的查找 8.2.1 顺序查找 1．顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是： 从表的一端开始，顺序扫描线性表，依次将扫描到的 结点关键字和待找的值Ｋ相比较，若相等，则查找成 功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元 素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序 表，查找可从前往后扫描，也可从后往前扫描，但若 采用单链表，则只能从前往后扫描。另外，顺序查找 的表中元素可以是无序的。 下面以顺序表的形式来描述算法
2.顺序查找算法实现 const int n=maxn /n为表的最大长度 struct node elemtype key;/key为关键字,类型设定为 Teletype int seqsearch(node R[+ll,elemtype k) 在表R 中查找关键字值为K的元素 (RIOJ key=k; int i=n ∥从人表尾开始向前扫描 while(r[i]. key!=k) return 1;)
2．顺序查找算法实现 const int n=maxn //n为表的最大长度 struct node {… elemtype key; //key为关键字，类型设定为elemtype }; int seqsearch (node R[n+1],elemtype k) //在表Ｒ 中查找关键字值为Ｋ的元素 {R[0].key=k; int i=n; //从表尾开始向前扫描 while(R[i].key!=k) i--; return i;}
它?在函数 seqsearch中,若返回的值为0表示查找不成功, 否则查找成功。函数中查找的范围从R[n到R[1], R[0]为监视哨,起两个作用,其一,是为了省去判 定 while循环中下标越界的条件讼1,从而节省比较时 间,其二,保存要找值的副本,若査找时,遇到它, 表示查找不成功。若算法中不设立监视哨R[O],程序 花费的时间将会增加,这时的算法可写为下面形式。 int seqsearch( node r[n+l], elemtype k) while(R[i]key!=k)&&(1>=1)1-; return 当然上面算法也可以改成从表头向后扫描,将监视哨设在右 边,这种方法请读者自己完成
在函数seqsearch中，若返回的值为０表示查找不成功， 否则查找成功。函数中查找的范围从Ｒ[n]到Ｒ[１]， Ｒ[０]为监视哨，起两个作用，其一，是为了省去判 定 while循环中下标越界的条件i≥1，从而节省比较时 间，其二，保存要找值的副本，若查找时，遇到它， 表示查找不成功。若算法中不设立监视哨R[0]，程序 花费的时间将会增加，这时的算法可写为下面形式。 int seqsearch(node R[n+1]，elemtype k) {int i=n; while(R[i].key!=k)&&(i>=1) i--; return i; } 当然上面算法也可以改成从表头向后扫描，将监视哨设在右 边，这种方法请读者自己完成
3顺序查找性能分析 偎设在每个位置查找的概率相等,即有p=1/n,由于查 找是从后往前扫描,则有每个位置的查找比较次数C=1, Ca2,,C=n,于是,查找成功的平均查找ASL= ∑p:c→(n-+l)=2,即它的时间复杂度为O(n 这就是说,查找成功的平均比较次数约为表长的一半。 若k值不在表中,则必须进行n+1次比较之后才能确定查 入找失败。另处,从ASL可知,当n较大时,ASL值较大, 查找的效率较低。 顺序查找的优点是算法简单,对表结构无任何要求,无 论是用向量还是用链表来存放结点,也无论结点之间是 否按关键字有序或无序,它都同样适用。顺序查找的缺 点是查找效率低,当n较大时,不宜采用顺序查找,而 必须寻求更好的查找方法
3.顺序查找性能分析 假设在每个位置查找的概率相等，即有pi =1/n，由于查 找是从后往前扫描，则有每个位置的查找比较次数Cn =1， Cn-1 =2，…，C1=n，于是，查找成功的平均查找ASL= = = = ,即它 的时间复杂度为O(n)。 这就是说，查找成功的平均比较次数约为表长的一半。 若k值不在表中，则必须进行n+1次比较之后才能确定查 找失败。另处，从ASL可知，当n较大时，ASL值较大， 查找的效率较低。 = n i i i p c 1 = − + n i n n i 1 1 [ ( 1)] 2 n+1 顺序查找的优点是算法简单，对表结构无任何要求，无 论是用向量还是用链表来存放结点，也无论结点之间是 否按关键字有序或无序，它都同样适用。顺序查找的缺 点是查找效率低，当n较大时，不宜采用顺序查找，而 必须寻求更好的查找方法
822二分查找 1三分找的基本想 二分查找,也称折半查找,它是一种高效率的查找方法。 但二分查找有条件限制:要求表必须用向量作存贮结构, 且表中元素必须按关键字有序(升序或降序均可)。我们不 妨假设表中元素为升序排列。二分查找的基本思想是: 首先将待查值K与有序表R[]到R[n的中点md上的关键 字Rrmd]key进行比较,若相等,则查找成功;否则,若 R[md]key>k,则在R[到R[mid-1中继续查找,若有 R[md]key<k,则在R[md+1到R[n中继续查找。每通 过一次关键字的比较,区间的长度就缩小一半,区间的 个数就增加一倍,如此不断进行下去,直到找到关键字 为K的元素;若当前的查找区间为空(表示查找失败)
8.2.2二分查找 1.二分查找的基本思想 二分查找，也称折半查找，它是一种高效率的查找方法。 但二分查找有条件限制：要求表必须用向量作存贮结构， 且表中元素必须按关键字有序(升序或降序均可)。我们不 妨假设表中元素为升序排列。二分查找的基本思想是： 首先将待查值K与有序表R[1]到R[n]的中点mid上的关键 字R[mid].key进行比较，若相等，则查找成功；否则，若 R[mid].key>k ， 则在R[1]到R[mid-1]中继续查找，若有 R[mid].key<k ， 则在R[mid+1]到R[n]中继续查找。每通 过一次关键字的比较，区间的长度就缩小一半，区间的 个数就增加一倍，如此不断进行下去，直到找到关键字 为K的元素；若当前的查找区间为空(表示查找失败)