corso ASD
Corso di Algoritmi e Strutture Dati a.a. 2013/2014

Esercizio 05

Si consideri la seguente implementazione di albero n-ario, commentata a lezione. Successivamente si esegua l'esercizio richiesto. Dopo aver testato adeguatamente la struttura, ed aver realizzato tutti i punti richiesti, inviare all'indirizzo paolo.buono@uniba.it l'esercitazione, in una cartella compressa in formato zip. Il file deve essere chiamato: "[ASDBR1314] esercizio05 - cognome.zip" e deve contenere solo file .h, .cpp, e il file di progetto. Scadenza dell'invio dell'esercitazione: 23.59 di domenica 1 dicembre.

//  main.cpp

#include <iostream>
 #include "alberon.h"
 #include "visitealberon.h"
int main(int argc, const char * argv[]){
    NodoN * n;
    NodoN nodo;
    AlberoN alberello;
    alberello.insRadice(1);
    n=alberello.radice();
    alberello.insPrimoFiglio(2, n);
    n=alberello.primoFiglio(n);
    nodo.scriviInfo(3);
    //alberello.insFratelloSucc(nodo, n);
     alberello.insFratelloSucc(3, n);
    alberello.insPrimoFiglio(4, n);
    n=alberello.primoFiglio(n);
    alberello.insPrimoFiglio(5, n);
    n=alberello.radice();
    alberello.insPrimoFiglio(6, n);
    n=alberello.primoFiglio(alberello.radice());
    n=alberello.succFratello(n);
    alberello.cancSottoalbero(n);
    
    previsita(alberello.radice(), alberello);
    return 0;
}
//  alberon.h

#ifndef proveASD_alberon_h
#define proveASD_alberon_h

#include "nodon.h"

using namespace std;

class AlberoN {
public:
    void creaAlbero();
    bool alberoVuoto();
    void insRadice(tipoelem);
    NodoN* radice();
    NodoN* padre(NodoN*);
    bool foglia(NodoN*);
    NodoN* primoFiglio(NodoN*);
    NodoN* succFratello(NodoN*);
    bool ultimoFratello(NodoN*);
    void insPrimoFiglio(tipoelem, NodoN*);//insPrimoSottoalbero
     void insFratelloSucc(tipoelem, NodoN*); //insSottoalbero
    void cancSottoalbero(NodoN*);
    tipoelem leggiNodo(NodoN*);
    void scriviNodo(tipoelem, NodoN*);

    AlberoN();
    ~AlberoN();
private:
    NodoN* alberon;
};

#endif
//  alberon.cpp
#include <assert.h>
#include "AlberoN.h"

AlberoN::AlberoN() {
        creaAlbero();
}
AlberoN::~AlberoN() {}

void AlberoN::creaAlbero() {
        alberon = NULL;//verificare se vuoto
}

bool AlberoN::alberoVuoto() {
        return alberon == NULL;
}

void AlberoN::insRadice(tipoelem ele) {
        alberon = new NodoN;
        scriviNodo(ele, alberon);
        alberon->scriviPrimofg(NULL);
        alberon->scriviSuccfr(NULL);
        alberon->scriviPadre(NULL);
}

NodoN* AlberoN::radice() {
        return alberon;
}

NodoN* AlberoN::padre(NodoN* u) {
        if (!alberoVuoto() && u->leggiPadre() != NULL)
                return u->leggiPadre();
        else
                return NULL;
}

bool AlberoN::foglia(NodoN* u) {
        assert(!alberoVuoto());
        return (u->leggiPrimofg() == NULL);
}

NodoN* AlberoN::primoFiglio(NodoN* u) {
        assert(!alberoVuoto() && !foglia(u));
    return u->leggiPrimofg();
}

bool AlberoN::ultimoFratello(NodoN* u) {
        assert(!alberoVuoto());
        return (u->leggiSuccfr() == NULL);
}

NodoN* AlberoN::succFratello(NodoN* u) {
        assert(!alberoVuoto() && !ultimoFratello(u));
    return u->leggiSuccfr();
}

void AlberoN::insPrimoFiglio(tipoelem ele, NodoN* u) {
        if (!alberoVuoto()){
        NodoN* nuovo = new NodoN;
        scriviNodo(ele, nuovo);
                nuovo->scriviPrimofg(NULL);
                nuovo->scriviPadre(u);
        if(foglia(u)) {
            nuovo->scriviSuccfr(NULL);
        }else{
            nuovo->scriviSuccfr(u->leggiPrimofg());
        }
        u->scriviPrimofg(nuovo);
    }
}

