Menu

Introduzione alle strutture dati in C ++

introduction data structures c

Prova Il Nostro Strumento Per Eliminare I Problemi

Un tutorial introduttivo sulle strutture dati in C ++.

“La struttura dei dati può essere definita come una raccolta organizzata di dati che aiuta un programma ad accedere ai dati in modo efficiente e rapido in modo che l'intero programma possa funzionare in modo efficiente. '

Sappiamo che nel mondo della programmazione i dati sono il centro e tutto ruota attorno ai dati. Dobbiamo eseguire tutte le operazioni sui dati, inclusa la memorizzazione, la ricerca, l'ordinamento, l'organizzazione e l'accesso ai dati in modo efficiente e solo allora il nostro programma può avere successo.

=> Vedi qui per esplorare l'elenco completo dei tutorial C ++.

Introduzione alle strutture dati in C ++ (1)

Cosa imparerai:

Panoramica

Dobbiamo trovare il modo più efficiente di archiviare i dati che possa aiutarci a costruire soluzioni dinamiche. La struttura dei dati ci aiuta a costruire tali soluzioni.

Durante l'organizzazione o la disposizione dei dati in strutture, dobbiamo assicurarci che la disposizione rappresenti quasi un oggetto del mondo reale. In secondo luogo, questa disposizione dovrebbe essere abbastanza semplice in modo che chiunque possa accedervi facilmente ed elaborarla quando necessario.

In questa serie, impareremo in dettaglio la struttura dei dati di base e quella avanzata. Impareremo anche in dettaglio le varie tecniche di ricerca e ordinamento che possono essere eseguite su strutture di dati.

Dopo aver appreso questa serie di tutorial, il lettore dovrebbe acquisire familiarità con ciascuna struttura di dati e la sua programmazione.

Esaminiamo alcuni dei termini che usiamo quando ci occupiamo di strutture dati:

Per esempio,prendi uno studente in particolare. Uno studente può avere i seguenti dettagli come rappresentati graficamente.

Esempio: struttura dei dati

  • Dati: È il valore elementare. Nella figura sopra, il numero del rotolo dello studente può essere dato.
  • Elemento del gruppo: Questo è l'elemento di dati che ha più di un sotto-elemento. Nella figura sopra, Student_name ha Nome e Cognome.
  • Disco: È una raccolta di elementi di dati. Nell'esempio sopra, elementi di dati come numero di studenti, nome, classe, età, grado, ecc. Formano un record insieme.
  • Entità: È una classe di record. Nel diagramma sopra, lo studente è un'entità.
  • Attributo o campo: Le proprietà di un'entità sono chiamate attributi e ogni campo rappresenta un attributo.
  • File: Un file è una raccolta di record. Nell'esempio precedente, un'entità studente può avere migliaia di record. Quindi un file conterrà tutti questi record.

Il lettore dovrebbe essere consapevole di tutti questi termini poiché li usiamo di tanto in tanto quando si utilizzano varie strutture di dati.

Le strutture dati sono l'elemento costitutivo principale del programma e, come programmatori, dovremmo stare attenti a quale struttura dati utilizzare. L'esatta struttura dei dati da utilizzare è la decisione più difficile da prendere per quanto riguarda la programmazione.

Parliamo della necessità della struttura dei dati nella programmazione.

Necessità della struttura dei dati nella programmazione

Man mano che la quantità di dati continua a crescere, le applicazioni diventano sempre più complesse, quindi diventa difficile per il programmatore gestire questi dati così come il software.

In genere, in qualsiasi momento, l'applicazione può incontrare i seguenti ostacoli:

# 1) Ricerca di grandi quantità di dati: Con una grande quantità di dati elaborati e archiviati, in qualsiasi momento al nostro programma potrebbe essere richiesto di cercare un dato dato. Se i dati sono troppo grandi e non organizzati correttamente, sarà necessario molto tempo per ottenere i dati richiesti.

Quando utilizziamo strutture di dati per archiviare e organizzare i dati, il recupero dei dati diventa più veloce e più facile.

# 2) Velocità di elaborazione: I dati disorganizzati possono comportare una velocità di elaborazione lenta poiché molto tempo verrà sprecato nel recupero e nell'accesso ai dati.

Se organizziamo i dati correttamente in una struttura dati durante l'archiviazione, non perderemo tempo in attività come il recupero, organizzandoli ogni volta. Invece, possiamo concentrarci sull'elaborazione dei dati per produrre l'output desiderato.

# 3) Richieste multiple simultanee: Molte applicazioni in questi giorni devono fare una richiesta simultanea ai dati. Queste richieste devono essere elaborate in modo efficiente affinché le applicazioni vengano eseguite senza problemi.

