Algoritmi e Strutture Dati

Note di Studio su Algoritmi e Strutture Dati

• Le strutture dati possono essere astratte (indipendenti dall'implementazione) ovvero interne (specifiche per l'elaboratore).

• Le strutture astratte rappresentano i dati in modo efficiente per gli algoritmi.

• La conversione da strutture astratte a strutture interne è fondamentale per le prestazioni.

Strutture Interne

• Elementari: Bit, byte, parole.

• Sequenziali: Gli elementi sono fisicamente adiacenti, come i vettori.

• Concatenate: Gli elementi sono logicamente sequenziali, come le catene.

Strutture Elementari

• Gli elementi più piccoli sono i bit. I byte sono sequenze di 8 bit, mentre le parole sono composte da più byte.

Strutture Sequenziali

• I vettori sono una struttura sequenziale semplice. Hanno un indirizzo base, un numero massimo di elementi e un tipo di dati.

• Inserimento e cancellazione di elementi richiedono spostamenti, con un costo O(m) per m elementi già presenti.

Strutture Concatenate

• Le catene sono costituite da elementi con un campo dati e un puntatore al successivo.

• Inserimento e cancellazione sono efficienti (O(1)), ma richiedono ricerca sequenziale.

Strutture Astratte

• Le strutture astratte includono pile e code, con operazioni specifiche per ciascuna.

Pila (Stack)

• Operazioni principali: push (inserimento) e pop (estrazione), seguendo il principio LIFO (Last In, First Out).

• Utilizzata in applicazioni come l'undo negli editor di testo.

Coda (Queue)

• Operazioni: enqueue (inserimento) e dequeue (estrazione), seguendo il principio FIFO (First In, First Out).

• Utilizzata per scenari come la gestione delle richieste in un server.

Coda con Priorità

• Gli elementi hanno una priorità associata; quelli con priorità maggiore vengono gestiti per primi.

• Operazioni: insert, remove, change, delete, join.

Struttura Dati Heap

• Gli heap sono utilizzati per implementare le code con priorità in modo efficiente.

• Le operazioni di inserimento e rimozione rispettano la condizione di heap con complessità O(log n).

Esplora le nozioni fondamentali sugli algoritmi e le strutture dati. Scopri la distinzione tra strutture dati astratte e interne, e analizza i vari tipi come le strutture elementari e sequenziali. Questo quiz mette alla prova le tue conoscenze su come i dati sono organizzati e gestiti nei computer.