淺談hashppt課件-閱讀頁
2025-05-14 03:10本頁面
【正文】 ，而相對來說，第 9 位分布比較均勻，所以留下這 3 位作為地址（表中右邊一列）。具體取多少位視實際要求而定，取哪 幾位常常結(jié)合數(shù)字分析法。 折疊法 如果關(guān)鍵碼的位數(shù)比地址碼的位數(shù)多，而且各位分布較均勻，不適于用數(shù)字分析法丟掉某些 數(shù)位，那么可以考慮用折疊法。 一般是先將關(guān)鍵字分割成位數(shù)相同的幾段（最后一段的位數(shù)可少一些），段的位數(shù)取決于散列 地址的位數(shù)，由實際需要而定，然后將它們的對應(yīng)位疊加和（舍去最高位進位）作為散列地址。 分析：分如下 3 段： 5 8 4 | 2 2 2 | 4 1，則相加： 5 8 4 2 2 2 4 1 _______ 8 4 7 h(Key)=847 基數(shù)轉(zhuǎn)換法 將關(guān)鍵碼值看成在另一個基數(shù)制上的表示，然后把它轉(zhuǎn)換成原來基數(shù)制的數(shù)，再用數(shù)字分析 法取其中的幾位作為地址。 如： key=(236075)10 是以 10 為基數(shù)的十進制數(shù)，現(xiàn)在將它看成是以 13 為基數(shù)的十三進制數(shù) (236075)13,然后將它轉(zhuǎn)換成十進制數(shù)。 設(shè)插入的元素的關(guān)鍵字為 x ， A 為存儲的數(shù)組。 // 用非常大的整數(shù)代表這個位置沒有存儲元素 p=9997。 var i:integer。 End。 begin h:= x mod p。 我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應(yīng)該存儲在什么位置，因此加入一個定位的函數(shù) locate function locate(x:longint):integer。 begin orig:=h(x)。 while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do inc(i)。 end。 var posi:integer。 //定位函數(shù)的返回值 if A[posi]=empty then A[posi]:=x else error。 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean。 begin posi:=locate(x)。 e
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1