Algorytmy

Algorytmy wyszukiwania

Poniższe algorytmy wyszukiwania powinny działać zarówno w Delphi jak i z drobną modyfikacją w Pascal'u.  

Pierwszy algorytm wyszukiwania polega na wyszukiwaniu wartości w tablicy. Załóżmy, że masz tablicę 10-elementową typu String i chcesz w tej tablicy wyszukać jakiś element ( poznać jej indeks ). Oto procedura przeszukująca:

type
  TSearch = String; // nowy typ bazujacy na typie String
  TTable = array[0..10] of TSearch;
 
function Find(Table : TTable; Data : TSearch; var Found : Integer) : Integer;
begin
{
  Ta procedura porownuje szukany element ( Data ) z kazdym elementem
  tablicy. Jezeli procedura znajdzie w tablicy element Data to zwraca
  rezultad w postaci numeru elementu.
}
  Found := 0;
  while (Found < High(Table)) and (Table[Found] <> Data) do Inc(Found);
    if Table[Found] <> Data then
      Result := -1 else Result := Found;
end;
 
Oto procedura wykorzystująca powyższy algorytm:
 
procedure TForm1.Button2Click(Sender: TObject);
var
  Tablica : TTable;
  Found : Integer;
begin
{ Wypelnienie tabliocy wartosciami }
  Tablica[0] := 'Jan';
  Tablica[1] := 'Adam';
  Tablica[2] := 'Aneta';
  Tablica[3] := 'Sylwia';
  Tablica[4] := 'Marta';
  Tablica[5] := 'Monika';
  Tablica[6] := 'Agata';
  Tablica[7] := 'Ewelina';
  Tablica[8] := 'Joanna';
  Tablica[9] := 'Krzysiek';
  Tablica[10] := 'Adrian';
 
  if Find(Tablica, 'Aneta', Found) > 0 then
    ShowMessage('Znelziono pod indeksem: ' + IntToStr(Found));
end;
 
A oto inny sposób zapisu tej procedury ( wyszukiwania ):
 
function Find(Table : TTable; Data : TSearch; var Found : Integer) : Integer;
begin
  Found := 0;
  repeat
    Inc(Found);
  until Table[Found] = Data;
  if Table[Found] <> Data then Result := -1  else Result := Found;
end;

3 komentarze

Toster 2007-03-30 11:24

Nie sprawdzalem w delphi ale kilka uwag:
1. Procka Find, (na samym dole) wysypie sie na Range checku w przypadku gdy bedziemy szukac ciagu ktory nie istnieje w tablicy
2. nie bardzo rozumiem po co jest ostatni warunek ? Skoro aby petla repeat sie zakonczyla wymagane jest Table[Found] = Data to linijke pozniej sprawdzenie czy Table[Found] <> Data jest bez sensu.
Procka z gory ekranu
3. Petla while ktora bazuje na ciaglym porownywaniu z High() jest nie effektywna, duzo lepsze efekty da For w dol
4. Przy kazdej iteracji ustawienie Result jest bez sensu, szkoda mocy CPU
5. Na 90% jestem pewien ze petla sie nie wykona jesli szukany element bedzie na 1 miejscu, a co sie z tym wiaze Result nie zostanie poprawnie ustawiony

Pozatym jak dla mnie indentacja mocno mi C++ smierdzi a procki sa pisane na kolanie, bez nalezytego przetestowania

Xitami 2006-10-17 00:07

----------------------------------------------------------------------------------------------------------------------
Dlaczego "inny sposób" jest błędny?
-----------------------------------------------------------------------------------------------------[ Xitami ]------

Klocek 2003-12-05 21:31

Spoko, akurat tego szukalem