Implementazione albero binario

Von_Neuman_1

il 17 feb 2015, 12:02

11 risposte

Von_Neuman_1

Pochi posts

Iscritto da: nov, 2014

Messaggi:: 13

Implementazione albero binario

17 feb 2015, 12:09

Perchè lanciando il seguente codice:


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


typedef struct elem{
    struct elem* sx;
    struct elem* dx;
    int info;

}node;

typedef node* albero;

main() {
    albero root;
    root=(albero)malloc(sizeof(node));
    root->info = 50;
    root->sx=(albero)malloc(sizeof(node));
    root->sx->info=13;
    root->sx->sx=NULL;
    root->sx->dx = (albero)malloc(sizeof(node));
    root->dx->info = 75;
    root->dx->sx= (albero)malloc(sizeof(node));
    root->dx->dx = NULL;
    root->sx->dx->info = 38;
    printf("%d\n",root->sx->info);

}

Mi appare il seguente errore?
[img]
http://imageshack.com/a/img537/1668/AFwUAj.pn
[/img]

11 Risposte

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21791
Re: Implementazione albero binario
17 feb 2015, 12:20
Devi controllare che quello che usi sia allocato ...

Non è così, ad esempio, per

root->dx->info = 75;

perché

root->dx

non è allocato
V
Von_Neuman_1
Pochi posts
Iscritto da
nov, 2014
Messaggi:
13
Re: Implementazione albero binario
17 feb 2015, 12:51
Risolto!
Grazie mille!!

Von_Neuman_1

Pochi posts

Iscritto da: nov, 2014

Messaggi:: 13

Re: Implementazione albero binario

17 feb 2015, 18:15

Stesso problema precedente, però stavolta richiamando una banale funzione che dovrebbe calcolare l'altezza di un albero binario:


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


typedef struct elem{
    struct elem* sx;
    struct elem* dx;
    int info;

}node;

typedef node* albero;

int max(int a, int b){
    if (a > b) return a;
    else return b;
}

int altezza(albero T){

    if (T == NULL) return -1;
    else
        return 1 + max(altezza(T->sx),altezza(T->dx));

}


main() {
    albero root;
    root=(albero)malloc(sizeof(node));
    root->info = 50;
    root->sx=(albero)malloc(sizeof(node));
    root->sx->info=75;
    root->sx->sx=NULL;
    root->dx=(albero)malloc(sizeof(node));
    root->dx->info = 13;
    root->dx->sx= (albero)malloc(sizeof(node));
    root->dx->dx = NULL;
    root->dx->sx->info = 38;
    root->sx->dx=NULL;
    printf("%d\n",altezza(root));

}

Qualche consiglio??

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21791
Re: Implementazione albero binario
17 feb 2015, 19:00
Esegui il programma linea per linea con il debugger e individua la posizione dell'istruzione che genera l'errore.
V
Von_Neuman_1
Pochi posts
Iscritto da
nov, 2014
Messaggi:
13
Re: Implementazione albero binario
17 feb 2015, 23:21
Se gli do in input un albero vuoto ritorna senza problemi -1; il programma si arresta inspiegabilmente appena ho uno o più elementi...

oregon

Super Famoso

Iscritto da: nov, 2011

Messaggi:: 21791

Re: Implementazione albero binario

17 feb 2015, 23:57

Hai fatto quello che ti ho consigliato?

Comunque l'albero non è costruito correttamente ... deve essere


albero root;

root=(albero)malloc(sizeof(node));
root->info = 50;
	
root->sx=(albero)malloc(sizeof(node));
root->sx->info=75;
root->sx->sx=NULL;
root->sx->dx=NULL;

root->dx=(albero)malloc(sizeof(node));
root->dx->info = 13;
root->dx->dx = NULL;

root->dx->sx= (albero)malloc(sizeof(node));
root->dx->sx->info = 38;
root->dx->sx->sx = NULL;
root->dx->sx->dx = NULL;

printf("%d\n",altezza(root));

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6073
Re: Implementazione albero binario
18 feb 2015, 07:40
ASSIOMA: la malloc non azzera la memoria allocata.

Il che vuol dire che 'root->sx' o 'root->dx' potrebbero non essere a zero, e quindi potresti pensare che li c'e' qualcosa di allocato.

O lo fai tu a mano con una memset, o usi la calloc

Ed infatto, nel codice di @oregon, corettamente , e' stato fatto a mano.
V
Von_Neuman_1
Pochi posts
Iscritto da
nov, 2014
Messaggi:
13
Re: Implementazione albero binario
18 feb 2015, 10:33
Grazie mille ragazzi, impeccabili come sempre!

Von_Neuman_1

Pochi posts

Iscritto da: nov, 2014

Messaggi:: 13

Re: Implementazione albero binario

20 feb 2015, 12:57

Nuovo cruccio:
devo implementare un programma C che prenda in input un albero binario di caratteri e un carattere. Se tale carattere è una foglia il programma deve creare dinamicamente un stringa che contenga i caratteri che formano il percorso radice-carattere.
Esempio:
f
/ \
a v
/ \ \
s b r

invocando il metodo cammino(T,'b') deve restituire un stringa del tipo: "fab/0"
mentre se gli do: cammino(T,'v') deve restituire NULL
Ho scritto il seguente codice, ma ahimè mi imbatto nel maledetto segmentation fault


#include "libreria.h"

int esiste_foglia(albero T,char f) {
    if (T==NULL)
        return 0;
    else
        if((T->info==f)&&(T->left==NULL)&&(T->right==NULL))
            return 1;

        else return esiste_foglia(T->left,f)|| esiste_foglia(T->right,f);


}

int is_leaf(albero T,char c) {
    if (T==NULL)
        return 0;
    else if(T->left==NULL&&T->right==NULL&&T->info==c)
        return 1;
    return is_leaf(T->left,c) || is_leaf(T->right,c);
}


int profondita_foglia(albero T, char c) {
    if (T==NULL || !is_leaf(T,c) || T->info==c)
        return 0;
    else
        if(is_leaf(T->left,c))
            return 1+profondita_foglia(T->left,c);
        else
            if(is_leaf(T->right,c))
                return 1+profondita_foglia(T->right,c);


}

char* cammino(albero T,char c){

    int i;
    char* stringa=NULL;
    int p;
    if(T==NULL || !is_leaf(T,c))
        return 0;

    else
        p=profondita_foglia(T,c);
        stringa=calloc(p+2,sizeof(char));
        i=0;
        cammino_aux(T,stringa,c,&i);
        return stringa;

}




void cammino_aux(albero T,char* s,char c,int* i) {


    if(T->info==c) {
        s[*i]=c;
        *i=*i+1;
        s[*i]='\0';
    }
    else
        if (is_leaf(T->left,c)){
            s[*i]=T->info;
            *i=*i+1;
            cammino_aux(T->left,s,c,*i);
        }
        else {
            if (is_leaf(T->right,c)){
                s[*i]=T->info;
                *i=*i+1;
                cammino_aux(T->right,s,c,*i);

            }
        }
}

Consigli? Suggerimenti? Insulti?

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21791
Re: Implementazione albero binario
20 feb 2015, 13:31
Nuovo cruccio nuovo thread...
V
Von_Neuman_1
Pochi posts
Iscritto da
nov, 2014
Messaggi:
13
Re: Implementazione albero binario
20 feb 2015, 15:47
Okappa!!

Devi accedere o registrarti per scrivere nel forum

11 risposte