- 注册时间
- 2011-3-10
- 最后登录
- 1970-1-1
该用户从未签到
|
我也不太明白。我找了一些资料看起来比较清晰。我会不断补充我对他的理解和看法。希望大家都指教一下
哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
========================初始化(makenull)========================
设插入的元素的关键字为 x ,A 为存储的数组。
初始化比较容易,例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[ i ]:=empty;
End;
========================函数值的运算(h(x))========================
function h(x:longint):Integer;
begin
h:= x mod p;
end;
========================定位函数 locate========================
我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
//素存储的单元,要么表已经满了
locate:=(orig+i) mod S;
end;
=====================插入元素========================
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误,当然这是可以避免的
end;
========================查找元素========================
查找元素是否已经在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end; |
|