Strutture dati Astrazione Non vogliamo sapere l’organizzazione fisica dei dati



Scaricare 445 b.
26.01.2018
Dimensione del file445 b.


Strutture dati


Astrazione

  • Non vogliamo sapere l’organizzazione fisica dei dati

    • indirizzi e celle di memoria
  • Ci interessa solo la loro organizzazione astratta



Strutture statiche e dinamiche

  • Statica: che non cambia nel tempo (forma o dimensione)

  • Es.: elenco di nomi: posso aggiungere o eliminare nomi?

  • Struttura statica: solo metodi per accedere ai dati e per modificarli

  • Struttura dinamica: anche metodi per aggiungere e togliere dati, e trovare spazio in memoria per i nuovi dati



Puntatori

  • Ogni cella di memoria ha un indirizzo

  • Indirizzo = valore numerico  puo’ essere memorizzato in una cella di memoria

  • Puntatore: cella/e di memoria che contiene l’indirizzo di un’altra cella di memoria

  • Puo’ servire a sapere dove sono stati memorizzati dei dati

  • Es.: registro contatore programma della CPU



Puntatori come tipi di dati

  • In molti linguaggi di programmazione

  • Dichiarazione, allocazione, gestione dei puntatori (come un real o un integer)

  • Es.: in memoria c’e’ una lista di romanzi (per ordine alfabetico del titolo)

    • Vogliamo trovare tutti i romanzi di un certo autore  aggiungo una cella ad ogni romanzo, che contiene il puntatore al romanzo successivo dello stesso autore, in un ciclo


Esempio



Array omogeneo

  • Viene memorizzato in memoria in celle contingue

  • Facile trovare l’elemento i:

  • Vado all’indirizzo di inizio dell’array, x

  • Vado all’indirizzo x + (i-1)*k celle, dove k=numero di celle per un elemento dell’array



Esempio



Array bidimensionale

  • Esempio: tabella con venditori sulle righe e giorni della settimana sulle colonne: numero di vendite in ogni cella  array bidimensionale

  • Una riga: vendite di un venditore in una settimana

  • Una colonna: vendite fatte in un giorno da tutti i venditori



Simulazione di tabella in memoria

  • Memoria: sequenza di celle con indirizzi consecutivi

  • Un array e’ statico  posso riservare un pezzo di memoria per l’intero array, e poi metterci l’array riga per riga



Esempio

  • Come trovare il valore in terza riga e quarta colonna?

  • Da prima cella, passiamo la prima riga e la seconda

  • Cinque elementi per riga  10 elementi pr arrivare al primo elemento della terza riga

  • Altri 3 elementi per quarto elemento della terza riga  13 elementi in totale



In generale ...

  • Array con c colonne, x indirizzo iniziale

  • Indirizzo di elemento in riga i e colonna j:

  • x + (c * (i-1)) + (j-1)

  • Il compilatore traduce i riferimenti (es. Vendite[2,4]) in indirizzi di memoria

  • Il programmatore usa la forma tabulare (struttura astratta), il compilatore usa la memorizzazione in memoria (struttura fisica)



Esercizio

  • Array bidimensionale con 8 righe e 11 colonne

  • Ogni elemento occupa 2 celle di memoria

  • Memorizzato per righe a partire dall’indirizzo 25

  • Indirizzo dell’elemento in terza riga e sesta colonna?

  • 25 + (11x2x2) + (2x5) = 25+44+10=79



Liste

  • Sequenza di elementi, dinamica

  • Es.: lista di nomi, ogni nome 8 lettere  8 celle di memoria

  • Come la memorizzo in memoria? Blocco di celle consecutive (80)?



Liste contigue

  • Devo cancellare un nome  spazio vuoto  devo spostare tutti i nomi che seguono (ordine alfabetico)

  • Devo inserire un nuovo nome  non c’e’ spazio  devo spostare tutto il blocco



Lista concatenata

  • Gli elementi sono memorizzati in aree di memoria diverse invece che contigue

  • Nell’esempio, 9 celle per ogni nome: 8 per il nome, 1 per puntatore all’elemento successivo

  • Inoltre, puntatore al primo elemento (testa) della lista

  • Puntatore speciale (nil) nell’ultimo elemento

  • Per accedere all’elemento i-esimo: devo scorrere tutti gli elementi dal primo all’i-esimo



Lista concatenata



Cancellazione in liste concatenate

  • Modifico il puntatore che punta all’elemento da cancellare, e lo faccio puntare all’elemento successivo



Inserzione in liste concatenate

  • Trovo un blocco di 9 celle “libero”, dove metto il nome e il puntatore all’elemento che lo seguira’ nella lista

  • Cambio il puntatore di chi lo precedera’ per farlo puntare a lui



Code e pile

  • Le liste concatenate riducono gli spostamenti se permettiamo inserzioni e cancellazioni ovunque

  • Se permettiamo modifiche solo alle estremita’, anche una struttura contigua puo’ andare bene

  • Pila (stack): inserzioni (push) e cancellazioni (pop) solo ad una estremita’ (cima)  l’ultimo elemento inserito e’ il primo ad essere cancellato (LIFO)



Memorizzazione di una pila

  • Blocco di celle contigue, grande abbastanza per le inserzioni previste

  • Puntatore alla cima dello stack (ultimo elemento riempito)



Pila per chiamate di procedura

  • Quando un programma chiama una procedura, deve memorizzare da qualche parte l’indirizzo di ritorno (da cui riprendere l’esecuzione dopo)

  • Dove lo memorizza? In una pila

  • Chiamata dopo chiamata, gli indirizzi vengono memorizzati sulla pila

  • Alla chiusura delle procedure, gli indirizzi di ritorno vengono presi in ordine opposto



Pila per chiamate di procedura



Pila per ordine inverso

  • Vogliamo stampare gli elementi di una lista concatenata in ordine inverso

  • Ci serve una struttura dati per memorizzare ogni nome finche’ i nomi seguenti non sono stati stampati

  • Scorro la lista e metto i nomi su una pila

  • Alla fine della lista, stampo i nomi della pila







Esercizi e domande

  • Un programma chiama la procedura A, che chiama la B. Quando B termina, A chiama la procedura C.

  • Seguire questo percorso mantenendo aggiornata la pila delle posizioni di ritorno.



Coda

  • Tutti gli inserimenti ad una estremita’ (coda)

  • Tutte le cancellazioni all’altra estremita’ (testa)

  • FIFO

  • Memorizzazione:

    • celle contigue
    • due puntatori
      • alla testa: primo elemento
      • alla coda: primo elemento libero
  • Coda “circolare”: quando gli elementi ragiungono la fine del blocco, inserisco dall’altra estremita’



Code



Code



Code circolari



Code circolari



Esercizio



Esercizio



Esercizio



Esercizio

  • Coda

  • Ogni elemento occupa una cella di memoria

  • Puntatore alla testa = 11

  • Puntatore alla coda = 17

  • Quali soni i valori dei due puntatori dopo aver inserito un elemento e eliminati due?






©astratto.info 2017
invia messaggio

    Pagina principale