Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 9.Implementazioni di Liste Doppiamente Puntate e Circolari


Indice

  • Liste puntate semplici: Gli elementi sono organizzati in modo sequenziale e si possono scorrere in un unico verso. La lista ha un primo elemento (testa) e un ultimo elemento (coda).
  • Liste doppiamente puntate: Sono simili alle liste puntate sem-plici, ma permettono di scorrere gli elementi in entrambi i versi.
  • Liste puntate semplici circolari: Sono liste puntate semplici senza testa ne coda.
  • Liste doppiamente puntate circolari: Liste doppiamente puntate senza testa ne coda.

Liste puntate doppie

Una Lista Doppia Puntata è un insieme dinamico in cui ogni elemento ha uno o più campi contenenti informazioni e due riferimenti, uno all’elemento successivo (next) della lista ed uno all’elemento precedente (prev) della lista.

Implementazione in C

Per definire la struttura di un elemento di una lista doppiamente puntata bisogna utilizzare due puntatori alla stessa struttura. Il primo punterà all’elemento precedente mentre il secondo punterà a quello successivo (vedi figura).

Per l’inizializzazione di una lista doppiamente puntata si può considerare il codice visto per l’inizializazione delle liste singolarmente puntate, introducendo opportunamente il codice per la gestione del puntatore all’elemento precedente.


Funzione crea_lista()

La funzione crea_lista() crea due puntatori ad elemento, uno di nome p (puntatore al primo elemento della lista) e l’altro di nome punt (puntatore che permette di scorrere la lista).


Funzione crea_lista()


Inserimento in coda: main()


Inserimento in coda: funzione


Liste puntate circolari

Una Lista Circolare puntata è un una lista puntata in cui il puntatore next dell’ultimo elemento della lista punta all’elemento in testa alla lista.

Infine, se la lista è doppiamente puntata, il puntatore prev della testa della lista punta all’elemento in coda alla lista.


Inserimento all’interno di liste doppiamente puntate

Supponiamo di voler inserire un elemento valore in una lista prima dell’elemento puntato da pos.


Eliminazione elemento da una lista circolare doppiamente puntata


Esercizio 1

Siano L1 e L2 due liste non circolare doppiamente puntate definite da… (vedi figura)

Si supponga che L1 e L2 siano ordinate in senso crescente.

Scrivere una funzione ricorsiva in linguaggio C che prese in input le due liste L1 e L2 generi una nuova lista L3 ordinata in senso crescente che contenga tutti gli elementi di L1 e L2


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion