老刘学数据结构

2021/02/02 09:30
阅读数 23

数据结构 查找

1.查找表:由同一类型的数据元素(或记录)构成的集合。
2.关键字:数据元素(或记录)中某个数据项的值,用以标识一个数据元素(或记录)。
3.查找:在查找表中确定一个其关键字等于给定值的记录或数据元素。
4.动态查找表:在查找的同时对表做修改操作(插入和删除),否则为静态查找表。
5.平均查找长度:ASL=求和Pi*Ci(Pi为查找表中第i个记录的概率,Ci为和给定值进行过的关键字个数)



顺序查找

又称线性查找,主要用于在线性表中进行查找。
从表的一端开始,依次将记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之则查找失败。
对无序线性表进行顺序查找,查找失败时要遍历整个线性表;对有序线性表进行顺序查找,查找失败时不一定要遍历整个线性表。
ASL成功=(n+1)/2
O(n)



折半查找

又称线性查找,主要用于在线性表中进行查找。
从表的一端开始,依次将记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之则查找失败。
对无序线性表进行顺序查找,查找失败时要遍历整个线性表;对有序线性表进行顺序查找,查找失败时不一定要遍历整个线性表。
ASL成功=(n+1)/2
O(n)



分块查找

又称索引顺序查找。
分块,子块内元素可以无序,但块间是有序的,即对于所有块有第i块的最大关键字小于第i+1块的所有记录的关键字。
ASL=Lb+Lw(Lb所在块的平均查找长度;Lw块中的平均查找长度)

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部