1.学习总结

1.1查找的思维导图

1.2 查找学习体会

• 线性表的查找相对来说简单多了，主要是它存储结构是线性的、逻辑比较容易理解，操作起来也比较容易。学到树表的查找后，内容有点多，而且也不太容易理解，二叉搜索树、平衡二叉树、AVL树、B-树、B+树，各种查找树，不仅逻辑上复杂，操作及代码的编写也复杂，还有各自ASL的计算，平衡二叉树的插入删除调整，所以学起来挺困难的，花了挺多时间。再到哈希表的查找，内容相对较少，但是也不好理解，单单是建表就不简单，还有解决哈希冲突的方法、ASL的计算。总之，树表与哈希表的查找相比线性表难度大了很多，需要花更多的时间去学习。

2.PTA实验作业

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

1.1设计思路（伪代码或流程图）

int LCA( Tree T,  int u, int v )
{
    如果T为空     return ERROR
    如果u不在树中或v不在树中   return ERROR
    如果u，v都等于T->Key     return T->Key
    如果 u>T->Key&&v<T->Key或者u<T->Key&&v>T->Key    return T->Key
    如果u>T->Key    递归调用LCA(T->Right,u,v) 
    如果u<T->Key    递归调用LCA(T->Left,u,v)
}

1.2代码截图

1.3PTA提交列表说明

• 刚开始提交部分正确，测试点提示不在树中的情况错误，原来是忽略了不在树中情况，后面为了还是用递归的方法，添加了一个判断节点是否在树中的find函数，修改完后提交正确。
  
  

题目2：

2.1设计思路（伪代码或流程图）

int main()
{
    map<string,string>a  创建一个map容器
    定义变量n,i;
    定义三个字符型数组 order[2],qq[12],password[22],分别表示指令,qq号码,密码
    输入n
    for(i=0   to   i=n-1)
    {
        输入order（L或N）
        如果指令是申请（N） 
        {
            输入号码qq,密码password ;
            如果a[qq]不为空  输出 ERROR: Exist
            否则 将password存入a[qq] 并输出 New: OK
        }
        如果指令是登陆（L）
        {
            输入号码qq,密码password ;
            如果a[qq]为空  输出 ERROR: Not Exist
            否则{
                如果a[qq]不等于password  输出ERROR: Wrong PW 
                否则  输出Login: OK 
            } 
        } 
    } 
}

2.2代码截图

2.3PTA提交列表说明

• 此题思路比较清晰，因为用了map容器，所以代码量较少许多，提交错误的原因在于指令内的判断写反了，在申请号码时，输出 ERROR: Exist应该是在a[qq]不为空时；在登陆号码时，输出ERROR: Not Exist，应该是在a[qq]为空时，改正后提交正确

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

3.1设计思路（伪代码或流程图）

int main()
{
    map<string,long long>a  创建一个map容器
    定义变量n,m,k,i;k为最低里程
    定义字符数组id[20]存储身份证号码,定义dis表示里程 
    输入n，k
    for(i=0   to   i=n-1)   
    {
         将信息存入map容器
    }
    输入m
    for(i=0   to   i=m-1) 
    {
        输入要查找的id
        如果id存在   输出a[id]
        否则   输出 No Info
    }
}

3.2代码截图

3.3PTA提交列表说明

• 此题提交了很久都是部分正确，后面两个点过不去，请教同学说是不能用c++的输出和string，改过来后还是不行，和舍友讨论很久，后来又把变量类型改成long int或者long long型的，还是提交不正确，最后觉得是程序运算有错，经过调试发现是在存储的时候出错了，我把最低里程k都当成了500，在判断dis时不是与k进行比较，而是与500进行比较，所以只有第一个测试点过的了，改过来后理所当然过了

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

PTA总分：145

3.1 PTA排名

3.2 我的总分：2.5分

4. 阅读代码

hash_map容器源码中put方法的实现

/**
*将指定的键key,值value放到HashMap中
*/
public V put(K key, V value) {
    
    if (key == null)
        return putForNullKey(value);
   
    int hash = hash(key.hashCode());
    
    int i = indexFor(hash, table.length);
    
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            
            e.recordAccess(this);
            return oldValue;
        }
    }
    
    modCount++;
    
    addEntry(hash, key, value, i);
    
    return null;
}

• 首先判断键key是否为null,若为null,则调用putForNullKey(V v)方法完成put，如果key不为null了，先调用hash(int)方法，计算key.hashCode的hash值，再调用indexFor(int,int)方法求出此hash值对应在table数组的哪个下标i上 (bucket桶)，遍历bucket桶上面的链表元素，找出HashMap中是否有相同的key存在，若存在，则替换其value值，返回原来的value值，若元素e.hash值和上面计算的hash值相等，并且(e.key == 入参key,或者入参key equals 相等 e.key)，则说明HashMap中存在了和入参相同的key了，执行替换操作；在执行替换操作的时候，调用Entry对象的recordAccess(HashMap

5. 代码Git提交记录截图

博客作业05--查找

原文：https://www.cnblogs.com/mayifang/p/9090693.html