本章思维导图：
1、线性表查找：
（1）顺序查找：从表的一端开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果扫描完整个表，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。优缺点：算法简单，对表结构无任何要求；但是平均查找长度较大，查找频率较低。
带哨兵的顺序查找：不需要每次查找都检测是否查找完毕
（2）折半查找（二分查找）：前提1.表中元素按关键字有序排列 2.必须采用顺序存储结构
时间复杂度：O（log2n）比较次数少，查找效率高，不适合数据元素经常变动的线性表
（3）分块查找：优点：插入、删除数据元素时，只要找到该元素对应的快就可以进行插入、删除。因为块内无序，所以插入、删除比较容易，不需要进行大量移动。
线性表更适合静态查找，用树表可以让动态查找更高效
2、树表的查找
（1）二叉排序树：左子树上所有结点值均小于根节点，右子树均大于根节点
!!中序遍历一棵二叉树时可以得到一个节点值递增的有序序列
!! 删除：分为 a.被删结点时叶子结点 b.只有左子树或者只有右子树 ：直接令左子树或右子树直接成为其双亲结点*f的左子树即可 c.左子树和右子树均不为空 ：在左子树上找中序最后一个结点填补
（2）平衡二叉树：如果二叉排序树的结构合理，查找速度越快，接近O（log2n）=>高度越小，查找速度越快=>平衡二叉树
特点：1.左右子树的深度之差绝对值不超过1 2.左右子树也是平衡二叉树
（3）B-树和B+树的区别
1）有n棵子树的结点中含有n个关键字
2）所有的叶子结点中包含全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而 大顺序链接
3）所有的非终端节点可以看成是索引部分，结点中仅含有其子树（根节点）中的最大（或最小）关键字
3、散列表的查找
处理冲突的方法：
PTA编程题Hashing
这道题我直接将输入的数用给出的散列函数映射到了bool数组，一开始数组初始化为false表示没有对应的数，经过散列函数映射，对应temp下标没使用就改为true，使用了就用二次探测解决。
首先要找到表长对应的最大素数，再对应进行相应操作：
1 bool isPrime(int num) 2 {//判断是否为素数 3 if(num==1) 4 return false; 5 for(int i=2;i<=sqrt(num);++i){ 6 if(num%i==0) 7 return false; 8 } 9 return true; 10 } 11 12 int findPrime(int num) 13 {//找到比给定值大的素数 14 for(int i=num; ;++i) 15 { 16 if(isPrime(i)) 17 return i; 18 } 19 }
散列 思路如下：
for(int i=0;i<N;++i) { cin>>num; temp=num%trueMsize;//进行散列函数运算 if(flag[temp]==false) {//temp下标没有存数据 cout<<temp; flag[temp]=true; } else{//temp下标有存数据 for(j=1;j<trueMsize;++j) {//用二次探测解决冲突 temp=(j*j+num)%trueMsize; if(flag[temp]==false) {//如果temp下标的单元为空 cout<<temp; flag[temp]=true; break;} } if(j>=trueMsize)//无法插入号码 cout<<"-"; } if(i!=N-1) cout<<" "; }
以下是完整代码
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 bool isPrime(int num); 6 int findPrime(int num); 7 void go(); 8 9 int main() 10 { 11 go(); 12 return 0; 13 } 14 15 bool isPrime(int num) 16 {//判断是否为素数 17 if(num==1) 18 return false; 19 for(int i=2;i<=sqrt(num);++i){ 20 if(num%i==0) 21 return false; 22 } 23 return true; 24 } 25 26 int findPrime(int num) 27 {//找到比给定值大的素数 28 for(int i=num; ;++i) 29 { 30 if(isPrime(i)) 31 return i; 32 } 33 } 34 35 void go() 36 { 37 int Msize, N,j; 38 cin>>Msize>>N; 39 int trueMsize=findPrime(Msize);//将表的大小重新定义为最大素数 40 bool flag[trueMsize]={false};//标记该地址是否有存放数据 41 int num; 42 int temp; 43 for(int i=0;i<N;++i) 44 { 45 cin>>num; 46 temp=num%trueMsize;//进行散列函数运算 47 if(flag[temp]==false) 48 {//temp下标没有存数据 49 cout<<temp; 50 flag[temp]=true; 51 } 52 else{//temp下标有存数据 53 for(j=1;j<trueMsize;++j) 54 {//用二次探测解决冲突 55 temp=(j*j+num)%trueMsize; 56 if(flag[temp]==false) 57 {//如果temp下标的单元为空 58 cout<<temp; 59 flag[temp]=true; 60 break;} 61 } 62 if(j>=trueMsize)//无法插入号码 63 cout<<"-"; 64 } 65 if(i!=N-1) 66 cout<<" "; 67 } 68 }
实践题目前还在摸索中，在弄懂了之后再好好整理一下。
上次的目标有好好完成了，也成功拯救了007。现在到了期末阶段了，接下来的目标就是：好好整理学过的东西，按计划开始复习，整理每一章要点。
原文：https://www.cnblogs.com/liulijun1551/p/10963166.html
