Algorytm Boyera I Moore'a - Problem

MitS · Wrzesień 18, 2005

Witam!

Zabrałem się za naukę algorytmów i chciałem npisać algorytm Boyera i Moore'a, ale gdy przystąpiłem do kompilacji wywala mi błędy:

program.cpp


#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>

using namespace std;



const K=26*2*2*2+1;          // znaki ASCII + polskie litery + spacja 
int shift[K];


int indeks(char c);
{
switch(c)
{
case ' ':  return 0;        // spacja = 0 
case 'a':  return 1;
case 'b':  return 2; 
case 'c':  return 3; 
case 'd':  return 4; 
case 'e':  return 5; 
case 'f':  return 6; 
case 'g':  return 7; 
case 'h':  return 8; 
case 'i':  return 9; 
case 'j':  return 10;
case 'k':  return 11;
case 'l':  return 12;
case 'm':  return 13;
case 'n':  return 14;
case 'o':  return 15;
case 'p':  return 16;
case 'q':  return 17;
case 'r':  return 18; 
case 's':  return 19; 
case 't':  return 20; 
case 'v':  return 21; 
case 'w':  return 22; 
case 'u':  return 23; 
case 'x':  return 24; 
case 'y':  return 25; 
case 'z':  return 26; 
case 'A':  return 27; 
case 'B':  return 28; 
case 'C':  return 29; 
case 'D':  return 30; 
case 'E':  return 31; 
case 'F':  return 32; 
case 'G':  return 33; 
case 'H':  return 34; 
case 'I':  return 35; 
case 'J':  return 36; 
case 'K':  return 37; 
case 'L':  return 38; 
case 'M':  return 39; 
case 'N':  return 40; 
case 'O':  return 41; 
case 'P':  return 42; 
case 'Q':  return 43; 
case 'R':  return 44; 
case 'S':  return 45; 
case 'T':  return 46; 
case 'V':  return 47; 
case 'W':  return 48; 
case 'U':  return 49; 
case 'X':  return 50; 
case 'Y':  return 51; 
case 'Z':  return 52; 
case 'ą':  return 53; 
case 'ź':  return 54;
case 'ż':  return 55;
case 'ę':  return 56;
case 'ś':  return 57;
case 'ć':  return 58;
case 'ę':  return 59;
case 'ń':  return 60;
case 'ó':  return 61;
case 'ł':  return 62;
case 'ą':  return 63; 
case 'Ż':  return 64;
case 'Ź':  return 65;
case '':  return 66;
case 'Ś':  return 67;
case 'Ć':  return 68;
case '':  return 69;
case 'Ń':  return 70;
case 'Ó':  return 71;
case 'Ł':  return 72;

default:
 if(islower(c))            // 'c’ jest małą literą ?
  return c-'a'+1; 
 else
  return c-'A'+27;
}
}

void init_shifts(char *w)
{
int i, M=strlen(w);
for(i=0; i<k; i++)
  shift[i]=m;
for(i=0; i<M; i++)
  shift[indeks(w[i])]=<-i-1;
}

int bm(char *w, char *t)
{
init_shifts(w);
int I, j,N=strlen(t),M=strlen(w);
for(i=M-1 , j=M-1; j >0; i-- , j--)
while(t[i]!=w[j])
{
  int x = shift[indeks(t[i])];
  if(M-j>x)
     i+=M-j;
  else
     i+=x;
  if (i>=N) 
     return -1;
     j=M-1;
}
return i;
}

int main(int argc, char *argv[])
{
 char *t="Z pamiętnika młodej lekarki";
 cout << "Wynik poszukiwan = " << bm("lek",t) << endl;

 return EXIT_SUCCESS;
}

Błędy:

cd '/home/mits/Desktop/aaa/debug' && WANT_AUTOCONF_2_5="1" WANT_AUTOMAKE_1_6="1" gmake -k

gmake all-recursive

Making all in src

kompilowanie aaa.cpp (g++)

