. - , .
() . ( ) - . . , . . . . , . ( ) , - . , , . , .
, . . :
1. ,
2. .
k - . k(i) r(i) - . Key - . rec. , , .
, . .
( search ).
for i:=1 to n
if k(i) = key then
search = i
return
endif
next i
search = 0
return
:
for i:=1 to n do
if k[i] = key then
begin
search = i;
exit;
end;
search = 0;
exit;
. min = 1, Mmax = n. , (n + 1)/2.
, 2
n = n + 1
k(n) = key n:=n+1;
r(n) = rec k[n]:=key;
search = n r[n]:=rec;
return search:=n;
exit;
, (. 5.2).
:
: q=nil p=table while (p <> nil) do if k(p) = key then search = p return endif q = p p = nxt(p) endwhile s = getnode k(s) = key r(s) = rec nxt(s) = nil if q = nil then table = s else nxt(q) = s endif search = s return | : q:=nil; p:=table; while (p <> nil) do begin if p^.k = key then begin search = p; exit; end; q:= p; p:= p^.nxt; end; New(s); s^.k:=key; s^.r:=rec; s.^nxt:= nil; if q = nil then table = s else q.^nxt = s; search:= s; exit |
, , . , .
|
|
.
, . , .
-
: ( ) , , (. 5.3).
. , , - low, - - hi, (kind > key).
, key = 101.
, low hi.
:
: i = 1 while (i <= m) and (kind(i) <= key) do i=i+1 endwhile if i = 1 then low = 1 else low = pind(i-1) endif if i = m+1 then hi = n else hi = pind(i)-1 endif for j=low to hi if key = k(j) then search=j return endif next j search=0 return | : i:=1; while (i <= m) and (kind[i] <= key) do i=i+1; if i = 1 then low:=1 else low:=pind[i-1]; if i = m+1 then hi:=n else hi:=pind[i]-1; for j:=low to hi do if key = k[j] then begin search:=j; exit; end; search:=0; exit; |