[C] Stringhe palindrome, con pile

xbubbax · 25-05-2008, 08:32

Mi dite perchè non funziona questo programma che dice se due stringhe sono palindrome?

grazie

Codice HTML:

#include <stdio.h>
#include <stdlib.h>
#include "pile.h"

int Palindroma(char *s)
{
    //PRE   LA FUNZIONE Palindroma PRENDE IN INGRESSO UNA STRINGA s.
    //POST LA FUNZIONE Palindroma RESTITUISCE 1 SE LA STRINGA s E' PALINDROMA, 0 ALTRIMENTI. LA VERIFICA AVVIENE UTILIZZANDO LE PILE.

    pilaPtr P1=NULL;
    pilaPtr P2=NULL;
    pilaPtr P3=NULL;

    for(;*s!='/0';s++)
    {
        P1=Push(P1,*s);
        P2=Push(P2,*s);
    }

    while(!Empty(P2))
    {
        P3=Push(P3,Top(P2));
        P2=Pop(P2);
    }

    while(!Empty(P1))
    {
        if(Top(P1)!=Top(P3))
        {
            return 0;
        }

        P1=Pop(P1);
        P3=Pop(P3);

    }

    return 1;
}

    int main(void)
    {
        char *s="abba";

        printf("%d\n", Palindroma(s));
    }

wingman87 · 25-05-2008, 12:35

Dovresti aggiungere il codice dei metodi della pila.

wizard1993 · 25-05-2008, 13:34

ma le pile dove le inizializzi?

Vincenzo1968 · 25-05-2008, 19:49

Perchè usare tre pile quando ne basta una?

Codice:

#include <stdio.h>
#include <stdlib.h>

typedef struct tagPila
{
    char c;
    struct tagPila *next;
} Pila;

Pila* NewNode(char c)
{
    Pila *n;

    n = (Pila *)malloc(sizeof(Pila));

    if( n == NULL )
        return NULL;

    n->c = c;
    n->next = NULL;

    return n;
}

Pila* Push(Pila *p, char c)
{
    Pila *nuovo;

    nuovo = NewNode(c);
    nuovo->next = p;

    return nuovo;
}

Pila* Pop(Pila *p, char *c)
{
    Pila *pRet;

    if ( !p )
        return NULL;

    *c = p->c;
    pRet = p->next;

    free(p);

    return pRet;
}

int Empty(Pila *p)
{
    if ( !p )
        return 1;
    else
        return 0;
}

int Palindroma(char *s)
{
    // LA FUNZIONE Palindroma PRENDE IN INGRESSO UNA STRINGA s.
    // RESTITUISCE 1 SE LA STRINGA s E' PALINDROMA, 0 ALTRIMENTI.
    // LA VERIFICA AVVIENE UTILIZZANDO LE PILE.

    int k = 0;
    Pila * P1 = NULL;
    char c;

    for(; *(s + k); k++)
    {
        P1 = Push(P1, *(s + k));
    }

    k = 0;
    while( !Empty(P1) )
    {
	P1 = Pop(P1, &c);
	if ( c != *(s + k) )
	    return 0;
	k++;
    }

    return 1;
}

int main(void)
{
    char *s = "abba";

    if ( Palindroma(s) )
        printf("La stringa %s e' palindroma\n", s);
    else
        printf("La stringa %s non e' palindroma\n", s);
}

DanieleC88 · 25-05-2008, 21:49

E questa cos'è?

Quote:

Originariamente inviato da xbubbax

Codice:

    for(;*s!='/0';s++)

xbubbax · 26-05-2008, 08:01

come cos'è?

come faccio a scorrere la stringa?

le funzioni per la pila sono giuste visto che con gli altri esercizi funzionano

sottovento · 26-05-2008, 08:36

Quote:

Originariamente inviato da Vincenzo1968

Perchè usare tre pile quando ne basta una?

Codice:

<cut>

Attenzione: andra' in crash in maniera random!

wingman87 · 26-05-2008, 08:46

Quote:

Originariamente inviato da xbubbax

le funzioni per la pila sono giuste visto che con gli altri esercizi funzionano

Ci dev'essere qualche problema lì perché concettualmente il programma mi sembra corretto

sottovento · 26-05-2008, 08:48

