[C] Albero binario di ricerca

[starxy]

Ciao a tutti. Sono nuovo del forum, e avrei gentilmente bisogno di una mano per un progetto dell'università... Non sono ancora molto pratico del C, quindi vi chiedo una mano.

Allora, il codice qui sotto rappresenta un albero binario di ricerca: ho definito una struttura nodo_ric (i nodi sono identificati da nomi, quindi stringhe), e poi delle funzioni (creazione di un nodo singolo, ricerca, e insermineto mantenendo l'ordine). Lo scopo del main è puramente di test: chiede l'inserimento di cinque nomi, dopo ognuno dei quali stampa "PRIMO" se è il primo nodo creato, "OK" se è stato fatto correttamente l'inserimento del nuovo nodo e "Già presente" se il nome inserito fa già parte dell'albero. Il primo nome inserito stampa sempre "PRIMO" correttamente, ma dal secondo nome stampa sempre "Già inserito". L'errore è nel while della funzione di ricerca: le due stringhe tra cui fa il confronto sono sempre entrambe l'ultima stringa inserita dall'utente, e non viene passati i nodi precedenti dell'albero. Dove sbaglio?
Poi un'altra domanda molto più stupida: perchè se inserisco stringhe troppo lunghe (es. 20 caratteri) mi dà errore di segmentazione?

Di seguito il codice, grazie mille in anticipo a chiunque possa aiutarmi.

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

typedef char *Stringa;


struct nodo_ric{
	Stringa nome;
	struct nodo_ric *l, *r;
};

typedef struct nodo_ric *Nodo_ric;



Nodo_ric bit_new(Stringa nome_ric){
	
	Nodo_ric new = malloc(sizeof(struct nodo_ric));
	
	if(new == NULL){
		printf("\nMemoria Esaurita\n");
		exit(-1);
	}
	
	new -> l = new -> r = NULL;
	new -> nome = nome_ric;
	return new;
}







int cerca_ric(Nodo_ric r, Stringa nome_ric, Nodo_ric *pf, Nodo_ric *p){
	
	int res;
	*pf = NULL;
	*p = r;
	
	if(!r)	/** equivale a if(r == NULL) **/
		return -1;
	
	
	while(*p && (res = strcmp(nome_ric, (*p)->nome ) != 0)) {
		*pf = *p;
		if(res < 0)
		 	(*p) = (*p) -> l; 
		 else
		 	(*p) = (*p) -> r;
	}

	if(*p == NULL)	/** non ci sono nodi con chiave k **/
		return -1;
	
	return 0;
}


int inserisci_ric(Nodo_ric *r, Stringa nome_ric){
	Nodo_ric qf, q = *r, new = bit_new(nome_ric);
		
	if(q == NULL) {
		/** inserisco nell'albero vuoto **/
		*r = new;
		return 1;
	}

	if(cerca_ric(*r, nome_ric, &qf, &q) == 0) {
		 /** la chiave c'è già, non inserisco niente **/
		 return -1;
	}

	/** qf è il padre del nuovo nodo **/
	if(strcmp(nome_ric, qf->nome < 0))
		qf -> l = new;
	else
		qf -> r = new;	
	
	return 0;
}




int main(){
	
	
	Stringa nome_ric = malloc(sizeof(Stringa));
	Nodo_ric albero = NULL;
	
	int temp;
	
	
	
	printf("\nInserisci un nome: ");
	scanf("%s",nome_ric);
	temp = inserisci_ric(&albero,nome_ric);
	if(temp == 0)
		printf("OK");
	if(temp == -1)
		printf("Già presente");
	if(temp == 1)
		printf("PRIMO");
	
	
	
	printf("\nInserisci un nome: ");
	scanf("%s",nome_ric);
	temp = inserisci_ric(&albero,nome_ric);
	if(temp == 0)
		printf("OK");
	if(temp == -1)
		printf("Già presente");
	if(temp == 1)
		printf("PRIMO");
	
	
	printf("\nInserisci un nome: ");
	scanf("%s",nome_ric);
	temp = inserisci_ric(&albero,nome_ric);
	if(temp == 0)
		printf("OK");
	if(temp == -1)
		printf("Già presente");
	if(temp == 1)
		printf("PRIMO");
		
	printf("\nInserisci un nome: ");
	scanf("%s",nome_ric);
	temp = inserisci_ric(&albero,nome_ric);
	if(temp == 0)
		printf("OK");
	if(temp == -1)
		printf("Già presente");
	if(temp == 1)
		printf("PRIMO");
		
	printf("\nInserisci un nome: ");
	scanf("%s",nome_ric);
	temp = inserisci_ric(&albero,nome_ric);
	if(temp == 0)
		printf("OK");
	if(temp == -1)
		printf("Già presente");
	if(temp == 1)
		printf("PRIMO");
	
	
	
	
	return 0;
	
}

[SancheZ]

Ciao, direi che hai almeno un paio di problemi:

1) in main(): l'istruzione Stringa nome_ric = malloc(sizeof(Stringa)); alloca sempre 4 bytes, che è la dimensione di un qualsiasi puntatore (compreso quello a stringa), quindi se riesci a scrivere fino a 20 caratteri è grasso che cola, visto che lo stack è già bello incasinato a partire quinto
In pratica con la malloc() devi allocare tanto spazio per quanto è richiesto dalla dimensione massima che hai stabilito per la tua stringa.

2) in bit_new(): con l'istruzione new -> nome = nome_ric; l'unica cosa che ottieni è una copia del puntatore, non della tua stringa. A causa di questo, il puntatore new->nome viene sempre inizializzato con l'indirizzo di memoria che contiene il termine che ho appena digitato, per cui l'algoritmo di ricerca dirà sempre "Già inserito" (di fatto confronterà sempre una stringa con sé stessa, fatta eccezione per il primo passaggio in cui l'albero e vuoto e non viene eseguito alcun controllo!). Per risolvere, l'istruzione deve diventare: new -> nome = malloc(MAX_STRING_SIZE); per allocare lo spazio necessario seguita da strcpy() (o strncpy()) per copiare la stringa dal buffer di input allo spazio riservato nell'albero.

Stefano.

[ramy89]

Originariamente inviato da SancheZ
Ciao, direi che hai almeno un paio di problemi:

1) in main(): l'istruzione Stringa nome_ric = malloc(sizeof(Stringa)); alloca sempre 4 bytes, che è la dimensione di un qualsiasi puntatore (compreso quello a stringa) [...]

Non è vero, la dimensione di un puntatore dipende dalla macchina, non è sempre 4 byte.

[oregon]

Originariamente inviato da ramy89
Non è vero, la dimensione di un puntatore dipende dalla macchina, non è sempre 4 byte.

Sì, ma non è questo il punto. Anche fosse 8 byte, il concetto espresso da SancheZ sarebbe sempre valido in quanto si parlava di "stringhe troppo lunghe (es. 20 caratteri)" ...

[ramy89]

Lo so, era una precisazione.

[oregon]

Originariamente inviato da ramy89
Lo so, era una precisazione.

Anche io so che lo sapevi ma quello che intendevo era che ritengo che è meglio "deporre le armi" ed evitare flame ...

[ramy89]

Finchè il discorso è tecnico e in topic non ci possono ne ci devono essere flame, lasciami partecipare alla discussione nel rispetto del regolamento.

[SancheZ]

In effetti ha ragione ramy89... sono troppo ancorato ai sistemi a 32bit