|
 Forum
Grundkurs
»Introduktion
»Snabbguide
»Komponenter
»Händelser
»Strängar
»Räkna med Delphi »Egna
typer
»Selektion
»Iteration
»Menyer
»Funktioner
»Arraystrukturer
Tips & Tricks
»Nya tips
»Blandat
»Databaser
»Filer
»Forms
»Grafik
»Internet
»Komponenter
»Matematik
»Multimedia
»Objekt/ActiveX
»Skrivare
»Strängar
»System
»Mest lästa tips
Artiklar
»Delphi och ADO
»Bygga en DLL
»Skapa en enkel rapport
»Hantera registret
»Enheter, units
»Klassen TCanvas
»Använd LookUp Controls
 Nya
tips
 Lägg
till tips
 Delphilänkar
 Gästbok
|
|
|
|
|
|
Sök efter ett element i en array på snabbaste vis
|
Kategori: Strangar
Inlagt: 2004-12-15
Läst: 1470
Inlagt av: Staffan Berg
|
|
Beskrivning |
|
Detta exempel letar upp önskat element i en array med hjälp av binärsökning.
|
|
Kod |
type
TStringArray = array of string ;
{--------------------------------------------------------------------}
//Start is the index of the first item of the array - usually 0
//Stop is the index of the last item of the array
procedure QuickSort(var Strings: TStringArray; Start, Stop: Integer);
var
Left: Integer;
Right: Integer;
Mid: Integer;
Pivot: string ;
Temp: string ;
begin
Left := Start;
Right := Stop;
Mid := (Start + Stop) div 2;
Pivot := Strings[mid];
repeat
while Strings[Left] < Pivot do Inc(Left);
while Pivot < Strings[Right] do Dec(Right);
if Left <= Right then
begin
Temp := Strings[Left];
Strings[Left] := Strings[Right]; // Swops the two Strings
Strings[Right] := Temp;
Inc(Left);
Dec(Right);
end;
until Left > Right;
if Start < Right then QuickSort(Strings, Start, Right); // Uses
if Left < Stop then QuickSort(Strings, Left, Stop); // Recursion
end;
{--------------------------------------------------------------------}
function BinSearch(Strings: TStringArray; SubStr: string ): Integer;
var
First: Integer;
Last: Integer;
Pivot: Integer;
Found: Boolean;
begin
First := Low(Strings); //Sets the first item of the range
Last := High(Strings); //Sets the last item of the range
Found := False; //Initializes the Found flag (Not found yet)
Result := -1; //Initializes the Result
//If First > Last then the searched item doesn't exist
//If the item is found the loop will stop
while (First <= Last) and (not Found) do
begin
//Gets the middle of the selected range
Pivot := (First + Last) div 2;
//Compares the String in the middle with the searched one
if Strings[Pivot] = SubStr then
begin
Found := True;
Result := Pivot;
end
//If the Item in the middle has a bigger value than
//the searched item, then select the first half
else if Strings[Pivot] > SubStr then
Last := Pivot - 1
//else select the second half
else
First := Pivot + 1;
end;
end;
{--------------------------------------------------------------------}
//To use the Binary Search:
procedure Button1Click(Sender: TObject);
var
MyStrings: TStringArray;
begin
//Give some values to your string s and remember to
//Set it to the correct length :)
//..
//..
//..
QuickSort(MyStrings, 0, High(MyStrings);
ShowMessage('The index of 'Derek' is: ' +
IntToStr(BinSearch(MyStrings, 'Derek')
//If 'Derek' is in MyStrings, its index value will be returned,
//otherwise -1 will be returned.
end;
|
|
|