Sfide intellettuali sulle strutture di dati

di
RayD
il
11 risposte
R
RayD
Pochi posts
Iscritto da
gen, 2014
Messaggi:
41

Sfide intellettuali sulle strutture di dati

Vorrei proporre una serie di test sulle strutture dati non banali ad esempio alberi e grafi dato che implementare in c è bello e utile a scopo didattico.. il primo giorno direi di rispondere solo se si è arrivati alla soluzione ed il giorno dopo magari postate le vostre soluzioni per dar modo anche agli altri di ragionarci. .. inizio col postarne uno io poi postateli anche voi interessati:
Dato un albero binario, a data la classica rappresentazione parentetica del tipo: albero vuoto uguale (), albero con solo la radice uguale a (r ()()) ecc.. forma generica (r sx dx)
Con r radice e sx e dx figli sinistro e destro scrivere una procedura che stampi sempre la forma parentetica però con una visita simmetrica (inorder) del tipo se vuoto (), solo radice (() r ()), forma generica (sx r dx)

11 Risposte

  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Sfide intellettuali sulle strutture di dati

    Perdonami ma non ho capito le stampe che dovrebbe fare. Potresti espilicitare più esempi, per favore?

    Ad esempio per quest'albero che cosa dovrebbe stampare? 
    
                                    5
                            3              8
                        1      2        0
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Chiamata su quest'albero deve stampare:

    ( (((()1()) 3 ((()2()))) 5 ((() 0 ()) 8 ()))

    un nodo foglia con valore 3 ad esempio è rappresentato in questo modo; (() 3 ())
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Sfide intellettuali sulle strutture di dati

    O la logica non l'ho ben compresa oppure l'output dovrebbe essere questo:

    ((((()1()))3((()2()))))5((((()0()))8())))

    Controlla per favore!
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Si esatto devo aver sbagliato qlche parentesi per aver postato da smartphone..
    comunque il concetto è che prendendo la tipica rappresentazione a parentesi... che è in preordine perche è (r sx dx)
    con r radice, sx sotto albero sx e dx destro, quindi mi occupo della radice e poi passo ai sotto alberi... la procedura in questione vuole stampare inorder ossia mi occupo del sotto albero sinistro stampo la radice e poi mi occupo del sotto albero destro sempre con caso base albero vuoto = ()
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Sfide intellettuali sulle strutture di dati

    Va bene! Una lieve modifica al codice standard della inorder.
    
void stampa(albero r){
     if(r==NULL)
        return;

     printf("((");
     stampa(r->sx);
     printf(")");
     print(radice);
     printf("(");
     stampa(r->dx);
     printf("))");
}
    Così dovrebbe funzionare!
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Si è funzionante
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Esercizio n°2:

    scrivere una funzione che prende in input un albero binario e ritorna il numero di nodi che hanno lo stesso valore del padre del padre,
    per semplicità usare una struttura con anche un riferimento al nodo padre, poi è possibile scrivere la stessa funzione con una struttura collegata solo in basso? (cioè solo con i riferimenti ai figli)
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Sfide intellettuali sulle strutture di dati

    Tanto per curiosità ma la sfida intellettuale, su questi esercizi qual è?
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Magari per te sono ultra banali pero penso sia utile per gli interessati iniziare da esercizi semplici per poi arrivare a sfide vere e proprie
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Sfide intellettuali sulle strutture di dati

    Allora apri un thread dal titolo: Esercizi sulle strutture dati

    Perchè altro non sono che esercizi, scolastici. O meglio esercizi sugli alberi binari, nulla di più!
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Sfide intellettuali sulle strutture di dati

    Si infatti per sfide intellettuali volere dire esercizi abbasta complicati ma comunque sempre didattici niente di piu
Devi accedere o registrarti per scrivere nel forum
11 risposte