Preparazione per l'esame di Fondamenti di Informatica

D

 come  radice:  

  G  D  H  I  

Se  vediamo  

F  come  radice:   L  F  M  N  

Quindi  in  generale:     G  D  H  I  B  E  -­‐  A  -­‐  C  L  F  M  N  

Ma  perché  utilizzare  gli  alberi  binari?  Perché  qualsiasi  albero  ordinato  può  essere  trasformato  in  

un  albero  binario  ed  essi  hanno  una  struttura  molto  semplice  da  rappresentare  in  memoria.    

E  come  trasformare  un  albero  ordinato  in  un  albero  binario?    

1. La  radice  dell’albero  ordinato  

S

 coincide  con  la  radice  dell’albero  binario  

T  

2. ogni  nodo  di   T  ha  come  figlio  sinistro  il  primo  figlio  del  nodo  corrispondente  in  

S

3. ogni  nodo  di   T  ha  come  figlio  destro  il  fratello  del  nodo  corrispondente  in  

S

  Appunti di Jessica Asietti, non fotocopiare!

Quindi,  nell’esempio:  

1. D  rimane  la  radice  

2. il  figlio  sinistro  rimane   A

3. il  figlio  destro  diventa  

F  

4. A  non  avrà  figlio  sinistro  

5. A  avrà   C  come  figlio  destro  

e  così  via  fino  a  trovare  le  “parentele”  per  ogni  

nodo.    

Con   l’albero   si   chiudono   tutte   le   strutture   astratte   di   dati.   Vediamo   ora   le   strutture   concrete  

ovvero   quelle   strutture   che   veramente   rappresentano   la   memoria   del   calcolatore   per   le   quali   le  

strutture  astratte  sono  solo  una  semplificazione.    

Le  strutture  concrete  sono  tre:  la  struttura  sequenziale,  la  catena  e  il  plesso.  

La  struttura  sequenziale   La  struttura  sequenziale,  come  dice  la  parola  

stessa,   è   formata   da   un   insieme   di   elementi  

adiacenti   tra   di   loro   che   possono   richiedere  

una   o   più   celle.   Solitamente   ogni   elemento  

utilizza  lo  stesso  numero  di  celle,  cioè  hanno  

tutti  la  stessa  lunghezza,  ma  questo  non  è  per  

forza  vero.    

I   parametri   necessari   in   una   struttura  

sequenziale  sono:  

i   indirizzo  primo  elemento  

• b

m   numero  di  elementi  

• d   numero  di  celle  per  elemento  

•

Quindi:  

indirizzo  (X )  =  i  

1 b

indirizzo  (X )  =  i  +  i*d     cioè  l’indirizzo  del  primo  elemento  più  un  certo  numero  di  celle  per  

i b

        raggiungere  l’i-­‐esimo  elemento.  

  i

  sarà   comunque   un   numero   compreso   tra   1   e   m   ed   m   non   è   più   modificabile   dopo   la  

creazione.   Questo   vuol   dire   che   la   struttura   sequenziale   è   una   struttura   rigida   e   per   questo   è  

necessario  sapere  a  priori  quanti  dati  verranno  inseriti!  

Abbiamo   detto   che   non   è   per   forza   vero   che   tutti   gli   elementi   utilizzano   lo   stesso   numero   di   celle.  

In  questo  caso  ci  sono  solo  due  possibili  soluzioni  per  trattare  la  nuova  struttura:  

normalizzo   tutti   gli   elementi   alla   stessa   lunghezza   basandomi   sull’elemento   che   richiede  

• più  celle  di  memoria  

lascio   ad   ognuno   la   sua   lunghezza   ma   devo   essere   in   grado   di   fornire   abbastanza  

• informazioni  per  calcolare  tutti  gli  indirizzi  senza  troppi  problemi…  e  questo  non  è  per  nulla  

semplice!   Appunti di Jessica Asietti, non fotocopiare!

Inoltre   le   strutture   sequenziali   non   sono   per   niente   flessibili,   infatti   se   volessi   inserire   un   nuovo  

elemento  in  una  certa  posizione  dovrei  cancellare  tutti  gli  elementi  presenti  da  quella  posizione  in  

avanti.  Stesso  discorso  per  cancellare  un  elemento.  

La  catena  (o  lista)    

A   differenza   della   struttura   sequenziale   che   risultava   non   flessibile,   la   catena   permette  

l’inserimento  o  la  cancellazione  di  un  elemento  anche  se  esso  si  trova  in  mezzo  alla  lista.    

Ogni  elemento  è  formato  da  due  parti:  il   dato  che  è  il  vero  contenuto  (diciamo  l’elemento  astratto  

da  rappresentare)  e  il  puntatore  cioè  l’indirizzo  all’elemento  successivo  nella  catena.  Quindi,  per  

poter   raggiungere   un   determinato   elemento   si   partirà   dal   primo   puntatore   e   si   percorrerà   tutta   la  

lista   (grazie   a   tutti   i   puntatori)   fino   ad   arrivare   all’elemento   desiderato.   L’ultimo   elemento   della  

lista  avrà  puntatore  nullo.  

Esistono  vari  tipi  di  lista:  

lista   bidirezionale:   ogni   elemento   è   formato   da   tre   “celle”;   il   dato   e   due   puntatori,   uno  

• all’elemento  successivo  e  uno  all’elemento  precedente  

lista  circolare  (o  ciclica):  il  puntatore  dell’ultimo  elemento  non  è  nullo  bensì  punta  al  primo  

• elemento  della  lista  

lista  multipla:   ogni   elemento   ha   tre   celle;   il   dato,   il   puntatore   all’elemento   successivo   e   un  

• altro  puntatore  ad  un’altra  lista.  

  Ma   come   si   comportano   i   puntatori   quando   si  

inserisce/cancella  un  elemento  della  lista?  

Supponiamo  di  voler   inserire   un   elemento   K

 tra  due  

elementi  

H   e   H .  

i i+1

Il  puntatore  di  

H  sarà  l’indirizzo  di   K

• i

il  puntatore  di  

K

 sarà  l’indirizzo  di   H  

• i+1

  Se  invece  volessimo   cancellare   l’elemento  H  il  

i

puntatore  di  

H  sarà  l’indirizzo  di   H  

i-­‐1 i+1

Come  per  le  strutture  sequenziali  abbiamo  considerato  il  caso  in  cui  tutti  gli  elementi  richiedano  lo  

stesso   spazio   nella   memoria.   In   realtà   potrebbero   avere   occupazioni   diverse   e   allora   ogni  

elemento  non  sarebbe  più  formato  da  due  campi  ma