Articles

Astratte strutture dati

by admin

tipi di dati Astratti

In informatica, un tipo di dati astratto (ADT) è un modello matematico per i tipi di dati in cui un tipo di dati è definito dal suo comportamento (semantica) dal punto di vista di un utente dei dati, in particolare in termini di valori possibili, operazioni possibili su dati di questo tipo, e il comportamento di queste operazioni. Ciò contrasta con le strutture dati, che sono rappresentazioni concrete dei dati e sono il punto di vista di un implementatore, non di un utente.

Formalmente, un ADT può essere definito come una “classe di oggetti il cui comportamento logico è definito da un insieme di valori e un insieme di operazioni”; questo è analogo a una struttura algebrica in matematica. Ciò che si intende per “comportamento” varia a seconda dell’autore, con i due tipi principali di specifiche formali per il comportamento che sono specifiche assiomatiche (algebriche) e un modello astratto; questi corrispondono rispettivamente alla semantica assiomatica e alla semantica operativa di una macchina astratta. Alcuni autori includono anche la complessità computazionale (“costo”), sia in termini di tempo (per le operazioni di calcolo) che di spazio (per la rappresentazione dei valori).

Il motivo per cui usiamo strutture astratte è perché usano in modo efficiente la memoria in base alla progettazione dei dati memorizzati in esse. Con grandi quantità di dati o dati che cambiano molto frequentemente, la struttura dei dati può fare un’enorme differenza nell’efficienza (tempo di esecuzione) del programma per computer.

Nel linguaggio più comune, una struttura di dati astratta è solo una disposizione di dati che abbiamo integrato in una disposizione ordinata.

perfettamente bella panoramica

Alcuni tipi di dati astratti strutture

Valutati dalla IB

  1. statica e dinamica struttura di dati
  1. array
  2. array bidimensionali
  3. stack
  4. coda
  5. lista
  6. albero
  7. albero binario
  8. collezioni
  9. la ricorsione

NON Valutato dall’IB, ma si deve sapere loro

  1. liste
  2. dizionari
  3. set
  4. tupla

operazioni di Base di strutture di dati

ho trovato questo ottimo slide da Simon Allardice.

Operazioni di base degli array.png

Confronto delle diverse strutture di dati

Struttura di Dati Forza Debolezze
array Inserimento e cancellazione di elementi, l’iterazione attraverso la raccolta Ordinamento e ricerca, Inserimento e cancellazione – soprattutto se l’inserimento e l’eliminazione all’inizio o alla fine dell’array
lista diretta di indicizzazione, Facile da creare e utilizzare accesso diretto, la ricerca e l’ordinamento
pila e coda progettato per LIFO / FIFO accesso diretto, la ricerca e l’ordinamento
albero binario velocità di inserimento e cancellazione, la velocità di accesso, mantenere ordinati in ordine un po ‘ di sovraccarico

  • strutture Fisse sono più veloce / più piccolo
  • Quando si stanno valutando se è necessario utilizzare un astratto struttura di dati, ci si dovrebbe chiedere: ciò che tiene la maggior parte dei dati e ciò che vale più di frequente i dati modificati?

Confronto tra strutture dati statiche e dinamiche

Questo confronto è usato dal nostro libro di testo di informatica.

Struttura dati statica Struttura dati dinamica
Inefficiente in quanto viene allocata memoria che potrebbe non essere necessaria. Efficiente in quanto la quantità di memoria varia in base alle esigenze.
Accesso rapido a ciascun elemento di dati come la posizione di memoria è fisso quando il programma è scritto. Accesso più lento a ciascun elemento mentre la posizione di memoria viene allocata in fase di esecuzione.
Gli indirizzi di memoria allocati saranno contigui quindi più veloci da accedere. Gli indirizzi di memoria allocati potrebbero essere frammentati in modo più lento da accedere.
Le strutture sono di dimensioni fisse, rendendole più prevedibili per lavorare. Ad esempio, possono contenere un’intestazione. Le strutture variano di dimensioni, quindi deve esserci un meccanismo per conoscere la dimensione della struttura corrente.
La relazione tra diversi elementi di dati non cambia. La relazione tra diversi elementi di dati cambierà man mano che il programma viene eseguito.

Scegliere quale struttura dati utilizzare

Questa grafica viene utilizzata con enorme gratitudine dal Dipartimento di Informatica della Dartford Grammar School.

Scelta di un diagramma di flusso del tipo di dati.png

Standard

  • Identifica una situazione che richiede l’uso del pensiero ricorsivo.
  • Identifica il pensiero ricorsivo in una soluzione di problema specificata.
  • Traccia un algoritmo ricorsivo per esprimere una soluzione a un problema.
  • Descrivere le caratteristiche di un array bidimensionale.
  • Costruire algoritmi utilizzando matrici bidimensionali.
  • Descrivere le caratteristiche e le applicazioni di una pila.
  • Costruisci algoritmi usando i metodi di accesso di uno stack.
  • Descrivere le caratteristiche e le applicazioni di una coda.
  • Costruire algoritmi utilizzando i metodi di accesso di una coda.
  • Spiegare l’uso di array come stack statici e code.
  • Descrivere le caratteristiche e le caratteristiche di una struttura dati dinamica.
  • Descrivi come le liste collegate funzionano logicamente.
  • Disegna liste collegate (singole, doppie e circolari).
  • Descrivere le caratteristiche e le applicazioni di una collezione.
  • Costruire algoritmi utilizzando i metodi di accesso di una raccolta.
  • Discutere la necessità di sottoprogrammi e raccolte all’interno di soluzioni programmate.
  • Costruire algoritmi utilizzando sottoprogrammi predefiniti, array unidimensionali e / o collezioni.
  • Descrivi come gli alberi funzionano logicamente (sia binari che non binari).
  • Definire i termini: genitore, figlio sinistro, figlio destro, sottoalbero, radice e foglia.
  • Stato il risultato di inorder, postorder e preorder albero traversal.
  • Disegna alberi binari.
  • Definire il termine struttura dati dinamica.
  • Confronta l’uso di strutture dati statiche e dinamiche.
  • Suggerire una struttura adatta per una data situazione.