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 è:

1. Inizio
2. Per i= 1 a 10 esegui
3. ciclo
4. scrivi “dammi elemento”
5. leggi b[i]
6. fine ciclo
7. 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:

1. Per i=1 a 5 esegui
2. ciclo
3. temp=a[i]
4. a[i]=a[2i]
5. a[2i]=temp
6. fine ciclo
7. 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à:

1. inizio
2. cont=0
3. scrivi “inserisci l’elemento da cercare”
4. leggi num
5. Per i=1 a 10 esegui
6. ciclo
7. se a[i]=num allora
8. cont=cont+1
9. fine ciclo
10. scrivi “il numero di volte che si ripete il valore inserito è: ” ,num
11. 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 è:

1. inizio
2. scrivi “dammi il valore da cercare”
3. leggi valore
4. trovato=falso // sto utilizzando una variabile logica
5. sinistro=1
6. destro=10 // o la dimensione del vettore
7. centro=(sinistro + destro)/2
8. ripeti
9. Se a[sinistro]=valore o a(destro)=valore o a(centro)=valore allora
10. trovato=vero
11. altrimenti
12. se a[centro]<valore allora
13. sinistro=centro+1
14. altrimenti
15. destro=centro-1
16. finché trovato=vero o sinistro>destro
17. Se trovato=vero allora
18. scrivi “valore trovato all’interno del vettore”
19. altrimenti
20. scrivi “valore non trovato”
21. 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à:

1. procedura carica_città
2. inizio
3. per i=1 a 5 esegui
4. ciclo
5. scrivi “dammi il nome della città”
6. leggi cit[i]
7. fine ciclo
8. fine carica_città
9. procedura carica_redditi
10. inizio
11. per i= 1 a 5 esegui
12. ciclo
13. scrivi “inserisci il reddito per abitante”
14. leggi reddito[i]
15. fine ciclo
16. fine carica_redditi
17. procedura calcola
18. max=0
19. cit_max=””
20. per i=1 a 5 esegui
21. se redditi[i]> max allora
22. max=redditi[i]
23. cit_,max=cit[i]
24. fine ciclo
25. scrivi “la città con reddito più alto è”
26. scrivi cit_max
27. scrivi “con reddito per abitante di “
28. scrivi max
29. 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.

1. inizio
2. somma=0
3. media=0
4. scrivi “dammi il numero degli alunni”
5. leggi n
6. per i=1 a n esegui
7. ciclo 1
8. per j=1 a 8 esegui
9. ciclo 2
10. scrivi “dammi il voto dell’alunno”,i,”-mo”
11. leggi voti[i][j]
12. fine ciclo 2
13. fine ciclo 1
14. per i=1 a n esegui
15. ciclo 1
16. per j=1 a 8 esegui
17. ciclo 2
18. somma=somma+voti(i,j)
19. fine ciclo 2
20. media=somma/8
21. scrivi voti[i][h]
22. somma=0 //queste due righe sono necessarie per ricominciare il calcolo della media//
23. media=0
24. fine ciclo 1
25. 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 è:

1. inizio
2. cont=0
3. somma=0
4. per i= 1 a 4 esegui
5. ciclo 1
6. per j=1 a 5 esegui
7. ciclo 2
8. scrivi “dammi i numeri estratti su tutte le ruote”
9. leggi lotto[i][j]
10. fine ciclo 2
11. fine ciclo 1
12. scrvi “dammi i numeri giocati”
13. leggi n1,n2,n3
14. per i=1 a 4 esegui
15. ciclo 1
16. per j=1 5 esegui
17. ciclo 2
18. se lotto(i,j)=n1 o lotto[i][j]=n2 o lotto[i][j]=n3 allora
19. cont=cont+1
20. fine ciclo 2
21. se cont=1 allora
22. somma=somma+5*5
23. se cont=2 allora
24. somma=somma+5*10
25. se cont=3 allora
26. somma=somma +5*50
27. cont=0
28. fine ciclo 1
29. se somma =o allora
30. scrivi “non hai vinto niente”
31. altrimenti
32. scrivi “hai vinto €” , somma
33. 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à:

1. Inizio
2. somma=0 // inizializzazione
3. scrivi “dammi il numero delle righe e delle colonne”
4. leggi n
5. per i=1 a n esegui
6. ciclo 1
7. per j=1 a n esegui
8. ciclo 2
9. scrvi “dammi elemento di riga “,i,” colonna “,j
10. leggi mat[i][j]
11. fine ciclo 1
12. fine ciclo 2
13. per i= 1 a n esegui
14. ciclo 3
15. somma=mat[i][j]+somma
16. fine ciclo 3
17. scrivi “la somma degli elementi della diagonale è:”
18. scrivi somma
19. 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

1. Inizio
2. scrivi “dammi la dimensione”
3. leggi n
4. per i = 1 a n esegui
5. ciclo 1
6. per j=1 a n esegui
7. ciclo 2
8. scrivi “dammi gli elementi della matrice”
9. leggi mat[i][j]
10. fine ciclo 1
11. fine ciclo 2
12. se n è pari allora
13. per i= 1 a n esegui
14. ciclo 1
15. per j=n 1 esegui
16. ciclo 2
17. se i+j=n+1 allora
18. somma=somma + mat[i][j]
19. fine ciclo 1
20. fine ciclo 2
21. altrimenti //n è dispari
22. per i= 1 a n esegui
23. ciclo 1
24. per j=n a 1 esegui
25. ciclo 2
26. se i+j=n+1 allora
27. somma=somma + mat[i][j]
28. fine ciclo 1
29. fine ciclo 2
30. scrvi “la somma è”, somma
31. 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.

1. Inizio carica
2. Scrivi “Dammi il numero degli alunni”
3. Leggi N
4. Ciclo 1
5. Per k=1 a N esegui
6. Scrivi “Inserisci il nome”
7. Leggi tabella(k).nome
8. Scrivi “Inserisci il cognome”
9. Leggi tabelle[k].cognome
10. Scrivi “Inserisci età”
11. Leggi tabella[k].eta
12. Fine ciclo 1
13. Fine Carica

1. Inizio Visualizza
2. NC=””
3. C=””
4. Ciclo 1
5. Per k=1 a N esegui
6. Se tabella[k].eta >= 18 allora
7. NC=tabella[k].nome
8. C=tabella[k].cognome
9. Scrivi NC
10. Scrivi C
11. Fine Se
12. Fine Ciclo
13. 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