DS博客作业05--查找

0.PTA得分截图

1.本周学习总结

1.1 总结查找内容

查找概念
内查找&外查找

·内查找：整个查找过程都在内存进行

·外查找：查找过程中需要访问外存
动态查找表&静态查找表

·动态查找表：查找的同时对表做修改操作（如插入和删除）

·静态查找表：查找的同时对表不做处理
平均查找长度

·即ASL，查找过程中执行的关键字平均比较个数。用于衡量查找算法性能的主要指标

·分为成功和不成功情况下的ASL

·ASL（成功）：找到T（查找表）中任一记录平均需要的关键字比较次数。

·ASL（不成功）：查找失败（在T中未查找到）平均需要的关键字比较次数。
线性表查找
静态查找
顺序查找

·基本思路：从表的一段向另一端逐个将元素的关键字和给定值k比较。

·成功时ASL：(n+1)/2；不成功时ASL：n

·时间复杂度：O(n)

·优点：算法简单，对表的结构没有什么要求。

·缺点：查找效率低，n较大时不宜采用顺序查找法。
二分查找

·即折半查找，要求线性表是有序表，表中元素按关键字有序

·基本思路：

·二分查找的过程可用二叉树进行描述，由此得到的二叉树称为判定树或比较树

·ASL（成功）：log2 (n+1)-1

·时间复杂度：O(log2 n)

·伪代码：

int BinSearch(RecType R[],int n,KeyType k)
{
    定义low,high,mid;
    low=0;high=n-1;
    while low小于等于high
    {
        mid取值;
        if 查找成功
            return mid+1;
        if 关键字小于中间值
            high=mid-1;
        if 关键字大于中间值
            low=mid+1;
    }
    未找到，return 0;
}

·优点：查找的效率高

·注：对于二分查找来说，需要查找表的存储结构具有随机存取特性。所以在采用顺序表时，折半查找算法设计更方便，效率更高。

分块查找

·这是一种性能介于顺序查找和折半查找之间的查找方法，主要是利用到索引存储结构

·基本思路：首先查找索引表(元素有序)，采用折半查找或顺序查找来确定待查的元素在哪一块。然后在已确定的块中进行顺序查找(元素无序)

·ASL(成功)=log2(n/s+1)+s/2

·伪代码
```
int IdxSearch(IdeType I[],int b,RecType R[],int n,KeyType k)
{
    定义每块的元素个数s=n/b;
    定义low,high,mid;
    while low小于等于high
    {
        mid=(low+high)/2;
        if 关键字小于中间元素
            high=mid-1;
        else
            low=mid+1;
    }
    i=I[high+1].link;//让i等于对应块的下标
}
```
·缺点:增加一个索引表的存储空间和建立索引表的时间
动态查找
二叉排序树

·定义：空树或是满足以下性质的二叉树：

（1）若它的左子树非空，则左子树上所有结点值（指关键字值）均小于根结点值；
（2）若它的右子树非空，则右子树上所有结点值均大于根结点值；
（3）左、右子树本身又各是一棵二叉排序树。

·基本操作：

（1）插入与创建

·基本思路：若二叉树为空，创建一个key域为k的结点作为根结点；否则将k与根结点关键字进行比较；k小于关键字，插入左子树；大于，插入右子树；相等，return false；带有一种先序遍历的思想。

·伪代码：
```
BSTNode *CreateBST(KeyType a[],int n)
{
    初始化bt为空树;
    while i小于n
    {
        进行数据插入
    }
    return bt;
}
bool InsertBST(BSTNode *&bt,KeyType k)
{
    if 树为空
    {
        bt申请空间;
        bt关键字=k;
        bt左子树，右子树赋值为NULL;
    }
    if k等于关键字
        return false;
    if k小于关键字
        递归插入左子树;
    if k大于关键字
        递归插入右子树;
}
```
（2）查找

·基本思路：二叉排序树也可看为有序，所以在进行查找与二分查找类似。逐步缩小查找范围的一个过程。

·伪代码：
```
BSTNode *SearchBST(KeyType k,BSTNode *bt)
{
    if 树为空或关键字等于k
        return bt;
    if k小于关键字
        递归查找左子树;
    if k大于关键字
        递归查找右子树;
}
```
（2）删除

·基本思路：删除结点分为几个情况；①叶子结点，直接删去；②只有左子树而无右子树，左孩子进行替代；③只有右子树而无左子树，右孩子替代；④左右子树都存在，从左子树选择关键字最大结点进行替代。

