设为首页收藏本站

编程十万个为什么,属于程序员的编程论坛

 找回密码
 5秒快速注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
查看: 165|回复: 0

[转载文章] 数据结构常用算法精析(8)

[复制链接]
发表于 2017-1-10 15:46:51 | 显示全部楼层 |阅读模式
第九章 查找
查找分成静态查找和动态查找,静态查找只是找,返回查找位置。而动态查找则不同,若查找成功,返回位置,若查找不成功,则要返回新记录的插入位置。也就是说,静态查找不改变查找表,而动态查找则会有插入操作,会改变查找表的。
不同的查找所采用的存储结构也不同,静态查找采用顺序表,而动态查找由于经常变动,所以用二叉排序树,二叉平衡树、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.key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧:先将k存入监视哨,若对某个i(≠0)有r.data.key=k,则查找成功,返回i;若i从n递减到1都无记录的key为k,i再减1为0时,必有r.data[0].key=k,说明查找失败,返回i=0。
平均查找成功长度ASL= ,而查找失败时,查找次数等于n+l。
折半查找算法及分析
当记录的key按关系≤或≥有序时,不管是递增的还是递减的,只要有序且采用顺序存储。
您需要登录后才可以回帖 登录 | 5秒快速注册

本版积分规则

关闭

BcWhy推荐上一条 /1 下一条

QQ|关于我们|最新帖子|小黑屋|手机版|编程十万个为什么 ( 粤ICP备16108587号-2  

GMT+8, 2017-3-26 13:18 , Processed in 0.183529 second(s), 27 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表