第七章小结

数据与算法之美 2020-06-28

第七章--查找

一、

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;
}

相关推荐