这一章主要学习了查找的基本概念、线性表的查找、树表的查找、散列表的查找等查找的相关知识
线性表的查找包括顺序查找、折半查找和分块查找
顺序查找比较简单，基本就是以前最常用的查找方法，不过现在多学了一个小技巧，可以在数组中设置哨兵，免去检测表是否查找完毕，减少查找所需时间
1 int search(int st[], int key, int n) 2 { 3 st[0]=key; 4 for(int i=n; st[i]!=key; --i); 5 return i; 6 }
折半查找在上学期的计算机科学导论课有了初步的认识，现在更深入地学习了这个算法
要注意在操作过程中如果把high=mid-1改成high=mid，或者把low<=high改成low<high，都会发生错误
分块查找包括块间查找和块内查找两步，块间查找可以用顺序查找或二分查找，块内只能用顺序查找
树表的查找主要是学了二叉排序树，每个结点的左子树中每个元素的值小于自身，右子树大于自身
在一些情况下树的结构会不平衡，所以需要平衡二叉树，通过每一次插入结点的同时移动结点位置使整棵树平衡
除了二叉排序树之外还学习了b树、b+树等特殊结构
然后学习了散列表
散列表的构造方法包括数字分析法、平方取中法、折叠法、和常用的除留余数法等
处理冲突的方法包括开放地址法和链地址法两大类
开放地址法包括线性探测法、二次探测法、伪随机探测法等，用画图的方式很好理解，不过这周做题的时候忘了数组第一个下标是0，把第一个想成了1，然后后面全部画错，犯了低级错误，以后要记住这个教训
链地址法是用于链表的查找
这一周学习的内容比起上一章算不上很难，但很容易犯细节上的错误，接下来在学习中要多注意数组下标还有查找过程中容易出现的错误
另外最近上课方式从之前录播转到直播后还是有一点不太习惯，接下来要努力适应
原文：https://www.cnblogs.com/nzgfs/p/13198859.html