[C]Liste con un puntatore: problema stanck overflow
Ciao a tutti, non capisco perchè mi dia errore di stack overflow quando eseguo questo programma :
Qualcuno mi può aiutare?
[mod="Luc@s"]Per maggiore chiarezza, in futuro, potresti mettere il codice inserito nel tag apposito? Grazie
[/mod]
Qualcuno mi può aiutare?
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef struct st_Elem{
char elem;
struct st_Elem *next;
} listElemType;
/*===================
funzione implementa
====================*/
listElemType* initList()
{
char ch;
listElemType *auxptr, *listptr;
ch=getchar();
if (ch!='\n')
{listptr=(listElemType*)malloc(sizeof(listElemType));
listptr->elem=ch;
auxptr=listptr;}
else
{listptr=NULL;
return listptr;}
ch=getchar();
while (ch!='\n')
{auxptr ->next=malloc(sizeof(listElemType));
auxptr=auxptr->next;
auxptr->elem=ch;
ch=getchar();}
auxptr->next=NULL;
return listptr;
}
/*===================
funzione stampa
====================*/
int printList(listElemType *listptr)
{
printf("lista ---> ");
/* ciclo di scansione */
while(listptr != NULL)
{
printf("%c", listptr->elem);
printf(" ---> ");
listptr = listptr->next;
}
printf("NULL\n");
}
void freeMemory(listElemType *listptr)
{
listElemType *save;
while (listptr!=NULL)
{
save=listptr->next;
free (listptr);
listptr=save;
}
}
/*=======================
FUNZIONE CONFRONTA
=======================*/
int confronta(listElemType *pattern, listElemType *proposta,listElemType *save,listElemType *graffetta)
{
switch (save->elem)
{
case '+' : if (save->elem== proposta ->elem)
{
graffetta= pattern;
pattern=pattern->next;
proposta=proposta->next;
save=save->next;
confronta(pattern,proposta,save,graffetta);
}
default : if (proposta->elem == graffetta->elem);
{
proposta=proposta->next;
confronta(pattern,proposta,save,graffetta);
}
pattern=pattern->next;
if (proposta->elem == pattern->elem)
{
graffetta=pattern;
proposta=proposta->next;
pattern=pattern->next;
save=pattern;
confronta(pattern,proposta,save,graffetta);
}
return 1;
}
return 0;
}
int main ()
{
listElemType *pat;
listElemType *prop;
listElemType *graf;
listElemType *s;
int responso;
graf=(listElemType*)malloc(sizeof(listElemType));
s=(listElemType*)malloc(sizeof(listElemType));
printf("Inserisci Pattern\n");
pat=initList();
printf("Inserisci Proposta\n");
prop=initList();
responso=confronta(pat,prop,s,graf);
printf ("%d\n", responso);
return 0;
}[mod="Luc@s"]Per maggiore chiarezza, in futuro, potresti mettere il codice inserito nel tag apposito? Grazie
[/mod]
Risposte
Vorrei prima di tutto consigliarti di attivare sempre gli avvisi al massimo e di trattare gli avvisi come errori nel tuo compilatore. Semplicemente attivando questa opzione ho trovato i seguenti errori nel codice:
La funzione printList dovrebbe restituire un valore intero ma non restituisce valori. Immagino che il corretto tipo di ritorno fosse void.
La funzione confronta restituisce sempre 1. Il primo case dello switch non contiene né break, né return e quindi anche il blocco di codice dentro default viene eseguito. Lo switch presenta alcuni problemi per cui è consigliabile utilizzare degli if nei casi in cui ci siano pochi casi come questo. In questo caso sarebbe inoltre probabilmente stato più semplice da leggere.
Questo errore con quello superiore dovrebbe rispondere alla tua domanda.
1>...\main.c(50) : warning C4716: 'printList' : must return a value
La funzione printList dovrebbe restituire un valore intero ma non restituisce valori. Immagino che il corretto tipo di ritorno fosse void.
1>...\main.c(101) : warning C4702: unreachable code
La funzione confronta restituisce sempre 1. Il primo case dello switch non contiene né break, né return e quindi anche il blocco di codice dentro default viene eseguito. Lo switch presenta alcuni problemi per cui è consigliabile utilizzare degli if nei casi in cui ci siano pochi casi come questo. In questo caso sarebbe inoltre probabilmente stato più semplice da leggere.
1>...\main.c(102) : warning C4717: 'confronta' : recursive on all control paths, function will cause runtime stack overflow
Questo errore con quello superiore dovrebbe rispondere alla tua domanda.
Grazie per le risposte veloci!
@ Luk@s : La prossima volta starò attenta e lo farò, scusami.
@ apatriarca :Compilando con cywing non mi dava warning!
Comunque come avrai notato dal programma non sono un genio, e infatti pensavo che i break -essendoci le chiamate ricorsive- non servissero per no fargli fare il defult. Mi puoi fare luce su questo punto?
edit:
Ho modificato lo switch mettendo prima di ogni chiamata ricorsiva return.
Ma ancora eseguendo mi da questo errore :
@ Luk@s : La prossima volta starò attenta e lo farò, scusami.
@ apatriarca :Compilando con cywing non mi dava warning!
Comunque come avrai notato dal programma non sono un genio, e infatti pensavo che i break -essendoci le chiamate ricorsive- non servissero per no fargli fare il defult. Mi puoi fare luce su questo punto?
edit:
Ho modificato lo switch mettendo prima di ogni chiamata ricorsiva return.
Ma ancora eseguendo mi da questo errore :
10 [main] pattern 1232_cygtls:: handle_exceptions: Error while dumping state
segmentation Fault
Prova ad aggiungere l'opzione -Wall. Esistono comunque anche dei programmi che eseguono un analisi statica del tuo programma alla ricerca di possibili errori (http://en.wikipedia.org/wiki/List_of_tools_for_static_code_analysis).
Venendo alla tua funzione confronta. Potresti spiegare meglio quale sia lo scopo della funzione? Immagino sia un esercizio, mostreresti il testo?
Venendo alla tua funzione confronta. Potresti spiegare meglio quale sia lo scopo della funzione? Immagino sia un esercizio, mostreresti il testo?
È spesso più complicato seguire il codice di una funzione ricorsiva. Nel tuo caso ogni percorso all'interno del tuo codice porta ad una chiamata ricorsiva. La funzione viene quindi richiamata all'infinito e questo causa lo stack overflow.
Credo che il primo problema della funzione sia il nome. Una funzione confronta dovrebbe eseguire semplicemente un confronto tra due oggetti e restituire se sono uguali o diversi e in che modo. Ma i nomi dei tuo parametri fanno più che altro pensare che tu stia facendo una specie di ricerca di un pattern all'interno di una stringa. Qualcosa come cercaPattern in questo caso sarebbe stato un nome più intuitivo. Cos'è graffetta esattamente? Nonostante si tratti di un termine di uso comune il significato all'interno del codice non è del tutto evidente. Si tratta di una specie di 'cursore' che indica la posizione attuale nel pattern? Perché fai uso di una variabile aggiuntiva quando è possibile fare la stessa cosa utilizzando semplicemente la lista pattern? L'uso dello switch rende solo più difficile la comprensione del codice non aggiungendo alcun vantaggio in termini di performance o spazio utilizzato. Direi che è quindi meglio utilizzare un semplice if.
ATTENTO AL PUNTO E VIRGOLA DOPO ALL'IF. In questo modo è come se quella riga non fosse stata inserita. Eliminando il punto e virgola viene corretto il problema dello stack overflow sul mio PC ma secondo me la funzione è ancora sbagliata (o comunque è meglio scriverla in modo più chiaro).
Credo che il primo problema della funzione sia il nome. Una funzione confronta dovrebbe eseguire semplicemente un confronto tra due oggetti e restituire se sono uguali o diversi e in che modo. Ma i nomi dei tuo parametri fanno più che altro pensare che tu stia facendo una specie di ricerca di un pattern all'interno di una stringa. Qualcosa come cercaPattern in questo caso sarebbe stato un nome più intuitivo. Cos'è graffetta esattamente? Nonostante si tratti di un termine di uso comune il significato all'interno del codice non è del tutto evidente. Si tratta di una specie di 'cursore' che indica la posizione attuale nel pattern? Perché fai uso di una variabile aggiuntiva quando è possibile fare la stessa cosa utilizzando semplicemente la lista pattern? L'uso dello switch rende solo più difficile la comprensione del codice non aggiungendo alcun vantaggio in termini di performance o spazio utilizzato. Direi che è quindi meglio utilizzare un semplice if.
if (proposta->elem == graffetta->elem);
ATTENTO AL PUNTO E VIRGOLA DOPO ALL'IF. In questo modo è come se quella riga non fosse stata inserita. Eliminando il punto e virgola viene corretto il problema dello stack overflow sul mio PC ma secondo me la funzione è ancora sbagliata (o comunque è meglio scriverla in modo più chiaro).
Mi sono dimenticato di dirti che ti sei dimenticato di deallocare la memoria allocata...
Per quanto riguarda la funzione confronta, quello che faceva l'aveo giàmesso ma è sparito o.O
Ecco di nuovo qui tutto quello che dovrebbe fare:
Esercizio 4: Pattern matching
Il "pattern matching" consiste nel verificare se una sequenza rispetta una certa regolarità, cioè se è costruita secondo una certa legge. Questo problema si ritrova in tantissimi campi dell'informatica, fra cui i compilatori e linguaggi di programmazione, la ricerca di stringhe, il confronto strutturale fra documenti, e anche in ambiti interdisciplinari come l'analisi informatica di sequenze genetiche.
Utilizzando le funzioni ausiliarie definite negli esercizi precedenti, si implementi una funzione che legge una sequenza di lettere minuscole terminata da ’\n’, la confronta con un pattern passato come parametro alla funzione, ed inizializzato nel main (o, meglio, inizializzato da una seconda funzione che viene richiamata nel main), e restituisce 1 se la sequenza letta rispetta il pattern, e 0 altrimenti.
La memoria allocata va deallocata quando non serve più.
In questo esercizio, per "pattern" si intende una sequenza composta da lettere minuscole e dal simbolo +.
Il simbolo + posto dopo una lettera qualunque indica la possibilità di ripetere 1 o più volte la lettera che lo precede.
Il segno + si riferisce sempre alla lettera che lo precede, quindi in un pattern non possono esserci due simboli + uno dopo l’altro. Inoltre, per lo stesso motivo, il pattern non può iniziare con il simbolo +.
Poiché il + indica una ripetizione della lettera precedente, la lettera seguente deve essere diversa da quella che lo segue (altrimenti sarebbe stata inglobata nella ripetizione).
Una qualsiasi sequenza “rispetta il pattern” indicato, se ogni lettera della sequenza si trova nella corretta posizione rispetto al pattern, oppure se rappresenta una ripetizione di una lettera ammissibile perché nel pattern, nella posizione corrispondente, c’è il simbolo +, e la lettera ripetuta nella sequenza è proprio quella che precede il + nel pattern.
In altre parole, il pattern rappresenta una possibile famiglia di sequenze, e una sequenza che "rispetta il pattern" è una sequenza che appartiene a tale famiglia.
Quindi se ad esempio pattern = abc+d+aaa, la sequenza abcdaaa rispetta il pattern, come pure le sequenze abcccccccdaaa e abcdddddaaa.
La sequenza abdaaa invece non lo rispetta.
Allora ho corretto l'IF togliendo il punto e virgol che mi dicevi ma torna 1 .. e c'è da piangere perchè ritorna sempre 1.
Diciamo che è interamente da rifare, l'avevo fatto solo con gli If all'inizio ma poi mi sono detta che dovevo provare a farlo con lo switch...
ora mi riguardo la sintassi dello switch non vorrei cadere proprio lì.
Altrimenti ci sarà qualche (anzi molti) errori di fondo...
Grazie per la pazienza..
Ah! ma cosa dovrei ancora allocare?? mi sembra di avere già allocato tutto.
Ecco di nuovo qui tutto quello che dovrebbe fare:
Esercizio 4: Pattern matching
Il "pattern matching" consiste nel verificare se una sequenza rispetta una certa regolarità, cioè se è costruita secondo una certa legge. Questo problema si ritrova in tantissimi campi dell'informatica, fra cui i compilatori e linguaggi di programmazione, la ricerca di stringhe, il confronto strutturale fra documenti, e anche in ambiti interdisciplinari come l'analisi informatica di sequenze genetiche.
Utilizzando le funzioni ausiliarie definite negli esercizi precedenti, si implementi una funzione che legge una sequenza di lettere minuscole terminata da ’\n’, la confronta con un pattern passato come parametro alla funzione, ed inizializzato nel main (o, meglio, inizializzato da una seconda funzione che viene richiamata nel main), e restituisce 1 se la sequenza letta rispetta il pattern, e 0 altrimenti.
La memoria allocata va deallocata quando non serve più.
In questo esercizio, per "pattern" si intende una sequenza composta da lettere minuscole e dal simbolo +.
Il simbolo + posto dopo una lettera qualunque indica la possibilità di ripetere 1 o più volte la lettera che lo precede.
Il segno + si riferisce sempre alla lettera che lo precede, quindi in un pattern non possono esserci due simboli + uno dopo l’altro. Inoltre, per lo stesso motivo, il pattern non può iniziare con il simbolo +.
Poiché il + indica una ripetizione della lettera precedente, la lettera seguente deve essere diversa da quella che lo segue (altrimenti sarebbe stata inglobata nella ripetizione).
Una qualsiasi sequenza “rispetta il pattern” indicato, se ogni lettera della sequenza si trova nella corretta posizione rispetto al pattern, oppure se rappresenta una ripetizione di una lettera ammissibile perché nel pattern, nella posizione corrispondente, c’è il simbolo +, e la lettera ripetuta nella sequenza è proprio quella che precede il + nel pattern.
In altre parole, il pattern rappresenta una possibile famiglia di sequenze, e una sequenza che "rispetta il pattern" è una sequenza che appartiene a tale famiglia.
Quindi se ad esempio pattern = abc+d+aaa, la sequenza abcdaaa rispetta il pattern, come pure le sequenze abcccccccdaaa e abcdddddaaa.
La sequenza abdaaa invece non lo rispetta.
Allora ho corretto l'IF togliendo il punto e virgol che mi dicevi ma torna 1 .. e c'è da piangere perchè ritorna sempre 1.
Diciamo che è interamente da rifare, l'avevo fatto solo con gli If all'inizio ma poi mi sono detta che dovevo provare a farlo con lo switch...
ora mi riguardo la sintassi dello switch non vorrei cadere proprio lì.
Altrimenti ci sarà qualche (anzi molti) errori di fondo...
Grazie per la pazienza..
Ah! ma cosa dovrei ancora allocare?? mi sembra di avere già allocato tutto.
Buona parte del testo dell'esercizio è riservato alla descrizione di cosa sia un pattern valido. Credo sia quindi utile, in un'applicazione reale sicuramente anche necessario, verificare la correttezza del pattern.
Un pattern corretto verifica le seguenti condizioni:
1. È formato esclusivamente da lettere minuscole e '+'
2. "++" non può essere una sottostringa del pattern
3. '+' non può essere il primo carattere del pattern
4. La lettera precedente e successiva ad un '+' devono essere diverse
Sul punto 4 non sono in realtà del tutto d'accordo. Il pattern "a+a" ha un comportamento diverso da "a+". Nel primo caso infatti "a" non rispetta il pattern mentre lo rispetta nel secondo. Ma in effetti accettare pattern di quel tipo rende solo il codice più complicato e lo stesso comportamento avrebbe potuto essere ottenuto con il pattern valido "aa+".
La lettura e verifica del pattern e il confronto di una stringa con il pattern sono entrambe operazioni che possono essere facilmente implementate usando delle macchine a stati. Sai già qualcosa sulle macchine a stati?
Un pattern corretto verifica le seguenti condizioni:
1. È formato esclusivamente da lettere minuscole e '+'
2. "++" non può essere una sottostringa del pattern
3. '+' non può essere il primo carattere del pattern
4. La lettera precedente e successiva ad un '+' devono essere diverse
Sul punto 4 non sono in realtà del tutto d'accordo. Il pattern "a+a" ha un comportamento diverso da "a+". Nel primo caso infatti "a" non rispetta il pattern mentre lo rispetta nel secondo. Ma in effetti accettare pattern di quel tipo rende solo il codice più complicato e lo stesso comportamento avrebbe potuto essere ottenuto con il pattern valido "aa+".
La lettura e verifica del pattern e il confronto di una stringa con il pattern sono entrambe operazioni che possono essere facilmente implementate usando delle macchine a stati. Sai già qualcosa sulle macchine a stati?
Prima di iniziare a risolvere l'esercizio vero e proprio vorrei discutere il codice vecchio. Direi che va abbastanza bene ma ci sono alcune cose che si possono fare per migliorarlo.
Non c'è alcun motivo per usare nomi diversi per il tag e per il nome del tipo. So che è molto comune ma a mio parere non ha senso: perché usare due nomi diversi per la stessa cosa? Quando scrivo in C definisco le strutture nel seguente modo:
Come vedi separando il typedef dalla definizione (e mettendolo prima) ho potuto evitare l'uso di struct List come tipo della variabile membro. Si tratta comunque esclusivamente di preferenza personale. Ho deciso di chiamare la struttura List perché listElemType mi fa pensare ad un typedef per il tipo della variabile membro elem.
La funzione va abbastanza bene anche se probabilmente avrei usato un nome diverso per la variabile save (come next). Il vero problema di questa funzione è il nome. freeMemory fa pensare ad un funzione per la deallocazione generica di memoria, mentre distrugge esclusivamente liste. Un nome un po' più sensato sarebbe stato freeList. I nomi delle funzioni e delle variabili sono importanti e dovrebbero richiamare l'operazione che svolgono. Ricordati di usare questa funzione alla fine del main per eliminare le liste che hai creato.
Per prima cosa, come aveva già fatto notare il mio compilatore, il tipo di ritorno dovrebbe essere void perché non restituisci valori. Il codice è corretto ma è molto inefficiente. Lo scopo di printf è quello di mostrare dei valori formattati. Per visualizzare stringhe o caratteri ci sono metodi più semplici ed efficienti (che spesso non vengono insegnati).
Anche in questo caso il nome è un po' ambiguo. readList sarebbe più appropriato visto che lo scopo della funzione è quello di leggere una stringa da console e restituire la lista corrispondente. Ho comunque diversi commenti da fare:
1. getchar restituisce un numero intero e non un char. Nonostante la conversione sia automatica alcuni compilatori (tra cui il mio) visualizzano un warning che può essere soppresso con un semplice cast.
2. malloc non richiede un cast in C anche se lo richiede in C++. Ci sono diverse opinioni a favore o contro l'uso del cast ma cerca comunque di essere coerente. Quando lavori con strutture è spesso utile creare una funzione per allocare la memoria e inizializzare la struttura. Nel tuo codice avrei per esempio implementato la funzione:
Con questa funzione il codice della funzione di lettura diventa:
Il principale vantaggio di questo metodo è che l'inizializzazione dei membri della struttura è assicurato e non è necessario stare attenti ad inserire la dimensione corretta all'interno del malloc.
typedef struct st_Elem {
char elem;
struct st_Elem *next;
} listElemType;
Non c'è alcun motivo per usare nomi diversi per il tag e per il nome del tipo. So che è molto comune ma a mio parere non ha senso: perché usare due nomi diversi per la stessa cosa? Quando scrivo in C definisco le strutture nel seguente modo:
typedef struct List List;
struct List {
char elem;
List *next;
};
Come vedi separando il typedef dalla definizione (e mettendolo prima) ho potuto evitare l'uso di struct List come tipo della variabile membro. Si tratta comunque esclusivamente di preferenza personale. Ho deciso di chiamare la struttura List perché listElemType mi fa pensare ad un typedef per il tipo della variabile membro elem.
void freeMemory(listElemType *listptr)
{
listElemType *save;
while (listptr != NULL) {
save = listptr->next;
free(listptr);
listptr = save;
}
}
La funzione va abbastanza bene anche se probabilmente avrei usato un nome diverso per la variabile save (come next). Il vero problema di questa funzione è il nome. freeMemory fa pensare ad un funzione per la deallocazione generica di memoria, mentre distrugge esclusivamente liste. Un nome un po' più sensato sarebbe stato freeList. I nomi delle funzioni e delle variabili sono importanti e dovrebbero richiamare l'operazione che svolgono. Ricordati di usare questa funzione alla fine del main per eliminare le liste che hai creato.
int printList(listElemType *listptr)
{
printf("lista ---> ");
/* ciclo di scansione */
while(listptr != NULL) {
printf("%c", listptr->elem);
printf(" ---> ");
listptr = listptr->next;
}
printf("NULL\n");
}
Per prima cosa, come aveva già fatto notare il mio compilatore, il tipo di ritorno dovrebbe essere void perché non restituisci valori. Il codice è corretto ma è molto inefficiente. Lo scopo di printf è quello di mostrare dei valori formattati. Per visualizzare stringhe o caratteri ci sono metodi più semplici ed efficienti (che spesso non vengono insegnati).
void printList(listElemType *listptr)
{
fputs("lista ---> ", stdout); /* stampa una stringa nello standard output (la console). */
while(listptr != NULL) {
putchar(listptr->elem); /* stampa un carattere nella console. */
fputs(" ---> ", stdout);
listptr = listptr->next;
}
puts("NULL"); /* stampa una stringa nella console aggiungendo il carattere '\n' alla fine. */
}
listElemType* initList()
{
char ch;
listElemType *auxptr, *listptr;
ch = getchar();
if (ch != '\n') {
listptr = (listElemType*) malloc(sizeof(listElemType));
listptr->elem = ch;
auxptr = listptr;
} else {
listptr = NULL;
return listptr;
}
ch = getchar();
while (ch != '\n') {
auxptr->next = malloc(sizeof(listElemType));
auxptr = auxptr->next;
auxptr->elem = ch;
ch = getchar();
}
auxptr->next = NULL;
return listptr;
}
Anche in questo caso il nome è un po' ambiguo. readList sarebbe più appropriato visto che lo scopo della funzione è quello di leggere una stringa da console e restituire la lista corrispondente. Ho comunque diversi commenti da fare:
1. getchar restituisce un numero intero e non un char. Nonostante la conversione sia automatica alcuni compilatori (tra cui il mio) visualizzano un warning che può essere soppresso con un semplice cast.
2. malloc non richiede un cast in C anche se lo richiede in C++. Ci sono diverse opinioni a favore o contro l'uso del cast ma cerca comunque di essere coerente. Quando lavori con strutture è spesso utile creare una funzione per allocare la memoria e inizializzare la struttura. Nel tuo codice avrei per esempio implementato la funzione:
listElemType *newListNode(char elem)
{
listElemType *ret = malloc(sizeof(listElemType));
if (ret) {
ret->elem = elem;
ret->next = NULL;
}
return ret;
}
Con questa funzione il codice della funzione di lettura diventa:
listElemType* readList()
{
char ch;
listElemType *auxptr, *listptr;
ch = (char) getchar();
if (ch != '\n') {
listptr = newListNode(ch);
auxptr = listptr;
} else {
return NULL;
}
ch = (char) getchar();
while (ch != '\n') {
auxptr->next = newListNode(ch);
auxptr = auxptr->next;
ch = (char) getchar();
}
return listptr;
}
Il principale vantaggio di questo metodo è che l'inizializzazione dei membri della struttura è assicurato e non è necessario stare attenti ad inserire la dimensione corretta all'interno del malloc.
Possiamo quindi passare alla verifica della correttezza del pattern. Il principale motivo per cui ti spiego questa funzione è che presenta alcune somiglianze con la funzione per il pattern matching. In effetti in entrambi i casi devi scorrere una stringa e verificare se rispetta alcune regole.
Parto quindi dal codice e poi te lo spiego.
Nella funzione viene visitata l'intera lista (usando un codice iterativo invece che una funzione ricorsiva) e ad ogni carattere (tranne il primo che ha regole particolari) verifico le regole. Per farlo ho bisogno di memorizzare alcune variabili di stato che mi permettono di comprende in che situazione mi trovo. In particolare è necessario conoscere se è stato appena trovato un '+' (è lo scopo di canBePlus). Per poter applicare le leggi è inoltre necessario memorizzare l'ultima lettera letta (e questo è lo scopo di current). Nonostante il codice non sia quello di una macchina a stati finiti ho in effetti modellato questa funzione su una FSM. Non ho provato a compilare il codice, ma dovrebbe essere corretto.
Parto quindi dal codice e poi te lo spiego.
#include <ctype.h>
/* Ho definito questa enumerazione solo per comodità... */
enum Bool {False = 0, True = 1};
typedef enum Bool Bool;
Bool isPattern(listElemType *pattern)
{
char current;
Bool canBePlus;
/* una stringa nulla non è un pattern. */
if (NULL == pattern) {
return False;
}
/* verifico che la prima lettera del pattern sia una lettera minuscola. */
if (islower(pattern->elem)) {
current = pattern->elem;
canBePlus = True;
pattern = pattern->next;
}
/* controllo il resto della stringa. */
for (; NULL != pattern; pattern = pattern->next) {
if (islower(pattern->elem)) {
if (!canBePlus && pattern->elem == current) {
return False; /* elemento prima e dopo il + uguali */
} else {
current = pattern->elem;
canBePlus = True;
}
} else if (canBePlus && '+' == pattern->elem) {
canBePlus = False;
} else {
return False;
}
}
return True;
}
Nella funzione viene visitata l'intera lista (usando un codice iterativo invece che una funzione ricorsiva) e ad ogni carattere (tranne il primo che ha regole particolari) verifico le regole. Per farlo ho bisogno di memorizzare alcune variabili di stato che mi permettono di comprende in che situazione mi trovo. In particolare è necessario conoscere se è stato appena trovato un '+' (è lo scopo di canBePlus). Per poter applicare le leggi è inoltre necessario memorizzare l'ultima lettera letta (e questo è lo scopo di current). Nonostante il codice non sia quello di una macchina a stati finiti ho in effetti modellato questa funzione su una FSM. Non ho provato a compilare il codice, ma dovrebbe essere corretto.
"apatriarca":
La lettura e verifica del pattern e il confronto di una stringa con il pattern sono entrambe operazioni che possono essere facilmente implementate usando delle macchine a stati. Sai già qualcosa sulle macchine a stati?
Macchine a stati? assolutamente nulla!
Scusa se rispondo ora ma aspettavo magari una notifica per mail (come solitamente succede) dal forum.
Per quanto riguarda il controllo diciamo che l'ho tralasciato
Però ogni volta passavo una sequenza assolutamente giusta che anche con il controllo sarebbe passata.
edit:
Grazie apatriarca per le correzioni.
I nomi scelti per le funzioni e l'intera struct c'è stata data dagli insegnanti, noi dovevamo solo implementarla. E le prime tre funzioni comunque fanno quel che era richiesto (magari a dispetto del nome) e lo dico perchè il professore era riuscito a controllarle.
Continuo a leggere.. grazie ancora eh!
edit 2:
Ecco ho finito di leggere.
Le mie domande : islower è una funzione che si trova in
Grazie sei stato davvero chiaro. Ora provo a fare il pattern matching sulla falsa riga del tuo.
Starò allora più attenta al nome delle variabili, le dichiarazione delle funzioni invece ci sono state date così.
Sì, islower è una funzione definita in ctype.h che restituisce 0 se il carattere passato non è una lettera minuscola, un valore diverso da zero in caso contrario.
Immaginavo i nomi delle funzioni ti fossero state date dall'insegnante, ma quando dovrai scrivere un codice da sola è comunque una buona idea quella di cercare di dare nomi che richiamano la funzione. Soprattutto quando il numero di righe e di funzioni inizieranno a crescere.
Immaginavo i nomi delle funzioni ti fossero state date dall'insegnante, ma quando dovrai scrivere un codice da sola è comunque una buona idea quella di cercare di dare nomi che richiamano la funzione. Soprattutto quando il numero di righe e di funzioni inizieranno a crescere.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo