Indice dei contenuti
- Introduzione
- Vettori
- Matrici
- Tabelle e Record
- Video numero 1 – Strutture dati astratte
Video numero 2 – Strutture dati astratte
Video numero 3 – Strutture dati astratte - Corso Udemy dall’Algoritmo alle Basi in C++ in promozione fino al 2 Marzo 2022 affrettati
Strutture dati semplici
Introduzione
In informatica spesso si devono utilizzare grosse quantità di informazioni e pertanto per il loro utilizzo e gestione occorre definire delle variabili personalizzate, che in modo collettivo raggruppino dei dati che hanno lo stesso tipo di caratteristiche.
Una struttura dati semplice è pertanto una struttura dati costruita dall’utente a partire da quelle semplici. Esse si distinguono in omogenee e eterogenee. Nel primo caso l’aggregato ottenuto è costituito da elementi dello stesso tipo mentre nel secondo sono di tipo diverso. Tutte le strutture dati astratte sono temporanee quando la memorizzazione avviene in memoria centrale. I dati in essa inseriti, sono disponibili solo per il tempo necessario all’esecuzione del programma. Ben altra cosa è l’utilizzo di strutture dati permanenti, nei quali i dispositivi atti alla memorizzazione dell’informazione sono i supporti di mMatriciemoria di massa.
Vettori e Matrici
Un vettore è una variabile strutturata costituita da n variabili di tipo semplice identificata da un nome collettivo e da un indice che ne seleziona il valore. La nomenclatura sui vettori suole indicare i vettori con il nome collettivo seguito da una coppia di parentesi al cui interno è indicato l’indice che obbligatoriamente indicando una posizione è intero. Ad esempio a[3]indica il terzo elemento del vettore, a[i] indica l’i-mo elemento del vettore. Alcuni linguaggi di programmazione ammettono la dichiarazione della dimensione del vettore nella parte dichiarativa (pascal, fortran) altri invece consentono un dimensionamento dinamico nel programma. Normalmente anche se la dimensione del vettore deve essere fissata all’inizio prima dell’esecuzione dell’algoritmo, non è un grosso problema ricondurlo ad una gestione dinamica come vedremo in alcuni esempi.
Il vettore graficamente può essere rappresentato con un insieme di caselle al cui interno vi sono i valori che possono essere sia di tipo semplice che composto.
Normalmente per l’utilizzo del vettore è opportuno procedere al caricamento dei valori attraverso l’utilizzo di un ciclo. Supponiamo di voler caricare un vettore di nome b co
In informatica spesso si devono utilizzare grosse quantità di informazioni e pertanto per il loro utilizzo e gestione occorre definire delle variabili personalizzate, che in modo collettivo raggruppino dei dati che hanno lo stesso tipo di caratteristiche.
Una struttura dati astratta è pertanto una struttura dati costruita dall’utente a partire da quelle semplici. Esse si distinguono in omogenee e eterogenee. Nel primo caso l’aggregato ottenuto è costituito da elementi dello stesso tipo mentre nel secondo sono di tipo diverso. Tutte le strutture dati astratte sono temporanee quando la memorizzazione avviene in memoria centrale. I dati in essa inseriti, sono disponibili solo per il tempo necessario all’esecuzione del programma. Ben altra cosa è l’utilizzo di strutture dati permanenti, nei quali i dispositivi atti alla memorizzazione dell’informazione sono i supporti di Matrici e memoria di massa.
Imposto da 10 elementi interi; l’algoritmo sotto forma di pseudo-codice è:
- Inizio
- Per i= 1 a 10 esegui
- ciclo
- scrivi “dammi elemento”
- leggi b[i]
- fine ciclo
- fine
In questo esempio viene chiesto all’utente di inserire dei valori da tastiera che verranno memorizzati nel vettore b[]. Come primo esercizio si scambino gli elementi di posto pari con quelli di posto dispari di un vettore di 10 elementi interi. Dopo aver caricato il vettore come fatto in precedenza l’algoritmo che risponde la problema dovrebbe essere:
- Per i=1 a 5 esegui
- ciclo
- temp=a[i]
- a[i]=a[2i]
- a[2i]=temp
- fine ciclo
- fine
In questo algoritmo si è utilizzata la variabile “temp” per memorizzare temporaneamente i valori che vengono soprascritti con l’istruzione 4. Un altro esercizio potrebbe essere dato un vettore di 10 elementi contare e visualizzare quante volte un elemento introdotto da tastiera si ripete. in questo problema oltre al vettore a[] è necessario utilizzare una variabile “cont” intera che conti il numero delle occorrenze, una variabile “num” che contenga l’elemento inserito da tastiera di cui si vuole verificare il numero delle occorrenze. La procedura per il caricamento è sempre la stessa per cui la omettiamo. L’algoritmo che risolve il problema richiesto sarà:
- inizio
- cont=0
- scrivi “inserisci l’elemento da cercare”
- leggi num
- Per i=1 a 10 esegui
- ciclo
- se a[i]=num allora
- cont=cont+1
- fine ciclo
- scrivi “il numero di volte che si ripete il valore inserito è: ” ,num
- fine
In questo algoritmo si inserisce l’elemento da contare da tastiera, poi si confronta ogni elemento del vettore con il valore di riferimento attraverso un ciclo e alla fine si visualizza il risultato ottenuto. Nei vettori sono molto diffuse le procedure di ricerca di elementi specifici in strutture ordinate. Si supponga di avere un vettore di 20 elementi numerici interi ordinati in ordine crescente. La ricerca di un elemento specifico può avvenire in modo sequenziale come nel caso dell’algoritmo precedente, o attraverso il metodo dicotomico. Con questo metodo si riduce notevolmente il numero di scansioni degli elementi del vettore. Nella ricerca dicotomica utilizza il metodo delle divisioni successive. Per meglio chiarire riportiamo di sotto un vettore di 10 elementi interi ordinato in modo crescente:
1 3 4 5 6 8 9 12 15 18;
ora supponiamo che l’elemento da cercare è “9”. La dimensione del vettore è 10, quindi si introducono tre indici sinistro, destro e centrale. Al primo passaggio sinistro=1, destro=10, centrale=(sinistro + destro)/2=6 (intero successivo) ora gli elementi del vettore di posizione sinistro=1 (“1”), destro (“18”), centro (“8”) non sono uguali all’elemento richiesto. A questo punto se l’elemento di centro è minore del valore da cercare sinistro =centro+1 altrimenti destro=centro-1, e si ripete la procedura. in questo caso l’uscita dal ciclo è condizionata o all’evento che è stato trovato l’elemento o che sinistro è diventato maggiore di destro (sconfinamento dell’indice). Sulla base di questo esempio l’algoritmo escludendo la parte di caricamento è:
- inizio
- scrivi “dammi il valore da cercare”
- leggi valore
- trovato=falso // sto utilizzando una variabile logica
- sinistro=1
- destro=10 // o la dimensione del vettore
- centro=(sinistro + destro)/2
- ripeti
- Se a[sinistro]=valore o a(destro)=valore o a(centro)=valore allora
- trovato=vero
- altrimenti
- se a[centro]<valore allora
- sinistro=centro+1
- altrimenti
- destro=centro-1
- finché trovato=vero o sinistro>destro
- Se trovato=vero allora
- scrivi “valore trovato all’interno del vettore”
- altrimenti
- scrivi “valore non trovato”
- fine
In questo algoritmo si fa suo di tre indici per la ricerca dell’elemento. Tale metodo riduce la ricerca di N/2 scansioni ad ogni passaggio di divisione. Nell’utilizzo dei vettori spesso è necessario operare con più vettori in simultanea. Ad esempio in un vettore di 5 elementi di stringhe si inseriscano i nomi delle città, in un altro composto da 5 elementi reali il reddito medio per abitante. Supponiamo di voler calcolare e visualizzare in quale città un abitante ha il reddito massimo. Allora fermiamoci un agoritimo a descrivere le variabili in gioco nel problema. Esse sono:
Classe< | Nome | Tipo |
Inupt | cit | vettore di stringhe di 5 elementi |
Input | reddito | vettore di 5 elementi reali |
Interna | i | indice vettori |
Output | cit_max | stringa |
Output | max | numero reale conterrà il reddito massimo |
Nella tabella precedente sono presenti due variabili di output max che rappresenta il massimo reddito e cit_max che rappresenta il nome della città ove ogni abitante ha il reddito più alto. Questo algoritmo viene risolto con l’utilizzo della tecnica top-down o procedurale. Infatti tale algoritmo si può scomporre in alcuni sottoalgoritmi che sono: carica_città, carica_redditi, calcola. Ora è possibile impostare l’algoritmo utilizzando variabili globali e procedure.L’algoritmo sarà:
- procedura carica_città
- inizio
- per i=1 a 5 esegui
- ciclo
- scrivi “dammi il nome della città”
- leggi cit[i]
- fine ciclo
- fine carica_città
- procedura carica_redditi
- inizio
- per i= 1 a 5 esegui
- ciclo
- scrivi “inserisci il reddito per abitante”
- leggi reddito[i]
- fine ciclo
- fine carica_redditi
- procedura calcola
- max=0
- cit_max=””
- per i=1 a 5 esegui
- se redditi[i]> max allora
- max=redditi[i]
- cit_,max=cit[i]
- fine ciclo
- scrivi “la città con reddito più alto è”
- scrivi cit_max
- scrivi “con reddito per abitante di “
- scrivi max
- fine calcola
- programma principale
- carica_citta
- carica_redditi
- calcola
- fine
Questo problema è un esempio tipico di problemi risolti attraverso l’uso di vettori paralleli. La risoluzione risulta agevole se le dimensioni dei vettori sono uguali altrimenti occorre utilizzare più indici.
Matrici
Un’altra struttura di dati molto utilizzata in informatica è la matrice ovvero un vettore bidimensionale organizzato in una serie di elementi organizzati in righe e colonne. Infatti se supponiamo che la matrice si chiama “mat” per indicare l’elemento di riga i e colonna j, si utilizza la simbologia mat[i][j]. Come per i vettori sulle matrici è possibile compiere alcune operazioni come caricamento ovvero inserimento di elementi, ordinamento, ricerca di elementi. E’ bene notare che viene definita matrice un vettore bidimensionale i cui elementi sono costituiti da variabili semplici tutte dello stesso tipo. La dimensione delle matrici in alcuni linguaggi di programmazione devono essere fissate a priori in altri casi si può definirla dinamicamente. Supponiamo di voler risolvere il seguente problema: dato una serie di voti per n alunni calcolare e visualizzare le medie. Tale problema all’apparenza sembra complesso ma se correttamente impostato si risolve in modo molto semplice. Ipotizziamo che ogni riga della matrice è costituita da 8 elementi rappresentanti i voti degli alunni nelle 8 materie di studio. una volta caricata la matrice basterà calcolare la media di riga per visualizzare la media di un alunno. Nel problema non è dato il numero degli alunni. In questo caso dimensioniamo le righe della matrice a 30 elementi, e richiediamo il numero degli alunni in input. La tabella delle variabili sara:
Classe | Nome | Tipo |
Input | voti | matrice di 30 righe e 8 colonne |
Input | n | numero di alunni |
Interna | i,j | indici matrice |
Interna | somma | reale somma dei voti di alunno |
Output | media | reale media dei voti di un alunno |
L’algoritmo verrà svolto in un unico blocco senza l’ausilio delle procedure per esporre i concetti. Le strutture cicliche idonee per le matrici sono strutture nidificate in quanto si deve tener conto che un indice sposta la riga e l’altro la colonna. Una volta richiesto in input il numero degli alunni memorizzato nella variabile n, il ciclo esterno sarà svolto fino a n, mentre quello interno fino a 8.
- inizio
- somma=0
- media=0
- scrivi “dammi il numero degli alunni”
- leggi n
- per i=1 a n esegui
- ciclo 1
- per j=1 a 8 esegui
- ciclo 2
- scrivi “dammi il voto dell’alunno”,i,”-mo”
- leggi voti[i][j]
- fine ciclo 2
- fine ciclo 1
- per i=1 a n esegui
- ciclo 1
- per j=1 a 8 esegui
- ciclo 2
- somma=somma+voti(i,j)
- fine ciclo 2
- media=somma/8
- scrivi voti[i][h]
- somma=0 //queste due righe sono necessarie per ricominciare il calcolo della media//
- media=0
- fine ciclo 1
- fine
Alcuni chiarimenti sulle istruzioni di scrittura come:
scrivi “dammi il voto dell’alunno”,i,”-mo”
questa infatti non fa altro che stampare le stringhe fra virgolette (messaggi) concatenate al valore della variabile i. Inoltre come si vede nell’algoritmo è necessario chiudere prima il ciclo interno e poi quello esterno. Questo è solo un esempio di quello che è possibile fare con le matrici. Un esempio molto utile a chiarire il concetto e l’uso delle matrici può essere dato dal seguente problema:
Siano date 4 ruote del lotto napoli, roma, milano, venezia. Su ogni ruota vengono estratti 5 numeri. Un giocatore vuole verificare una giocata di € 5 fatta di tre numeri. Se su una ruota è presente un numero il giocatore vince 5 volte la puntata, 10 per due numeri, e 50 per il terno per ogni ruota. Si chiedano in input al giocatore i tre numeri e si verifichi se ha vinto e in caso positivo la somma vinta. Questo algoritmo all’apparenza complesso può essere risolto con l’ausilio delle matrici dando come dimensione una matrice 4 per 5. ogni riga della matrice costituirà la ruota di una delle quattro città. Ad esempio sulla prima riga vi sarà la ruota di “Napoli”, sulla seconda roma e così via. Una volta richiesti i tre numeri bisognerà contare quanti di questi sono usciti su una ruota. La tabella delle variabili è pertanto:
Classe | Nome | Tipo |
Input | lotto | matrice di 4 righe e 5 colonne di interi contenente i numeri estratti |
Input | n1,n2,n3 | interi numeri giocati |
Interna | i,j | indici matrice |
Interna | cont | intera numeri di estratti indovinati dal giocatore |
Output | somma | intera somma eventualmente vinta dal giocatore |
L’algoritmo consiste in una prima parte ove si carica la matrice con gli estratti, e poi di una parte che controlla il numero degli estratti indovinati. Alla fine del ciclo si comunicherà la giocatore se ha vinto oppure no. Pertanto l’algoritmo è:
- inizio
- cont=0
- somma=0
- per i= 1 a 4 esegui
- ciclo 1
- per j=1 a 5 esegui
- ciclo 2
- scrivi “dammi i numeri estratti su tutte le ruote”
- leggi lotto[i][j]
- fine ciclo 2
- fine ciclo 1
- scrvi “dammi i numeri giocati”
- leggi n1,n2,n3
- per i=1 a 4 esegui
- ciclo 1
- per j=1 5 esegui
- ciclo 2
- se lotto(i,j)=n1 o lotto[i][j]=n2 o lotto[i][j]=n3 allora
- cont=cont+1
- fine ciclo 2
- se cont=1 allora
- somma=somma+5*5
- se cont=2 allora
- somma=somma+5*10
- se cont=3 allora
- somma=somma +5*50
- cont=0
- fine ciclo 1
- se somma =o allora
- scrivi “non hai vinto niente”
- altrimenti
- scrivi “hai vinto €” , somma
- fine
In questo problema due osservazioni la prima è che la puntata è fissa come richiesto dal problema ed è quindi una costante dell’algoritmo. La seconda invece risiede nell’utilizzo dell’operatore logico “o” nel confronto per verificare l’uguaglianza dei numeri giocati con ogni singolo estratto. E’ stata fatta questa scelta per ridurre il numero delle condizioni che altrimenti sarebbero state tre. Per comprendere ancora l’utilizzo delle matrici sia dato il seguente problema: data una matrice quadrata di dimensione n i cui elementi sono interi dopo aver inserito i dati calcolare la somma della diagonale principale (per intenderci gli elmenti che hanno stessa coordinata di riga e di colonna). La tabella dati dell’algoritmo che segue sarà:
classe | nome e descrizione | tipo |
input | mat matrice di dimensione n | tipo matrice n per n di interi |
input | \n numero di righe e colonne della matrice | intero |
interne | i,j indici della matrice | interi |
output | somma | intera |
L’algoritmo sarà:
- Inizio
- somma=0 // inizializzazione
- scrivi “dammi il numero delle righe e delle colonne”
- leggi n
- per i=1 a n esegui
- ciclo 1
- per j=1 a n esegui
- ciclo 2
- scrvi “dammi elemento di riga “,i,” colonna “,j
- leggi mat[i][j]
- fine ciclo 1
- fine ciclo 2
- per i= 1 a n esegui
- ciclo 3
- somma=mat[i][j]+somma
- fine ciclo 3
- scrivi “la somma degli elementi della diagonale è:”
- scrivi somma
- fine
Come si può notare dall’algoritmo nel calcolare la somma è stato necessario un solo ciclo, perché gli elementi di diagonale principale hanno la caratteristica di avere indice di riga e colonna uguali. Nelle matrici si definisce anche la diagonale secondaria come gli elementi della matrice che partono dall’elerecord-e-tabellemento di riga 1 e colonna n e arrivano all’elemento di riga n e colonna 1 passando per l’elemento caratterizzato dall’avere coordinata di riga e colonna uguali. Un algoritmo molto più complesso del precedente potrebbe essere quello di calcolare la somma degli elementi di diagonale secondaria attraverso sempre l’uso dei cicli di una matrice di ordine n. In questo caso basta osservare che gli elementi di diagonale secondaria sono caratterizzati dal fatto che la somma degli indici è pari alla dimensione della matrice che ricordo essere quadrata aumentata di un’unità.
3 | 2 | 0 |
1 | 2 | 6 |
5 | 5 | 7 |
In questa matrice 3 per 3 sopra rappresentata si nota che i valori 0,2 e 5 sono caratterizzati dal fatto che la somma dei loro indice è pari sempre a 4, ma se la dimensione della matrice è 3 vuol dire che il tutto è aumentato di un’unità. L’algoritmo pertanto è:
somma=0
- Inizio
- scrivi “dammi la dimensione”
- leggi n
- per i = 1 a n esegui
- ciclo 1
- per j=1 a n esegui
- ciclo 2
- scrivi “dammi gli elementi della matrice”
- leggi mat[i][j]
- fine ciclo 1
- fine ciclo 2
- se n è pari allora
- per i= 1 a n esegui
- ciclo 1
- per j=n 1 esegui
- ciclo 2
- se i+j=n+1 allora
- somma=somma + mat[i][j]
- fine ciclo 1
- fine ciclo 2
- altrimenti //n è dispari
- per i= 1 a n esegui
- ciclo 1
- per j=n a 1 esegui
- ciclo 2
- se i+j=n+1 allora
- somma=somma + mat[i][j]
- fine ciclo 1
- fine ciclo 2
- scrvi “la somma è”, somma
- fine
Record e tabelle
Quanto le informazioni da gestire sono di tipo diverso allora è opportuno definire delle strutture di dati eterogenee dette record. Un record è una variabile strutturata astratta identificata da un nome collettivo i cui elementi sono di tipo diverso. Ogni componente è detta campo. Un insieme di record raggruppati in un vettore ovvero un vettore di record è detta tabella. La prima fase di analisi del problema che coinvolgono i record è la definizione del tracciato record che indica i campi che costituiscono il record la loro tipologia e dimensione. Ad esempio supponiamo che dato un elenco di alunni di una classe si vuole visualizzare i dati relativi ai maggiorenni. Possiamo pertanto definire un tracciato record come segue:
Cognome | Nome | Età |
Stringa * 16 caratteri | Stringa * 16 Caratteri | Intero |
Nome Record A |
Abbiamo definito il tracciato record con nome modello A e campi cognome, nome, età con i loro tipi. Si definisce modello una struttura dati astratta definita dall’utente infatti nella fase di dichiarazione delle variabili si definisce una variabile di tipo tabella formata da righe di tipo A. Il record così come la tabella sono variabili ad accesso diretto ovvero la selezione di un elemento avviene indicando direttamente il nome del campo preceduto dal nome del record separato dal carattere “.”. Quindi A.Nome richiama il campo nome del record A. Vediamo la tabella delle variabili per il problema posto.
Classe | Nome | Tipo |
Input | tabella | vettore di N elementi di tipo A |
Input | N | intero |
Interno | K,NC,C | Intero, Stringa*16, Stringa*16 |
Output | tabella | vettore di N elementi di tipo A |
L’algoritmo per comodità verrà frammentato in due procedure carica e visualizza.
- Inizio carica
- Scrivi “Dammi il numero degli alunni”
- Leggi N
- Ciclo 1
- Per k=1 a N esegui
- Scrivi “Inserisci il nome”
- Leggi tabella(k).nome
- Scrivi “Inserisci il cognome”
- Leggi tabelle[k].cognome
- Scrivi “Inserisci età”
- Leggi tabella[k].eta
- Fine ciclo 1
- Fine Carica
- Inizio Visualizza
- NC=””
- C=””
- Ciclo 1
- Per k=1 a N esegui
- Se tabella[k].eta >= 18 allora
- NC=tabella[k].nome
- C=tabella[k].cognome
- Scrivi NC
- Scrivi C
- Fine Se
- Fine Ciclo
- Fine
Il programma principale è pertanto costituito dalla chiamata delle due procedure.
- Inizio
- Carica
- Visualizza
- Fine
Un altro esempio può essere dato dall’ordinamento di una tabella secondo un criterio prestabilito ovvero in ordine alfabetico di nome, cognome o età. Gli algoritmi di ordinamento sono simili a quelli utilizzati per i vettori ovvero ordinamento sequenziale o a bolle.
Video n.1
video n.2
Video n.3