Politechnika Zielonogórska Wydział Elektryczny	Anna Rożnowska Marcin Kozłowski	Gr. lab. 25A	Nr. ćwicz. 2	Ocena:
Laboratorium algorytmy i struktury danych.
Temat ćwiczenia: Przeszukiwanie liniowe, binarne, haszowanie.		Data wykon. ćw. 18-10-99	Data oddania spraw. 25-10-99	Sprawdz.

Przeszukiwanie liniowe.

NIE TAK

NIE

TAK

program liniowe;

const n=10;

type tablica=array[1..n] of string;

var a:tablica;

i:integer;

b:string;

Begin

for i:=1 to n do

begin

writeln('podaj ',i,' element tablicy: ');

readln(a[i]);

end;

i:=1;

writeln('podaj szukany element');

readln(b);

for i:=1 to n do

if a[i]=b then

begin

writeln('istnieje');

exit;

end;

writeln('nie istnieje');

End.

Przeszukiwanie binarne

NIE TAK

NIE TAK

Program binarne;

Const n=20;

tablica:array[1..n] of real;

ostat, srod, pierw: integer;

a:tablica;

b:real;

Begin

pierw:=1;

ostat:=n;

for srod:=1 to n do readln (a[srod]);

write(`Podaj szukany element: `);

readln(b);

srod:=(ostat+pierw) div 2;

while(a[srod]<>b) and (ostat<>pierw) do

begin

if a[srod]<b then ostat:=srod

else pierw:=srod;

srod:=(ostat+pierw) div 2

end;

if a[srod]=b then writeln(`Element istnieje')

else writeln(`Element nie istnieje');

End.

Haszowanie

Wpisywanie

NIE

TAK

Szukanie

NIE

TAK

T

Haszowanie

NIE

TAK

NIE

TAK

NIE

TAK

Program Haszowanie;

Uses Crt;

Const n=25;

Type

Wskaznik = ^elem;

elem=record

nast:wskaznik;

wart:string[30];

end;

tablica=array[0..n] of wskaznik;

var

i,j,k,l:integer;

s:string[30];

t:tablica;

element:wskaznik;

elem2:wskaznik;

z:char;

Begin

For i:=0 to n do t[i]:=nil;

Repeat

Readln(s);

k:=0;

for i:=1 to length(s) do

begin

j:=ord(upcase(s[i]))-64;

for l:=1 to (i mod 5) do

begin

j:=j*2;

if j>32 then j:=j-31;

end;

k:=k xor j;

end;

new(element);

element^.nast:=nil;

element^.wart:=s;

if t[k]=nil then t[k]:=element

else

begin

elem2:=t[k];

while elem2^.nast<>nil do elem2:=elem2^.nast;

elem2^.nast:=element;

end;

writeln('Czy wpisać następne dane T/N');

z:=readkey;

until upcase(z)='N';

readln(s);

k:=0;

for i:=1 to length(s) do

begin

j:=ord(upcase(s[i]))-64;

for l:=1 to (i mod 5) do

begin

j:=j*2;

if j>32 then j:=j-31;

end;

k:=k xor j;

end;

if t[k]=nil then writeln('Element nie istnieje')

else

begin

elem2:=t[k];

while(elem2^.wart<>s) and (elem2^.nast<>nil) do elem2:=elem2^.nast;

if elem2^.wart=s then writeln('Element istnieje')

else writeln('Element nie istnieje');

end;

End.

Wnioski:

Powyższe algorytmy stosuje się przy wyszukiwaniu podanego klucza np.: w słownikach, książkach telefonicznych, itp.Algorytmy wyszukiwania liniowego i binarnego są mniej skomplikowane ale przypłacają to dlugim, w porownaniu do haszowania, czasem szukania klucza.Haszowanie skraca czas wyszukiwania elementu, jednak nie mogac znaleść idealnej funkcji nie powodującej kolizji, musimy tworzyć bardziej zlożone struktury takie jak lista list, tabela list, itd.

1

9

START

Wczytaj dane do tablicy oraz szukany element 'b'

i:=1

i>n

a[i]=b

i:=i+1

Element nie

istnieje

Element istnieje w tablicy.

STOP STOP

Element nie istnieje

Element istnieje

Czy tablica jest pusta

STOP STOP

Weź pierwszą lub druga połowę tablicy zależnie od wyniku porównania

Sprawdź czy `b' jest równe środkowemu elementowi tablicy

Wczytaj dane do tablicy oraz szukany element `b'

START STOP

START SSTART

Wprowadź klucz

k=H(v)

Wpisz na koniec listy T[k]

Koniec wprowadzania danych

STOP

START

STOP

Wprowadź klucz

k=H(v)

Czy istnieje element w liście t[k]

Element nie istnieje

Element istnieje

START

k:=0

i:=1

i<=length(s)

j:=ord(upcase(s[i]))-64

l:=1

l<=i div 5

j:=j*2

k:=k xor j

j > 32

j:=j-31

STOP

l:=l+1

---