Un nuovo tipo di dati

Gli array

Supponiamo di essere in questa situazione

Vogliamo memorizzare 1000 valori per poterli manipolare in momenti diversi

Non è possibile pensare a dichiarare 1000 variabili

Pensate solo a scrivere l’istruzione che le somma tutte

Allora come possiamo fare?

Dobbiamo utilizzare una struttura dati.

Un dato strutturato è un tipo di dato che attraverso una sola dichiarazione di una sua variabile possiamo memorizzare più dati contemporaneamente.

Vi sono strutture dati omogenee ed eterogenee

Oggi studiamo quelli appartenenti alla prima classe

I vettori

I vettori

Sono strutture dati i cui elementi sono tutti dello stesso tipo

I dati in essi contenuti possono essere semplici o strutturati

Essi sono caratterizzati da:

La dimensione che indica quanti elementi possono contenere

Il nome

Il tipo cioè il tipo di dati che possono contenere

L’indice indica il particolare elemento a cui vogliamo fare riferimento

I vettori

Graficamente essi sono così rappresentati

2 34 10 25 -16 2 99 1001 7 4

Questo è un vettore di interi

Come vedete esso contiene valori numerici di tipo int

Ha dimensione 10

Può contenere valori uguali

È residente in memoria centrale e pertanto deve essere inizializzato come tutte le variabili

Ecco due esempi di vettori di char

‘a’ ‘b’ ‘c’ ‘d’ ‘d’ ‘e’ ‘f’ ‘h’ ‘z’ ‘q’

‘0’ ‘1’ ‘a’

I vettori

Dichiarazione di un vettore in C++

Le regole sono:

<Tipo_dati>< nome_variabile>[<dimensione>]

Alcuni esempi

int vett[10];

char nome[20];

const int DIM=30;

float classe[DIM];

bool a[15];

I vettori

Come inserire i dati in un vettore?

Gli esempi proposti fanno tutti riferimento a vettori di tipo intero di dimensione DIM =10, indice intero i, ma si possono estendere a vettori di altri tipi.

Inizializzazione di un vettore v

In modo statico valido per tutte le esecuzioni del programma a livello di dichiarazione

Int v[DIM]={0};

Azzera tutti gli elementi del vettore

Int v[DIM]={1,3,5,67,34,0,57,12,901,1024};

Attribuisce al vettore v sempre gli stessi valori di partenza

I vettori

Per accede ad un elemento del vettore devo utilizzare un indice

L’indice è generalmente di tipo intero al più enumerativo come i char o color

L’indice parte da 0 e assume valore massimo dimensione del vettore -1

Cioè se un vettore ha dimensione 10 l’indice assume i valori da 0 a 9

L’indice non può mai essere di tipo float perché indica la posizione all’interno del vettore

Dichiarato il seguente vettore

int vett[20];

int i;

Se voglio stampare a schermo il terzo elemento del vettore scriverò

cout<<vett[2]

I vettori

Inizializzazione di un vettore in modo dinamico e differente per ogni esecuzione

for (int i=0;i<DIM;i++)

v[i]=rand()%1001;

// inserisce in modo casuale nel vettore numeri positivi compresi tra 0 e 1000

for (int i=0;i<DIM;i++)

cin>>v[i];

// inserisce valori dati in input da tastiera

Per visualizzare tutti gli elementi

for (int i=0;i<DIM;i++)

cout<<v[i];

I vettori

Per modificare un elemento

cout <<“inserire la posizione dell’elemento da modificare la prima è 0”;

cin>> i;

cout<<“inserire il valore”;

cin>>v[i];

I vettori

Il seguente frammento di codice somma tutti gli elementi del vettore v

int s=0;

for (int i=0;i<DIM;i++)

s=s+v[i];

Mentre il seguente somma solo quelli di posto pariint s=0;for (int i=0;i<DIM/2;i++) s=s+v[2*i];

I vettori

esercizio

Cosa fa questo codice?

int m=v[0];for (int i=1;i<DIM;i++){ if (m<v[i]) m=v[i]; }cout<<m;

Calcola il valore massimo contenuto nel vettore

I vettori

Come si passa un vettore come parametro ad una procedura?

Supponiamo che si vogliano creare due vettori a e b il primo lungo 20 e il secondo lungo 30: si vuole utilizzare un’unica procedura per la creazione, e stampa dei due vettori.

Proponiamo il seguente codice

#include <cstdlib>#include <iostream>using namespace std;int a[20],b[30];void carica(int v[], int dim);void stampa(int v[], int dim);int main(int argc, char *argv[]){ cout<<"inserire i valori del vettore a essi sono 20"<<endl; carica (a,20); cout<<"inserire i valori del vettore b essi sono 30"<<endl; carica (b,30); cout<< "ecco il vettore a "<<endl; stampa (a,20); cout<< "ecco il vettore b "<<endl; stampa (b,30); system("PAUSE"); return EXIT_SUCCESS;}void carica(int v[], int dim){ for(int i=0;i<dim;i++) cin>>v[i]; return;}void stampa(int v[], int dim){ for(int i=0;i<dim;i++) cout<<v[i]<<" "; return;

}

I vettori: la ricerca

Costruiamo una funzione che verifica se un valore è presente nel vettore

bool ricerca (int v[],int dim,int x){

bool t=false;for (int i=0;i<dim;i++){ if (x==v[i]) t=true; }return t; }

Questo algoritmo ha una complessità computazionale pari alla dimensione del vettore e si dice che complessità O(n) dove n indica la lunghezza del vettore questo vale anche se l’elemento da ricercare è nella prima posizioneSi può migliorare?Vediamo come

I vettori: la ricerca

bool ricerca2 (int v[],int dim,int x){

bool t=false;

Int i=0;while (i<dim && t==false){ if (x==v[i]) t=true;i++; }

return t; }

Questo algoritmo ha una complessità computazionale O(n/2)Si può migliorare?Se il vettore è ordinato:ovviamente per ottenere un guadagno il termini di tempo di computazione il numero delle ricerche deve essere notevolmente maggiore rispetto all’ordinamento.

I vettori: l’ordinamento

Ordinamento per scambio è l’algoritmo più elementare ma anche il più lento:

Esso consiste nel ricercare l’elemento più piccolo da inserire nella prima posizione, poi riesegue la ricerca perla seconda e così via

void ordinaperscambio (int v[],int dim){for (int i=0;i<dim-1;i++) for (int j=i+1;j<dim;j++) if (v[i]>v[j]) scambia(v[i],v[j]);return ;}void scambia(int &a,int &b){int c; c=a; a=b; b=c;return;}La sua complessità algoritmica è n(n-1)/2 cioè O(n2) sempre.

I vettori: l’ordinamento

Ordinamento a bolle consiste nel confrontare elementi consecutivi del vettore in modo tale che i valori più alti si spostano in coda al vettore: i confronti si ripetono finchè ci sono scambi:si sfrutta il preordinamento.

void ordinaabolle (int v[],int dim){

Int k=dim-1; bool scambio=true; while (scambio==true){ scambio=false; for (int j=0;j<k;j++){ if (v[j]>v[j+1]) { scambia(v[j],v[j+1]); scambio=true; } }k--;}return;}

I vettori: l’ordinamento

Ordinamento per inserimento consiste nell’ordinare il vettore come si ordinano in mano un mazzo di carte: partendo dal secondo elemento si fanno scivolare all’indietro tutti gli elementi minori

void ordinaperinserimento (int v[],int dim){

Int k; for(int i=1;i<dim;i++){ k=i-1; while(k>=0 && v[k]>v[k+1]){ scambia(v[k],v[k+1]); k--; } }return;}

I vettori: la ricerca ordinata

Se il vettore è ordinato allora l’algoritmo di ricerca migliora e diventa

bool ricercaordinata (int v[],int dim,int x){bool t=false;Int i=0;while (i<dim && t==false && v[i]<=x){ if (x==v[i]) t=true;i++; }

return t; }

I vettori: la ricerca binaria

Sfruttando l’ordinamento dei vettori questa ricerca funziona come l’elenco telefonico: si divide il vettore a metà e si sceglie quella parte il cui intervallo dei valori appartiene all’elemento da cercare finchè si trova l’elemento e i due estremi dell’intervallo coincidono.

void ricercabinaria (int v[],int dim,int x ){ int centro, primo=0, ultimo=dim-1;bool t=false;while (primo<=ultimo && t==false){ centro=(primo+ultimo)/2; if (v[centro]==x) t=true; else if (v[centro]<x) primo=centro+1; else ultimo=centro-1;}return t;}