void AlberoN::insFratelloSucc(tipoelem ele, NodoN* u) {
        if (!alberoVuoto() && u != radice()) {
                NodoN* nuovo = new NodoN;
                scriviNodo(ele, nuovo);
                nuovo->scriviPadre(u->leggiPadre());
                nuovo->scriviPrimofg(NULL);
        if(ultimoFratello(u)){
            nuovo->scriviSuccfr(NULL);
        }else{
            nuovo->scriviSuccfr(u->leggiSuccfr());
        }
        u->scriviSuccfr(nuovo);
        }
}

tipoelem AlberoN::leggiNodo(NodoN* u) {
        return u->leggiInfo();
}

void AlberoN::scriviNodo(tipoelem ele, NodoN* u) {
        u->scriviInfo(ele);
}

void AlberoN::cancSottoalbero(NodoN* u) {
    NodoN* aux;
    if (foglia(u))      {
        aux=padre(u);
        if (primoFiglio(aux)==u){
            aux->scriviPrimofg(u->leggiSuccfr());
        }else {
            aux=aux->leggiPrimofg();
            while (aux->leggiSuccfr()!=u) aux=aux->leggiSuccfr();
            aux->scriviSuccfr(aux->leggiSuccfr()->leggiSuccfr());
        }
            delete u;
    }else{
        aux=primoFiglio(u);
        while (!ultimoFratello(aux)) {
            aux=succFratello(aux);
            cancSottoalbero(aux);
        }
        cancSottoalbero(primoFiglio(u));
        cancSottoalbero(u);
    }
}
//  nodon.h

#ifndef proveASD_nodon_h
#define proveASD_nodon_h

#include <cstdlib>
#include <iostream>
#include "tipodato.h"

using namespace std;

class NodoN {
public:
        tipoelem leggiInfo();
        NodoN* leggiPrimofg();
        NodoN* leggiSuccfr();
        NodoN* leggiPadre();
        void scriviInfo(tipoelem);
        void scriviPrimofg(NodoN*);
        void scriviSuccfr(NodoN*);
        void scriviPadre(NodoN*);
    
        NodoN();
        ~NodoN();
        
private:
        tipoelem info;
        NodoN* primofg;
        NodoN* succfr;
        NodoN* padre;
};

#endif
//  nodon.cpp

#include "nodon.h"

NodoN::NodoN() {}
NodoN::~NodoN() {}

tipoelem NodoN::leggiInfo() {
        return info;
}

NodoN* NodoN::leggiSuccfr() {
        return succfr;
}

NodoN* NodoN::leggiPrimofg() {
        return primofg;
}

NodoN* NodoN::leggiPadre() {
        return padre;
}

void NodoN::scriviInfo(tipoelem i) {
        info = i;
}

void NodoN::scriviPrimofg(NodoN* fg) {
        primofg = fg;
}

void NodoN::scriviSuccfr(NodoN* fr) {
        succfr = fr;
}

void NodoN::scriviPadre(NodoN* p) {
        padre = p;
}
//  tipodato.h

#ifndef alberon_tipodato_h
 #define alberon_tipodato_h
 #include "computer.h"
typedef int tipoelem;

#endif
//  computer.h

#ifndef alberon_Computer_h
 #define alberon_Computer_h
 #include <string>
 using namespace std;

class Computer{
public:
    Computer();
    string processore();
    void processore(string);
    
private:
    string _processore;
};

#endif
//  computer.cpp

#include "computer.h"
string Computer::processore(){
    return _processore;
};

void Computer::processore(string processore){
    _processore=processore;
};
//  codaalberon.h

#ifndef CodaAlberoN_H
#define CodaAlberoN_H

const int MAXLUNG=100;

#include "nodon.h"


class CodaAN{
public:
    CodaAN();
    ~CodaAN();
    void creaCoda();
    bool codaVuota() const;
    NodoN * leggiCoda() const;
    void fuoriCoda();
    void inCoda (NodoN *);
private:
    NodoN * elementi[MAXLUNG];
    int testa;
    int lunghezza;
};

#endif //CodaAlberoN_H
//  codaalberon.cpp

#include <iostream>
#include <assert.h>
#include "codaalberon.h"

