Caricare documenti e articoli online  
INFtube.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

Cenni teorici - Nodi e liste concatenate

informatica


Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a yahoo - corso di



ALTRI DOCUMENTI

ANALISI DEL PROGRAMMA SULLE LISTE
Corso di Microsoft Access
ALGORITMI - SISTEMI DI NUMERAZIONE
Da Div-X a DVD-R
Informatica
ESERCIZI HTML (FRAMES E FORMS)
MODULO 1 ECDL - RIASSUNTO DI PREPARAZIONE ALL'ESAME
Riassunto - Linking
LE BASI DI DATI
DIAGRAMMA A BLOCCHI

Cenni teorici

In questa esercitazione si reso necessario utilizzare due strutture dati molto importanti: la pila e la coda. Per implementare queste due classi per necessario affrontare le liste.

Nodi e liste concatenate

In informatica si possono dare due definizioni di lista, una sequenziale e una ricorsiva.

DEFINIZIONE SEQUENZIALE

Una lista un insieme di elementi in cui 929f59j ogni elemento, tranne il primo e l'ultimo, hanno un solo predecessore e un solo successore.

DEFINIZIONE RICORSIVA

Una lista una lista vuota oppure una coppia di elementi ( i , l ) dove i un informazione ed detta testa della lista, mentre l a sua volta una lista ed detta coda della lista.

Per implementare una lista viene utilizzata una classe Nodo, che rappresenta ogni nodo della lista. Ogni nodo caratterizzato da un campo informazione e da un puntatore al nodo successivo della lista. Se il puntatore null allora significa che la lista terminata. La classe Nodo implementata nel seguente modo:



public class Nodo

}

Ci che segue una semplice rappresentazione di una lista:


Per costruire una lista come quella scritta sopra si pu usare il seguente frammento di codice:

Nodo a = new Nodo(a1,null);

Nodo b = new Nodo(a2,null);

Nodo c = new Nodo(a3,null);

a.next = b;

b.next = c;

Per visitare una lista in modo iterativo si pu far riferimento al seguente algoritmo:

Nodo n = a; // a il puntatore d'accesso alla lista

while (n!=null)

Per inserire un elemento in testa basta usare il seguente frammento di codice:

n.next = first; // n il nodo da inserire

first = n; // first il puntatore d'accesso

Per inserire un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si pu inserire, in questo modo:

n.next = prec.next; // n il nodo da inserire

prec.next = n;

Per eliminare un elemento in testa basta rifarsi al seguente frammento di codice:

first = first.next;

Per eliminare un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si pu cancellare, in questo modo:

prec.next = prec.next.next;

Ci sono altri tipi di lista, come la lista doppiamente concatenate o la lista circolare, ma in questa tesina non ne parliamo, quindi passeremo a trattare le pile e le code.

Pila

Una pila una successione di elementi in cui 929f59j tutte le operazioni di inserimento e di cancellazione avvengono dallo stesso estremo detto testa della pila. La pila esegue una disciplina LIFO(Last In First Out). Le pile sono molto utilizzate per controllare le chiamate ai sottoprogrammi. Le pile possono essere implementate in maniera illimitata, attraverso una lista, o in maniera limitata, attraverso un vettore.

In questa tesina vedremo solo l'utilizzo di una pila illimitata. Il diagramma UML di una classe Pila il seguente:

Pila

- testa: Nodo




+ Pila()

+ isEmpty():boolean

+ top():Object

+ pop()

+ push(obj:Object)

Le operazioni che si possono eseguire su una pila sono quindi le seguenti:

-         push (x) : inserisce l'elemento x nella pila;

-         pop ( ) : elimina l'elemento in testa alla lista senza ritornarlo;

-         top ( ) : restituisce l'elemento in testa alla pila senza rimuoverlo;

-         isEmpty ( ) : indica se la pila vuota;

Coda

Una coda una struttura dati che utilizza la disciplina FIFO ( First In First Out ). Anche le code possono essere implementate, come le pile, o in modo illimitato, con delle liste concatenate, o in modo limitato, con un vettore.

In questa tesina vedremo solo l'utilizzo di una coda illimitata. Il diagramma UML di una classe Coda il seguente:

Coda

- first: Nodo

- last: Nodo

+ Coda()

+ isEmpty():boolean

+ front():Object

+ dequeue()

+ enqueue(obj:Object)

Le operazioni che si possono eseguire su una coda sono quindi le seguenti:

-         enqueue (x) : inserisce l'elemento x in fondo alla coda;

-         dequeue ( ) : elimina l'elemento in testa alla coda senza ritornarlo;

-         front ( ) : restituisce l'elemento in testa alla coda senza rimuoverlo;

-         isEmpty ( ) : indica se la coda vuota;







Privacy

Articolo informazione


Hits: 1254
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2019