C语言数组常用算法3-分块查找和哈希查找

(1)分块查找

①、原则1:

前一块中的最大数据,小于后一块中的所有数据。(块内无序,块间有序)

②、原则2:

块数数量一般等于数字的个数开根号。例如,16个数字一般分为4块左右。

③、核心思路

先确定要查找的元素在哪一块,然后在块内挨个查找。

(2)分块查找的基本查找

查找30

块代码的书写

在内存中,就会生成如下的索引表

查找步骤:

先用二分查找找max的值,发现第三块的max值大于30,就在第三块的索引范围内查找数字30的索引。

(3)分块查找的扩展查找—无规律的数据

面对无序的数据,也可以分块,但是块与块之间的数据范围(即min~max)不能有交集。

比如查找48,去比较每一块数据的范围,最后确定在第五块,再在第五块的索引范围中查找数字为48的索引。

(4)分块查找的扩展查找—查找的过程中还需要添加数据,即哈希查找

由于要存100个数字,对100开根号,可以分成10块,每一块的范围依次递增。

当获取20时,20的范围在1-100之间,所以丢到块1;如果又生成了一个40,40也属于块1,但是块1零索引已经有数据为20,此时可以把40挂在20的后面。

如果遇到块中已经有的数据,先判断该数据的范围属于哪一块,再把数据放到块中的索引范围进行查找,一样就重新获取,不一样就存储好之后进行下一次获取。

文末附加内容
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