Instrukcja IEF Algorytmy i struktury danych lab1, Politechnika, AiSD
[ Pobierz całość w formacie PDF ]
//-->Instrukcja IEF Algorytmy i struktury danychLaboratorium 1: ”Przeszukiwanie tekstów”.1. Wstęp.Algorytmy przeszukiwania wzorca w tekście służą do odnajdywania w zadanym tekście określonego ciąguznaków. Ciąg ten może oczywiście występować więcej, niż jeden raz. Możliwe jest również,żeposzukiwanyciąg nie występuje w tekście. W opisie algorytmów zakłada się,żetekst i wzorzec są jednowymiarowymitablicami znaków, indeksowanymi od zera.2. Informacje wstępne z języka C:••deklaracja łańcucha:char nazwa[rozmiar];wczytanie łańcucha:gets(nazwa);fgets(nazwa,rozmiar,stdin);scanf(”%(rozmiar-1)[^\n]s”,nazwa);instrukcja warunkowa:if(warunek)instrukcja1;elseinstrukcja2;instrukcja pętli:while(warunek)instrukcja;for(wyrażenie1;wyrażenie2;wyrażenie3)instrukcja;przykład przeglądania łańcucha znaków:i=0;while(nazwa[i]!=’\0’){instrukcja;i++;}for(i=0;nazwa[i]!=’\0’;i++)instrukcja;••3. Opis algorytmu naiwnego – brute forceAlgorytm ten jest najprostszą metodą na znalezienie wzorca w tekście. Zasada działania opiera się naporównywaniu odpowiednich liter tekstu i wzorca, zaczynając od pierwszej litery tekstu i wzorca. Jeślifragmenty tekstu i wzorca są zgodne, porównywany jest następny znak tekstu z następnym znakiem wzorca itd.Jeśli wystąpiła niezgodność w dowolnym miejscu – algorytm rozpoczyna całą procedurę przeszukiwania oddrugiego znaku tekstu i pierwszego znaku wzorca. Jeśli zostanie znaleziony cały szukany wzorzec, algorytmmoże zakończyć przeszukiwanie lub rozpocząć je od następnego znaku (tj. wzorzec jest „przesuwany” o jedenznak).Złożoność obliczeniowa w najgorszym przypadku wynosi O(N*M), gdzie N jest długością tekstu, M –długością wzorca.Przykład:tekst:ZZXZZYIteracja 1↓tekstwzorzecZZ↑Iteracja 2↓tekstwzorzecZZZ↑Iteracja 3↓tekstwzorzecZZXZ↑Iteracja 4↓tekstwzorzecZZXZZ↑↓ZZ↑↓YY↑ZZZYY↓XZ↑ZYZY↓ZZ↑↓XY↑ZZYwzorzec:ZZYZnaleziono rozwiązanie: Wzorzec zaczyna się od indeksu 3.4. Zadania do wykonania:Proszę napisać:•funkcję, która znajduje długość łańcucha:int długosc(char*lan);•funkcję, która sprawdza, czy dany wzorzec wystąpił w tekście. Jeśli tak, to zwraca indeks odktórego zaczyna się wzorzec w tekście lub -1:int sprawdz(char*tekst, char*wzor);•funkcję, która znajduje wszystkie wzorce występujące w tekście, zwraca wskaźnik do tablicyindeksów (wewnątrz funkcji dynamiczna rezerwacja pamięci dla tablicy indeksów) orazudostępnia ich ilość przez wskaźnik :int* sprawdz_w(char* tekst, char * wzor, int* ilosc);•funkcjęmain,w której należy wczytać dwa dowolne łańcuchy, wywołać funkcjęsprawdziwypisać wynik (czy znaleziono wzorzec, jeśli tak, to od jakiego indeksu się zaczyna). Jeśliznaleziono wzorzec, należy wywołać funkcjęsprawdz_wi również wypisać odpowiednie wyniki(ilość znalezionych wzorców i ich indeksy). Operacje: wczytania łańcuchów, wywołania funkcji iwypisywania wyników przeprowadzać dopóki wzorzec znajduje się w tekście.
[ Pobierz całość w formacie PDF ]