考研总分_优质考研机构推荐_中州考研信息网

计算机考研:数据结构常用算法解析(8)

作者: 报考宝典  发布:2020-01-17

  第九章 查找

  

  查找分成静态查找和动态查找,静态查找只是找,返回查找位置。而动态查找则不同,若查找成功,返回位置,若查找不成功,则要返回新记录的插入位置。也就是说,静态查找不改变查找表,而动态查找则会有插入操作,会改变查找表的。

  

  不同的查找所采用的存储结构也不同,静态查找采用顺序表,而动态查找由于经常变动,所以用二叉排序树,二叉平衡树、B-和B+。

  

  静态查找有,顺序查找,折半查找,分块查找(索引顺序查找)

  

  顺序查找(Sequential Search)是最简单的一种查找方法。

  

  算法思路

  

  设给定值为k,在表(R1 R2……Rn)中,从Rn即最后一个元素开始,查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k,则查找成功,返回记录序号i;否则,查找失败,返回0。

  

  算法描述

  

  int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//

  

  { int i;

  

  r.data[0].key=k; //k存入监视哨//

  

  i=r.len; //取表长//

  

  while(r.data[i].key!=k)

  

  i--; //顺序查找//

  

  return(i);

  

  }

  

  算法用了一点技巧:先将k存入监视哨,若对某个i(≠0)有r.data[i].key=k,则查找成功,返回i;若i从n递减到1都无记录的key为k,i再减1为0时,必有r.data[0].key=k,说明查找失败,返回i=0。

  

  平均查找成功长度ASL= ,而查找失败时,查找次数等于n+l。

  

  折半查找算法及分析

  

  当记录的key按关系≤或≥有序时,不管是递增的还是递减的,只要有序且采用顺序存储。

  

  算法描述

  

  int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//

  

  { int low,high,mid;

  

  low=1;high=r.len; //上下界初值//

  

  while(low

  

  { mid=(low+high)/2; //求当前mid//

  

  if (k==r.data[mid].key)

  

  return(mid); //查找成功,返回mid//

  

  if (k

  

  high=mid-1; //调整上界,向左部查找//

  

  else

  

  low=mid+1; //调整下界,向右部查找//

  

  }

  

  high,查找失败//

  

  }

  

  判定树:用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树,但他的叶子结点所在层次之差不超过1。所以,折半查找在查找成功时和给定值进行比较的关键字个数至多为

  

  ASL=

  

  分块查找算法及分析

  

  分块查找(Blocking Search),又称索引顺序查找(Indexed Sequential Search),是顺序查找方法的一种改进,目的也是为了提高查找效率。

  

  1.分块

  

  设记录表长为n,将表的n个记录分成b= 个块,每块s个记录(最后一块记录数可以少于s个),即:

  

  且表分块有序,即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key,但块内记录可以无序。

  

  2.建立索引

  

  每块对应一索引项:

  

  KeymaxLink

  

  其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。

  

  3.算法思路 分块索引查找分两步进行:

  

  (1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)

  

  (2)在块内顺序查找。(只能用顺序查找,块内是无序的)
 

本文由考研总分_优质考研机构推荐_中州考研信息网发布于报考宝典,转载请注明出处:计算机考研:数据结构常用算法解析(8)

关键词: 报考宝典