Riassunto esame Fondamenti di Informatica, prof. Sernani, libro consigliato Fondamenti di programmazione in C++, Aguilar

Capitolo 11. Vettori e Strutture

Figura 11.1: allocamento in memoria degli elementi di un vettore.

Assegna 400 alla variabile n.

Se, invece, si vuole conoscere la dimensione di un elemento individuale dell'array, si può scrivere: n = sizeof(numeri[14]);

11.4 Limiti dei vettori

I vettori hanno alcuni limiti, tra cui:

1. NO operazioni di confronto.
2. NO operazioni aritmetiche.
3. NO operazione di assegnamento sull'intero vettore (solo inizializzazione).
4. NO restituzione di vettori da funzioni.

Tuttavia, per quanto riguarda il limite 2), cioè che non si possono effettuare operazioni aritmetiche, c'è un'osservazione da fare.

11.4.1 Offset tra due vettori

Tra due vettori non è possibile effettuare un'addizione, un prodotto o un quoziente; tuttavia possiamo effettuare la sottrazione tra due vettori (anche tra due puntatori dal momento che un vettore è un puntatore che punta all'indirizzo di memoria del primo elemento). Il risultato

La sottrazione tra due vettori (o puntatori) è il loro "offset", cioè la "distanza" in celle di memoria tra loro due. Ad esempio:

int vett1[] = {1, 2, 3};
int vett2[] = {4, 5, 6};
cout << vett2 - vett1 << endl;

stamperà a schermo il valore 3, perché la cella di memoria del primo elemento di vett2 è distante 3 celle di memoria da quella del primo elemento di vett1.

N.B.: stiamo parlando di due vettori presi interamente, non di ogni elemento preso singolarmente.

Programmazione in C++ CAPITOLO 11. VETTORI E STRUTTURE

Nella sottrazione i due vettori (o puntatori) di cui si vuole calcolare l'offset devono essere dello stesso tipo.

N.B.:

11.5 Stringhe

In C++ una stringa di testo è un vettore di caratteri che termina con il carattere nullo (\0).

Senza il carattere nullo finale, la stringa non è tale ma rimane un semplice vettore di char.

Una stringa può essere definita in uno dei modi presenti nei seguenti

Esempi:

char stringa[] = {'P', 'r', 'o', 'v', 'a', '\0'};
char stringa[6] = "Prova"; // In questi casi il carattere nullo viene inserito
char stringa[] = "Prova"; // automaticamente dal compilatore

11.5.1 Stringhe e I/O

Il carattere nullo serve all'operatore di inserimento perché, trovandosi davanti ad un array di char, sa di dover leggere in memoria ogni singolo suo elemento in locazioni di memoria contigue, fino a che non trova una locazione di memoria in cui c'è il carattere nullo. Infatti, se ad esempio definissimo una stringa senza il carattere nullo finale e se definissimo subito dopo delle variabili di tipo char a cui assegniamo dei caratteri; allora l'operatore di inserimento continuerebbe a leggere e stampare i caratteri che si trovano anche dopo il vettore di tipo char (che non possiamo considerare come una stringa dal momento che non ha un carattere nullo finale) che abbiamo

int vettore2d[2][3] = {{1, 2, 3}, {4, 5, 6}};

1 2 3
4 5 6

int vettore2d[2][3] = {1, 2, 3, 4, 5, 6};

tipo_elementi nome_vettore [numeroRighe][numeroColonne] = {elementi};

primo elemento. Infatti vale l'esempio seguente:

int gradi[5] = {10, 20, 30, 40, 50};
gradi[0] == *gradi; // 10
gradi[1] == *(gradi + 1); // 20
gradi[2] == *(gradi + 2); // 30
gradi[3] == *(gradi + 3); // 40
gradi[4] == *(gradi + 4); // 50

Tuttavia, il nome di un vettore, una volta definito, non può essere assegnato ad un indirizzo di memoria diverso; per questo motivo il nome di un array è un puntatore costante.

11.9 Ordinamento dei vettori

Supponiamo di avere un vettore di elementi sui quali è possibile definire un certo tipo di ordinamento (quindi sui quali valga l'operatore di confronto) e di voler ordinare questi elementi in ordine crescente o decrescente. C++ ci fornisce vari algoritmi di ordinamento per poter ordinare un vettore, noi ne analizzeremo solo alcuni, i quali si differenziano tra loro per la propria complessità temporale (cioè il numero di operazioni necessarie per effettuare l'ordinamento). In generale la complessità

La complessità computazionale di un algoritmo di ordinamento di array varia al variare delle caratteristiche dell'array (numero di elementi, ordinamento già presente, ...); per questo motivo di solito si parla asintoticamente di complessità computazionale degli algoritmi di ordinamento (ma anche di qualsiasi tipo di algoritmo), nel senso che si parla di algoritmi a complessità lineare (n elementi comportano n operazioni), a complessità quadratica (n elementi comportano n^2 operazioni), e così via.

