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

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

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

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;

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

begin p:=mid;exit;end;

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

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 2023 244 ... 4

当给定值k=84,则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。

当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记录。

5.5 查找第k小元素

查找第k小元素即在n个元素中（未排序）找到第k小的元素。方法同快速排序，采用递归方式。

程序如下：

program kspv;

const n=7;

type

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

var

b:arr;

i,k:integer;

function p(s,t:integer):integer;

var i,j,t1,x:integer;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x) and (j>i) do j:=j-1;

if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

while (b[i]<=x) and (i

if i

until i=j;

b[i]:=x;

p:=i;

end;

function find(s,t,k:integer):integer;

var p1,q:integer;

begin

if s=t then find:=b[s] else

begin

p1:=p(s,t);

q:=p1-s+1;

if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);

end;

end;

begin

write('input data:');

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

write('input k:');read(k);

write('output data:');

writeln('kthsmall:=',find(1,n,k));

end.

关于合肥市青少年信息学竞赛更多的信息，请关注优学合肥奥数网“青少年信息学竞赛”频道。

信息学竞赛常用算法与策略：排序

信息学竞赛常用算法与策略：回溯

信息学竞赛常用算法与策略：递归

信息学竞赛常用算法与策略：算法的概念

更多精彩内容推荐>>