1.本周学习总结

1.思维导图

2.谈谈你对查找运算的认识及学习体会。

对于查找这一章，这章跟之前的章节相比，没有了一个具体的数据结构，像队列、栈、树、图之类的结构，感觉像是学了几种算法，这几种算法

在时间复杂度上跟我们现在用的算法有着明显的优势，以前一般都是用一些很普通的算法来查找一个值，一般时间复杂度也比较高，可能是因为

在PTA上做题不用那么考虑时间复杂度的问题，答案对了就行代码没问题的话一般也不会超时，在写代码的时候也很少会想起来要用较优的算法

来减少时间复杂度。查找这一块内容在写任何程序的时候还是经常用到的，特别是对线性表的查找，以后写代码也不用像最开始学习编程一样查

找都是从头到尾按顺序查找，而是可以参考书上的算法、

2.PTA实验作业

2.1.题目1：7-2 航空公司VIP客户查询

2.1.1设计思路（伪代码）

int map
    
     vipfor i=0 to n then     对vip赋值end forfor i=0 to m then     输入要查找的账户，并输出账户中的积分信息，不存在则输出"No Info"end for
    

2.1.2代码截图

2.1.3本题PTA提交列表说明。

Q1:超时问题

A1:ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

在主函数的开头加上这串代码就可以减少程序运行的时间

Q2:初始对map赋值

A2:在开头对map赋值时，最初的代码有一个查找的操作判断有无会员信息，然后再考虑里程是直接赋值还是要和之前的相加，

后来发现不用查找，所有的map中的值全都都相加并没有关系

2.2.题目1：6-4 jmu-ds-哈希表操作集

2.2.1设计思路（伪代码）

创建hash表函数for i=0 to m then     初始化hash表end forfor i=0 to n then      对hash表赋值，并使用线性探测的解决冲突end for查找hash表函数if(ha[num].key == k)     return num      //第一次查找就找到对应数值else    while(1)        依次往下查找，直到找到对应数值或找到为空的单位     end whileend if

2.2.2代码截图

2.2.3本题PTA提交列表说明

Q1:部分正确

A1: 1、在建立哈希表的时候条件判断语句条件错误，应该是在哈希表为空的时候进行赋值，而不是在哈希表不为空的时候赋值，==写成!=

2、uns_count没有加上最后一次的次数，导致不成功的查找次数少1

3、在查找时，若k%p的位置上不是当前查找的元素，进行循环时没有对长度num+j进行取余，导致哈希表越界

2.3.题目3：6-3 二叉搜索树中的最近公共祖先

2.3.1设计思路（伪代码）

p1=根节点Twhile(p1!=NULL)     查找树中是否存在值为u的结点end whilep1=Twhile (p1!=NULL)     查找树中是否存在值为v的结点end whilep1=Twhile(p1!=NULL)      if(v和u分别大于和小于当前结点或u或v中有一个等于当前结点的值)            return T->key      end if      if(u和v都小于当前结点的值)            T= T->Left       end if      if(u和v都大与当前结点的值)            T=T->Right       end ifend while

2.3.2代码截图

2.3.3本题PTA提交列表说明。

Q1:运行超时

A1:超时问题刚开始还以为是算法问题，以为是算法太复杂了导致的超时，后来发现是没有考虑到几种情况导致查找

找不到一个结果，这几种情况就是当输入的结点之一就是他们最近的公共祖先时，这是函数就没有出口而是一直查找

下去

3、阅读代码

3.1 题目

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

来源：力扣（LeetCode）

3.2 解题思路

先判断当前这个树是否个位数的平方和为1，若是的话直接返回1，否则就判断set中的头尾是否相等，若不相等则这个树

就不可能是个快乐数返回false，没有返回false的话则将当前数的各位平方和插入到set中继续下一轮循环。

3.3 代码截图

3.4 学习体会

在查找这一章中，不仅学会了一些查找的算法和数据结构，像二分查找、分块查找、树表的查找和哈希表的查找等等，

在学习这些的过程中同时也学到了两种c++中的容器的使用，set和map，这两种容器在查找个别数据时会显得非常方便

在加上这些容器中有自带的查找函数，根本不用自己打代码，不仅节省时间而且也减少了出错率。