[problemi]Alberi binari in C

[jittox]

Devo scrivere una libreria che fa varie operazioni sugli alberi binari,ma quelle più complesse mi danno problemi di segmentation fault.

[code2=cpp]#include "abr_header_gc.h"

const char alfa[] = {'a','b','c','d','e','f','g','h','i','l','m','n','o','p','q','r','s','t','u','v','z'};

int readS(char *str){
int i=0;
char c;
while ( (c=getchar())!= '\n' ) {
str+=c;
i=i+1;
}
return i;
}

abr_node *insertElem(abr_node* root,char *str){ //Funziona

if (root==NULL) {
root = (abr_node *)malloc(sizeof(abr_node));
root->left = NULL;
root->right = NULL;
root->s=(char *)malloc(sizeof(char)*(strlen(str)+1));
strcpy(root->s,str);
return root;
}
else if( strcmp(str,root->s)<0 ){
root->left = insertElem(root->left,str);
return root;
}
else{
root->right = insertElem(root->right,str);
return root;
}
return root;
}

void stampaAbr(abr_node *root){ //Funziona
if(root!=NULL){
stampaAbr(root->left);
printf("%s\n",root->s);
stampaAbr(root->right);
}
}

void eliminaAbr(abr_node* root){ //Funziona
if(root->left!=NULL){
eliminaAbr(root->left);
}
if(root->right!=NULL){
eliminaAbr(root->right);
}
free(root);
}

abr_node* cancellaElem(abr_node *root,char *str){ //Funziona

if(strcmp(root->s,str)==0){
if(root->left==NULL){
return root->right;
}
else if(root->right==NULL){
return root->left;
}
else if(root->left==NULL&&root->right==NULL){
return NULL;
}
else{
abr_node *minimum;
minimum=root->right;
while(minimum->left!=NULL){
minimum=root->left;
}
minimum->left=root->left;
return root->right;
}
}

if(root->left!=NULL){
root->left = cancellaElem(root->left,str);
}
if(root->right!=NULL){
root->right= cancellaElem(root->right,str);
}
return root;
}

void cancellaConCondizione(abr_node *root,int p_o_d,char *a,char *b){
//dovrebbe cancellare dall'albero tutte le stringhe che hanno lunghezza pari o dispari
//e sono comprese tra le stringhe a e b e ogni volta mi da errore di segmentation fault, o
//rimane l'albero invariato.

}


void abrCasuale(abr_node *root,int n){
//funziona solo se io ho già inserito un altro elemento,ma se l'albero è null non funziona,anche se io uso sempre
//insertElem sempre nello stesso modo
int i,j;
char *str=(char *)malloc(sizeof(char)*10);
for(i=0;i<n;i++){
for(j=0;j<10;j++){
str[j]=alfa[rand()%strlen(alfa)];
}
root = insertElem(root,str);
}
}

void dupAbr(abr_node *root1,BTree *t2){ //Funziona
if(root1!=NULL){
t2->root = insertElem(t2->root,root1->s);
}
if(root1->left!=NULL){
dupAbr(root1->left,t2);
}
if(root1->right!=NULL){
dupAbr(root1->right,t2);
}
}

int abrCmp(abr_node *root1,abr_node *root2,int i){ //Funziona
if((root1!=NULL && root2!=NULL) || (root1!=NULL || root2!=NULL)){
if(strcmp(root1->s,root2->s)!=0){
i=1;
printf("sono diversi");
return i;
}
}
if(root1->left!=NULL){
return abrCmp(root1->left,root2->left,0);
}
if(root1->right!=NULL){
return abrCmp(root1->right,root2->right,0);
}
return 0;
}


void vectAbr(abr_node *root,char **a,int n,int *riemp){ //Funziona

if(root!=NULL){

vectAbr(root->left,a,n+1,riemp);
a[n]=(char *)malloc(sizeof(char)*strlen(root->s));
*riemp = *riemp + 1;
strcpy(a[n],root->s);
vectAbr(root->right,a,n+1,riemp);
}
}

void abrBilanciato(abr_node *nuovo,char **a,int p,int q,int riemp){
//Con l'array che ho creato precedentemente con la funzione sopra
//a ogni ricorsione inserisco l'elemento n/2, e passo i parametri cambiati in modo che
// p e q rappresentino gli estremi e io prendo sempre q-p/2,ma non funziona.
if(q-p==1){
nuovo = insertElem(nuovo,a[q-p]);
}
else{
nuovo = insertElem(nuovo,a[(q-p)/2]);
abrBilanciato(nuovo->left,a,p,q/2,riemp-1);
abrBilanciato(nuovo->right,a,(q-p)/2,q,riemp-1);
}
}[/code2]

Se mi potete dire dove sbaglio, perchè le funzioni semplici funzionano tutte, sopratutto quelle di lettura, mentre tutte queste sono di modifica dell'albero e ho pensato che magari sbaglio a fare qualcosa.

[jittox]

abrCasuale ho risolto cambiando il tipo di ritorno:

Codice: Seleziona tutto