using namespace std;

CodaAN::CodaAN(){
    creaCoda();
}

CodaAN::~CodaAN() {};

void CodaAN::creaCoda(){
    testa=0;
    lunghezza=0;
}

bool CodaAN::codaVuota() const {
    return (lunghezza==0);
}

NodoN* CodaAN::leggiCoda() const {
    assert (!codaVuota());
    return elementi[testa];
}

void CodaAN::inCoda(NodoN* el){
    assert (testa<=MAXLUNG);
    elementi[(testa+lunghezza)%MAXLUNG]=el;
    lunghezza++;
}

void CodaAN::fuoriCoda() {
    assert (!codaVuota());
    testa=(testa+1)%MAXLUNG;
    lunghezza--;
}
//  visitealberon.h

#ifndef proveASD_visitealberon_h
#define proveASD_visitealberon_h

#include "nodon.h"
#include "alberon.h"

void previsita (NodoN *, AlberoN);
void postvisita(NodoN *, AlberoN);
void simmetrica(NodoN *, AlberoN);
void BFS(AlberoN);

#endif
//  visitealberon.cpp

#include "visitealberon.h"
#include "codaalberon.h"

void previsita (NodoN * u, AlberoN a){
    NodoN* temp;    
    if (u == a.radice()){
        cout << "RADICE: "<< a.leggiNodo(u)<< endl;
    }else{
        cout<<"  "<<a.leggiNodo(u) << "(" << a.leggiNodo(a.padre(u))<<")"<< endl;}
    
    if(!a.foglia(u))
    {
        temp = a.primoFiglio(u);
        while(!a.ultimoFratello(temp)){
            previsita (temp, a);
            temp = a.succFratello(temp);
        }
        previsita(temp,a);
    }
}

void postvisita(NodoN * u, AlberoN a){
    NodoN* temp;
        if(!a.alberoVuoto()){
        if (!a.foglia(u)){
            temp = a.primoFiglio(u);
            while(!a.ultimoFratello(temp)){
                postvisita(temp,a);
                temp = a.succFratello(temp);
            }
            postvisita(temp,a);
        }
        cout << a.leggiNodo(u) << " ";
    }
}

void simmetrica(NodoN * u, AlberoN a){//verificare
    NodoN* temp;
    if(!a.alberoVuoto()){
        if (a.foglia(u)){
            cout << a.leggiNodo(u) << " ";
        }else{
            temp = a.primoFiglio(u);
            simmetrica(temp,a);
            cout << a.leggiNodo(u) << " ";
            while(!a.ultimoFratello(temp)){
                temp = a.succFratello(temp);
                simmetrica(temp,a);
            }
        }
    }
}

void BFS(AlberoN r){//todo: verificare questo algoritmo
        if (!r.alberoVuoto()){
        tipoelem info;
        CodaAN tmp;
        NodoN* aux = new NodoN();
        
        info=r.leggiNodo(r.radice());
        cout << info << " ";
        
        if (!r.foglia(r.radice())){
            tmp.inCoda(r.radice());
            while (!tmp.codaVuota()){
                aux = tmp.leggiCoda();
                                tmp.fuoriCoda();
                aux = r.primoFiglio(aux);
                do {
                    info = r.leggiNodo(aux);
                    cout << info << " ";
                    
                    if (!r.foglia(aux))
                        tmp.inCoda(aux);
                    aux = r.succFratello(aux);
                }while(!r.ultimoFratello(aux));
            }
        }
    }
}

Si realizzino i seguenti punti, che rappresentano una gerarchia di computer in un'azienda:

  1. Modificare l'albero in modo che al posto degli interi gestisca computer e rappresenti una gerarchia di computer che gestiscono altri computer;
  2. Modificare classe Computer in modo che contenga marca, modello, capacità dell'HD (intero che esprime GB) e nome della persona che gestisce quel computer;
  3. Creazione funzione caricamento dell'albero che inserisca 10 diversi computer;

Si realizzino le seguenti funzioni / metodi:

  1. void stampa(), che stampa a video la gerarchia di computer;
  2. void shift(NodoN, NodoN), che effettua lo scambio del contenuto di due nodi dell'albero di computer;
  3. int calcoloCapacitàGerarchiaComputer(AlberoN), che restituisce la capacità dotale della gerarchia di computer, data dalla somma delle capacità dei singoli HD dei vari computer.
corso ASD