典型查找算法-编程.pptx

第第8章章 典型查找算法典型查找算法 顺顺序序查查找找、折折半半查查找找和和分分块块查查找找的的方方法法和算法，相应的平均查找长度和算法，相应的平均查找长度二二叉叉排排序序树树查查找找方方法法和和算算法法，二二叉叉平平衡衡树概念树概念散散列列表表的的概概念念，散散列列函函数数的的构构造造方方法法，处处理理冲冲突突的的方方法法及及散散列列表表各各种种运运算算的的实实现算法现算法 第第8章章 典型查找算法典型查找算法 8.1 8.1 实例：学生分配座位实例：学生分配座位 8.2 8.2 静态查找静态查找 8.3 8.3 动态查找动态查找 8.4 8.4 散列查找散列查找 本章总结本章总结8.1 实例：学生分配座位实例：学生分配座位 8.1.1 问题描述问题描述 8.1.2 问题的分析问题的分析 8.1.3 实现算法实现算法 8.1.4 基本概念基本概念 8.1.1 问题描述问题描述 教室中的学生座位分配教室中的学生座位分配是一个最简单的例子。假定某教室有35个座位，如果不加限定任意就坐或按某种规律就座，则要要查找某学生查找某学生时就要将待查找的学生与当前将待查找的学生与当前座位上的学生进行比较座位上的学生进行比较。8.1.2 问题的分析问题的分析 用计算机来解决查找学生问题，通常需要做以下工作：第一，学生信息以什么形式表示和存储学生信息以什么形式表示和存储；第二，查找的具体实现方法查找的具体实现方法(算法)。struct student int num1;/表示座号int num2;/表示学号char name12;/表示姓名 ；struct listStudent stusize;/保存学生记录Int len;/学生人数;学生信息的存储方式：学生信息的存储方式：从第一个学生开始，依次与查找的学生进依次与查找的学生进行比较行比较。在查找过程中，若某个学生的记录与所查找学生记录相等相等，则查找成功查找成功，返回该学返回该学生在表中位置生在表中位置；若全部比较完毕，没有符合条件的学生记录，则查找不成功查找不成功，返回返回-1。查找学生的方法：查找学生的方法：8.1.3 实现算法实现算法 int search(List&L,int,s)/从表L.stu0,L.stu1,L.stun-1的n个元素中查找关键字为S元素，若查找成功返回该生学号，否则返回-1 int i;for(i=0;iL.len;i+)if(L.stui=S)break;if(in)return L.stui.num2;else return -1;8.1.4 基本概念基本概念 查查找找表表：利用计算机查找时，首先要确定原始数据的逻逻辑辑结结构构和和存存储储结结构构，变为计算机中处理的数据结构，这种数据结构称为存储表存储表。查查找找：在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。查找成功，返回该记录的存储位置；查找失败，返回一个特定值。平平均均查查找找长长度度：在查找成功情况下的平均比较次数。对于含有n个记录的表，查找成功时的平均查找长度为：ASL=其中：Ci为查找第i个元素时同给 定值K进行比较的次数；Pi为查找第i个记录的概率，且 在等概率情况下，则P1=P2=Pn=8.2 静态查找静态查找8.2.1 顺序查找顺序查找 8.2.2 折半查找折半查找 8.2.3 分块查找分块查找 8.2 静态查找静态查找 查找过程中，进行如下操作：查查询询某某个个特特定定的的数数据据元元素素是是否否在在查查找找表表中中或检检索索某某个个数数据据元元素素的的各各种种属属性性。此查找表称为静态查找表静态查找表(Static Search Table)。查找表定义为顺序存储的线性表顺序存储的线性表，数据类型定义如下：struct Elemtype /数据元素类型定义keytype key;/关键字项 ；#define maxlen maxsize/分配的存储单元个数struct ListSq Elemtype e maxsize;int len;8.2.1 顺序查找顺序查找 顺序查找（顺序查找（线性查找）基本思想：基本思想：从线性表的一端开始，依次将每个元素的关键字每个元素的关键字同给定值同给定值K进行比较进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。实现算法：实现算法：（略）ASLASL：等概率等概率前提下，ASL=(n+1)/2；若查找失败，需要比较n+1次，所以时间复杂为时间复杂为O(n)。8.2.2 折半查找折半查找 使用折半查找（二分查找）的前提：使用折半查找（二分查找）的前提：有序表有序表形式表示。折半查找的思想：折半查找的思想：设存在顺序有序表ListSq L，表中元素的下界为0，上界为L.len-1。先取整个有序表的中间点元素L.emid(L.emid(mid=mid=（(上界上界+下界下界)/2)/2）的关键字同给定值）的关键字同给定值K K进行比较进行比较。若相等，则查找成功，返回该元素的下标mid；若KL.emid.key，则说明待查元素若存在只能在右子表右子表(下下标从标从mid+1mid+1到到n n1 1的范围的范围)中，只要在右子表中继续二分查找即可。重复执行，直到找到关键字为重复执行，直到找到关键字为K K的元素或当前查找的元素或当前查找区间为空区间为空(即表明查找失败即表明查找失败)为止。为止。实现算法：实现算法：（略）二叉判定树：二叉判定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找根结点表示当前查找区间的中间点元素区间的中间点元素，它的左子树和右子树分别对应该区左子树和右子树分别对应该区间的左子表和右子表间的左子表和右子表。二叉判定树是一棵二叉排序树。二叉判定树是一棵二叉排序树。二分查找的平均查找长度为：二分查找的平均查找长度为：8.2.3 分块查找分块查找 分块查找分块查找(索引顺序查找索引顺序查找)基本思想：基本思想：首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表逻辑子表，为每个子表分别建立一个索引索引项项，由所有子表的索引项构成一个索引表索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定先根据所给的关键字查找索引表，从中查找出给定值值K K刚好小于等于索引值的那个索引项，找到待查块，然刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录后再到主表中查找该块，从中查找待查的记录。实现算法：实现算法：（略）索引表是有序的索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意任意的的，所以在块内只能采用顺序查找。平均查找长度为：平均查找长度为：设将长度为n的表均匀分成b块，每块有s个记录，则b=n/s，查找表中每条记录的概率相等，则每块查找的概率为1/b，块中每条记录的查找概率为1/s。则顺序查找索引表时：8.3 动态查找动态查找 8.3.1 8.3.1 二叉排序树查找二叉排序树查找 8.3.2 8.3.2 二叉平衡树二叉平衡树 动态查找表特点：动态查找表特点：表结构本身是在查找过程中在查找过程中动态生成的动态生成的，即对于给定值key，若表中存在表中存在关键字等于关键字等于key的记录的记录，则查找成功；否则插入关键字为插入关键字为key的元素的元素。8.3.1 二叉排序树查找二叉排序树查找 二叉排序树(二叉搜索树、二叉查找树二叉搜索树、二叉查找树)：或者是一棵空树，或是一棵有如下特性的非空二叉树：l若它的左左子子树树非非空空，则左左子子树树上上所所有有结结点点的的关关键键字字均小于根结点的关键字均小于根结点的关键字。l若它的右右子子树树非空，则右右子子树树上上所所有有结结点点的的关关键键字字均大于等于根结点的关键字均大于等于根结点的关键字。l左、右子树本身又各是一棵二叉搜索树左、右子树本身又各是一棵二叉搜索树。结论：二叉排序树中序遍历得到的必是一个有序序列。结论：二叉排序树中序遍历得到的必是一个有序序列。二叉排序树的查找过程（二叉排序树的查找过程（递归查找过程）：）：查找一个给定值为k的结点，若二叉树不为空，首先将它与根结点进行比较根结点进行比较，若K与根结点相等与根结点相等，查找成功；若K小于根结点小于根结点，则表示若K存在，应在其左子树左子树中；否则若K存在，应在其右子树右子树中。对左、右子树同样按上述对左、右子树同样按上述过程先与子树的根结点进行比较，根据比较的结果定下过程先与子树的根结点进行比较，根据比较的结果定下一步的操作。一步的操作。若在查找过程中遇到叶子结点遇到叶子结点，还没有找到待找结点，则表示二叉排序树中不存在该结点二叉排序树中不存在该结点，查找不成功。实现算法：实现算法：（略）时间复杂度：时间复杂度：分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。普通情况下，对二叉排序树进行查找的时间复杂度为O()；最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。8.3.2 二叉平衡树二叉平衡树 二叉平衡树二叉平衡树(AVL树)：或者是一棵空树，或者是一棵具有如下性质的非空二叉树：它的左子树和右子树都是二叉平衡树，且左子树左子树和右子树的深度之差的绝对值不大于和右子树的深度之差的绝对值不大于1 1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子平衡因子BFBF，则BFBF的值只可能为的值只可能为1 1、0 0和和1 1。对二叉排序树插入结点而构造平衡二叉树的规律：对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：LLLL型：型：单向右旋平衡处理单向右旋平衡处理 RRRR型：型：单向左旋平衡处理单向左旋平衡处理 LR LR型：型：双向旋转双向旋转(先左后右先左后右)平衡处理平衡处理 RL RL型：型：双向旋转双向旋转(先右后左先右后左)平衡处理平衡处理时间复杂度：时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时时间间复复杂杂度度为为O(O(log2n)。8.4 散列查找散列查找 8.4.1 散列存储和散列函数的构造方法散列存储和散列函数的构造方法 8.4.2 解决冲突的方法解决冲突的方法 8.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析 8.4.1 散列存储和散列函数构造散列存储和散列函数构造基本术语：基本术语：散列存储：散列存储：以数据中每个元素的关键字K为自变量，通过一个函数f(k)计算出函数值，把这个值同存储空间中一个唯一的存储位置相对应，将该元素存储到这个存储位置中。函数f(k)称为散列函数散列函数或哈希函数。f(k)的值称为散列地址散列地址或哈希地址；进行散列存储的地址空间称为散列表散列表或哈希表。冲突：冲突：实际应用中，由于散列函数的构造方法不同，常会出现多个元素同时占用一个存储单元多个元素同时占用一个存储单元的情况，即散列地址相同，这种现象叫冲突冲突。具有相同函数值的不同关键字的元素，称为同义词同义词。常用的构造散列函数的方法：常用的构造散列函数的方法：直接定址法直接定址法数字分析法数字分析法平方取中法平方取中法 折叠法折叠法 除留余数法除留余数法 8.4.2 解决冲突的方法解决冲突的方法 常用的解决冲突的方法有以下几种：常用的解决冲突的方法有以下几种：开放定地址开放定地址链地址法链地址法 从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲存储单元，把发生冲突的待插入元素存入到该单元中的一类解决冲突的方法。设H(key)为散列函数，m为散列表长度。则开放定址法中找下一个空闲空间的散列函找下一个空闲空间的散列函数为：数为：Hi=(H(key)+dHi=(H(key)+di i)%m)%m 其中，i=1,2k；d di i称为增称为增量量，以di的取值分为以下三种：(1)di=1,2,3m-1,称线性探测再散列线性探测再散列。(2)di=12,-12，22，-22，k2,(km/2)称二次探测再散二次探测再散列列。(3)di=随机数序列，称为随机探测再散列随机探测再散列。开放定址法：开放定址法：把具有相同散列地址的关键字放在同一链表中相同散列地址的关键字放在同一链表中，称为同义词链表同义词链表。通常把具有相同散列地址的关键字都存放在一个同义词链表中，有m个散列地址就有m个链表，同时用数组tm存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以ti为头指针的单链表中。链地址法：链地址法：8.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析实现算法：实现算法：（略）结论：结论：l由于产生“冲突”，查找过程仍是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表的查找效率的量度。l查找过程中比较个数取决于因素：散列函数、解决冲突的方法和散列表的装填因子。装填因子装填因子定义：=越小，发生冲突的可能性就越小；越大，发生冲突的可能性就越大。本章总结本章总结本章主要介绍了数据处理中的几几种种典典型型的的查查找找方方法法、及及实现算法和各种查找方法的性能分析实现算法和各种查找方法的性能分析。查查找找：指在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。查找过程：查找过程：是数据处理的一个环节，它的下一环节是对查找到的结果进行处理，根据所做的操作的不同根据所做的操作的不同，将查找方法分为静态查找静态查找和动态查找动态查找。静态查找方法介绍了顺序查找、二分查找和分块查找三种方法。动态查找方法介绍了二叉排序树查找和二叉平衡树查找。顺顺序序查查找找既适用于顺序表，也适用与单链表，时时间间复复杂度是杂度是O（n），），平均查找长度为（平均查找长度为（n+1）/2。折折半半查查找找只适用于顺顺序序存存储储的的有有序序表表。折半查找的的时时间间复复杂杂度度为为O（log2n）。折半查找的查找过程可以画成一棵二叉判定树二叉判定树，它是一棵二叉排序树是一棵二叉排序树。分分块块查查找找过过程程分分为为两两部部分分：先在索索引引表表中查找；然后在主表的对应块主表的对应块中顺序查找。二二叉叉排排序序树树查查找找：根根据据二二叉叉排排序序树树的的定定义义，首先访问根结点，若其值等于给定值则查找成功；若给定值比根结点大，继续向右子树中查找；否则给定值比根结点小，继续在左子树中查找，直到找到该结点或找不到为止，此时查找失败。二叉平衡树的BFBF的的值值只只可可能能为为1 1、0 0和和1 1。二叉平衡树的构造过程中进行调整的方法共有四种。二叉平衡树的查找过程也与二叉排序树类似，从根结点开始，向左或右子树进行查找。散散列列存存储储是是一一种种存存储储方方法法，也也是是一一种种查查找找方方法法。散列存储通过对元素的关键字按给定函数进行计算，得到存储地址，此地址称为散散列列地地址址，用于计算地址的给定函数称为散散列列函函数数，用于存储元素的地址空间称为散散列列表表。构造散列函数方法有直接定址法、数字分析法、平均取中法、折叠法和除留余数法。常常用用的的解解决决冲冲突突的的方方法法有有开开放放定定址址法法、链链地地址址法法。平平均均查查找找长长度度等等于于查找每个元素时的比较次数之和除以所有元素的个数。