下面是第七章的知识梳理。
一、查找的基本概念：
（1）查找表：查找表是由同一类型的数据元素（或记录）构成的集合。
（2）关键字：关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。
（3）查找：查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值得记录或数据元素。
（4）动态查找表和静态查找表：若在查找的同时对表作修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。
（5）平均查找长度（ASL）：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，成为查找算法在查找成功时的平均查找长度。
二、线性表
线性表查找方法：顺序查找、折半查找、分块查找。
顺序查找：1.适用于线性表的顺序存储结构，又适用于链式存储结构；
2.时间复杂度O（n）,空间复杂度O（1）
3.优点：算法简单，对表结构没有要求，且对记录是否按关键字有序均可应用
4.缺点：平均查找长度较大，查找效率较低，n很大的时候不适合用
折半查找：1.线性表必须采用顺序存储结构，而且表中的元素按关键字有序排列；
2.时间复杂度O（log2 n）
3.在查找成功与否的情况下：和给定值进行比较的关键字个数最多也不超过向下取整的(log2 n )+1
4.优点：比较次数少，查找效率高；
5.缺点：对表的要求高，一定要是顺序存储，且关键字必须有序；费时：1.查找前排序；2.对有序表进行插入和删除的时候，平均比较和移动表中一半的元素
6.折半查找不适用于数据元素经常变动的线性表
三、树表
树表的查找方法：二叉排序树、平衡二叉树、B-、B+树
①二叉排序树（二叉查找树）：对排序和查找都很有用的特殊二叉树
二叉排序树的二叉链表存储的类型定义与树类似，此外，二叉排序树的查找、插入、创建等操作可以通过递归实现，删除操作较为复杂一点，要分情况：①被删除的结点是叶子结点（先找到存放该值的结点，指向该结点和其双亲的指针，判断是否为叶子结点）。②被删除的结点只有左子树或只有右子树。③被删除的结点有左子树和右子树。
折半查找长度为n的顺序表的判定数是唯一的，但含有n个结点的二叉树却不唯一。因此，含有n个结点的二叉排序树的平均查找长度和树的形态有关。较好情况下，时间复杂度为O(log2n)，最坏情况下二叉排序树为单支树，时间复杂度为O(n)。
②平衡二叉树：保证搜索次数逼近log2n;
③B-树：解决平衡二叉树（当n很大时，高度很大）的局限性
④B+树：根据区间划分，实现区间查找。
四、散列表
（1）基本概念：
数字分析法；平方取中法；折叠法；除留余数法 （假设散列表表长为m，选择一个不大于m的数p，用p去除关键字，除后所得余数为散列地址）
（3）处理冲突的办法
开放地址法：线性探测法；二次探测法；伪随机探测法、链地址法
上周的目标算是达到了，自己好好钻研了下题目。下周的计划是好好复习准备迎接期末啦