Se i nostri dati vengono archiviati in modo casuale, non saremo in grado di elaborare tutte le richieste simultanee contemporaneamente. Quindi è una decisione saggia organizzare i dati in una struttura dati adeguata in modo da ridurre al minimo i tempi di risposta delle richieste simultanee.

Classificazione della struttura dei dati

Le strutture dati utilizzate in C ++ possono essere classificate come segue.

Classificazione delle strutture dati

Una struttura dati è un modo per organizzare i dati. Quindi possiamo classificare le strutture di dati come mostrato in strutture di dati primitive o standard e strutture di dati non primitive o definite dall'utente.

Abbiamo visto tutti i tipi di dati supportati in C ++. Poiché questo è anche un modo per organizzare i dati, diciamo che si tratta di una struttura dati standard.

Le altre strutture dati non sono primitive e l'utente deve definirle prima di utilizzarle in un programma. Queste strutture di dati definite dall'utente sono ulteriormente classificate in strutture di dati lineari e non lineari.

Struttura dati lineare

Le strutture dati lineari hanno tutti i loro elementi disposti in modo lineare o sequenziale. Ogni elemento in una struttura dati lineare ha un predecessore (elemento precedente) e un successore (elemento successivo)

Le strutture dati lineari sono ulteriormente suddivise in strutture dati statiche e dinamiche. Le strutture dati statiche di solito hanno una dimensione fissa e una volta che la loro dimensione è stata dichiarata in fase di compilazione, non può essere modificata. Le strutture di dati dinamici possono cambiare la loro dimensione dinamicamente e adattarsi.

L'esempio più popolare di struttura dati statica lineare è un array.

Vettore

Un array è una raccolta sequenziale di elementi dello stesso tipo. È possibile accedere a ciascun elemento dell'array utilizzando la sua posizione nell'array chiamato indice o pedice dell'array. Il nome dell'array punta al primo elemento dell'array.

Vettore

Quanto sopra mostrato è un array 'a' di n elementi. Gli elementi sono numerati da 0 a n-1. La dimensione dell'array (n in questo caso) è anche chiamata dimensione dell'array. Come mostrato nella figura sopra, il nome dell'array punta al primo elemento dell'array.

L'array è la struttura dati più semplice ed è efficiente in quanto è possibile accedere agli elementi utilizzando direttamente gli indici. Se vogliamo accedere al terzo elemento dell'array, dobbiamo solo dire a (2).

Ma aggiungere o eliminare gli elementi dell'array è difficile. Quindi utilizziamo array solo in applicazioni semplici o in applicazioni in cui non è richiesta l'aggiunta / eliminazione di elementi.

Le strutture di dati dinamici lineari più diffuse sono elenco collegato, stack e coda.

Lista collegata

Un elenco collegato è una raccolta di nodi. Ogni nodo contiene l'elemento dati e un puntatore al nodo successivo. I nodi possono essere aggiunti ed eliminati dinamicamente. Un elenco collegato può essere un elenco collegato singolarmente in cui ogni nodo ha un puntatore solo all'elemento successivo. Per l'ultimo elemento, il puntatore successivo è impostato su null.

Nella lista doppiamente concatenata, ogni nodo ha due puntatori uno al nodo precedente e il secondo al nodo successivo. Per il primo nodo, il puntatore precedente è nullo e per l'ultimo nodo, il puntatore successivo è nullo.

Lista collegata

Come mostrato nella figura sopra, l'inizio della lista è chiamata testa mentre la fine della lista collegata è chiamata coda. Come mostrato sopra, ogni nodo ha un puntatore all'elemento successivo. Possiamo facilmente aggiungere o eliminare elementi cambiando il puntatore al nodo successivo.

Pila

Stack è una struttura di dati lineare in cui gli elementi possono essere aggiunti o rimossi solo da un'estremità nota come 'Top' dello stack. In questo modo, lo stack mostra il tipo di accesso alla memoria LIFO (Last In, First Out).

Pila

Come mostrato sopra, gli elementi nella pila vengono sempre aggiunti a un'estremità e anche rimossi dalla stessa estremità. Questo è chiamato il 'Top' dello stack. Quando un elemento viene aggiunto, viene spinto verso il basso nella pila e la parte superiore della pila viene incrementata di una posizione.

Allo stesso modo, quando un elemento viene rimosso, la parte superiore della pila viene decrementata. Quando una pila è vuota, la parte superiore della pila è impostata su -1. Ci sono due operazioni principali 'Push' e 'Pop' che vengono eseguite sullo stack.

Coda