abr_node *abrCasuale(abr_node *root,int n){
	int i,j;
	char *str=(char *)malloc(sizeof(char)*10);
	for(i=0;i<n;i++){
		for(j=0;j<10;j++){
			str[j]=alfa[rand()%strlen(alfa)];
		}
		root = insertElem(root,str);
	}
	return root;
} 

[jittox]

up: Dovete pensare che stavo da ieri mattina su sta libreria, e solo ora sto riuscendo ad andare avanti, ho fatto anche eliminaConCondizione:

Codice: Seleziona tutto

abr_node* cancellaConCondizione(abr_node *root,int p_o_d,char *a,char *b){
	if(root!=NULL){
		root->left = cancellaConCondizione(root->left,p_o_d,a,b);
		root->right = cancellaConCondizione(root->right,p_o_d,a,b);
		if(strlen(root->s)%2==p_o_d && strcmp(root->s,a)>0 && strcmp(root->s,b)<0){
			root = cancellaElem(root,root->s);
		}
	}
	return root;
}

[ienaplinsky]

Codice: Seleziona tutto

void abrBilanciato(abr_node *nuovo,char **a,int p,int q,int riemp){ 
 //Con l'array che ho creato precedentemente con la funzione sopra
  //a ogni ricorsione inserisco l'elemento n/2, e passo i parametri cambiati in modo   che       
  // p e q rappresentino gli estremi e io prendo sempre q-p/2,ma non funziona.
 if(q-p==1){
     nuovo = insertElem(nuovo,a[q-p]);
   }
   else{
       nuovo = insertElem(nuovo,a[(q-p)/2]);
       abrBilanciato(nuovo->left,a,p,q/2,riemp-1);
      abrBilanciato(nuovo->right,a,(q-p)/2,q,riemp-1);
 }
}

anche qui o ti fai ritornare l' albero dalla funzione oppure devi passare l' indirizzo di nuovo,
poi ci sono dei piccoli errori allora se vuoi ritornare l' albero dovresti fare una cosa del genere

Codice: Seleziona tutto

abr_node* abrBilanciato(char **array, int first, int last) {
  if(first > last) {
    return NULL;
  }
  int mid = (last + first) / 2;
  abr_node *root = creaNodo(array[mid]); // funzione che ti ritorna un nodo
  root->sx = abrBilanciato(array, first, mid - 1);
  root->dx = abrBilanciato(array, mid + 1, last);
  return root;
}
abr_node *creaNodo(char *stringa) {
  abr_node *nuovo = malloc(sizeof(abr_node));
  nuovo->key = malloc((strlen(stringa) + 1) * sizeof(char));
  strcpy(nuovo->key, stringa);
  nuovo->left = nuovo->right = NULL;
  return nuovo;
}

[ienaplinsky]

Codice: Seleziona tutto

void abrBilanciato_(abr_node **root, char **array, int first, int last) {
  if(first <= last) {
    int mid = (last + first) / 2;
    *root = creaNodo(array[mid]);
    abrBilanciato_(&(*root)->sx, array, first, mid -1);
    abrBilanciato_(&(*root)->dx, array, mid +1, last);
  }
}

giusto per completezza ti lascio anche l' altra versione, quella in cui devi passare l' indirizzo del puntatore

[jittox]

Grazie mille!!

[jittox]

void vectAbr(abr_node *root,char **a,int n,int *riemp){ //Funziona

if(root!=NULL){

vectAbr(root->left,a,n+1,riemp);
a[n]=(char *)malloc(sizeof(char)*strlen(root->s));
*riemp = *riemp + 1;
strcpy(a[n],root->s);
vectAbr(root->right,a,n+1,riemp);
}
}

Non si capisce perchè,ma questa funziona non funziona come dovrebbe, infatti il primo elemento è ricoperto con segni indecifrabili, e gli altri sono apposto. Stiamo da 2 giorni io e altri ragazzi che non siamo in grado di aggiustarlo.

[ienaplinsky]

Codice: Seleziona tutto

void vetAbr(abr_node *root, char ***array, int *num) {
  if(root != NULL) {
    vetAbr(root->sx, array, num);
    *num += 1;
    *array = realloc(*array, sizeof(char *) * (*num));
    (*array)[(*num) - 1] = malloc(sizeof(char) * (strlen(root->key) + 1));
    strcpy((*array)[(*num) - 1] , root->key);
    vetAbr(root->dx, array, num);
  }
}

anche qui non passate l' indirizzo dell' array, quindi o passate l' indirizzo di' array oppure dovete allocare la memoria per array nel main e nella funzione per ogni stringa allocate memoria, e poi fate la realloc in base a quante stringhe avete inserito,
nota: nella funzione chiamante **array deve essere = NULL
e la chiamata

Codice: Seleziona tutto

vetAbr(root, &array, &num)

[jittox]

A scopo informativo posto anche il codice per salvare gli elementi di un albero in un array,con il valore di ritorno,non con il terzo puntatore,che al professore non sarebbe piaciuto.

