PROBLEMA ALGORITMO INCASINATO IN C!!

di il
3 risposte

PROBLEMA ALGORITMO INCASINATO IN C!!

Salve a tutti!
Ho un grosso problema: Dovrei risolvere il seguente algoritmo ASSOLUTAMENTE (e purtroppo!) in linguaggio C :
"Gli studiosi di testi letterari a volte fanno un esame statistico delle
lettere (A,B,..), articoli (Il, lo,...),preposizioni(di, del, al...) e
parole presenti in un certo testo. Scrivere un programma che faccia
questa analisi stampando per ciascun di questi elementi le percentuali
di occorrenza in ordine crescente. Come esempi si prendano testi a
carattere matematico, informatico, un aricolo di giornale sportivo, un
racconto di uno scrittore".

Ho provato ad implementarlo da un pò di tempo ma non riesco a trovare l'errore che c'è (presumo) nella funzione pmatch: l'istruzione j = insuccesso[j-1]+1; viene ripetuta all'infinito. Inoltre la funzione confronta_stringa effettua la sua analisi solo con un elemento della lista anzichè con tutti gli elementi. C'E' QUALCUNO CHE RIESCE A TROVARE GLI ERRORI????
IL CODICE DA ME IMPLEMENTATO E' IL SEGUENTE:

//----------------------------------------------------------------------------------

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define tot_lettere 36 /*Tutte le lettere dell'alfabeto + i numeri del sistema decimale*/
#define dim_max 100

struct lista{
char *parola;
int contatore;
struct lista *next;
};

typedef struct lista list;

void spazio (void);
void analisi(char *);
int pmatch(char *, char *);
void insucc(char *);
void incrementa_lettera(char );
list *crea_lista(list *, char *);
list *confronta_stringa(char *, list *);
void stampa(list *);

int insuccesso[dim_max];
char lettere[tot_lettere]; /*array contenente tutte le lettere dell'alfabeto + num.del sist decimale*/
char max_parola[dim_max]; //Parola massima composta da 25 caratteri
char pat[dim_max];

main()
{
int s, i;
char *testo;

do
{
spazio();
printf("\t\tDIGITI:\n\n");
printf("\n1- Analizzare il testo esistente (che verrà visualizzato)\n2- Inserire un nuovo testo\n0- ESCI dal programma");
spazio();
scanf("%d",& s);

switch (s){

case 1 : clrscr();
spazio();
printf("Il testo esistente e':");
spazio();
//80 caratteri per riga nella schermata dell'applicativo
printf("\nDurante i primi decenni della loro esistenza, le reti di computer sono state\nusate principalmente dai ricercatori universitari per inviare messaggi\nelettronici, e dai dipendenti di industrie per condividere stampanti.\nIn questi ambiti, la segretezza non aveva ragione di esistere.\nInvece adesso, con milioni di comuni cittadini che utilizzano le reti per\noperazioni bancarie, commerciali e fiscali questo problema e' apparso\nell orizzonte come potenzialmente collettivo.\nLa sicurezza in rete e' un argomento vasto e riguarda una moltitudine di\ncrimini.\nNella sua forma piu' semplice, si occupa di assicurare che nessuno possa leggere\no, peggio ancora, modificare i messaggi destinati ad altri. Si occupa di persone\nche cercano di accedere a servizi remoti che non sono autorizzati a usare.\nLa sicurezza si occupa anche di problemi come l intercettazione di messaggi\nautografi e la loro riproduzione, e di persone che cercano di negare di aver\nspedito tali messaggi.\n");
spazio();
testo = "\nDurante i primi decenni della loro esistenza, le reti di computer sono state\nusate principalmente dai ricercatori universitari per inviare messaggi\nelettronici, e dai dipendenti di industrie per condividere stampanti.\nIn questi ambiti, la segretezza non aveva ragione di esistere.\nInvece adesso, con milioni di comuni cittadini che utilizzano le reti per\noperazioni bancarie, commerciali e fiscali questo problema e' apparso\nell orizzonte come potenzialmente collettivo.\nLa sicurezza in rete e' un argomento vasto e riguarda una moltitudine di\ncrimini.\nNella sua forma piu' semplice, si occupa di assicurare che nessuno possa leggere\no, peggio ancora, modificare i messaggi destinati ad altri. Si occupa di persone\nche cercano di accedere a servizi remoti che non sono autorizzati a usare.\nLa sicurezza si occupa anche di problemi come l intercettazione di messaggi\nautografi e la loro riproduzione, e di persone che cercano di negare di aver\nspedito tali messaggi.\n ";
printf("\n\n\n\t\t...[INVIO] per continuare...\n");
getchar(); getchar();
clrscr();
analisi(testo);

for(i=0; i<tot_lettere; i++)
printf("\n%d lettera : %d ", i+1, lettere[i]);
break;

case 2 : //clrscr();
spazio();
printf("\tINSERISCA UN NUOVO TESTO, tutto su una riga ([INVIO] per terminare):");
gets(testo);
//clrscr();
spazio();
printf("\t\tHA INSERITO:");
spazio();
puts(testo);
spazio();
printf("\n\n\n\t\t...[INVIO] per continuare...\n");
getchar();
//clrscr();
analisi(testo);
break;

case 0 : exit(0);

default : //clrscr();
printf("\a\t\tSELEZIONE NON PRESENTE!\n\n\t\tDigiti [INVIO] e ripeta la scelta:");
getchar();
break;
}
}
while(s < 0 || s > 2);


fflush(stdin);
getchar();
}

