信息学竞赛常用算法与策略：查找

标签：信息学

查字典合肥奥数网讯：信息学竞赛常用算法与策略：查找。

查找是在数据结构中查找指定值的结点。

5.1 顺序查找

1.顺序查找的思想是是：

将查找值顺序逐个与结点值进行比较,相等即为查找成功,否则查找失败.

程序如下：

program sxcz;

const n=7;

type

arr=array[1..n] of integer;

var x1,i:integer;

a:arr;

b:boolean;

place:integer;

procedure search(r:arr;m,x:integer; var found:boolean;var p:integer);

begin

p:=1;found:=false;

while(p<=m) and not found do

if r[p]=x then found:=true else p:=p+1;

end;

begin

write('Enter array:');

for i:=1 to n do read(a[i]);

writeln;

write('Enter search data:');

read(x1);

search(a,n,x1,b,place);

if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end

else writeln('no');

end.

5.2 二分查找

1.二分查找的基本思想:首先将结点按关键字排序,其次将查找值与中间位置的值比较,相等,查找成功;不等,则中间数据大于或小于查找值,无论怎样查找将在一半的数据中查找。

2.例:输入序列数据查找指定值.

程序:

program sxcz;

const n=7;

type

arr=array[1..n] of integer;

var x1,i:integer;

a:arr;

place:integer;

procedure paixv(var r:arr;m:integer);

var k,j,i,t:integer;

begin

k:=m;

while k>0 do

begin

j:=k-1;k:=0;

for i:=1 to j do

if r[i]>r[i+1] then

begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;

end;

procedure search(r:arr;m,x:integer; var p:integer);

var low,high,mid:integer;

begin

p:=0;low:=1;high:=m;

while low<=high do

begin

mid:=(low+high) div 2;

if x>r[mid] then low:=mid+1 else

if x<r[mid] then high:=mid-1 else

begin p:=mid;exit;end;

end;

begin

write('Enter array:');

for i:=1 to n do read(a[i]);

writeln;

write('Enter search data:');

read(x1);

paixv(a,n);

search(a,n,x1,place);

if place<>0 then writeln('yes') else writeln('no');

end.

5.3 二叉排序树查找

因为二叉排序树的左子树若不为空则左子树的所有结点的值均小于它的根结点的值,而右子树若不为空,则右子树的所有结点的值均不小大于它的根结点的值,根据这个性质查找算法如下:

program pxtree;

const

a:array[1..8] of integer=(10,18,3,8,12,2,7,3);

type point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var root,first:point;k:boolean;i,x:integer;

procedure maketr(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin w:=d;right:=nil;left:=nil end;

if k then begin root:=p; k:=false end;

end

else with p^ do if d>=w then maketr(d,right) else maketr(d,left);

end;

function searchtr(x:integer;p:point):boolean;

begin

if p=nil then searchtr:=false

else if x=p^.w then searchtr:=true

else if x<p^.w then searchtr:=searchtr(x,p^.left)

else searchtr:=searchtr(x,p^.right);

end;

begin

first:=nil;k:=true;

for i:=1 to 8 do maketr(a[i],first);

write('want find data x:');read(x);

if searchtr(x,first) then writeln('yes') else writeln('No');

end.

5.4 哈希(Hash)表

以上讲的查找方法基于比较的,查找效率依赖比较次数,其实理想的查找希望不经比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,这样查找k时,只要根据这个对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存储时容易冲突（collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。

1.哈希函数的构造方法

直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)

如:人口数字统计表

地址 1 2 3 ... 100

年龄 1 2 3 ... 100

人数 67 3533 244 ... 4