算法基础

查找算法

问题一：在哪里找？

在查找表中查找，查找表是一种由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。

问题二：什么是查找？

根据给定的值，在查找表中确定一个其关键字等于给定值的数据元素（记录）

主关键字：唯一标识

次关键字：不唯一标识

问题三：如何判断查找成功？

查找——根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录），若存在此记录则查找成功，否则失败。

问题四：查找的目的

1.判断某个特定的数据元素是否在查找表中

2.检索某个特定的数据元素的各种属性。

3.在查找表中执行增删改查操作。

查找表的分类有哪些？

1.静态查找表：仅供查找

2动态查找表：执行插入，删除操作的查找表

如何评价查算法的优劣？

平均查找长度：关键字的平均比较次数。（ASL)Average Search Length

ASL = Pi*Ci(累加i从1到n)，Pi表示记录i出现的概率，Ci表示找到第i个记录所需的比较次数。

在查找过程中，我们要研究什么？

查找的方法取决于查找表的结构，即表中数据元素是以何种关系组织在一起的。对于查找表来说，一般都是一一对照着来查找。我们主要研究如何提高查找表查找的效率。

Time:2022.9.17

• 任务：学完线性表的查找。

线性表的查找

范围：顺序表或线性链表，表内元素是无序的。

顺序表

typedef struct {
    KeyType key;// 关键字域
}ElemType;
typedef struct 
{
    ElemType *R;// 表基地址
    int length;//表长
}SSTable // Sequential Search Table
SSTable ST;// 定义顺序表

int Search_Seq(SSTable ST, KeyType key)
{
    for( int i = ST.length; i >= 1; i--)
    {
        if(ST.R[i].key == key) return i;
    }
    return 0;
}

顺序查找2

int Search_Seq(SSTable ST, KeyType key)
{
    for(int i = ST.length; ST.R[i].key != key; --i)
    // for(int i = ST.length; ST.R[i].key != key&& i >0);
    // if(i > 0 ) return i; else return 0;
    {
        if(i <= 0) break;
    }
    if(i > 0) return i;
    else return 0;
}

改进

int Search_Seq(SSTable ST, KeyType key)
{
    ST.R[0].key = key;// 把关键字放在0位置
    for(i = ST.length; ST.R[i].key != key; --i);
    return i;// 找到就返回对应下标，否则返回关键字本身所在下标即0
}

顺序查找算法效率分析

记录的查找概率不相等时如何提高查找效率？

按照查找概率从高到低存储，查找概率越高，比较次数越少，查找概率越低，比较次数越多。

记录的查找概率无法测定时如何提高查找效率？

方法：按照查找概率动态调整记录顺序，在每个记录中设一个访问频度域，始终保持记录按非递增有序的次序排列;

在每次查找后均将刚查到的记录直接移动到表头。

顺序查找的特点

逻辑次序无要求，不同存储结构均使用。

ASL太长，时间效率太低。

折半查找（二分查找/对分查找）

每次将待查记录所在区间缩小一半

向下取整。

key == midsuccess
key < mid high = mid - 1
key > mid low = mid + 1
if low > high defeat

int Search_Bin(SSTable ST, KeyTable key)// 非递归算法
{
    low = 1;high = ST.length;// 设置区间初值
    while(low <= high)
    {
        mid = (low + high)/2;//计算中点
        if(ST.R[mid].key == key) return mid;// 如果找到了要查找的值
        else if(key < ST.R[mid].key)
            high = mid - 1;//高端移动至中点左侧
        else low = mid + 1;//低端移动至中点右侧
    }
    return 0;
}// Search_Bin

int Search_Bin(SSTable ST, KeyType key, int low, int high)
{
    if(low > high) return 0;// 查找不到直接退出
    mid = (low + high)/2;//计算出中值
    if(key == ST.elem[mid].key) return mid;
    else if(key < ST.elem[mid].key) Search_Bin(ST, key, low, mid - 1);
    else Search_Bin(ST, key, mid + 1, high);
}

