1.学习总结

1.1查找的思维导图

1.2 查找学习体会

• 这一章要学习的东西很多，看到他们说比较简单，但对于我来说我觉得还是非常有难的，你需要熟练掌握他们的原理和各种方法的ASL计算，这样才能根据题目找到最优解，但是这是很有难度的，平时需要抽时间去学习，记忆和理解。

  2.PTA实验作业

  题目1：6-2 是否二叉搜索树

  2.1设计思路

  非递归做法
  在T节点不为空的情况下{
           Q等于T节点
    while（栈中元素大于0或Q不为空）{
                扫描Q的所有左节点并进栈
     if（栈不为空） {
      进行出栈
        判断出栈元素数值是否为递增，不是则返回0
       转向处理Q的右孩子
              }
  }
  循环顺利结束证明为二叉搜索树
  }

  递归做法
  调用遍历完节点的左孩子
  判断节点数值是否为递增 不是返回0；
  进行节点右孩子的函数调用

  2.3 代码截图

  
  

  2.4 PTA提交列表说明

  
  

• 之前是先将树中的中序遍历的值放数组中，然后在进行判断数组是否为递增。在进行数组比较的时候最后面一个数没比较到，然后就部分正确，对循环条件改了一下就对了，但还是太麻烦了。后面老师上课有将到这题，回来就把数组去掉了，不然太麻烦。

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

  2.1设计思路

    增加一个查找函数 若存在返回1，不存在返回0
    节点T为空或者输入的节点在树中不存在，返回ERROR
    两结点中有答案结点，返回该结点
    当前根节点为祖先，返回该根节点的数值
    除去上述情况（证明两结点在当前节点的同一侧）
     根据情况进行函数递归调用

  2.2 代码截图

  

  2.3 PTA提交列表说明

  

• 没有考虑到上述的情况，一开始也不会如何去改，后面发现第二个测试点和第四个测试点要用递归去解决，第三个测试点用个if语句进行判断。

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

  2.1 设计思路

  定义map<string,int>Q
  输入N和K
  用数组C来存放用户身份证号码 
  计算会员的里程并存放到map函数中
  输入用户身份证
    若map存在存在，则输出里程
  不存在输出NO info 

  2.2 代码截图

  

  2.3 PTA提交列表说明

  
  

• 一开始是对一个点，后面是运行超时，然后照老师说的方法改了一下，把

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

  3.1PTA排名

  

  3.23.2 我的总分：145（PTA总分在120分--145分：2.5分）

  4阅读代码

  map按照value值查找的方法，就是find_if函数

  #include <string>
  #include<map> 
  #include <algorithm>
  class map_value_finder
  {
  public:
     map_value_finder(const std::string &cmp_string):m_s_cmp_string(cmp_string){}
     bool operator ()(const std::map<int, std::string>::value_type &pair)
     {
          return pair.second == m_s_cmp_string;
     }
  private:
      const std::string &m_s_cmp_string;                    
  };
  int main()
  {
  std::map<int, std::string> my_map;
  my_map.insert(std::make_pair(10, "china"));
  my_map.insert(std::make_pair(20, "usa"));
  my_map.insert(std::make_pair(30, "english"));
  my_map.insert(std::make_pair(40, "hongkong"));    
  
  std::map<int, std::string>::iterator it = my_map.end();
  it = std::find_if(my_map.begin(), my_map.end(), map_value_finder("English"));
  if (it == my_map.end())
     printf("not found\n");       
  else
     printf("found key:%d value:%s\n", it->first, it->second.c_str());
  return 0;        
  }

  class map_finder即用于比较的函数对象，它的核心就是重载的()运算符。因为每个容器迭代器的*运算符得到的结果都是该容器的value_type值，所以该运算符的形参就是map迭代器指向的value_type类型的引用。
  STL中源代码对map的value_type类型的定义

  template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
  class map
  {
  public:
  typedef Key key_type;
  typedef pair<const Key, T> value_type;
  ......
  };

  map的value_type是std::pair

  5代码Git提交记录截图

  

博客作业05--查找

原文：https://www.cnblogs.com/peng075078/p/9088531.html