Quote:

Originariamente inviato da wingman87

Ci dev'essere qualche problema lì perché concettualmente il programma mi sembra corretto

Il problema principale l'ha segnalato, sebbene in maniera un po' troppo criptica, DanieleC88. Andrebbe corretto.
Poi c'e' un secondo problema. Non e' necessario, per ora, controllare la libreria delle pile. Prima vanno corretti questi due problemi

wingman87 · 26-05-2008, 08:56

Quote:

Originariamente inviato da sottovento

Il problema principale l'ha segnalato, sebbene in maniera un po' troppo criptica, DanieleC88. Andrebbe corretto.
Poi c'e' un secondo problema. Non e' necessario, per ora, controllare la libreria delle pile. Prima vanno corretti questi due problemi

Hai ragione, c'è la slash al contrario

non l'avevo notato.
L'altro errore non lo vedo però

Adesso lo rileggo meglio

EDIT: non ho trovato altri errori... stavolta però ho usato un compilatore

Questo è il codice:

Codice:

#include <stdio.h>

struct nodo{
    char value;
    struct nodo* next;
};

typedef struct nodo* pilaPtr;

pilaPtr Push(pilaPtr p,char c){
    pilaPtr nuovo=malloc(sizeof(struct nodo));
    nuovo->value=c;
    nuovo->next=p;
    return nuovo;
}

pilaPtr Pop(pilaPtr p){
    pilaPtr ret=p->next;
    free(p);
    return ret;
}

char Top(pilaPtr p){
    return p->value;
}
int Empty(pilaPtr p){
    return (p==NULL);
}

int Palindroma(char *s)
{
    //PRE   LA FUNZIONE Palindroma PRENDE IN INGRESSO UNA STRINGA s.
    //POST LA FUNZIONE Palindroma RESTITUISCE 1 SE LA STRINGA s E' PALINDROMA, 0 ALTRIMENTI. LA VERIFICA AVVIENE UTILIZZANDO LE PILE.

    pilaPtr P1=NULL;
    pilaPtr P2=NULL;
    pilaPtr P3=NULL;

    for(;*s!='\0';s++)
    {
        P1=Push(P1,*s);
        P2=Push(P2,*s);
    }

    while(!Empty(P2))
    {
        P3=Push(P3,Top(P2));
        P2=Pop(P2);
    }

    while(!Empty(P1))
    {
        if(Top(P1)!=Top(P3))
        {
            return 0;
        }

        P1=Pop(P1);
        P3=Pop(P3);

    }

    return 1;
}

int main(void)
{
    char *s="abba";
    printf("%d\n", Palindroma(s));
    system("pause");
}

khelidan1980 · 26-05-2008, 09:43

Quote:

Originariamente inviato da xbubbax

come cos'è?

come faccio a scorrere la stringa?

le funzioni per la pila sono giuste visto che con gli altri esercizi funzionano

io lo scriverei così:

Codice:

 while (*s!='\0')
    {
    	P1=Push(P1,*s);
    	P2=Push(P2,*s);
    	s++;
    }

Vincenzo1968 · 26-05-2008, 18:15

Quote:

Originariamente inviato da sottovento

Attenzione: andra' in crash in maniera random!

Ciao sottovento,

potresti gentilmente indicarmi dove sta il problema?

Ciao

Vincenzo1968 · 27-05-2008, 02:38

Credo di esserci arrivato da solo ( con un piccolo aiuto da parte di Donald E. Knuth

)

Codice:

#include <stdio.h>
#include <stdlib.h>

typedef struct tagPila
{
    char c;
    struct tagPila *next;
} Pila;

void Push(Pila** topRef, char c)
{
    Pila* newNode = malloc(sizeof(Pila));
    newNode->c = c;
    newNode->next = *topRef;
    *topRef = newNode;
}

char Pop(Pila** topRef)
{
    Pila* top;
    char c;

    top = *topRef;
    if ( !top )
        return 0;

    c = top->c;
    *topRef = top->next;

    free(top);

    return c;
}

int Empty(Pila *p)
{
    if ( !p )
        return 1;
    else
        return 0;
}

void Free(Pila *first)
{
    Pila *n1 = first, *n2;
    while ( n1 != NULL )
    {
        n2 = n1->next;
        free(n1);
        n1 = n2;
    }
}

