Strona główna Wstęp Nauka Programy Rozrywka Pomoc Księga gości Kontakt
Algorytmy przeszukiwania w języku C(C++)
Inne strony o tej tematyce: Algorytmy sortowania w języku C(C++) Język C++ - ściąga z programowania obiektowego (autor : Piotra Różnicki) Język C ,opis języka - struktury dynamiczne (autor : Robert Chwastek) Kurs języka C - opracowany przez mojego kolegę. Przykładowe programy w C i C++
Przeszukiwanie liniowe O(N) Przeszukiwanie binarne O(log2n) Przeszukiwanie ciągów znakowych O(N) Powrót na początek strony Objaśnienia: Typ_elementu typ elementu zdefiniowany np. przez typedef int Typ_elementu; tablica[max_rozmiar] - tablica o rozmiarze max_rozmiar przechowująca dane typu Typ_elementu przeznaczone do sortowania lewy - lewa granica tablicy przeznaczonej do sortowania(początek) prawy - prawa granica tablicy przeznaczonej do sortowania(koniec). Przeszukiwanie liniowe Algorytm wykonuje pętlę, która dla każdego elementu sprawdza, czy to on jest tym poszukiwanym i jeśli tak to ustawia wartość funkcji na numer tego elementu i ją kończy. Oczywiście złożoność obliczeniowa jest rzędu N. Średnia założoność: (N+1)/2. Uwaga - jeśli element nie znajduje się w tablicy to zwracany indeks ostatniego elementu.
int szukaj(Typ_elementu tablica[n],Typ_elementu x) { for(int i=0;(i<n)&&(tablica[i]!=x);i++); return i; }
Powrót na początek strony Przeszukiwanie binarne Opis zawiera się w komentarzach: Jest to jeden z najszybszych algorytmów. Złożoność obliczeniwa tego algorytmu jest rzędu O(log2n). Uwaga algorytm wymaga danych posortowanych.
int szukaj_binarnie(Typ_elementu * tablica,Typ_elementu x,int lewy,int prawy) {//funkcja zwraca indeks znalezionego elementu if(lewy>prawy) return -1; //jesli tablica ma dlugosc 0 to zwróć -1 else { int mid=(lewy+prawy)/2;//srodek tablicy if(tablica[mid]==x) return mid; // element znaleziony w srodku else if(x<tablica[mid])return szukaj_binarnie(tablica,x,lewy,mid-1); else return szukaj_binarnie(tablica,x,mid+1,prawy); } }
Powrót na początek strony Przeszukiwanie ciągów znakowych Algorytm zwraca pozycję szukanego podciągu w ciągu znakowym. Jest to tzw. algorytm bruteforce...czyli szukamy po znaku aż znajdziemy odpowiedni podciąg.
int szukajciag(char *p, char *a) {//p-ciag szukany,a-ciag w ktorym szukamy int i, j, M = strlen(p), N = strlen(a); for (i = 0, j = 0; j < M && i < N; i++, j++)
if (a[i] != p[j]) { i -= j-1; j = -1; } if (j == M) return i-M; else return i; }