Informatyka I rok
Laboratorium Metod Programowania
2000/2001

Zadanie z dnia:  9.04.01
Termin odbioru: 30.04.01

Zad. 3

Należy napisać program szukaj. Zadaniem tego programu jest 
zindeksowanie wszystkich plików o wskazanego rodzaju 
znajdujących się we wskazanym katalogu a następnie wypisywanie
na ekranie nazw wszystkich plików zawierających podane przez
użytkownika słowo. Indeksowanie (które samo może trwać dłużej)
ma zapewnić szybkie udzielanie odpowiedzi na pytania zadawane 
przez użytkownika.

Program szukaj można wywoływać następująco:
  szukaj <nazwa katalogu> <wzorzec nazwy pliku>
np.
  szukaj c:\ *.txt
Efektem tego wywołania jest przejrzenie wszystkich plików *.txt 
na dysku c: i stworzenie (w pamięci operacyjnej) struktury danych
opisującej słowa występujące w tych plikach. Teraz program 
przystępuje do drugiej fazy pracy: wypisuje tekst zachęty i czeka
na podanie słowa (puste słowo kończy pracę). Po wczytaniu słowa 
od użytkownika (i sprawdzeniu, że jest to słowo w sensie definicji
z tego zadania), program powinien wypisać na ekranie, po jednej 
w wierszu, pełne nazwy (tj ze ścieżką) wszystkich plików zawierających
to słowo, posortowane nierosnąco względem liczby wystąpień tego słowa.
Naraz można wyświetlić nie więcej niż 23 pliki, następne dopiero po 
nacisnięciu przez użytkownika spacji.

Fragment przykładowej sesji pracy użytkownia z programem szukaj (tekst 
podawany przez użytkownika to tylko słowo programowanie):

  Podaj szukane słowo (samo enter kończy): programowanie

Następny ekran:

  Liczba plików zawierających słowo "programowanie": 124. Oto ich lista:
   45: c:\mojedane\jezyki.txt
   45: c:\mojedane\jezyki2.txt
   42: c:\gry\roboty\instr.txt
   41: c:\zadania\mp\wyklad.txt
   23: c:\hobby\programowanie.txt
   < ... dalsze 17 plików ... >
   7: c:\zajecia\Wstep\opis.txt 
  Naciśnij spację żeby zobaczyć dalsze pliki ...

Przy wyszukiwaniu nie rozróżniamy dużych i małych liter. Wszelkie 
sytuacje błędne i nietypowe (np. brak plików zawierających szukane słowo)
muszą być stosownie sygnalizowane przez program.

W implementacji należy zastosować (co najmniej) moduł ze strukturą danych
pamiętającą poindeksowane słowa. Ma nią być BST ze słowami jako kluczami
i posortowanymi listami pełnych nazw plików zawierających wskazane słowo.
Zadbaj o to, by interfejs tego modułu był prosty i czytelny.

Przez słowo rozumiemy maksymalny ciąg liter (łacińskich). Można 
założyć, że słowa i katalogi mieszczą się w typie string. Uwaga: pamiętanie
słów/nazw plików jako całych napisów byłoby bardzo nieefektywne pamięciowo.
Pamięć na słowa należy przydzielać operacją GetMem (w rzeczywiście koniecznej
wielkości), a nazwy plików pamiętać tylko raz (w listach wystąpień słów
należy pamiętać wskaźniki do nazw plików a nie same nazwy plików).

Jak zwykle program powinien wypisać informacje o zajętości pamięci na początku
działania i na końcu (oczywiście te liczby powinny byc równe).

Możliwe rozszerzenia programu (nie wymagane do zdobycia maksymalnej 
liczby punktów):
 - możliwość znajdowania plików zawierających jednocześnie kilka podanych
   słów lub jedno z podanych słów (np. +metody +programowanie),
 - bardziej zaawansowana niż BST struktura danych (np. wyważone BST), wybór
   struktury należy zatwierdzić u prowadzącego ćwiczenia,
 - oszczędniejsze gospodarowanie pamięcią: ścieżki występujące w nazwach plików
   zawierają wspólne elementy - nie warto ich wielokrotnie pamiętać.
   
Miejsce skąd można pobierać treści zadań zaliczeniowych: 
   www.mimuw.edu.pl/~janusz (i potem dość oczywiste dowiązania)