//******************************************************************************

void spazio(void)
{
printf("\n--------------------------------------------------------------------------\n");
}

//******************************************************************************

void analisi (char *testo)
{
int cont = 0, i;
list *inizio, *p;

inizio = p = NULL;

do
{
/*Se la lettera corrente è uguale ad un qualsiasi carattere di punteggiatura si effettua la verifica*/
if(*testo != ',' && *testo != '.' && *testo != ' ' && *testo != '?' && *testo != '!' && *testo != '"' && *testo != '=' && *testo != '\\' && *testo != ':' && *testo != '<' && *testo != '>' && *testo != ';' && *testo != '£' && *testo != '$' && *testo != '%' && *testo != '(' && *testo != ')' && *testo != '*' && *testo != '_' && *testo != '+' && *testo != '-' && *testo != '/' && *testo != '|' && *testo != '#' && *testo != '@' && *testo != '[' && *testo != ']' && *testo != '\'')
{
incrementa_lettera(*testo); //Incrementa il contatore della lettera

max_parola[cont] = *testo;

cont++;
testo++;
}
else
{
if (cont == 0 || cont ==1) /*Se è una lettera il suo contatore è già stato incrementato*/
{
testo++;
cont = 0;
}
else
{
inizio = confronta_stringa(max_parola, inizio);
cont = 0;
}

for(i=0; i<tot_lettere; i++) /*Inizializziamo a vuoto tutte le componenti dell'array*/
max_parola[i] = '\0';
}

}
while(*testo != '\0');

stampa(p);
}

//******************************************************************************

list *confronta_stringa(char *v, list *inizio)
{
int flag = -1;

while(inizio && flag == -1) /*non si è raggiunta la fine del testo e non si è trovata la stringa*/
{
flag = pmatch(v, inizio->parola);
if(flag != -1) /*Se il pattern non è stato trovato pmatch restituisce -1 */
{
inizio->contatore ++; /*Incrementa il contatore della stringa esistente*/
return(inizio);
}
else
inizio = inizio->next;
}

if(flag == -1)
inizio = crea_lista(inizio, v);

return(inizio);
}

//******************************************************************************

int pmatch(char *stringa, char *pat)
{
int i=0, j=0;

int lens = strlen(stringa);
int lenp = strlen(pat);

while(i<lens && j<lenp)
{
if(stringa[i] == pat[j])
{i++; j++;}
else
if(j==0)
i++;
else
j = insuccesso[j-1]+1;
}
return( (j==lenp) ? (i-lenp) : -1);
}


//******************************************************************************

list *crea_lista(list *inizio, char *pattern)
{
list *p;

p = (list *)malloc(sizeof(list));

strcpy(p->parola, pattern);
p->contatore = 1;
p->next = inizio;

return(p);
}

//******************************************************************************

void stampa (list *inizio)
{
spazio();
printf("\t\tCOMPOSIZIONE TESTO:");
spazio();

while(inizio)
{
printf("\n%s compare nel testo %d volte.", inizio->parola, inizio->contatore);
inizio = inizio->next;
}
spazio();
}

//******************************************************************************
void incrementa_lettera(char lettera)
{
switch (lettera){
case 'a' :
case 'A' : lettere[0]++; break;
case 'b' :
case 'B' : lettere[1]++; break;
case 'c' :
case 'C' : lettere[2]++; break;
case 'd' :
case 'D' : lettere[3]++; break;
case 'e' :
case 'E' : lettere[4]++; break;
case 'f' :
case 'F' : lettere[5]++; break;
case 'g' :
case 'G' : lettere[6]++; break;
case 'h' :
case 'H' : lettere[7]++; break;
case 'i' :
case 'I' : lettere<img src=imgfaccina8ball.gif border=0 align=middle>++; break;
case 'j' :
case 'J' : lettere[9]++; break;
case 'k' :
case 'K' : lettere[10]++; break;
case 'l' :
case 'L' : lettere[11]++; break;
case 'm' :
case 'M' : lettere[12]++; break;
case 'n' :
case 'N' : lettere[13]++; break;
case 'o' :
case 'O' : lettere[14]++; break;
case 'p' :
case 'P' : lettere[15]++; break;
case 'q' :
case 'Q' : lettere[16]++; break;
case 'r' :
case 'R' : lettere[17]++; break;
case 's' :
case 'S' : lettere[18]++; break;
case 't' :
case 'T' : lettere[19]++; break;
case 'u' :
case 'U' : lettere[20]++; break;
case 'v' :
case 'V' : lettere[21]++; break;
case 'w' :
case 'W' : lettere[22]++; break;
case 'x' :
case 'X' : lettere[23]++; break;
case 'y' :
case 'Y' : lettere[24]++; break;
case 'z' :
case 'Z' : lettere[25]++; break;
case '1' : lettere[26]++; break;
case '2' : lettere[27]++; break;
case '3' : lettere[28]++; break;
case '4' : lettere[29]++; break;
case '5' : lettere[30]++; break;
case '6' : lettere[31]++; break;
case '7' : lettere[32]++; break;
case '8' : lettere[33]++; break;
case '9' : lettere[34]++; break;
case '0' : lettere[35]++; break;

default : break;
}
}