[code2=cpp]char **vetAbr(abr_node *root, char **array, int *num) {
if(root != NULL) {
array = vetAbr(root->left, array, num);
*num += 1;
array = (char**)realloc(array, sizeof(char*) * (*num));
array[(*num)-1] = malloc(sizeof(char) * (strlen(root->s) + 1));
strcpy(array[(*num)-1],root->s);
array = vetAbr(root->right, array,num);
}
return array;
}[/code2]

[jittox]

Ho un nuovo problema, dopo aver fatto la libreria sugli alberi binari con funzioni tutte ricorsive,adesso dovrei fare le stesse funzioni ricorsive, ma non riesco a finire il pop dello stack, in pratica i cambiamenti che faccio su ST(implementato su liste):
-salvare l'elemento in testa
-far puntare lo stack al prossimo elemento
-diminuire di 1 la grandezza dello stack
-ritornare il valore.

non permangono, quindi chiamando:

Codice: Seleziona tutto

        printf("%d\n",isEmpty(st));
	printf("%s\n",top(st)->s);
	pop(st);
	printf("%d\n",isEmpty(st));
        printf("%s\n",top(st)->s);

ho 2 volte gli stessi valori.

[code2=cpp]abr_node *pop(Stack *ST){
if(!isEmpty(ST)){
abr_node *tmp;
tmp = top(ST);
ST->top = ST->top->next;
ST->size = ST->size - 1;
return tmp;
}
}[/code2]

[ienaplinsky]

scusa ma che c' enrtrano i nodi di un abr con i nodi di una lisa'?

[jittox]

io ho implementato lo Stack con una lista di puntatori a nodi di albero.
Ogni elemento ha:
- il puntatore al nodo dell'albero
- il puntatore all'elemento successivo

[ienaplinsky]

ti dispiace postare la struttura e la funzione top?

[jittox]

[code2=cpp]//stack.c
#ifndef stack_H_INCLUDED
#define stack_H_INCLUDED

#include "abr_header_gc.h"

struct elem{
struct elem *next;
abr_node *root;
};

struct Stack{
struct elem *top;
int size;
};

typedef struct elem elem;
typedef struct Stack Stack;

elem *creaNodo(abr_node *node);
int isEmpty(Stack *ST);
Stack *initStack();
Stack *push(Stack *ST,abr_node *node);
abr_node *top(Stack *ST);
abr_node *pop(Stack *ST);

#endif // Stack_H_INCLUDED[/code2]

[code2=cpp]//stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "abr_header_gc.h"

elem *creaNodo(abr_node *root){
elem *nuovo = (elem *)malloc(sizeof(elem));
nuovo->next = NULL;
nuovo->root = root;
return nuovo;
}

int isEmpty(Stack *ST){
if(ST->size==0){
return 0;
}
else{
return ST->size;
}
return 1;
}

Stack *initStack(){
Stack *nuovo = (Stack *)malloc(sizeof(Stack));
nuovo->top = NULL;
nuovo->size = 0;
return nuovo;
}

Stack * push(Stack *ST,abr_node *root){
if(isEmpty(ST)){
ST->top = creaNodo(root);
ST->size++;
}
else{
elem *tmp;
tmp = ST->top;
ST->top = creaNodo(root);
ST->top->next = tmp;
ST->size++;
}
return ST;
}

abr_node* top(Stack *ST){
return ST->top->root;
}

abr_node *pop(Stack *ST){
if(!isEmpty(ST)){
abr_node *tmp;
tmp = top(ST);
ST->top = ST->top->next;
//ST->size = ST->size - 1;
return tmp;
}
}[/code2]

[ienaplinsky]

ho decommentato la riga che decrementa il size della pop a me funziona metto quello che ho cambiato

Codice: Seleziona tutto

abr_node *pop(Stack *ST){
  if(!isEmpty(ST)){
    abr_node *tmp;
    tmp = top(ST);
    ST->top = ST->top->next;
    ST->size--;
    return tmp;
  }
  return NULL; // la funzione deve sempre ritornare qualcosa
}

int isEmpty(Stack *ST){
  return ST->size == 0;
}

abr_node *pop(Stack *ST){
  if(!isEmpty(ST)){
    abr_node *tmp;
    tmp = top(ST);
    ST->top = ST->top->next;
    ST->size--; // perchè c'era il commento ?
    return tmp;
  }
  return NULL;
}

[ienaplinsky]

non so perchè ma non riesco ad editare il messaggio

comunque la logica di isEmpty era un pò incasinata
se la pila era vuota (size = 0) la funzione tornava 0 (in c = falso), altrimenti ritornava la dimensione, e il return alla fine non serve a niente dato che se non entri nel if sei nel else o viceversa

[jittox]

mo provo se funziona, il mio problema era che:
-inizialmente mi dava segmentation fault,
ma poi il pop veniva eseguito, ma non aveva effetto, in quanto top(st) era sempre uguale anche dopo un pop(st).

[jittox]

nooo!! adesso funziona, grazie!!!

[jittox]

Ma fai il programmatore di professione?

[ienaplinsky]

No ero uno studente come voi alle prese con il mitico massimo