计算机考研:数据结构常用算法精析(8)
2013.12.11 14:42

  

  数据结构是计算机考研408计算机学科专业基础综合的重要组成部分,考生需要认真复习,尤其是对于数据结构中一些常用的算法问题,考生一定要弄懂弄会,理解的去掌握。新东方在线小编下面一一为大家分析一下,帮助考生更好地去掌握。

  第九章 查找

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

  不同的查找所采用的存储结构也不同,静态查找采用顺序表,而动态查找由于经常变动,所以用二叉排序树,二叉平衡树、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按关系≤或≥有序时,不管是递增的还是递减的,只要有序且采用顺序存储。

MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved