Indice dei contenuti
- Record e Tabelle definizioni generali
- Algoritmi di esempio in flow chart e pseucodice
- Uso di tabelle in C++ dettagli di programmazione
Tabelle e Record
Nella programmazione quando si devono memorizzare grosse quantità di dati nella memoria centrale del calcolatore è opportuno definire delle strutture dati astratte costituite da una raccolta di tipi semplici aggregati attraverso un nome collettivo e identificati da un indice. Ad esempio la gestione di una rubrica telefonica può essere ottenuta definendo per ciascun soggetto il nome, cognome, l’indirizzo e il numero di telefono. Se i soggetti sono molti ad esempio già in numero superiore a 10, la gestione di queste informazioni diventa gravosa e pertanto si conviene organizzare tali informazioni in una struttura di tipo tabella in cui ogni riga costituisce il recapito telefonico di un soggetto. Una struttura dati di questo tipo in memoria centrale è detta appunto tabella, su memoria di massa (su un unità di memorizzazione tipo disco fisso, unità a dischetti) è detto file.
Per poter definire una tabella è importante definire la struttura dati elementare di cui è costituita la tabella: il record. Un record è una variabile strutturata eterogenea composta da elementi di tipo diverso e identificata da un nome collettivo. Ad esempio nell’esempio precedente si può definire un record di nome “recapito”. Le componenti del record sono detti campi. E’ utile quando si definisce in un algoritmo e quindi programma un record definire un modello di tale struttura che dia informazioni anche sulla dimensione del record (dimensione logica). La dimensione logica di un record è la somma delle dimensioni di tutte le dimensioni dei campi che formano il record stesso. Inoltre alcuni campi come quelli alfanumerici sono definiti dall’utente altri come quelli numerici hanno dimensioni prefisssate e la loro dimensione varia a seconda del linguaggio di programmazione in cui si codifica l’algoritmo. Ipotizzando che i numeri interi si rappresentano con interi di 2 o 4 byte a massimo e che i numeri reali da 4 a 16 byte non è difficile calcolare la dimensione logica del record.
Infatti ogni carattere alfanumerico in base alla sua codifica ASCII occupa lo spazio di un solo byte o di almento due byte nella rappresentazione Unicode. Nell’esempio introduttivo se ne rappresenta il tracciato record che è una rappresentazione formale della struttura dati (modello) che il programmatore definisce.
Nell’esempio proposto il tracciato record è:
| Recapito | |||
| Cognome | Nome | Indirizzo | Telefono |
| 15 caratteri | 15 caratteri | 50 caratteri | 10 caratteri |
| Dimensione logica 90 caratteri = 90 byte in codifica ASCII 8 bit o 180 in codifica Unicode |
Poiché il programmatore nel problema ha necessità di avere più record dello stesso tipo allora si definisce una tabella una variabile strutturata identificata da un nome collettivo in cui ogni singolo record è individuato da un indice intero.
Selezione di un campo specifico in un record e di un campo specifico nella tabella.
L’operazione di selezione di un campo specifico all’interno di un record avviene secondo la nomenclatura nome-record.nome-campo ad esempio se nel record “recapiti” si vuole selezionare il campo “indirizzo” si scriverà recapiti.indirizzi. In una tabella se si vuole selezionare del decimo decimo record il campo “telefono” la nomenclatura adottata ipotizzando che il nome della tabella sia “tb” e l’indice della tabella e/o vettore di record i:
tb(10).telefono
Come esempio poniamo il seguente problema dato una tabella di N record del tipo “recapito” caricare la tabella.
L’utente inserisci a richiesta il numero dei contatti che devono essere inseriti nella tabella.
Un ipotesi
| Classe | Nome | Tipo |
| Input | tb | tabella di 100 elementi di tipo record |
| Input | N | Intero |
| interno | k | intero indice della tabella |
Non ci sono output perché l’algoritmo ci chiede solo di caricare la tabella. La variabile r viene definita a partire dal modello. In fase di codifica si definisce prima un tipo dati (il nostro modello) e poi in seguito una variabile strutturata a partire dal tipo definito.
- Inizio
- scrivi “Quanti contatti vuoi inserire ?”
- leggi N
- Ciclo k= 1 a N
- scrivi “dammi il cognome”
- leggi tb(k).cognome
- scrivi “dammi il nome”
- leggi tb(k).nome
- scrivi “dammi l’indirizzo”
- leggi tb(k).indirizzo
- scrivi “dammi telefono”
- leggi tb(k).telefono
- fine ciclo
- Fine
Il Flow chart del nostro algoritmo è:
Utilizzo di strutture dati di tipo Record in C++
L’uso di tabella in C++ come strutture dati statiche avviene utilizzando le dichiarazioni di tipo. Infatti poichè il record per sua definizione è una struttura dati eterogenea definita dall’utente; è opportuno prima dichiarare la struttura come modello e poi utilizzare quel modello come tipo di variabile.
In altri temini si definisce il tipo di record con la seguente dichiarazione:
struct nome {
tipo nome;
tipo nome;
…..
tipo nome: };
Notare il punto e virgola dopo le parentesi graffe.
Dopo aver dichiarato la struttura del record, nella dichiarazione delle variabili si definisce un array che come tipo di variabile è proprio del tipo record dichiarato in precedenza.
L’algoritmo in C++ utilizzando il procedimento top-down senza parametri è:
#include <iostream>
#include <string>
using namespace std;
struct recapito {
char cognome[15];
char nome[15];
char indirizzo[30];
char telefono[10];
};
int n; // Numero contatti dato di input//
recapito tb[100]; // definisco una tabella di 100 record di tipo recapito //
// definizione procedura carica dati tabella //
void carica();
int main()
{
cout << “\n Inserisci il numero dei contatti\t”;
cin >> n;
carica();
return 0;
}
void carica()
{ int k;
for (k=0;k<n;k++)
{
{getchar();
cout << “\n Inserisci il cognome\t”;
cin.getline(tb[k].cognome,15);
cout << “\n Inserisci il nome \t”;
cin.getline(tb[k].nome,15);
cout << “\n Inserisci indirizzo \t”;
cin.getline(tb[k].indirizzo,30);
cout << “\n Insrisci il numero di teleofno\t”;
cin.getline(tb[k].telefono,10);
cout << “Premi un tasto per continuare”;
}}
}
}
Osservazioni sulla codifica in C++
Ogni programma, è conveniente quando deve eseguire più compiti, scomporlo in sottoprogrammi.
Per fare questo ogni compito del programma può essere associato ad un sottoprogramma. I sottoprogrammi sono dichiarati come prototipi subito dopo le dichiarazioni delle variabili globali, e dopo l’intestazione del programma (le sezioni che includno le librerie e altre clausole dichiarative). In seguito il main o funzione principale e poi l’implementazione dei sottoprogrammi dichiarati nella parte di prototipazione.
Possiamo riassumere la struttura di un programma in sotto programmi secondo questo schema:
Problematiche di sicurezza del codice:
Questo listato non protegge da attacchi buffer overflow sulle stringhe; infatti se l’utente supera il numero ei caratteri indicati nella getline i dati inseriti nelle stringhe successive saranno sovrascritti alterando il loro contenuto.
Una soluzione può essere quella di realizzare una piccola funzione che legga carattere per carattere i dati di input fin quando l’utente non digita il tasto invio.
La funzione potrebbe essere così scritta:
void leggi(char input[],int l)
{
int k=0;
while (( input[k!=’\n’) && (k<l)
{
input[k]=getchar();
k++;
}
}
Intestazione
Dichiarazione modelli dati e variabili globali
Prototipi delle funzioni
int main() // Programma principale
Implementazione delle funzioni
Nel programma proposto sono state utilizzate le funzionni getchar() e getline che consentono un pieno controllo delle stringhe. La prima riceve in input un carattere anche una spaziatura, la seconda assicura che la variabile stringa anche se contiene spaziature sia integralmente inserita nella variabile di una lunghezza pari al secondo argomento della istruzione ad esempio
getline(variabile stringa,30);
consentirà all’utente l’input di una variabile di massimo 29 caratteri comprese le spaziature; da notare che l’ultimo carattere è utilizzato come terminatore di stringa “\0”.
La prima funzione quindi assicura che la prima spaziatura non sia l’input della prima istruzione di input del programma.
Funzione di ricerca
Come secondo esempio, è stata realizzata una funzione che prevede la ricerca per cognome all’interno della tabella.
Nel caso di tabelle con pochi record qualunque funzione di ricerca sia realizzata è accettabile in termini di progamma e velocità di esecuzione. Nel caso in cui la tabella contiene molti record ad esempio la tabella sia il risultato di un caricamento di un file con migliaia di dati, occorre pensare bene all’algoritmo che può risolvere il problema. Questo perché potrebbe essere che l’algoritmo e poi il relativo programma che lo implementa potrebbe snon fornre la soluzione a causa di un elevata complessità computazionale.
La complesità computazionale è una parte importante dell’informatica che stdua come rendere gli algoritmi e le strutture dati ottimizzate per problemi di enorme complessità.
Nel prossimo sotto programma occorre utilizzare una funzione delle stringhe strcmp che confronta due stringhe e indica se le stringhe comparate sono uguali carattere per carattere oppure diverse. Questa funzione disponibile attraverso le librerie delle stringhe C o del tipo string del C++ aumentano di molto i tempi di esecuzione del programma per grandi quantità di dati.
Nella nostra soluzione scriviamo una funzione ausiliaria che svolgerà proprio lo stesso compito ma con una maggiore velocità di esecuzione. E’ chiaro che anche la funzione che effettua la ricerca dovrebbe essere ottimizzata, per ora ci accontentiamo di scrivere la funzione di compotrazione in modo ottimale.
Ora all’esercizio svolto realizzare una procedura per la rcierca di un nominativo specifico. Alla tabella dati si deve aportare la seguente variazione:
| Classe | Nome | Tipo |
| input | cognome1 | stringa 15 caratteri |
| input | tb | tabella di 10 elementi di tipo r |
| interno | k,trovato | intero indice della tabella, variabile che vale 1 se il nominativo è trovato 0 in caso contrario |
| output | nominativo | record di tipo recapito |
L’algoritmo associato alla procedura di ricerca è:
Inizio cerca
k=1
trovato= 0
Scrivi "dammi il cognome della persona da cercare"
Leggi cognome1
Mentre tb(k).cognome <>""
Se confronto(tb[k].cognome,cognome1)=0
trovato=1
scrivi nominativo.nome
scrivi nominativo.cognome
scrivi nominativo.telefono
scrivi nominativo.indirizzo
esci dal sotto programma
Fine Se
k=k+1
Fine ciclo
Se trovato = 0 allora
scrivi "nominativo non trovato"
Fine Se
FineLa relativa codifica in C++ sempre a livello di procedura senza parametri è:
int confronta(char a[],char b[])
{
int i;
for (i=0;a[i]==b[i];i++)
if (a[i]==0) return 0;
return a[i]-b[i];
}
void cerca()
{
char cognome1[15];
int k=0;
int trovato=0;
cout << "\n Inserisci il cognome da cercare\n";
cin.getline(cognome1,15);
while (tb[k].cognome[0]|='\0')
{
if (confronta(tb[k].cognome,cognome1)==0)
{
trovato=1;
cout << "\n Dati Trovati\n";
cout << "\nCognome:\t"<< tb[k].cognome;
cout << "\nNome:\t"<< tb[k].nome;
cout << "\nIndirizzo:\t"<< tb[k].indirizzo;
cout << "\nTelefono;\t"<< tb[k].telefono;
return;
}
k++;
}
if (trovato==0)
cout << "\n Nono sono stati individuati dati corrispondenti al criterio richiesto\n";
}Indice dei contenuti
- Record e Tabelle definizioni generali
- Algoritmi di esempio in flow chart e pseucodice
- Uso di tabelle in C++ dettagli di programmazione
Tabelle e Record
Nella programmazione quando si devono memorizzare grosse quantità di dati nella memoria centrale del calcolatore è opportuno definire delle strutture dati astratte costituite da una raccolta di tipi semplici aggregati attraverso un nome collettivo e identificati da un indice. Ad esempio la gestione di una rubrica telefonica può essere ottenuta definendo per ciascun soggetto il nome, cognome, l’indirizzo e il numero di telefono. Se i soggetti sono molti ad esempio già in numero superiore a 10, la gestione di queste informazioni diventa gravosa e pertanto si conviene organizzare tali informazioni in una struttura di tipo tabella in cui ogni riga costituisce il recapito telefonico di un soggetto. Una struttura dati di questo tipo in memoria centrale è detta appunto tabella, su memoria di massa (su un unità di memorizzazione tipo disco fisso, unità a dischetti) è detto file.
Per poter definire una tabella è importante definire la struttura dati elementare di cui è costituita la tabella: il record. Un record è una variabile strutturata eterogenea composta da elementi di tipo diverso e identificata da un nome collettivo. Ad esempio nell’esempio precedente si può definire un record di nome “recapito”. Le componenti del record sono detti campi. E’ utile quando si definisce in un algoritmo e quindi programma un record definire un modello di tale struttura che dia informazioni anche sulla dimensione del record (dimensione logica). La dimensione logica di un record è la somma delle dimensioni di tutte le dimensioni dei campi che formano il record stesso. Inoltre alcuni campi come quelli alfanumerici sono definiti dall’utente altri come quelli numerici hanno dimensioni prefisssate e la loro dimensione varia a seconda del linguaggio di programmazione in cui si codifica l’algoritmo. Ipotizzando che i numeri interi si rappresentano con interi di 2 o 4 byte a massimo e che i numeri reali da 4 a 16 byte non è difficile calcolare la dimensione logica del record.
Infatti ogni carattere alfanumerico in base alla sua codifica ASCII occupa lo spazio di un solo byte o di almento due byte nella rappresentazione Unicode. Nell’esempio introduttivo se ne rappresenta il tracciato record che è una rappresentazione formale della struttura dati (modello) che il programmatore definisce.
Nell’esempio proposto il tracciato record è:
| Recapito | |||
| Cognome | Nome | Indirizzo | Telefono |
| 15 caratteri | 15 caratteri | 50 caratteri | 10 caratteri |
| Dimensione logica 90 caratteri = 90 byte in codifica ASCII 8 bit o 180 in codifica Unicode |
Poiché il programmatore nel problema ha necessità di avere più record dello stesso tipo allora si definisce una tabella una variabile strutturata identificata da un nome collettivo in cui ogni singolo record è individuato da un indice intero.
Selezione di un campo specifico in un record e di un campo specifico nella tabella.
L’operazione di selezione di un campo specifico all’interno di un record avviene secondo la nomenclatura nome-record.nome-campo ad esempio se nel record “recapiti” si vuole selezionare il campo “indirizzo” si scriverà recapiti.indirizzi. In una tabella se si vuole selezionare del decimo decimo record il campo “telefono” la nomenclatura adottata ipotizzando che il nome della tabella sia “tb” e l’indice della tabella e/o vettore di record i:
tb(10).telefono
Come esempio poniamo il seguente problema dato una tabella di N record del tipo “recapito” caricare la tabella.
L’utente inserisci a richiesta il numero dei contatti che devono essere inseriti nella tabella.
A questo punto la funzione confronta restituisce 0 se le stringhe sono uguali e un valore diverso da zero in caso contrario, in particolare valori negativi indicano che la prima stringa precede la seconda nell’ordinamento alfabetico secondo il codice ASCII, mentre se il valore è positivo la prima stringa è successiva alla prima.
Se durante la ricerca il confronto da esito positivo nel senso che è soddisfatto che il valore di ritorno della funzione è zero, allora è stato travto il record interessato e dopo la stampa è possibile uscire dal sotto programma.
Sono state realizzate due procedure una per il caricamento della tabella, e uno per la ricerca dei dati della tabella. La variabile trovato serve nella procedura di ricerca per vedere se il nominativo è presente nella tabella. La ricerca svolta in questa procedura è di tipo sequenziale in quanto la tabella, non è ordinata. Un’altra importante modifica è l’utilizzo dell’istruzione geline prevista dalla libreria iostream per la gestione di inserimento di stringhe con caratteri speciali.