1.学习总结(2分)

1.1查找的思维导图

各种查找的时间复杂度，ASL成功，不成功。都要体现。

1.2 查找学习体会

谈谈你对查找算法学习体会。也可以谈谈STL容器中查找如何用的。

2.PTA实验作业（4分）

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

2.2 设计思路

int LCA( Tree T,  int u, int v ){
    定义 Tree类型变量 BST ,BSV，分别存放u，v在树的节点
    BST等于BSV等于T
    while BST不等于 NULL 遍历BST
        若找不到u
            return 错误
    如果找到了u
        while （BST不等于NULL）遍历 BST
        若找不到v
            return 错误
    如果找到了，对公共祖先的情况进行判断
    遍历T
        如果u和v都小于根节点 
            T指向左孩子
        如果u和v都大于根节点
            T指向右孩子
        如果根节点等于u
            返回 公共祖先u
        如果根节点等于v
            返回 公共祖先v
        如果 v和u分布在 根节点两侧
            返回 公共祖先 根节点的值
    end遍历
    如果 T==NULL
        return 错误；

}

2.3 代码截图

2.4 PTA提交列表说明。

部分正确：

• 一开始的想法是找到u和v在树的节点位置，然后向根节点遍历直到找到第一个相同的节点就是它们的公共祖先，但是操作难度有点大，就先用6-1 二叉搜索树的操作集中的查找函数先把u和v找出来提交了就有了部分正确..
• 后来是在网上找思路的时候，看到了这样的思路，就按照这个思路自己写了
  

2.1 题目2：7-1 QQ帐户的申请与登陆

2.2 设计思路

map定义一个用string 作为索引,并拥有相关联的指向string的指针 qq
定义整型变量 n,i;分别存放用户总数和循环变量
定义字符型变量 c 存放操作类型L or N
定义字符串型变量 user，pw 分别存放用户账号和密码

输入人数
for i=0 to i=N；共N次
    输入操作类型
    输入 用户和密码
    通过map对象的方法获取的iterator数据类型it
    it 等于在qq里寻找 user 的结果
    switch （操作类型）
        case L：{
        如果  账户不存在
            输出 "ERROR: Not Exist" 
        如果 账户存在 但是 密码错误
            输出"ERROR: Wrong PW"
        其他
            输出"Login: OK"
        }break；
        case N：{
            如果  用户已经存在
                输出 "ERROR: Exist"
            其他
                qq[user]等于pw；
                输出 OK
        }break；

2.3 代码截图

2.4 PTA提交列表说明。

1多种错误：.

• 一开始用函数的方法做这道题目,思路如下，多次提交记录不行是因为有些循环变量没有初始化等等的问题，后来过了题目sample的测试点，但是由于使用了太多的循环导致下面的两个测试点直接段错误，这时候问同学的时候提示说要用容器，确实相对之前的代码量，使用容器十分的清楚便捷。
  

定义全局变量人数num=0;
主函数：
    输入人数及操作类型lon
    输入 用户账号acc和密码word
    swich（lon）：{
            case ‘L‘:函数Local(acc,word);break; 
            case ‘N‘:函数New(acc,word);break;
}

void Local(char acc[],char word[]){//老用户登录
    如果 人数为0
        输出 ERROR: Not Exis
    否则
        for i=0 to i等于用户人数 ，共num次
            while 遍历账号数组
                如果 某位账号不符合 
                    break；
            end while
            如果全部配对
                while遍历密码数组
                    如果 某位密码不配对
                        break；
                end while
            如果配对成功
                输出Login: OK 并结束
            否则 
                输出"ERROR: Wrong PW 并结束

        end for
}

void New(char acc[],char word[]){//新用户申请
        如果人数等于 0
            直接录入
        否则 
            与之前的所有账号对比
            如果有配对成功的
                输出 ERROR: Exist
            否则
                录入新纪录
        人数 num加一

}

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

2.2 设计思路

int main（）{
定义整型变量 i 做循环变量
    N,M 存放用户数量
    K 存放官方最小里程
    trip 存放用户里程
定义long long类型变量 id，ID，分别存放，记录时身份证的前17位，查询时身份证的前17位
定义字符型变量 c 存放身份证最后一位校验码
map定义一个用long long 作为索引,并拥有相关联的指向int的指针 record.

    输入 N,K;
    for i=0 to i=N 共N次
    {       输入要录入的 id和c，还有里程数trip；
        如果 trip 小于最小里程
            则 trip 等于 最小里程
        通过map对象的方法获取的iterator数据类型it
        it 等于 在record里寻找 id的结果
        如果 找不到
            record[id]等于 用户里程数
        找到则
            该用户的里程数 加 trip          
    }end for;
    输入 M;//查询部分
    for i=0 to i=M,共M次
    {       输入查询的ID 和c
        通过map对象的方法获取的iterator数据类型it 
        it 等于 在record里寻找 id的结果
        如果 找不到
            输出 "No Info\n"
        找到则
            输出该会员里程数
    }end for；
return 0；
}

2.3 代码截图

2.4 PTA提交列表说明。

运行超时：.

• 1.怀疑变量类型长度不够 ，所以试着将int类型的N,M,K换成long 类型----运行超时！
• 2.然后换成long long -----运行超时！
• 3.后来问同学，说是使用cin，cout的时间比scanf，printf 的时间长，所以整型的变量的输入都换成了scanf，输出都换成 printf，但是字符串id还是用 cin--------运行超时！
• 4.最后把id分成了long long类型变量id前十七位数字和最后一位校验码字符型c，用scanf("%lld%c%d\n",&id,&c,&trip);输入会员账号和里程数-----成功！.

3.截图本周题目集的PTA最后排名

（201721123002）

3.1 PTA排名：4名

3.2 我的得分：2.5分（145分）

4. 阅读代码（必做，1分）

5. 代码Git提交记录截图

博客05--查找

原文：https://www.cnblogs.com/Zeng99/p/9084760.html