int Palindroma(char *s)
{
    // LA FUNZIONE Palindroma PRENDE IN INGRESSO UNA STRINGA s.
    // RESTITUISCE 1 SE LA STRINGA s E' PALINDROMA, 0 ALTRIMENTI.
    // LA VERIFICA AVVIENE UTILIZZANDO UNA PILA.

    int k = 0;
    Pila * P1 = NULL;

    for(; *(s + k); k++)
    {
        Push(&P1, *(s + k));
    }

    k = 0;
    while( !Empty(P1) )
    {
        if ( Pop(&P1) != *(s + k++) )
            return 0;
    }

    return 1;
}

int main(void)
{
    char *s = "abba";

    if ( Palindroma(s) )
        printf("La stringa %s e' palindroma\n", s);
    else
        printf("La stringa %s non e' palindroma\n", s);
}

sottovento · 27-05-2008, 04:24

Quote:

Originariamente inviato da Vincenzo1968

Credo di esserci arrivato da solo ( con un piccolo aiuto da parte di Donald E. Knuth

)

Codice:

<CUT>

Vincenzo,
prima di tutto, scusami: non volevo essere ne' criptico ne' saccente. Il tuo codice e' ottimo.

Direi che e' OK. Se mi permetti un'osservazione: controlla sempre l'esito della malloc(), altrimenti pecchi di "fede cieca" (blind trust, http://it.wikipedia.org/wiki/Fede_ci...nformatica%29).

Ciao

Vincenzo1968 · 27-05-2008, 15:26

Quote:

Originariamente inviato da sottovento

Vincenzo,
prima di tutto, scusami: non volevo essere ne' criptico ne' saccente. Il tuo codice e' ottimo.

Direi che e' OK. Se mi permetti un'osservazione: controlla sempre l'esito della malloc(), altrimenti pecchi di "fede cieca" (blind trust, http://it.wikipedia.org/wiki/Fede_ci...nformatica%29).

Ciao

Figurati Sottovento,

non hai di che scusarti, anzi, devo ringraziarti. Hai ancora una volta ragione: generalmente controllo sempre, come nella prima versione del codice che ho postato, il valore di ritorno.
La funzione Push va, dunque, modificata così:

Codice:

void Push(Pila** topRef, char c)
{
    Pila* newNode = malloc(sizeof(Pila));
    if ( !newNode )
        return;

    newNode->c = c;
    newNode->next = *topRef;
    *topRef = newNode;
}

e la funzione Palindroma, così:

Codice:

int Palindroma(char *s)
{
    // LA FUNZIONE Palindroma PRENDE IN INGRESSO UNA STRINGA s.
    // RESTITUISCE 1 SE LA STRINGA s E' PALINDROMA, 0 ALTRIMENTI.
    // LA VERIFICA AVVIENE UTILIZZANDO LE PILE.

    int k = 0;
    Pila * P1 = NULL;

    if ( !*s )
        return 0;

    for(; *(s + k); k++)
    {
        Push(&P1, *(s + k));
        if ( !P1 )
        {
            printf("Errore: memoria insufficiente.\n");
            return 0;
        }
    }

    k = 0;
    while( !Empty(P1) )
    {
        if ( Pop(&P1) != *(s + k++) )
        return 0;
}

    return 1;
}

Ciao

25-05-2008, 13:34	#3
wizard1993 Senior Member Iscritto dal: Apr 2006 Messaggi: 22462	ma le pile dove le inizializzi? __________________ amd a64x2 4400+ sk939;asus a8n-sli; 2x1gb ddr400; x850 crossfire; 2 x western digital abys 320gb\|\| asus g1 Se striscia fulmina, se svolazza l'ammazza

25-05-2008, 12:35	#2
wingman87 Senior Member Iscritto dal: Nov 2005 Messaggi: 2794	Dovresti aggiungere il codice dei metodi della pila.

26-05-2008, 08:01	#6
xbubbax Senior Member Iscritto dal: Apr 2007 Messaggi: 381	come cos'è? come faccio a scorrere la stringa? le funzioni per la pila sono giuste visto che con gli altri esercizi funzionano

Strumenti
Mostra una versione stampabile Invia questa pagina per email