Gli algoritmi di ordinamento che analizzeremo sono i seguenti:

• ordinamento per inserimento diretto. Insertion sort:
• ordinamento per selezione diretta. Selection sort:
• ordinamento per scambio diretto. Bubble sort:
• ordinamento per partizione. Quick sort:

Tra questi algoritmi, i primi tre sono generalmente sconsigliati, dal momento che tutti e tre nella media dei casi possibili hanno una complessità quadratica.

complessità quadratica. Il quarto algoritmo, cioè il quick sort, quello più efficiente: infatti, nella media dei casi ha una complessità secondo la quale n elementi del vettore comportano n log n operazioni. Tuttavia, anche il quick sort, nel peggiore dei casi, comporta una complessità quadratica, ma questo caso è difficilmente raggiungibile. Analizzeremo tutti questi algoritmi e il loro funzionamento e li implementeremo in C++ supponendo di avere un vettore di numeri interi e di doverli ordinare in ordine crescente.

11.9.1 Insertion sort

Uno degli algoritmi più semplici è quello dell'inserimento. L'idea di questo algoritmo consiste nel partire dal primo elemento del vettore e lasciarlo in quella posizione; si passa poi agli elementi via via successivi, i quali vengono presi e portati posizione per posizione indietro fino a che non si trovano con un elemento minore nella posizione precedente oppure nella

prima posizione.Nella media dei casi il numero di operazioni richieste è un quindi si tratta di un algoritmo22 O(n ),a complessità quadratica.Vediamo ora come implementare in C++ questo algoritmo.Premessa: nel codice seguente la variabile x serve per memorizzare l'elemento che viene preso e poiposizionato; la variabile j è necessaria come contatore per il ciclo più interno degli elementi chedovranno essere confrontati.Alla prima riga definiamo il vettore da ordinare daOrd. Alla seconda riga inizia la procedura cheeffettivamente riordina gli elementi del vettore.2 Consideriamo come caso medio quello in cui il vettore non è né già quasi totalmente ordinato ma nemmenototalmente disordinato. 112 Programmazione in C++CAPITOLO 11. VETTORI E STRUTTUREint daOrd[] = {44, 55, 12, 42, 94, 18};1 void insertionSort(int daOrd[], int n)2 {3 int x, j;4 for (int i = 1; i < n; i++)5 {6 x = daOrd[i];7 j = i - 1;8 while (j >= 0 && x

<code>
<span class="line">6 </span>for (int i = 1; i < n; i++) {
<span class="line">7 </span>int x = daOrd[i];
<span class="line">8 </span>int j = i - 1;
<span class="line">9 </span>while (j >= 0 && x < daOrd[j]) {
<span class="line">10</span>daOrd[j + 1] = daOrd[j];
<span class="line">11</span>j--;
<span class="line">12</span>}
<span class="line">13</span>daOrd[j + 1] = x;
<span class="line">14</span>}
<span class="line">15</span>}
<span class="line">16</span>

<p> Alla riga 6 inizia il ciclo più esterno: comincia da i = 1 perché il primo elemento deve rimanere al suo posto inizialmente, quindi non è necessario prenderlo e spostarlo; inizia il ciclo e alla riga 8 assegniamo a x l'elemento i-esimo del vettore daOrd, che è quello da ordinare; poi alla riga successiva assegniamo a j il valore di i - 1, perché j rappresenta l'elemento j-esimo del vettore, cioè quello che deve essere confrontato con l'elemento i-esimo. Alla riga 11 inizia il ciclo più interno, che andrà avanti fintantoché l'indice j è maggiore o uguale a zero (dato che l'indice -1 non esiste per i vettori) e finché l'elemento i-esimo (assegnato a x) è minore dell'elemento j-esimo: quindi il ciclo comincerà e andrà avanti finché prima dell'elemento i-esimo.
</p>

Ci sarà un elemento j-esimo maggiore di quello i-esimo, in caso negativo il ciclo termina e si passa direttamente all'istruzione della riga 17; in caso affermativo l'elemento j-esimo deve scorrere avanti di una posizione, quindi l'elemento j-esimo diventa l'elemento (j + 1)-esimo e j viene decrementata e il ciclo ricomincia in caso dopo, ovviamente, aver verificato la condizione del while.

Si esce poi dal ciclo interno e si torna nel ciclo for esterno e, infine, alla riga 17, assegniamo l'elemento (j + 1)-esimo definito nel ciclo interno alla variabile x, quindi l'elemento i-esimo della riga 8.

In questo modo il vettore sarà ordinato in modo crescente. Notiamo che, appunto, essendoc