Algoritmi - Strutture Dati

1. Tipi di Strutture

1. Tipi di Strutture

1.1. Strutture elementari

Si intente il piu' piccolo tipo di dato utilizzabile formato da uno o piu' byte e le operazioni che si possono fare su questi sono definite nel linguaggio di programmazione utilizzato e la limite possono essere ridefinite, sono :

Bit: può rappresentare due stati dell’informazione.
Byte: composto da 8 bit, possiamo rappresentare in numerazione binaria fino a 28 .
Indirizzo.
Parola.
Parola doppia.

1.2. Strutture Interne

Una struttura dati è detta interna quando definisce l’implementazione concreta dell’archiviazione e dell’accesso ai dati, influenzando direttamente le operazioni possibili, la loro complessità computazionale e l’uso delle risorse (memoria/cache). Può essere sia a organizzazione fissa (array statici) che dinamica (hash table, alberi)

1.2.1. Strutture sequenziali

Sono in cui le unita' contenenti l' informazione sono sequenziali e sono tutte dello stesso tipo. Le unita' possono essere formati da strutture elementari o record. Un vettore e' un esempio perfetto.

Indirizzo  : [0x1000] [0x1004][0x1008][0x100C][0x1010]
             +-------+-------+-------+-------+-------+
Valore     : |   10  |   20  |   30  |   40  |   50  |
             +-------+-------+-------+-------+-------+
Indice     :     0       1       2       3       4

L'indirizzo della cella successiva e' quello ottenuto sommando all'indirizzo della cella precedente la dimensione del contenuto della cella.

I linguaggi di programmazione mettono a disposizione una notazione del tipo \(nome_struttura[indice]\) ma vi si puo' accedere anche mediante l'indirizzo della cella.

        /*
        VettoreDemo/
        ├── src/
        │   ├── VettoreBase.java          (Classe base con array tradizionale)
        │   ├── VettoreByteBuffer.java    (Versione con ByteBuffer)
        │   └── Main.java                 (Classe principale)
        */

    package vector.memory.demo;

    public class Main {
        public static void main(String[] args) {
            int[] dati = {10, 20, 30, 40, 50};

            System.out.println("=== VETTORE BASE ===");
            VettoreBase vb = new VettoreBase(dati);
            vb.set(2, 99);
            vb.stampa();

            System.out.println("\n=== VETTORE BYTEBUFFER ===");
            VettoreByteBuffer vbb = new VettoreByteBuffer(dati);
            vbb.set(3, 88);
            vbb.stampa();
        }
    }


  /*

    === OUTPUT ===

    === VETTORE BASE ===
    Indice 0: 10
    Indice 1: 20
    Indice 2: 99
    Indice 3: 40
    Indice 4: 50

    === VETTORE BYTEBUFFER ===
    Offset 0 (0x0): 10
    Offset 4 (0x4): 20
    Offset 8 (0x8): 30
    Offset 12 (0xc): 88
    Offset 16 (0x10): 50
*/

package vector.memory.demo;

/**
 * Gestione vettore con accesso tramite indice (standard Java)
 */
public class VettoreBase {
    private int[] vettore;

    public VettoreBase(int[] dati) {
        this.vettore = dati.clone();
    }

    public int get(int indice) {
        return vettore[indice];
    }

    public void set(int indice, int valore) {
        vettore[indice] = valore;
    }

    public void stampa() {
        for (int i = 0; i < vettore.length; i++) {
            System.out.printf("Indice %d: %d\n", i, vettore[i]);
        }
    }
}

package vector.memory.demo;

import java.nio.ByteBuffer;
import java.nio.ByteOrder;

/**
 * Gestione vettore con ByteBuffer (memoria diretta ma sicura)
 */
public class VettoreByteBuffer {
    private ByteBuffer buffer;
    private int dimensione;

    public VettoreByteBuffer(int[] dati) {
        this.dimensione = dati.length;
        this.buffer = ByteBuffer.allocateDirect(dimensione * Integer.BYTES);
        buffer.order(ByteOrder.nativeOrder());

        // Scrittura iniziale
        for (int i = 0; i < dimensione; i++) {
            set(i, dati[i]);
        }
    }

    public int get(int indice) {
        return buffer.getInt(indice * Integer.BYTES);
    }

    public void set(int indice, int valore) {
        buffer.putInt(indice * Integer.BYTES, valore);
    }

    public void stampa() {
        for (int i = 0; i < dimensione; i++) {
            System.out.printf("Offset %d (0x%x): %d\n", 
                i * Integer.BYTES,
                i * Integer.BYTES,
                get(i));
        }
    }
}

1.2.2. Strutture concatenate

Sono costituite da elementi non fisicamente adiacenti nella memoria, ma tra i quali la sequenzialità viene mantenuta registrando l’informazione assieme ai dati stessi (sequenzialità logica), quindi ogni dato rimanda alla posizione del dato successivo. È sufficiente quindi ricordarsi la posizione del primo elemento della catena per arrivare a tutti gli altri.

1.3. Strutture astratte

In informatica, le strutture astratte (o tipi di dato astratti, ADT) sono modelli teorici che definiscono cosa fa una struttura dati (comportamento e operazioni), senza specificare come è implementata.

Definizione Chiave
Una struttura astratta è un contratto che specifica:
Operazioni possibili (es.: push, pop per una pila).
Comportamento atteso (es.: "L'ultimo elemento inserito è il primo a essere rimosso").
Restrizioni sull'accesso ai dati.
Senza rivelare dettagli implementativi (array, liste, puntatori, ecc.).