/home/mits/Desktop/aaa/src/aaa.cpp:94:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:95:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:96:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:97:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:98:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:99:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:100:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:101:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:102:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:103:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:104:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:105:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:106:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:107:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:108:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:109:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:110:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:111:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:112:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:113:6: warning: multi-character character constant

/home/mits/Desktop/aaa/src/aaa.cpp:33: error: ISO C++ forbids declaration of ‘K’ with no type

/home/mits/Desktop/aaa/src/aaa.cpp:38: error: expected unqualified-id before ‘{’ token

/home/mits/Desktop/aaa/src/aaa.cpp: In function ‘void init_shifts(char*)’:

/home/mits/Desktop/aaa/src/aaa.cpp:126: error: ‘k’ was not declared in this scope

/home/mits/Desktop/aaa/src/aaa.cpp:127: error: ‘m’ was not declared in this scope

/home/mits/Desktop/aaa/src/aaa.cpp:129: error: expected primary-expression before ‘<’ token

/home/mits/Desktop/aaa/src/aaa.cpp: In function ‘int bm(char*, char*)’:

/home/mits/Desktop/aaa/src/aaa.cpp:136: error: ‘i’ was not declared in this scope

gmake[2]: *** [aaa.o] Błąd 1

gmake[2]: Obiekt `all' nie został wykonany z powodu błędów.

gmake[2]: Nie nic do roboty w `all-am'.

gmake[1]: *** [all-recursive] Błąd 1

gmake: *** [all] Błąd 2

*** Zakończono w stanie: 2 ***

Pomożecie mi to skompilować ???

Używam KDevelop.

bergo · Wrzesień 18, 2005

1. /home/mits/Desktop/aaa/src/aaa.cpp:33: error: ISO C++ forbids declaration of ‘K’ with no type

Widzisz kolego Twoje: const K=26*2*22*2+1 musi mieć podany typ zmiennej. Const to jedynie info dla kompilatora, że pod nią już nic nie możesz podstawić, że ona jest "read only". Natomiast typy to: int, char, long, itd... W tym przypadku powinno być:

const int K = 26*2*2*2+1;

2. /home/mits/Desktop/aaa/src/aaa.cpp:94:6: warning: multi-character character constant

To ostrzeżeni jest generowane gdy do zmiennej typu char podstawiasz literał znakowy składający się z kilku znaków. Zmienna char służy do przechowywania jednego znaku, a nie zlepku znaków. Jak chcesz jednak operować na ciągach znakowych to użyj: char*, albo char[], albo std::string.

3. /home/mits/Desktop/aaa/src/aaa.cpp:38: error: expected unqualified-id before ‘{’ token

Zerknij no na linijkę 38 - masz tam: int indeks(char c); A powinno być: int indeks(char c)

4. /home/mits/Desktop/aaa/src/aaa.cpp: In function ‘void init_shifts(char*)’:

/home/mits/Desktop/aaa/src/aaa.cpp:126: error: ‘k’ was not declared in this scope

/home/mits/Desktop/aaa/src/aaa.cpp:127: error: ‘m’ was not declared in this scope

W tej funkcji używasz zmiennej "k" jako delimitera instrukcji for, ale nigdzie wcześniej nie deklarujesz takiej zmiennej: for(i=0; i<k; i++). To samo tyczy się "m" - tzn. nie jest zadeklarowane.

5. /home/mits/Desktop/aaa/src/aaa.cpp:129: error: expected primary-expression before ‘<’ token

To ta ciagle ta sama funkcja - linijka następująca jest bez sensu:

shift[indeks(w)]=<-i-1;

6. /home/mits/Desktop/aaa/src/aaa.cpp: In function ‘int bm(char*, char*)’:

/home/mits/Desktop/aaa/src/aaa.cpp:136: error: ‘i’ was not declared in this scope

Pierwej zadeklaruj zmienną, w tym wypadku "i", a potem jej używaj.

Mała rada, jak widzę jestes bardzo poczatkujący w C/C++ - więc może najpierw skup sie na nauce samego języka programowania, a trudne algorytmy zostaw sobie na później. To nie były trudne błędy tylko wynikające z niewiedzy elementarnych rzeczy.

POzdrawiam

Bergo

MitS · Wrzesień 19, 2005

Ok to teraz poprawiłem kod tak że się kompiluje i że się uruchamia

KOD

#include <iostream>
#include <cstdlib>

using namespace std;



const int K=26*2*2*2+1;          // znaki ASCII + polskie litery + spacja 
int shift[K];
int i;


int indeks(char c)
{
switch(c)
{
case ' ':  return 0;        // spacja = 0 
case 'a':  return 1;
case 'b':  return 2; 
case 'c':  return 3; 
case 'd':  return 4; 
case 'e':  return 5; 
case 'f':  return 6; 
case 'g':  return 7; 
case 'h':  return 8; 
case 'i':  return 9; 
case 'j':  return 10;
case 'k':  return 11;
case 'l':  return 12;
case 'm':  return 13;
case 'n':  return 14;
case 'o':  return 15;
case 'p':  return 16;
case 'q':  return 17;
case 'r':  return 18; 
case 's':  return 19; 
case 't':  return 20; 
case 'v':  return 21; 
case 'w':  return 22; 
case 'u':  return 23; 
case 'x':  return 24; 
case 'y':  return 25; 
case 'z':  return 26; 
case 'A':  return 27; 
case 'B':  return 28; 
case 'C':  return 29; 
case 'D':  return 30; 
case 'E':  return 31; 
case 'F':  return 32; 
case 'G':  return 33; 
case 'H':  return 34; 
case 'I':  return 35; 
case 'J':  return 36; 
case 'K':  return 37; 
case 'L':  return 38; 
case 'M':  return 39; 
case 'N':  return 40; 
case 'O':  return 41; 
case 'P':  return 42; 
case 'Q':  return 43; 
case 'R':  return 44; 
case 'S':  return 45; 
case 'T':  return 46; 
case 'V':  return 47; 
case 'W':  return 48; 
case 'U':  return 49; 
case 'X':  return 50; 
case 'Y':  return 51; 
case 'Z':  return 52; 
case 'ą':  return 53; 
case 'ź':  return 54;
case 'ż':  return 55;
case 'ę':  return 56;
case 'ś':  return 57;
case 'ć':  return 58;
case 'ń':  return 69;
case 'ó':  return 60;
case 'ł':  return 61;
case 'Ż':  return 62;
case 'Ź':  return 63;
case '':  return 64;
case 'Ś':  return 65;
case 'Ć':  return 66;
case 'Ń':  return 67;
case 'Ó':  return 68;
case 'Ł':  return 69;

default:
 if(islower(c))            // 'c’ jest małą literą ?
  return c-'a'+1; 
 else
  return c-'A'+27;
}
}

void init_shifts(char *w)
{
int k, M=strlen(w);
for(i=0; i<k; i++)
  shift[i]=M;
for(i=0; i<M; i++)
  shift[indeks(w[i])]=-i-1;
}

int bm(char *w, char *t)
{
init_shifts(w);
int j,N=strlen(t),M=strlen(w);
for(i=M-1 , j=M-1; j >0; i-- , j--)
while(t[i]!=w[j])
{
  int x = shift[indeks(t[i])];
  if(M-j>x)
     i+=M-j;
  else
     i+=x;
  if (i>=N) 
     return -1;
     j=M-1;
}
return i;
}

int main(int argc, char *argv[])
{
 char *t="Z pamiętnika młodej lekarki";
 cout << "Wynik poszukiwan = " << bm("lek",t) << endl;

 return EXIT_SUCCESS;
}

I teraz jest problem bo gdy program się uruchamia to w konsoli zamiast programu jest napis:

"naruszenie ochrony pamięci".

Co mam zrobić aby to nie występowało ???

Zaloguj się

Algorytm Boyera I Moore'a - Problem

Rekomendowane odpowiedzi

MitS

Odnośnik do komentarza

Udostępnij na innych stronach

bergo

Odnośnik do komentarza

Udostępnij na innych stronach

MitS

Odnośnik do komentarza

Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Zarejestruj nowe konto

Zaloguj się

Przeglądaj

Aktywność

Fedora.pl