·伪代码：
```
void Delete(BSTNode *&p)
{
    if p没有右子树
        用p的左孩子进行替代;
    if p没有左子树
        用p的右孩子进行替代;
    if p既有左子树又有右子树
    {
        递归寻找结点的左子树最右下结点r;
        将r的值存放到结点p;
        删除结点r并用r的左孩子进行代替;
        释放p的空间;
    }
}
```
·注：二叉排序树在进行中序遍历后所得到得序列为递增有序的。
平衡二叉树

·定义：一棵二叉树中所有结点的平衡因子的绝对值小于或等于1

·平衡因子：结点左子树的高度减去右子树的高度

·四种调整方法：

（1）LL型调整

（2）RR型调整

（3）LR型调整

（4）RL型调整

·删除结点

平衡二叉树与二叉排序树在删除结点类似，但又有所不同。平衡二叉树的删除主要是查找，删除，调整这三个步骤，删除分为以下几种情况：

（1）叶子结点：直接删除该结点

（2）单分支结点：用左右孩子进行替代

（3）双分支结点：用中序前驱结点进行替换
B树
B-树

·定义：又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构

·性质：

对于一颗m阶B-树：

①树中每个结点至多有m个孩子结点（即至多有m-1个关键字）

②除根结点外，其他非叶子节子点至少有m/2个孩子结点（即至少有m/2-1=(m-1)/2个关键字）

③若根结点不是叶子结点，则根结点至少有两个孩子结点

④所有外部结点都在同一层上，平衡因子均等于0

·B-树的操作

（1）查找

·基本思想：将k与根结点中的key[i]进行比较

·时间复杂度：O(logm n)

（2）插入

·基本思想：查找该关键字的插入结点（叶子结点层的结点），之后插入关键字。

·注：插入可能使B-树的高度+1

（3）删除

·基本思想：查找关键字所在的结点，进行删除。

·注：删除可能使B-树的高度-1

B+树

对于B+树，他是B-树的一些变形

·性质：

对于一颗m阶B+树：

①每个分支结点至多有m棵子树

②根结点没有子树或者至少有两棵子树

③除根结点外，其他每个分支结点至少有m/2棵子树

④有n棵子树的结点恰好有n个关键字

⑤所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字大小顺序连接。

⑥所有分支结点（索引的索引）中仅包含它的各个子结点（下级索引的索引块）中最大关键字及指向子结点的指针
散列查找
哈希表

·定义：又称散列表，是一种存储结构。

·基本思路：设置一个长度为m的连续内存单元，以每个元素的关键字为自变量通过哈希函数将关键字映射为内存单元的地址，并把关键字存储在这个内存单元中。

·几个概念：

·哈希冲突：两个不同的关键字得到相同的哈希地址，而这两个关键字也称为同义词

·填装因子：哈希表中已存入的元素数与哈希地址空间大小的比值。

·哈希函数的构造方法

（1）直接定址：以关键字k本身或关键字加上某个常量c作为哈希地址；即，h(k)=k+c;

（2）除留余数：用关键字k除以某个不大于哈希表长度m的整数所得的余数作为哈希地址；即，h(k)=k mod p;

（3）数字分析：提取关键字中取值较均匀的数字位作为哈希地址；

·哈希冲突的解决方法

（1）开放定址法

·线性探测法：从发生冲突的地址往下找一个地址直至空闲单元

优点：解决冲突简单

缺点：容易产生堆积问题

·平方探测法：探测序列为(d0+-i^2)……

优点：避免出现堆积问题

缺点：不一定能探测到哈希表上的所有单元

（2）拉链法

把所有的同义词用单链表连接起来，这样哈希表的每个单元存放的是相应同义词单链表的首结点指针。

例如：

优点：处理冲突简单，无堆积现象，平均查找长度短；单链表上的结点空间为动态申请，可以不知晓表长长度；节省空间；删除结点的操作更易实现。

运算算法
哈希表

·插入，建表：

求出关键字的adr，若该位置可以直接放置就直接放入；若冲突就采用线性探测法找到开放地址将关键字插入

·查找：

查找算法与建表过程类似，反复查找，直至某个地址单元与关键字比较相等

伪代码：
```
void SearchHT(HashTable ha[],int m,int p,KeyType k)
{
    adr=k%p;//计算哈希函数值
    while 单元不为空且单元不为k
        线性探测法往下探测;
    if adr地址所指向数值为k，找到;
    else 没找到;
}
```

