第七章小结

第七章--查找

一、

1、动态查找表和静态查找表

动态查找表：在查找的同时对表修改操作（如：插入和删除）

静态查找表：与动态查找表刚好相反

2、平均查找长度

（即关键字的平均比较次数）为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度

若查找概率相同： ASL = （C1+C2+C3+C4+...）/n

若查找概率相同且进行：ASL=  （C1+C2+C3..+Cn）/n = （n+1）/2

3、

二分查找法：

对线性表进行二分查找时，要求线性表必须以顺序方式存储，且结点按关键字值有序排列。

int Search_Seq(SSTable ST,KeyType key)
{//找到，则为该元素的位置，否则为0
low=1;high=ST.length;
while(low<-high)
{
mid = (low+high)/2;
if(key==ST.R[mid].key) return mid;
else if(key<ST.R[mid].key) high =mid-1;//前一字表查找
else low = mid+1;//后一字表查找
}
return 0;//找不到
}

这个方法的ASL=log2(n+1)

4、

二叉排序树：（时间复杂度接近二分查找法）

左子树上的所有节点的值小于它的根节点的值

右子树则大于它的根节点的值

平衡二叉树：

左子树和右子树的深度之差不超过一

左右子树均是平衡二叉树

5、

散列表的查找：

散列函数与散列地址：Hash函数，可以得到散列地址

散列表：一个有连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录

如何构造散列函数；

1）数字分析法； 2）平方取中法 ；3）折叠法； 4）除留余数法：H（key）=key%p(p为小于表长的最大质数）；

处理冲突的方法：

开放地址法：线性探测法（找空位法） 二次探测法（记得利用平方相加）链地址法：存放在链表里

二、pta

1、将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为M/S：T

散列表的装填因子定义为：α填入表中的元素个数/散列表的长度α是散列表装满程度的标志因子

2、召回率与准确率（这里是不太懂的）

https://www.cnblogs.com/Zhi-Z/p/8728168.html

3、已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是

比较次数最多为5次，最少为4次

 4、Hashing

判断素数，获取素数

int sushu(int m)//验证一个数是不是素数
{
 if (m == 1)
  return 0;
 int i = 2, n;
 n = sqrt(m) + 1; //n的平方数+1
 while (i < n)
 {
  if (m % i == 0)  //整除，直接返回函数值0 
   return 0;
  i++;
 }
 if (i == n) //非整除退出循环，i肯定等于n
  return 1;
}
int Getsushu(int x)//判断是不是素数，如果不是+1，循环
{
 int i = x;
 while (1)
 {
  if (sushu(i))//如果是素数，退出
   break;
  i++;
 }
 return i;
}