La coda è un'altra struttura di dati lineare in cui gli elementi vengono aggiunti a un'estremità chiamata 'posteriore' e cancellati da un'altra estremità chiamata 'anteriore'. Queue dimostra FIFO (First In, First Out) il tipo di metodologia di accesso alla memoria.

Coda

Il diagramma sopra mostra una coda con estremità posteriore e anteriore. Quando la coda è vuota, i puntatori posteriore e anteriore coincidono l'uno con l'altro.

Struttura dati non lineare

Nelle strutture di dati non lineari, i dati non sono disposti sequenzialmente, ma sono disposti in modo non lineare. Gli elementi sono collegati tra loro in una disposizione non lineare.

Le strutture dati non lineari sono alberi e grafici.

miglior software gratuito per scaricare video di YouTube

Alberi

Gli alberi sono strutture di dati multilivello non lineari aventi una relazione gerarchica tra gli elementi. Gli elementi dell'albero sono chiamati nodi.

Il nodo in alto è chiamato radice dell'albero. La radice può avere uno o più nodi figlio. I nodi successivi possono anche avere uno o più nodi figlio. I nodi che non hanno nodi figlio sono chiamati nodi foglia.

Alberi

Nel diagramma sopra, abbiamo mostrato un albero con 6 nodi. Di questi tre nodi sono i nodi foglia, un nodo più in alto è la radice e gli altri sono nodi figli. A seconda del numero di nodi, nodi figlio, ecc. O della relazione tra i nodi, abbiamo diversi tipi di alberi.

Grafici

Il grafico è un insieme di nodi chiamati vertici collegati tra loro tramite i link chiamati Bordi . I grafici possono avere un ciclo al loro interno, ovvero lo stesso vertice può essere un punto di partenza oltre che il punto finale di un particolare percorso. Gli alberi non possono mai avere un ciclo.

Grafici

Il diagramma sopra è un grafico non orientato. Possiamo anche avere grafici diretti in cui rappresentiamo i bordi usando frecce dirette.

Operazioni sulla struttura dei dati

Tutte le strutture dati eseguono varie operazioni sui suoi elementi.

Questi sono comuni a tutte le strutture dati e sono elencati come segue:

  • Ricerca: Questa operazione viene eseguita per cercare un particolare elemento o una chiave. Gli algoritmi di ricerca più comuni sono la ricerca sequenziale / lineare e la ricerca binaria.
  • Ordinamento: L'operazione di ordinamento implica la disposizione degli elementi in una struttura di dati in un ordine particolare ascendente o discendente. Sono disponibili vari algoritmi di ordinamento per le strutture dati. I più popolari tra loro sono Quicksort, Selection sort, Merge sort, ecc.
  • Inserimento: L'operazione di inserimento riguarda l'aggiunta di un elemento alla struttura dati. Questa è l'operazione più importante e come risultato dell'aggiunta di un elemento, la disposizione cambia e dobbiamo fare attenzione che la struttura dei dati rimanga intatta.
  • Cancellazione: L'operazione di cancellazione rimuove un elemento dalla struttura dati. Le stesse condizioni da considerare per l'inserimento devono essere soddisfatte anche in caso di operazione di cancellazione.
  • Traversata: Diciamo che attraversiamo una struttura dati quando visitiamo ogni singolo elemento della struttura. L'attraversamento è necessario per eseguire alcune operazioni specifiche sulla struttura dei dati.

Nei nostri argomenti successivi, impareremo prima le varie tecniche di ricerca e ordinamento da eseguire sulle strutture di dati.

Vantaggi della struttura dei dati

  • Astrazione: Le strutture dati vengono spesso implementate come tipi di dati astratti. Gli utenti accedono solo alla sua interfaccia esterna senza preoccuparsi dell'implementazione sottostante. Pertanto la struttura dei dati fornisce uno strato di astrazione.
  • Efficienza: Una corretta organizzazione dei dati si traduce in un accesso efficiente ai dati, rendendo i programmi più efficienti. In secondo luogo, possiamo selezionare la struttura dati corretta in base alle nostre esigenze.
  • Riusabilità: Possiamo riutilizzare le strutture dati che abbiamo progettato. Possono anche essere compilati in una libreria e distribuiti al client.

Conclusione

Con questo, concludiamo questo tutorial sull'introduzione alle strutture dati. Abbiamo introdotto brevemente ciascuna delle strutture dati in questo tutorial.

Nelle nostre esercitazioni successive, esploreremo di più sulle strutture dei dati insieme alle varie tecniche di ricerca e ordinamento.

=> Fare clic qui per la serie di formazione Absolute C ++.

Lettura consigliata

^