哈希链

哈希链是一种顺序和链式相结合的存储结构

·插入与建表

首先将ha[i]的firstp指针设置为空，然后调用插入算法插入关键字。

伪代码：

void InsertHT(HashTable ha[],int &n,int p,KeyType k)
{
    计算哈希函数值adr;
    建立单链表q;
    q存放关键字k;
    if 单链表adr为空
        令其等于q;
    else
        利用头插法插入到ha[adr]中;
}

·查找

查找关键字k，只需在ha[h(k)]中找到对应的结点q，当q为空时表示查找不成功。

伪代码：

void SearchHT(HashTable ha[],int p,KeyType k)
{
    计算哈希函数值adr;
    新建单链表q,并指向对应单链表的首结点;
    while q不为空
        扫描单链表adr中的所有结点;
        if 查找成功，退出循环;
    if q不为空 then 查找成功;
    else 查找失败;
}

1.2.谈谈你对查找的认识及学习体会

关于查找，我又学习到了很多。
1、关于动态查找，静态查找的一些方法
2、内查找，外查找
3、关于衡量查找方法性能的标准：平均查找长度
4、各种树表的查找算法，二叉排序树，AVL树，B-B+树……
5、哈希表，哈希链
之前就有接触过哈希表，但对他就是既陌生又熟悉。一道题目出来在以前我就不会想到要用哈希表去解决，现在去学习了解完他之后，我就能去运用它。也知道不同的哈希函数，解决哈希冲突的不同方法对于一道题都有不同的解决情况……还有这些查找方法啊，像二分查找啊以前也有接触过，现在去分析性能啥的也有一个更好的理解体会。而另外像B树这些新知识，我也有在认真的吸收掌握，就是这个B树的删除我到现在还懵懵的……就慢慢体会，多问问同学可以的。

2.PTA题目介绍

2.1 二叉搜索树的最近公共祖先

2.1.1 该题的设计思路

这道题总共有两个大的问题需要解决，1、建树；2、查找公共祖先；
建树：当我像课本一样进行建树时，就会遇到超时的问题；原本算法在循环时又再次进行递归，时间上消耗大；便利用二叉树进行中序遍历时可以得到有序递增的序列便可以将原本序列进行排序得到中序序列，结合前序中序遍历序列就可以进行时间消耗相对减小的建树。
查找公共祖先：我们在查找的同时也需要进行判断这个数据是否真的存在于二叉树中，所以利用存储前序序列的pre[]来进行判断。当两个数据都存在时，利用了递归的方法进行查找，并返回这个祖先结点。

·时间复杂度：O(n)

2.1.2 该题的伪代码

int main()
{
    定义 i,pair,n;
    定义二叉树tree;
    定义pre[],in[];
    for i=0 to n
        将数据存入pre[]和in[]中;
    对中序数组in[]进行排序;
    建树;
    for i=0 to pair
        输入数据;
        进行共同祖先的查找;
}
BST CreateBSTree(int* pre, int* in, int n)//建树
{
    if n小于等于0 
        return NULL;
    定义指针pos;
    定义二叉树bst;
    bst->data=pre[0];
    for pos=in to in+n
        在中序中查找到根结点;
    根据中序序列进行左右孩子递归建树;
    return bst;
}
void search(BST tree, int num[], int data1, int data2, int n)
{
    定义二叉树ans;
    判断data1,data2是否存在二叉树中，并相应输出
    if data1，data2都存在
    {
        ans=SearchAns();//查找公共祖先
        对ans的数值和data1,data2进行判断;
    }
}
BST SearchAns(BST tree, int data1, int data2)
{
    if data1和data2分别在左右子树
        则根就是共同祖先;
    if 在左子树
        递归左子树进行查找;
    if 在右子树
        递归右子树进行查找;
}

2.1.3 PTA提交列表

Q1：刚开始用书本的方法建二叉树的时候就没建好，我没有将它分成建树和插入两个函数，结合在一起刚开始有将树赋初值为空树再进行递归就会出错。
A1：将建树分为两个函数进行了，虽然后面还是错了。
Q2：关于数据1是数据2的祖先这个情况我没有处理好
A2：我新建了二叉树ans进行SearchAns的返回，再将ans->data进行数据判断
Q3：就是关于超时的问题了
A3：我是问了其他同学，得知了可以用先序中序遍历建树的方法避免超时

2.1.4 本题设计的知识点

