HomeWork3 < Architetture2/MZ/AA16

Tags: view all tags

---+ Homework 3 - manipolazione di un albero binario

%RED%
__ATTENZIONE: HO AGGIUNTO IL COMANDO "V" CHE STAMPA IL VETTORE__
%FINE%

In un vettore è possibile rappresentare implicitamente un albero binario, definito ricorsivamente come segue:
   * si pone la radice all'indice *1*
   * i figli del nodo all'indice *X* si trovano agli indici *2X* e *2X+1*

*NOTA:* Assumiamo che tutti gli elementi vuoti dell'albero contengano il valore 0 (zero).

Esempio: il vettore *0 1 2 3 4 5 6 0 8 9 10 0 0 13 0 0 16* rappresenta l'albero
<verbatim>
                      1
                  /         \
            2                  3
         /     \              /
      4        5         6
     /  \       /             \
   8    9  10             13
  /
16
</verbatim>

Per individuare un qualsiasi nodo nell'albero, oltre all'indice dell'elemento nel vettore, è possibile usare una successione di bit che indicano per ogni nodo se scendere verso il figlio sinistro (1) o il destro (0).

Leggiamo la successione di bit *da destra verso sinistra, ovvero dal bit meno significativo verso il più significativo.* Per evitare che gli zeri a sinistra valgano come una successione di mosse verso destra aggiungiamo un bit 1 che indica che siamo arrivati. Per cui, data un qualsiasi percorso indicato da una sequenza di bit *P*:
   * se *P==1*  siamo arrivati al nodo cercato
   * se *P>1* dobbiamo ancora scendere
      * il bit meno significativo di P indica se dobbiamo muoverci sul sottoalbero sinistro (1) o destro (0) del nodo in cui siamo
      * tolto il meno significativo, gli altri bit di *P* indicano come muoversi nel sottoalbero scelto

Quindi ad esempio:
   * *1=1* indica la radice (che contiene il valore 1)
   * *3=11* indica il suo figlio sinistro (che contiene il valore 2)
   * *2=10* indica il suo figlio destro (che contiene il valore 3)
   * *7=111* indica il figlio sinistro di *11* (che contiene il valore 4)
   * *5=101* indica il figlio destro di *11* (che contiene il valore 5)
   * *6=110* indica il figlio sinistro di *10* (che contiene il valore 6)
   * *4=100* indica il figlio destro di *10* (che è vuoto)
   * *12=1010* indica i 3 movimenti: destra, sinistra, destra, ovvero il nodo *13* nell'esempio precedente
   * *13=1011* indica i 3 movimenti: sinistra, sinistra, destra, ovvero il nodo *9* nell'esempio precedente

Realizzate il programma che:
   * alloca staticamente un vettore di almeno 1000 word che rappresenta un albero binario vuoto (contiene tutti 0)
   * legge una successione di comandi (formati da una lettera su una riga separata), seguiti se necessario da parametri sulle righe successive:
      * *Q*: (quit) esce dal programma
      * *P*: (print) stampa l'albero in *postordine* seguito da accapo, ovvero:
         * se la radice è zero non stampa nulla
         * altrimenti:
            * ricorsivamente, stampa il sottoalbero del figlio sinistro
            * ricorsivamente, stampa il sottoalbero del figlio destro
            * stampa la radice seguita da spazio
      * *A*: (add) aggiunge un nodo nella posizione indicata, argomenti:
         * *percorso*: numero intero che contiene la sequenza di bit come descritto sopra. *INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)*
         * *valore*: numero intero diverso da zero da inserire nel nodo individuato (assumete che nei test sia sempre diverso da 0)
      * *D*: (delete) elimina (azzera) un nodo nell'albero. Argomenti:
         * *percorso*: numero intero che contiene la sequenza di bit come descritto sopra. *INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)*
      * *C*: (copy) copia un sottoalbero da una posizione ad un'altra. Argomenti:
         * *percorso di partenza*: numero intero che contiene la sequenza di bit come descritto sopra. *INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)*
         * *percorso di arrivo*: numero intero che contiene la sequenza di bit come descritto sopra. *INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)*
         * *NOTA: POTETE ASSUMERE CHE NEI TEST I DUE PERCORSI INDICHERANNO SEMPRE SOTTOALBERI DISGIUNTI* (ovvero una sequenza di mosse non è il prefisso dell'altra)
         %RED%
         * *NOTA: la copia non deve mai copiare eventuali nodi vuoti (con valore 0)* 
      * *V*: (vettore) stampa su una riga seguita da accapo tutti i 1000 elementi del vettore, separati da spazio
      %FINE%


---+++ Esempio
La sequenza di comandi che ricrea l'albero precedente (commentata)
<verbatim>
A   # add
1   # alla radice
1   # il valore 1
A   # add
3   # 11=al suo figlio sinistro
2   # il valore 2
A   # add
2   # 10=al suo figlio destro
3   # il valore 3
A   # add
7   # 111=al figlio sinistro di 11
4   # il valore 4
A   # add
5   # 101=al figlio destro di 11
5   # il valore 5
A   # add
6   # 110=al figlio sinistro di 10
6   # il valore 6
A   # add
15  # 1111=al figlio sinistro di 111
8   # il valore 8
A   # add
11  # 1011=al figlio destro di 111
9   # il valore 9
A   # add
13  # 1101=al figlio sinistro di 110
10  # il valore 10
A   # add
10  # 1010=al figlio destro di 101
13  # il valore 13
A   # add
31  # 11111=al figlio sinistro di 1111
16  # il valore 16
P   # stampa l'albero in postordine su una riga
V   # stampa il vettore su una riga
Q   # esce dal programma
</verbatim>
Stamperà i valori
<verbatim>
16 8 9 4 10 5 2 13 6 3 1
0 1 2 3 4 5 6 0 8 9 10 0 0 13 0 0 16 0 0 0 0 0 ..... (TANTI ALTRI 0 FINO A 1000 ELEMENTI)
</verbatim>


---+++ Consegna entro lunedì 8 maggio ore 24

Per consegnare usate la [[http://twiki.di.uniroma1.it/~andrea/consegna-HW-2017.html][pagina di consegna]].

Trovate alcuni esempi di test nella [[%ATTACHURL%][pagina apposita]].

Per provare gli esempi potete, da riga di comando, usare la redirezione dei file per fornire il file di input che trovate nella pagina dei test:
   * java -jar Mars4_5.jar me nc sm ic vostrofile.asm &lt; test.in &gt; test.out
e poi confrontare il file prodotto (test.out) con quello atteso, che trovate nella pagina dei test