首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

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

2013-12-11 14:42:33来源：新东方在线编辑

　　

　　数据结构是计算机考研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按关系≤或≥有序时，不管是递增的还是递减的，只要有序且采用顺序存储。

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 4 5 6 7 8 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10