sa vida mia luchet che istella

3 Risposte

  • Re: PROBLEMA ALGORITMO INCASINATO IN C!!

    Allora,
    Errori risocntrati:

    1) nella crea_lista devi allocare anche il char* parola, altrimenti il programma crasha irrimediabilmente. Puoi scrivere semplicemente
    p->parola = new char[strlen(pattern)];

    2) L'istruzione j = insuccesso[j-1]+1; viene effettivamente ripetuta all'infinito, il motivo è che c'è un check con !=0 sopra, ed il +1 sotto non aiuta per niente... non entro nel merito dell'algoritmo, ma probabilmente c'è un problema di fondo con gli indici...

    In effetti la cosa migliore è riguardare il sistema che hai utilizzato, ci sono diversi punti in cui può essere migliorato e reso più snello... in particolare quell' if infinito (if(*testo != ',' && *testo != '.' && *testo != ' ' && *testo != '?' && *testo != '!' && *testo != '"' && *testo != '=' && *testo != '\\' && *testo != ':' && *testo != '<' && *testo != '>' && *testo != ';' && *testo != '£' && *testo != '$' && *testo != '%' && *testo != '(' && *testo != ')' && *testo != '*' && *testo != '_' && *testo != '+' && *testo != '-' && *testo != '/' && *testo != '|' && *testo != '#' && *testo != '@' && *testo != '[' && *testo != ']' && *testo != '\'')
    ) può essere trasformato in una semplice ricerca di carattere tra un set prestabilito (il C offre funzioni standard per questo genere di cose)

    Ciaociao

    Venite a visitarci qui: http://spazioinwind.libero.it/bottomapsoftware
  • Re: PROBLEMA ALGORITMO INCASINATO IN C!!

    PS: Anche la switch (lettera) in fondo al codice può essere riscritta in circa 2 righe (basta dichiarare un array di 256) ed utilizzare array[lettera]++, oppure trasformare la lettera in lowercase prima di siwthcarla, ti risparmi un sacco di codice...

    PPS: Non ho ben capito il motivo di un pattern matching per il confronto... non bastava una smplice !strcmp() ?

    Ciaociao

    Venite a visitarci qui: http://spazioinwind.libero.it/bottomapsoftware
  • Re: PROBLEMA ALGORITMO INCASINATO IN C!!

    Ho provato a effettuare le correzioni consigliate:
    Ho modificato la lista ed ho introdotto la funzione "insucc" (dall'algoritmo di pattern matching di Knut, Morris e Pratt):
    void insucc(char *pat)
    {
    int i, j;

    int n = strlen(pat);

    insuccesso[0] = -1;

    for(j=1; j<n; j++)
    {
    i = insuccesso[j-1];
    while((pat[j] != pat[i+1]) && (i>=0))
    i = insuccesso[i];

    if(pat[j] == pat[i+1])
    insuccesso[j] = i+1;
    else
    insuccesso[j] = -1;
    }
    }

    Questa funzione dovrebbe inizializzare l'arrey "insuccesso" correttamente.
    La chiamata per la funzione "insucc" l'ho effettuata all'inizio della funzione "pmatch" in questo modo:

    int pmatch(char *stringa, char *pat)
    {
    int i=0, j=0;

    int lens = strlen(stringa);
    int lenp = strlen(pat);

    insucc(pat);

    while(i<lens && j<lenp)
    {
    if(stringa[i] == pat[j])
    {i++; j++;}
    else
    if(j==0)
    i++;
    else
    j = insuccesso[j-1]+1;
    }
    return( (j==lenp) ? (i-lenp) : -1);
    }

    Ma il programma esegue ancora un ciclo infinito.
    Non riesco a trovare questo maledetto errore... AIUTO!


    sa vida mia luchet che istella
Devi accedere o registrarti per scrivere nel forum
3 risposte