Referat Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien

Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien

Eine etwas andere Art des Backtracking wird in der Praxis oft für das Suchen von Dateien in einem Verzeichnisbaum eingesetzt: Einer rekursive Prozedur wird ein Verzeichnis als Parameter übergeben. Sie durchsucht dieses zuerst nach dem eingegebenen Dateinamen und gibt gegebenenfalls passende aus. Anschließend wird das Verzeichnis nach Unterverzeichnissen durchsucht. Wird eines gefunden, ruft sich die Prozedur selbst auf, wobei sie als Parameter dessen Pfad übergibt. Danach wird mit dem Unterverzeichnis genauso verfahren wie mit dem Überverzeichnis. Der Suchvorgang bricht ab, sobald alle Unterverzeichnisse des vom Startverzeichnis ausgehenden Verzeichnisbaumes durchsucht worden sind.

Folgendes Programm verf hrt nach dem oben beschriebenen Prinzip. Wegen der

Übersichtlichkeit wurde der Arbeitsgang auf drei Prozeduren aufgeteilt:

program rekfsuch;

uses crt,dos tools07;

_{const abbruch : boolean = false;}

procedure ausgabe(erg : string; a:byte);

begin inc(anz);

if odd(anz) then textcolor else textcolor;

write(anz, : ,erg);

gotoxy(60,wherey);

if a and $01) $01 then write('RO ) else write(' ');

if (a and $02) $02 then write( H ) else write(' '); if a and $04) $04 then write( S ) else write ' '); if a and $10) $10 then write( D ) else write(' '); if a and $20) $20 then write('A') else write(' '); writeln;

textcolor;

_{if anz mod 15 = 0 then begin}

/ 26

writeln;

