Newsgroup: it.comp.lang.c
Titolo: [?] Alberi generici in C

Ciao a tutti,
    programmo in C da otto anni circa, e non mi sono mai trovato a fare un
uso massiccio di puntatori...fino ad ora. Sto preparando il laboratorio di
algoritmi e strutture dati, il penultimo esame per finire.
Uno degli esercizi e' implementare gli alberi con rappresentazione
figlio sinistro-fratello destro, ed e' da un po' di giorni che sono arenato.
Dopo una funzione ricorsiva per leggere l' input che non andava, ho deciso di
implementare una funzione iterativa con uno stack.
L' albero in input e' della forma: "(radice-lista di figli)" in cui la lista di figli può essere
costituita da sottoalberi della stessa forma.
Per esempio un' albero potrebbe essere "(ab(cde)fg)" e la sua rappresentazione grafica
(non mi serve produrla, e' solo per esemplificare):
a
|
b => c => f => g
        |
       d => e
Scrivo ieri sera il codice su carta, ad occhio sembra funzionare...
oggi lo compilo con Dev-C++... la compilazione non dà errori nè warning,
ma il programma si incricca durante la lettura...
Questo e' il codice, non riesco proprio a capire dove siano gli errori.
Grazie in anticipo a chi vorrà aiutarmi.
Saluti,
    Alessandro
#include <stdio.h>
#include <malloc.h>
#define EmptyTree NULL
#define EmptyStack NULL
typedef enum {FALSE, TRUE} Boolean;
typedef struct Nodo{
    char key;
    struct Nodo *leftChild,*rightBrother;
    }TNodo;
typedef TNodo *Tree;
typedef struct PStack{
    Tree *treep;
    struct PStack *next;
    } StackCell;
typedef StackCell *PNodeStack;
Boolean IsEmptyStack(PNodeStack s);
void Push(PNodeStack *s, Tree *p);
Tree *Pop(PNodeStack *s);
Tree ConsTree(char label);
Tree ReadTree(char input[]);
void PrintTree(Tree a);
void FreeTree(Tree a);
Boolean IsEmptyStack(PNodeStack s)
{
return(s==NULL ? TRUE : FALSE);
}
void Push(PNodeStack *s, Tree *p)
{
PNodeStack tmp;
tmp=(PNodeStack)malloc(sizeof(StackCell));
tmp->treep=p;
tmp->next=*s;
s=&tmp;
}
Tree *Pop(PNodeStack *s)
{
Tree *p;
PNodeStack toDel;
p=(*s)->treep;
toDel=*s;
s=&((*s)->next);
free(toDel);
return(p);
}
Tree ConsTree(char label)
{
Tree p=(Tree)malloc(sizeof(TNodo));
p->key=label;
p->leftChild=EmptyTree;
p->rightBrother=EmptyTree;
return(p);
}
Tree ReadTree(char input[]) //legge l' albero in forma parentesizzata
{
Tree a,*p;
PNodeStack stack;
int index;
if(input[0]=='\0') return(EmptyTree);
if(input[0]!='('){
    printf("Errore: l' albero di input deve essere in forma parentesizzata!\n");
    return(EmptyTree);
    }
if(input[1]==')') return(EmptyTree);
a=ConsTree(input[1]);
p=&(a->leftChild);
Push(&stack,p);
index=2;
do{
    if(input[index]==')'){
        p=Pop(&stack);
        *p=EmptyTree;
        }
    else if(input[index]=='('){
        *p=ConsTree(input[++index]);
        p=&((*p)->leftChild);
        Push(&stack,p);
        }
   else{
        *p=ConsTree(input[index]);
        p=&((*p)->rightBrother);
        }
   index++;
   }while(IsEmptyStack(stack)==FALSE);
return(a);
}
void PrintTree(Tree a)
{
Tree p;
if(a!=EmptyTree){
    printf("(Radice: %c",a->key);
    if(a->leftChild!=EmptyTree){
        printf(" Figlio sinistro: ");
        p=a->leftChild;
        printf(" %c",p->key);
        p=p->rightBrother;
        while(p!=EmptyTree){
            if(p->leftChild!=EmptyTree){
                printf(" Sottoalbero figlio: ");
                PrintTree(p);
                p=p->rightBrother;
                }
            else printf(" Altro figlio: %c ",p->key);
            p=p->rightBrother;
            }
        }
    }
printf(")");
}
void FreeTree(Tree a)
{
if(a!=EmptyTree){
    if(a->leftChild!=EmptyTree)
        FreeTree(a->leftChild);
    if(a->rightBrother!=EmptyTree)
        FreeTree(a->rightBrother);
    free(a);
    }
}
int main(void)
{
char albPar[30];
Tree t;
printf("Immetti l' albero: ");
scanf("%s",albPar);
t=ReadTree(albPar);
printf("Ecco l' albero che hai immesso: ");
PrintTree(t);
FreeTree(t);
//system("PAUSE");
return(0);
}

 ma il programma si incricca durante la lettura...
Il problema e' dovuto al fatto che questo codice e' sbagliato
<CODE>
  Tree a,*p;
  PNodeStack stack;
  int index;
..
  Push(&stack,p);
</CODE>
la prima volta che viene chiamata la funzione ReadTree() nello stack viene
messo un PNodeStack che punta Dio solo sa dove. Quando vai a svuotare lo
stack il Boom! non e' una eventualita' da escludere.
Evito commenti sul resto del codice :-(
C:\>iao Angelo
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it