1.学习总结(2分)

1.1查找的思维导图

1.2 查找学习体会

查找是C语言的重要内容，以前我就学过顺序查找和二分查找，现在学习的查找主要通过，哈希表，二叉搜索树，二叉平衡树等数据结构来等来实现，这样的查找方法可以更高效率地进行查找，学习的内容包括平衡树的LL、RR、RL、LR四种变换，哈希冲突的处理，以及查找的时间复杂度，ASL成功与不成功的计算，B-树插入删除时的分裂等等，但是遇到的问题是在学会基本原理的时候，对于查找的运用并不是了解很多，应该练习更多的对于查找的运用，还有就是map的使用使得函数更为简洁。我发现查找的内容还有很多没有学习精深，还有很多需要学习的，现在学习的只是基本的查找内容，还要更加努力。

2.PTA实验作业（4分）

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

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

bool IsBST ( BinTree T ) if(T节点为空）   return 1; else      {    定义一个静态整数变量min=-999999     递归左节点      if(T的data大于min）       min=T->Data;      else       return 0    递归右节点      }

2.3 代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

2.4 PTA提交列表说明。

• 这道题我起先是想用中序遍历将所有的数据存放在数组中，再将其中的树看是否顺序来判断，但是代码量太大，后来老师说了这种方法效率大大提高，
  用递归来操作，代码就几十行就完成了，受益匪浅。

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

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

int find(Tree T,int u)  查找函数  if(T为空）      return 0  else{     采用递归法查找     找到 return  1     若小于data则递归左边     否则递归右边         }查找最近公共祖先int LCA( Tree T,  int u, int v )  {  if(T为空）    return ERROER  if(T中没有u或v）    return ERROER  if(T的两边分别是v和u)    return T->Key  if(u大于T->KEY)    向右递归  if(u小于于T->KEY)    向左递归  }

2.3 代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

2.4 PTA提交列表说明。

• 这题我做了挺久但是还是没做出来，后来请教了舍友才明白怎么做，这道题重点是在于几个if的顺序，首先是先判断是否存在于搜索树中，
  然后判断是否是其祖先，（就是判断他的uv是否在左右两边）这点是这道题的关键。

2.1 题目1：7-1 QQ帐户的申请与登陆（25 分）

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

map
    
     pmap
     
      pp  定义n作为指令个数  定义x，y，z字符串存储QQ的账号密码  输入n while(n--) {    输入 x，y，z的值    if(x为L)     {          if（p[y]不存在）           输出ERROR: Not Exist          else             判断密码pp[y]，若pp[y]为z 则失败否则登陆成功     }    else     {         if(p[y]为1)          表示账号已存在         else               {                    将账号存入p[y]为1将密码z存入pp[y]                   并输出New: OK     }
     
    

2.3 代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

2.4 PTA提交列表说明。

• 这道题主要是map的使用，原先没用到map想算法的时候用红黑树的话要自己建树，代码量很大，用到map后，只需要定义一下mao就行，代码并不复杂只是关于map的使用。

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

3.1 PTA排名（截图带自己名字的排名）

3.2 我的总分：145

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

/* * 添加节点：将节点(node)插入到红黑树中 * * 参数说明： *     root 红黑树的根 *     node 插入的结点        //  */static void rbtree_insert(RBRoot *root, Node *node){    Node *y = NULL;    Node *x = root->node;    // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。    while (x != NULL)    {        y = x;        if (node->key < x->key)            x = x->left;        else            x = x->right;    }    rb_parent(node) = y;    if (y != NULL)    {        if (node->key < y->key)            y->left = node;                // 情况2：若“node所包含的值” < “y所包含的值”，则将node设为“y的左孩子”        else            y->right = node;            // 情况3：(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子”     }    else    {        root->node = node;                // 情况1：若y是空节点，则将node设为根    }    // 2. 设置节点的颜色为红色    node->color = RED;    // 3. 将它重新修正为一颗二叉查找树    rbtree_insert_fixup(root, node);}

• 这是红黑树的建立c语言代码，rbtree_insert(root, node)的作用是将"node"节点插入到红黑树中。其中，root是根，node是被插入节点。实现插入的时候将节点的颜色改变

  ，并且用递归方法调整了红黑树。十分巧妙。

• 这里面是我看到的比较详细的红黑树C语言实现讲的简洁清晰，细节方面写的很好，很好理解分享给大家。

5. 代码Git提交记录截图