Archives

by Andrea

Alberi binari


Notice: wpdb::escape è deprecata dalla versione 3.6.0! Utilizzare al suo posto wpdb::prepare() or esc_sql(). in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-includes/functions.php on line 3893

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 113

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 114

Una delle strutture fondamentali di tutta la programmazione è l’albero. Esiste un particolare tipo di albero, detto binario, che per le sue particolari proprietà si presta molto bene ad alcuni tipi di operazioni, quali l’analisi di espressioni matematiche o la ricerca dicotomica.
Particolari tipi di alberi binari sono utilizzati come nuovi tipi di strutture dati, particolarmente ottimizzati per operazioni di ricerca o ordinamento: è il caso degli heap, degli alberi di ricerca e così via.
In questo fascicolo analizzeremo tutti gli algoritmi basilari per la gestione di un albero binario, partendo dalle definizioni e ragionando su ogni algoritmo.
Il linguaggio scelto per la stesura dei programmi è il C++, anche se in realtà saranno utilizzati concetti del tutto compatibili con il C. E’ da sottolineare, tuttavia, che il codice è compilabile in ANSI C++, per la compilazione in C saranno necessarie alcune modifiche. Quindi quando vedete scritto [C/C++] non significa che il codice è compilabile in C, ma solo che la sintassi utilizzata non prevede elementi proprietari del C++, quali classi, template, reference e così via.
Naturalmente questo fascicolo è dedicato esclusivamente alla parte relativa all’albero binario come struttura dati, quindi tutti i discorsi relativi alla sintassi del linguaggio adottato sono dati per scontati. In particolare, è bene avere buona padronanza delle strutture, dei puntatori e delle funzioni ricorsive, anche se quest’ultimo punto è presente una piccola digressione.

Sommario

  1. Teoria degli alberi binari
  2. Implementazione di un albero binario
  3. Teoria della ricorsione
  4. Algoritmi di base

Documenti

by Andrea

Progetto e realizzazione di un componente per la visualizzazione e valutazione di Abstract Syntax Tree


Notice: wpdb::escape è deprecata dalla versione 3.6.0! Utilizzare al suo posto wpdb::prepare() or esc_sql(). in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-includes/functions.php on line 3893

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 113

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 114

Notice: wpdb::escape è deprecata dalla versione 3.6.0! Utilizzare al suo posto wpdb::prepare() or esc_sql(). in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-includes/functions.php on line 3893

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 113

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 114

Questo documento è stata la mia tesi di laurea in Ingegneria Informatica, nel corso triennale. E’ stata realizzata nell’ambito del corso di Ingegneria del software.

L’obiettivo di questa tesi è la realizzazione di un componente software per la visualizzazione e l’esecuzione di Expression Tree. Un Expression Tree è la specifica utilizzata da .NET per descrivere gli Abstract Syntax Tree, ossia strutture dati in grado di modellare codice compilabile e, quindi, eseguibile.

La prima parte consiste nell’analisi della struttura di un albero di espressione, nelle sue componenti principali e nei tipi di nodo più utilizzati, nonché nello studio delle classi che ne permettono la visita. Il modello di riferimento è quello delle Expression Tree versione 2 del Framework .NET 4.0. In questa versione, rispetto alla precedente (comunque compatibile), è possibile rappresentare un numero molto maggiore di nodi e, quindi, di costrutti sintattici.

Il passaggio immediatamente successivo consiste nello studio e realizzazione della parte esecutiva di una espressione: per prima cosa è stato scelto un sottoinsieme, tra tutte le possibili espressioni, per cui fornire un modulo di compilazione ed esecuzione; si è proceduto poi con l’analisi dei requisiti di compilabilità di una espressione, alla realizzazione del modulo per la raccolta dei dati di input, a quello per la compilazione e generazione del risultato e a quello per la visualizzazione dello stesso.

La seconda parte consiste nella creazione di un controllo utente per la rappresentazione dell’albero e la visualizzazione di tutte le proprietà specifiche di ogni singolo nodo. Per realizzare questa parte è stata utilizzata la tecnologia Windows Presentation Foundation (WPF), in parte integrata con controlli Windows Form, che consente una grossa flessibilità nella progettazione grafica dell’interfaccia utente. Per lo sviluppo, sono state utilizzate tecniche quali stili, data template, trigger e data binding.

Terminato lo sviluppo del componente software nella sua globalità, questo è stato incapsulato in una e utilizzata da un programma di test esterno per verificarne la funzionalità.