折半查找的算法效率分析

判定树

详参手写笔记

分块查找

#把所有的数据元素分为若干块，然后在块中查找。

分块查找，或者记录本身有序，或者是分块有序

建立索引表，（结构数组的内容包含每个节点的最大关键字域和指向本块第一个节点的指针，且结构体的排序按照对应记录出现在表中的顺序排序，方便快速确定所查关键字在哪一部分）

先确定要查记录所在块（可用顺序或者折半法），再在块内查找

分块查找性能分析

详参手写笔记

分块查找优缺点

1.方便插入和删除，无需进行大量移动

2. 要对索引进行额外运算，包括空间分配和索引排序

适用于既要快速查找又要经常修改

各种方法对比

顺序查找虽然效率低，但是它的使用范围最广

折半查找只适用于顺序存储，且要求表的内容是有序的，不过它的效率最高

分块查找，和顺序查找具有同样的使用范围，查找效率居于前两者之间。

树表的查找（二叉排序树，红黑树，B-,B+树，键树）

二叉排序树（二叉搜索树，二叉查找树）

若左子树非空，其值均小于根节点，若右子树非空，其值均大于或等于根节点。左右子树本身又构成二叉排序树。

二叉排序树的特性，若采用中序遍历则会生成一个非递减的序列。

二叉排序树的查找

typedef struct 
{
    KeyType key;//关键字域
    InfoType otherinfo;//其它数据域
}ElemType;

typedef struct BSTNode
{
    ElemType data;//数据域
    struct BSTNode* lchild,*rchild;//左右孩子
}BSTNode, *BSTree;
BSTree T;//定义二叉排序树

BSTree SearchBST(BSTree T,KeyType key)
{
    if((!T) || key == T->data.key) return T;//结束条件，无论找到找不到
    else if(key < T->data.key) return SearchBST(T->lchild,key);//进入左字数
    else return SearchBST(T->rchild,key);//进入右子树
}//SearchBST

二叉排序树的查找分析

比较次数和关键字所在深度是一致的。

二叉排序树的查找长度：详参手写版

二叉排序树的深度越大，平均查找长度就越大。

如何提高不平衡二叉排序树的查找效率？答：平衡二叉树。

二叉排序树的插入

插入的位置一定是叶子节点注：插入算法需要自己实现

二叉排序树的生成

从空树出发，经过一系列的查找，插入操作之后，可以生成一个二叉排序树。如果存在相同元素，则不反复插入。

一个无序序列可以通过构造二叉排序树从而变成有序序列。因为插入位置始终是叶子节点，所以只需要修改根节点的指针，无序移动其他节点。

二叉排序树根据输入元素的先后次序不同，会生成不同形态的二叉树

注意，因为输入次序会导致不同形体的二叉树，因此输入次序不应按照从小到大来输入。这回导致生成一棵类似顺序存储的树，大大降低查找效率。

二叉排序树的删除

应保证删除一个节点，不影响整个二叉排序树的性质（即左小右大），保证以后对其进行中序遍历仍能生成递增序列。树的高度同样不能增加（可以减小）

对于叶子节点的删除，可以直接删除。指针域该为空。

对于根节点的删除，若被删除的节点只有右孩子或左孩子，那么被删除的是右孩子，就用其父右指针，指向其孙，若为左孩子，就用其父左指针指向其孙。

对于同时具有左右子树的节点的删除，用其左子树中的最大节点替换进此位置。或用右子树中的最小节点来替换进此位置。

Time: 2022.9.19

• 实现深度遍历和广度遍历。

平衡二叉树

AVL树：平衡二叉树，Adelson-Velskii and Landis 两位俄国科学家

平衡二叉树的性质：一棵平衡二叉树或者是空树，或者左子树与右子树的高度之差的绝对值小于等于;左子树和右子树也是平衡二叉树。平衡二叉树首先是排序二叉树

平衡因子 = 左子树高度 - 右子树高度[-1,1]

