PDA

Visualizza la versione completa : [C] Inserimento iterativo BST


gaten
20-04-2012, 19:41
Ragazzi st cercando di utilizzare questa funzione :



// Inserimento in un BST iterativo
NODO *BST_InsertIter(NODO *root, COMPARE Compare, void *value)
{
NODO *New_Node, *curr, *prev;
curr = root;

// ricerco la posizione
prev = NULL;

while ( curr != NULL )
{
// salvo il nodo precedente prima di scorrere con il corrente
prev = curr;

if ( Compare ( value, curr->info ) < 0 )
{
// vado verso sinistra
curr = curr->sx;
}
else
if ( Compare ( value, curr->info ) > 0 )
{
// vado verso destra
curr = curr->dx;
}
}

// creazione del nuovo nodo da inserire
New_Node=(NODO*)malloc(sizeof(NODO));
New_Node->sx = NULL;
New_Node->dx = NULL;
New_Node->info = value;

/* aggiornamento
* se il valore pi piccolo del nodo corrente che non ha pi figli(n destro n sinistro)
* aggiungo il nodo a sinistra altrimenti a destra
*/
if ( Compare ( value, curr->info ) < 0 )
prev->sx = New_Node;
else if ( Compare ( value, curr->info ) > 0 )
prev->dx = New_Node;

return root;
}


praticamente l'inserimento in un albero binario di ricerca utilizzando un metodo iterativo.

nel main ho:




char *stringa;
NODO *rootString;

printf("Inserisci la stringa da inserire:\n");
stringa = GetInput();
rootString = BST_InsertIter(rootString, &CompareString, stringa );



funzione GetInput


char *GetInput(void)
{
char* result=(char*)malloc(10*sizeof(char)),temp,length= 0,dim=10;
while( (temp=getchar())!=10)
{
length++;
if(dim<length)
{
dim+=10;
result=(char*)realloc(result,dim*sizeof(char));
}
result[length-1]=temp;
}
result[length]='\0';//aggiunge il terminatore stringa

return result;
}


Quando provo a inserire un elemento si blocca il programma eppure non riesco a capire il perch, qualcuno pu aiutarmi?
Grazie anticipatamente

oregon
20-04-2012, 19:42
NODO *rootString;

non inizializzato.

gaten
20-04-2012, 20:19
prima ho dimenticato di scrivere


NODO *rootString = NULL;


che comunque d problemi.

oregon
20-04-2012, 20:29
Cio ? Quali problemi ?

gaten
20-04-2012, 20:31
si blocca il programma con la classica scritta "programma.exe ha smesso di funzionare" (windows 7)

Scara95
20-04-2012, 20:42
Semplicemente per il fatto che alla fine del ciclo curr un puntatore NULL e quindi non puoi accedere ad un suo campo, in realt devi solo assegrare New_Node a curr ed il gioco fatto, non servono quei controlli perch curr gi il luogo giusto, prova a farti uno schema su carta per riflettere, potrei essermi sbagliato, ma credo sia per quello, buona fortuna ;)

gaten
20-04-2012, 21:13
Non che abbia capito molto da quello che hai scritto

Scara95
20-04-2012, 21:24
Alla fine del ciclo while curr = NULL
Poi tu cerchi di accedere ad un campo della struttura:
curr->info
Il puntatore NULL...

curr gi il luogo dove devi inserire l'oggetto, quindi ti basta sostituire l'if a fine funzione con
curr = New_Node;

Dovrebbe funzionare ;)

gaten
20-04-2012, 21:39
Perfetto ho sostituito tutto l'if alla fine con curr=New_Node. Adesso provo a stampare usando:


/*=======================================
* Vistita in Order iterativa
*======================================*/
void InOrderIter(NODO *root, STAMPAINFO Stampa)
{
STACK *pila;
NODO *curr = root;

while ( pila != NULL || curr != NULL )
{
if ( curr != NULL )
{
pila = push(pila, curr);
curr = curr->sx;
}
else
{
curr = (NODO*)top(pila);
pila = pop(pila);
Stampa(curr->info);
curr = curr->dx;
}
}
}


ed ho questo nel main:


InOrderIter(rootString, &StampString);


StampString mi serve per capire che tipo di info devo stampare nel caso di una stringa ho:


/*===================================
* Stampo una stringa
*==================================*/
void StampString(void *value)
{
printf("%s", *((char*)value));
printf(" ");
}


Nella stampa mi da lo stsso errore

Scara95
20-04-2012, 22:01
*((char*)value): c' un * in pi, dovrebbe essere:
(char*)value
In quanto in C/C++ le stringhe sono date da un indirizzo di memoria che punta al primo byte di un segmento di memoria sequenziale.
Con il tuo codice individui appunto questo byte che poi il primo carattere...
Prova a vedere se cos funziona, premetto che non ho controllato tutto il codice ma ho solo dato un'occhiata...

Loading