典型查找算法编程

典型查找算法编程第一页，共三十页，2022年，8月28日第8章

典型查找算法

8.1实例：学生分配座位8.2静态查找8.3动态查找8.4散列查找本章总结第二页，共三十页，2022年，8月28日8.1实例：学生分配座位

8.1.1问题描述

8.1.2问题的分析

8.1.3实现算法

8.1.4基本概念

第三页，共三十页，2022年，8月28日8.1.1问题描述

教室中的学生座位分配是一个最简单的例子。假定某教室有35个座位，如果不加限定任意就坐或按某种规律就座，则要查找某学生时就要将待查找的学生与当前座位上的学生进行比较。

第四页，共三十页，2022年，8月28日8.1.2问题的分析

用计算机来解决查找学生问题，通常需要做以下工作：第一，学生信息以什么形式表示和存储；第二，查找的具体实现方法(算法)。第五页，共三十页，2022年，8月28日structstudent{intnum1;//表示座号intnum2;//表示学号charname[12];//表示姓名

┆}；structlist{Studentstu[size];//保存学生记录Intlen;//学生人数};

学生信息的存储方式：第六页，共三十页，2022年，8月28日

从第一个学生开始，依次与查找的学生进行比较。在查找过程中，若某个学生的记录与所查找学生记录相等，则查找成功，返回该学生在表中位置；若全部比较完毕，没有符合条件的学生记录，则查找不成功，返回-1。查找学生的方法：第七页，共三十页，2022年，8月28日8.1.3实现算法

intsearch(List&L,int,s)//从表L.stu[0],L.stu[1],……L.stu[n-1]的n个元素中查找关键字为S元素，若查找成功返回该生学号，否则返回-1{inti;for(i=0;i<L.len;i++)if(L.stu[i]==S)break;if(i<n)returnL.stu[i].num2;elsereturn-1;}第八页，共三十页，2022年，8月28日8.1.4基本概念

查找表：利用计算机查找时，首先要确定原始数据的逻辑结构和存储结构，变为计算机中处理的数据结构，这种数据结构称为存储表。

查找：在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。查找成功，返回该记录的存储位置；查找失败，返回一个特定值。平均查找长度：在查找成功情况下的平均比较次数。对于含有n个记录的表，查找成功时的平均查找长度为：

ASL=其中：Ci为查找第i个元素时同给定值K进行比较的次数；Pi为查找第i个记录的概率，且

在等概率情况下，则P1=P2=…=Pn=第九页，共三十页，2022年，8月28日8.2静态查找8.2.1顺序查找

8.2.2折半查找

8.2.3分块查找

第十页，共三十页，2022年，8月28日8.2静态查找

查找过程中，进行如下操作：查询某个特定的数据元素是否在查找表中或检索某个数据元素的各种属性。此查找表称为静态查找表(StaticSearchTable)。查找表定义为顺序存储的线性表，数据类型定义如下：structElemtype//数据元素类型定义{keytypekey;//关键字项┆}；#definemaxlenmaxsize//分配的存储单元个数structListSq{Elemtypee[maxsize];intlen;};第十一页，共三十页，2022年，8月28日8.2.1顺序查找

顺序查找（线性查找）基本思想：从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。

实现算法：（略）ASL：等概率前提下，ASL==(n+1)/2；若查找失败，需要比较n+1次，所以时间复杂为O(n)。

第十二页，共三十页，2022年，8月28日8.2.2折半查找

使用折半查找（二分查找）的前提：有序表形式表示。

折半查找的思想：设存在顺序有序表ListSqL，表中元素的下界为0，上界为L.len-1。先取整个有序表的中间点元素L.e[mid](mid=（(上界+下界)/2）的关键字同给定值K进行比较。若相等，则查找成功，返回该元素的下标mid；若K<L.e[mid].key，则说明待查元素若存在只能在左子表(下标从0到mid－1的范围)中，只要在左子表中继续折半查找即可；若K>L.e[mid].key，则说明待查元素若存在只能在右子表(下标从mid+1到n－1的范围)中，只要在右子表中继续二分查找即可。重复执行，直到找到关键字为K的元素或当前查找区间为空(即表明查找失败)为止。

第十三页，共三十页，2022年，8月28日实现算法：（略）二叉判定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找区间的中间点元素，它的左子树和右子树分别对应该区间的左子表和右子表。

二叉判定树是一棵二叉排序树。

二分查找的平均查找长度为：

第十四页，共三十页，2022年，8月28日8.2.3分块查找

分块查找(索引顺序查找)基本思想：

首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表，为每个子表分别建立一个索引项，由所有子表的索引项构成一个索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定值K刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录。

实现算法：（略）

索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。

第十五页，共三十页，2022年，8月28日平均查找长度为：设将长度为n的表均匀分成b块，每块有s个记录，则b=[n/s]，查找表中每条记录的概率相等，则每块查找的概率为1/b，块中每条记录的查找概率为1/s。则顺序查找索引表时：

第十六页，共三十页，2022年，8月28日8.3动态查找

8.3.1二叉排序树查找8.3.2二叉平衡树

动态查找表特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功；否则插入关键字为key的元素。第十七页，共三十页，2022年，8月28日8.3.1二叉排序树查找

二叉排序树(二叉搜索树、二叉查找树)：或者是一棵空树，或是一棵有如下特性的非空二叉树：l

若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字。l

若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字。l

左、右子树本身又各是一棵二叉搜索树。结论：二叉排序树中序遍历得到的必是一个有序序列。

第十八页，共三十页，2022年，8月28日二叉排序树的查找过程（递归查找过程）：查找一个给定值为k的结点，若二叉树不为空，首先将它与根结点进行比较，若K与根结点相等，查找成功；若K小于根结点，则表示若K存在，应在其左子树中；否则若K存在，应在其右子树中。对左、右子树同样按上述过程先与子树的根结点进行比较，根据比较的结果定下一步的操作。若在查找过程中遇到叶子结点，还没有找到待找结点，则表示二叉排序树中不存在该结点，查找不成功。

实现算法：（略）第十九页，共三十页，2022年，8月28日时间复杂度：分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。普通情况下，对二叉排序树进行查找的时间复杂度为O()；最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。

第二十页，共三十页，2022年，8月28日8.3.2二叉平衡树

二叉平衡树(AVL树)：或者是一棵空树，或者是一棵具有如下性质的非空二叉树：它的左子树和右子树都是二叉平衡树，且左子树和右子树的深度之差的绝对值不大于1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子BF，则BF的值只可能为－1、0和1。

第二十一页，共三十页，2022年，8月28日对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：

LL型：单向右旋平衡处理

RR型：单向左旋平衡处理

LR型：双向旋转(先左后右)平衡处理

RL型：双向旋转(先右后左)平衡处理时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时间复杂度为O(log2n)。

第二十二页，共三十页，2022年，8月28日8.4散列查找

8.4.1散列存储和散列函数的构造方法

8.4.2解决冲突的方法

8.4.3散列查找实现算法和性能分析

第二十三页，共三十页，2022年，8月28日8.4.1散列存储和散列函数构造基本术语：散列存储：以数据中每个元素的关键字K为自变量，通过一个函数f(k)计算出函数值，把这个值同存储空间中一个唯一的存储位置相对应，将该元素存储到这个存储位置中。函数f(k)称为散列函数或哈希函数。f(k)的值称为散列地址或哈希地址；进行散列存储的地址空间称为散列表或哈希表。

冲突：实际应用中，由于散列函数的构造方法不同，常会出现多个元素同时占用一个存储单元的情况，即散列地址相同，这种现象叫冲突。具有相同函数值的不同关键字的元素，称为同义词。

第二十四页，共三十页，2022年，8月28日常用的构造散列函数的方法：直接定址法数字分析法平方取中法折叠法除留余数法

第二十五页，共三十页，2022年，8月28日8.4.2解决冲突的方法

常用的解决冲突的方法有以下几种：开放定地址链地址法第二十六页，共三十页，2022年，8月28日从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲存储单元，把发生冲突的待插入元素存入到该单元中的一类解决冲突的方法。设H(key)为散列函数，m为散列表长度。则开放定址法中找下一个空闲空间的散列函数为：Hi=(H(key)+di)%m

其中，i=1,2…k；di称为增量，以di的取值分为以下三种：(1)di=1,2,3…m-1,称线性探测再散列。(2)di=12,-12，22，-22，…±k2,(k≤m/2)称二次探测再散列。(3)di=随机数序列，称为随机探测再散列。开放定址法：第二十七页，共三十页，2022年，8月28日把具有相同散列地址的关键字放在同一链表中，称为同义词链表。通常把具有相同散列地址的关键字都存放在一个同义词链表中，有m个散列地址就有m个链表，同时用数组t[m]存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以t[i]为头指针