对于一棵有n个节点的AVL树，其高度保持在O(以2为底n的对数)数量级，ASL也保持在O(以2为底n的对数）量级。

平衡二叉树如何保持平衡？

按照排序二叉树的传统惯例插入新节点会导致二叉树失衡。为了追求更高的效率，我们必须调整树的结构以使之称为平衡二叉树。

当失衡节点不止一个时，首先考虑最小失衡子树。

四种失衡形态：LL型，LR型，RL型，RR型

调整原则：降低高度，保持二叉排序树的性质。

失衡二叉排序树的分析与调整

详参手写版笔记

散列表的查找（Hash表）

记录的存储位置与关键字之间存在对应关系

优点查找效率高，空间效率低

散列方法：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放;查找时，由同一个函数对给定值K计算地址，将K与地址单元中元素关键码进行对比，确定查找是否成功。

散列函数：散列方法中所使用的转换函数

散列表：按照散列方法构造的表叫做散列表

冲突：不同的关键码映射到同一地址。

同义词：具有相同函数值的多个关键字

在散列表中，冲突是不可避免的只能尽可能减少。

散列函数的构造方法：

地址计算函数应尽可能简单高效，计算出的地址应集中均匀分布，以减少空间浪费。

提前考虑好如何应对冲突

散列表的大小，散列表的长度，关键字的分布情况，查找频率，执行速度。（构造散列函数必须要考虑的因素）

散列表的本质是用空间换时间

均匀的目的是尽可能减少冲突

直接定址法++
数字分析法
平方取中法
折叠法
除留余数法++
随机数法

直接定址法：关键码key作为一个线性函数的自变量计算出的函数值作为地址

出留余数法：Hash(key) = key mod p(p is int)

出留余数法关键：选取合适的p值，如果表长是m，则p应为小于等于m的质数

质数：除了1和它本身之外，不能被任何数整除的数叫做质数。

p的值规定啦Hash表的长度，如果想有更大的表长，则应该取更大的p值作为除数

散列表的查找

开放定址法（开地址法）++
链地址法（拉链法）++
再散列法（双散列函数法）
建立一个公共溢出区

++表示重点学习部分

开放定址法

基本思想，有冲突是就去寻找下一个空的散列地址，只要散列地址足够大，空的地址总能够找到。

针对出留余数法：Hi = (Hash(Key) + Di) mod m, Di为增量序列
线性探测法，Di =线性序列
二次探测法Di = 1^2,-12, 2^2, -2^2……
伪随机探测法，Di为伪随机数

散列表的查找之线性探测

解决冲突的方法：开放定址法，拉链法

链式存储法的基本思想：把相同散列地址的记录链成一单链表。m个散列地址就设m个单链表，然后用一个数组将m个单链表的头指针存储起来，形成一个动态的结构。同义词存储在同一个链表当中。

链地址法的优点：

非同义词不冲突，无“聚集”现象

链表上节点空间是动态申请的，方便日后添加。

缺点：空间效率不高。

二次探测法

Hi = (Hash(Key) + Di) mod m

其中m等于4k+3的质数，m是散列表的长度，具体原因还需要思考。

散列表的查找

基本流程：给定要查找的元素k，利用Hash方法计算出其存储地址，然后去访问这个地址，如果该地址为空则直接突出，如果不为空，看看这个地址上是不是我们要查找的元素，如果不是按照 处理冲突的方法计算下一个地址。（可能为：线性探测，二次探测，伪随机探测中的任何一种）

散列表的查找及性能分析

散列表的平均查找长度取决于：1. 散列函数 2.处理冲突的方法 3.散列表的装填因子（装填因子 = 表中填入的记录数 除以 哈希表的表长，装填因子越大，说敏记录越多，表就装的越满，发生冲突的可能性就越大，查找时的比较次数就会增多。）

链地址法优于开地址法

除留余数法作散列函数优于其它类型函数

Time：2022.9.22

• 仔细学习数据结构与算法-严蔚敏版散列表章节。
• 复习二叉树的的知识，包括笔记，视频，代码