淺談hashppt課件-資料下載頁
2025-04-29 03:10本頁面
【正文】 :=locate(x)。 //定位函數(shù)的返回值 if A[posi]=empty then A[posi]:=x else error。 //error 即為發(fā)生了錯(cuò)誤，當(dāng)然這是可以避免的 end。 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean。 var posi:integer。 begin posi:=locate(x)。 if A[posi]=x then member:=true else member:=false。 end。 快排 +二分： O(n)=n log2n 哈希表： O(n)=由于哈希函數(shù)的不同，時(shí)間復(fù)雜度很難估計(jì) 下面來看一下兩種排法的時(shí)間效率對(duì)比 1 2 3 4 5 6 7 8 9 10 11 12 但是，不能保證每個(gè)元素與函數(shù)值都是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)不同元素卻出現(xiàn)了相同的函數(shù)值 如 15 和 28對(duì)于 h(key):=key mod 13 有相同的函數(shù)值 —2 這樣就產(chǎn)生了“沖突” 另一個(gè)函數(shù) I 現(xiàn)在要儲(chǔ)存和使用下面的線性表： A: (1,75,324,43,1353,90,46). 上述兩種方法分別造成了時(shí)間和空間上的大量浪費(fèi)，尤其是數(shù)據(jù)范圍較廣時(shí)，可以對(duì)第二種方法進(jìn)行優(yōu)化 設(shè)計(jì)一個(gè)函數(shù) h(key):=key mod 13 然后把 key儲(chǔ)存在 a[h(key)]中， 這樣的話定義一個(gè) 0..12的數(shù)組就夠了 A:(18,75,60,43,54,90,46,5,15,33) h[i]:=i mod 13 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 18 mod 13=5 75 mod 13=10 60 mod 13=8 43 mod 13=4 54 mod 13=2 90 mod 13=12 46 mod 13=7 5 mod 13=5 15 mod 13=2 31 mod 13=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1