1、建树，建树方法不同，他的一些性能也不同。在不同场景用到不同的建树方法。
2、sort()函数，在库中。sort(in.begin(), in.end())就可以对一串数据进行排序。

2.1.5 代码截图

2.2 是否完全二叉搜索树

2.2.1 该题的设计思路

这道题目的三个关键步骤：1、建树，2、判断是否为完全二叉树，3、层次输出
判断是否为完全二叉树：将二叉树进行层次遍历，得到的序列计算在遇到null之前的非空结点个数，若与二叉树总结点数不符则不是完全二叉树。
层次输出：利用队列来进行输出

我们就是利用这个思路，再结合队列来进行解题。

2.2.2 该题的伪代码

int main()
{
    定义数组num[];
    定义二叉树tree;
    for i=0 to n
        将输入的数据存储在num[]中;
    建树;
    判断是否为完全二叉树并层次输出;
    是，输出YES;不是，输出NO;
}
int IsAll(BST& tree, int n)
{
    定义队列q，二叉树p;
    定义访问结点个数count，并赋初值为0;
    if 树为空
        return 1;
    else
        将树放入队列中;
        while 队首不为空且令p取队首值
        {
            将p的左右孩子入队;
            去队首;
            count自增;
        }
    if count等于n ，返回1说明是完全二叉树;
    else 返回0不是完全二叉树;
}
void PrintTree(BST& tree, int n)
{
    新建队列q;
    新建二叉树p;
    将tree放入队列中;
    while 队列不为空
    {
        p取队首;
        输出p结点数据;
        if 左孩子不为空
            左孩子入队;
        if 右孩子不为空
            右孩子入队;
    }
}

2.2.3 PTA提交列表

1、我在建树的时候在Create函数对bt进行申请空间，当递归时就会一直申请。所以就得把申请动态空间这一部分放在main函数中。
2、这道题题目呢有点小陷阱，我们需要把数值大的部分放入左子树，数值小的放入右子树。这样遍历出来才能跟样例相同。
3、在判断时，忘记将count赋初值为0.就导致一直判断不出来是否为完全二叉树。

2.2.4 本题设计的知识点

1、关于这个完全二叉树的定义。完全二叉树就是当二叉树的深度为k,除第 k 层外,其它各层 (1～k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边。我们利用层次遍历，当遍历序列的空结点后还有非空结点时就可以知道这不是完全二叉树了。
2、关于层次遍历进行队列的利用，结点出队，结点的左右孩子入队。这样往复我们就可以得到层次遍历序列。

2.2.5 代码截图

2.3 整型关键字的散列映射

2.3.1 该题的设计思路

这道题就是利用除留余数法求取地址，再发生哈希冲突时，在利用线性探测法往后寻找数据的地址。
不过这道题有个小陷阱就是有重复数据项的时候，这个数据应该还是在原来该有的位置上，而不是继续往后找直到有空位置。

2.3.2 该题的伪代码

int main()
{
    定义adr,num,numCount;
    定义结构体数组ha;
    定义数组index[]存放每个数字的下标;
    for i=0 to p
        初始化ha[];
    for i=0 to n
    {
        获取num;
        用除留取余法获取adr;
        if 这个地址还未访问过
            将num放入;
        else
            while 地址没有被访问过
            {
                if 有重复数据项
                    忽略;
                将查找次数递增;
                线性查找，+1往后访问;
            }
        将每个数据的下标存储在index[]中;
    }
    for i=0 to n
        输出每一个数据的下标;
}

2.3.3 PTA提交列表

刚开始，我也没有对哈希表进行初始化就直接往下了。后来一想，我没有初始化，怎么把count=0就当成是还未被访问过了呢？然后就初始化了一下……
（部分正确）：就是没注意到这个重复项的时候，刚开始还在想怎么改。然后第一次更改的时候我就把if判断语句放到while外面去了……就改的一塌糊涂。后来，迷途知返把这个放入while里面然后直接break；
（部分正确）：关于这个最大N过不了，刚开始吧MAX宏定义为1000。后来，看了几遍代码，其实是这个1000还不够。加了10，通过了。

2.3.4 本题设计的知识点

1、关于哈希表的建立，就是利用了除留余数法和发生哈希冲突后用到的线性探测法。
2、关于哈希表的初始化，进行初始化之后我们才能进行一些判断。比如我们初始化访问次数count为0，我们加上if语句才能知道这个数据到底有没有被访问过。