writeln('RO=Read Only, H Hidden, S=System, D Direktory, A=Archiv ;

write('Weiter mit Taste (Ende=[Esc ) . ;

repeat until keypressed;

ch: readkey;

if ch=#27 then abbruch =true;

if not abbruch then clrscr else gotoxy(1,wherey-2);

end;

end;

procedure suchdateien(verzeichnis:string ; var files : SearchRec; begin

if not abbruch then begin FindFirst(verzeichnis suchstring,anyfile,files); while (doserror 0) and not abbruch do begin

if ((files.attr and VolumeID)<>VolumeID)

then ausgabe(verzeichnis+files.name, files attr);

if keypressed then begin

ch: readkey;

if ch #27 then abbruch:=true;

end;

findnext(files);

end;

end;

end;

procedure such(verzeichnis:string ; var dirs : SearchRec; begin

if not abbruch then begin suchdateien(verzeichnis); FindFirst(verzeichnis ,directory,dirs); while (doserror 0) and not abbruch do begin if (dirs attr and directory=directory)

and (dirs.name <>'. )

and (dirs.name <>'. )

then such(verzeichnis+dirs.name ;

if keypressed then begin

ch: readkey;

if ch #27 then abbruch:=true;

end;

findnext(dirs ;

end;

end;

end;

begin color(15,1); anz: 0; clrscr;

writeln('                REKURSIVES DATEISUCHPROGRAMM');

writeln('     geschrieben von Stefan Krywult für seine Fachbereichsarbeit 1998 );

window(3,4 8 24);

color(7,0);

_clrscr;

/ 27

window(5,5 6 23); write('Suchpfad: ; readln(suchpfad);

write('Zu suchende Datei oder zu suchendes Verzeichnis: ;

readln(suchstring ;

writeln;

writeln('Suche beginnt bei Tastendruck. ;

writeln('Ein Abbruch ist jeder Zeit mit [Esc] möglich. ;

wt;

clrscr;

such(suchpfad);

writeln;

writeln('RO=Read Only, H Hidden, S=System, D Direktory, A=Archiv ;

If not abbruch then writeln('In ,suchpfad,' wurde suchstring ' anz,'mal gefunden. )

else writeln( In ,suchpfad,' wurde ,suchstring,' bis zum Abbruch anz, mal gefunden. ;

write('Programm endet bei Tastendruck... ;

wt; window(1,1,80 25); color(7,0);

clrscr;

end.

Die typisierte Konstante abbruch ist ein Variable vom Typ Boolean, die zu Beginn des Programmes den Wert False besitzt und als Flag verwendet wird . Ist es gesetzt, wird die Suche abgebrochen. Die Prozedur ausgabe gibt den in erg übergebenen Datei- oder Verzeichnisnamen mit Pfad und Attributen formatiert am Bildschirm aus . Das Unterprogramm suchdateien durchsucht das in der Variablen verzeichnis übergebene Unterverzeichnis nach der zuvor eingegebenen Datei und gibt sie gegebenenfalls mit Hilfe der Prozedur ausgabe aus. Als lokale Variable wird files als SearchRec deklariert. Dieser Variablentyp enthält mehrere Datenfelder und ist für den Aufruf der Pascalprozeduren FindFirst und FindNext notwendig . Ein Feld dieses Typs enthält den Dateinamen, andere die Dateiattribute, die Dateigröße sowie interne Daten, die für die Suche notwendig sind und mit denen ihr momentaner Status gespeichert ist.

Zunächst erfolgt der Aufruf von FindFirst, um die Suche zu initialisieren . Als Argumente werden der Dateiname (nach DOS-Konventionen, das heißt, es sind auch Sternchen erlaubt) mit vollständigem Pfad, nach dem gesucht werden soll, die Dateiattribute, die  sie haben müssen, um gefunden zu werden, und eine Variable vom Typ SearchRec angegeben. Für die Dateiattribute wurde im obigen Programm die Konstante anyfile angegeben, damit alle Dateien und Verzeichnisse gefunden werden. Wenn die Suche erfolgreich verlaufen ist, enth lt DosError den Wert Null, im Feld name von files ist die erste gefundene Datei

_{enthalten und es beginnt eine while-Schleife. Nach der Sicherstellung, ob das}

Suchergebnis nicht der Laufwerksname ist, wird es ausgegeben . Falls die Escape-Taste gedrückt wurde, wird das Flag abbruch gesetzt , was zum Abbruch der while-Schleife und der gesamten Suche führt. Anderenfalls wird die Suche mit dem Befehl FindNext fortgeführt

Die Schleife endet spätestens dann, wenn keine entsprechende Datei mehr  gefunden werden konnte und DosError daher einen Wert ungleich Null aufweist.

Die rekursiv programmierte Prozedur such ist ähnlich aufgebaut wie suchdateien, auch ihr wird ein Verzeichnisname als Parameter übergeben . Die einzige lokale Variable ist dirs vom Typ SearchRec die für FindFirst und FindNext notwendig ist . Die Prozedur wird nur dann weiter ausgeführt, wenn das Flag abbruch nicht gesetzt ist , und es wird suchdateien mit dem übergebenen Verzeichnis als Parameter aufgerufen, um alle entsprechenden Dateien in diesem Verzeichnis anzuzeigen . Dann wird FindFirst so aufgerufen, daß alle Unterverzeichnisse des übergebenen Verzeichnisses gefunden werden

. Wieder l uft eine while-Schleife, so lange, bis keine Unterverzeichnisse mehr gefunden werden können und DosError einen Wert ungleich Null besitzt oder bis das Flag abbruch gesetzt ist . In der Schleife wird zunächst kontrolliert, ob es sich bei dem Suchergebnis wirklich um ein Unterverzeichnis und nicht um eines der Symbole für das gegenwärtige bzw. das darüberliegende Verzeichnis handelt . (Wäre dies der Fall, käme es beim nachfolgenden Selbstaufruf nämlich zu einer endlosen Rekursion und somit zum Stack- Overflow.) Anschließend wird wieder überprüft, ob die Escape-Taste gedrückt wurde, und - wenn das der Fall ist - das Flag abbruch gesetzt . Dann wird die Suche mit FindNext fortgesetzt. Die Schleife läuft, solange bis Escape gedrückt wird und die Variable abbruch den Wert True besitzt oder keine weiteren Unterverzeichnisse mehr gefunden werden können.

Im Hauptprogramm wird die zu suchende Datei als globale Variable, die in allen Unterprogrammen zugänglich ist, gespeichert, das Startverzeichnis wird der Prozedur such als Parameter übergeben. Diese gibt dann zuerst alle entsprechenden Dateien des übergebenen Verzeichnisses aus, durchsucht es dann nach Unterverzeichnissen und ruft sich mit jedem brauchbaren Suchergebnis selbst auf. Da viele Suchen durcheinanderlaufen, ist es wichtig, daß deren Status genau gespeichert wird. Um das braucht sich der Programmierer jedoch nicht zu kümmern, da ihm die Prozeduren FindFirst und FindNext dies abnehmen.