Gli array sono strutture dati che consentono di immagazzinare una sequenza di variabili omogenee (dello stesso tipo) in memoria. Ogni elemento è accessibile tramite un indice.
Caratteristiche degli Array
Sequenza indicizzata: Gli elementi sono ordinati e accessibili tramite indici.
Omogeneità: Tutti gli elementi devono essere dello stesso tipo.
Dimensione statica: La dimensione è definita al momento della compilazione e non può essere modificata.
2. Dichiarazione e Uso
Sintassi
Tipo nomeArray[dimensione];
Esempi
int numeri[10]; // Array di 10 interi float valori[5]; // Array di 5 float char lettere[20]; // Array di 20 caratteri
Inizializzazione
Completa:
int numeri[5] = {1, 2, 3, 4, 5};
Parziale: Gli elementi non inizializzati sono impostati a 0.
int numeri[5] = {2};
Inferenza della dimensione:
int numeri[] = {1, 2, 3};
3. Accesso agli Elementi
numeri[0] = 10; // Assegna il valore 10 al primo elemento printf("%d", numeri[1]); // Stampa il secondo elemento
Nota: L'accesso a un indice fuori dai limiti dell'array causa un errore (segmentation fault).
4. Operazioni su Array
Popolamento
for (int i = 0; i < 5; i++) {
scanf("%d", &numeri[i]); // Input dall'utente
}
Calcolo della Somma
int somma = 0; for (int i = 0; i < 5; i++) {
somma += numeri[i];
}
Ricerca del Massimo
int max = numeri[0]; for (int i = 1; i < 5; i++) { if (numeri[i] > max) max = numeri[i];
}
5. Esempi Completi
Scrivere i primi 300 numeri
#include<stdio.h> intmain() { int numeri[300]; for (int i = 0; i < 300; i++) numeri[i] = i + 1; return0;
}
Media, Minimo e Massimo
#include<stdio.h> intmain() { int numeri[5] = {5, 3, 7, 2, 9}, somma = 0, max = numeri[0], min = numeri[0]; for (int i = 0; i < 5; i++) {
somma += numeri[i]; if (numeri[i] > max) max = numeri[i]; if (numeri[i] < min) min = numeri[i];
} printf("Media: %.2f, Massimo: %d, Minimo: %d", somma / 5.0, max, min); return0;
}
6. Copia e Confronto
Copia di Array
for (int i = 0; i < 5; i++) {
array2[i] = array1[i];
}
Confronto
int uguali = 1; for (int i = 0; i < 5; i++) { if (array1[i] != array2[i]) {
uguali = 0; break;
}
}
7. Algoritmi Avanzati
Stampare Array in Ordine Inverso
for (int i = 4; i >= 0; i--) { printf("%d ", numeri[i]);
}
Ricerca Sequenziale
int trovato = -1; for (int i = 0; i < 5; i++) { if (numeri[i] == valoreCercato) {
trovato = i; break;
}
} printf("Indice trovato: %d", trovato);
8. Errori Comuni
Accesso a un indice fuori dai limiti: Causa un errore di segmentazione (segmentation fault).
Dimensione dinamica non consentita senza memoria dinamica:
int dim; scanf("%d", &dim); int array[dim]; // Errore se dim non è noto a tempo di compilazione
9. Esercizi Proposti
Esercizio 1: Dato un array di 10 numeri, calcolare la somma dei valori prima di un indice dato e il prodotto di quelli successivi.
Esercizio 2: Data una lista di voti e crediti, calcolare la media pesata.
Esempio di Soluzione
#include<stdio.h> intmain() { int numeri[10], x, somma = 0, prodotto = 1; printf("Inserisci 10 numeri:\n"); for (int i = 0; i < 10; i++) scanf("%d", &numeri[i]); printf("Inserisci l'indice X (0-9): "); scanf("%d", &x); for (int i = 0; i < x; i++) somma += numeri[i]; for (int i = x + 1; i < 10; i++) prodotto *= numeri[i]; printf("Somma: %d, Prodotto: %d\n", somma, prodotto); return0;
}
C-Strings
Una C-string è una sequenza di caratteri che rappresenta una stringa in linguaggio C. Questa sequenza è implementata come un array di caratteri, con un carattere speciale di terminazione '\0' (nullo) posto subito dopo l'ultimo carattere utile della stringa.
Dettagli
Il carattere terminatore '\0' ha codice ASCII 0 e segnala la fine della stringa.
Gli elementi successivi al carattere nullo in un array di caratteri possono contenere valori indeterminati.
Ad esempio, la stringa "bisio" viene rappresentata in memoria come:
'b' 'i' 's' 'i' 'o' '\0' // Con gli indici:
0 1 2 3 4 5
char Cognome[30] = "bisio"; // Il compilatore aggiunge automaticamente il carattere '\0'.
Inserimento tramite input:
char Cognome[30]; scanf("%s", Cognome);
// Non si usa il simbolo & perché un array è già un puntatore al primo elemento.
11. Utilizzo di %s in printf
Il formato %s nella funzione printf in C è utilizzato per stampare una C-string. Questa funzione interpreta l'indirizzo fornito come l'inizio di una sequenza di caratteri (array di caratteri) e stampa i caratteri uno per uno fino a incontrare il carattere terminatore '\0'.
Comportamento
Stampa della stringa fino al terminatore: La funzione printf legge la sequenza di caratteri a partire dall'indirizzo specificato e continua finché non incontra il carattere nullo '\0'.
Ignorati i caratteri successivi: Tutti i caratteri successivi al terminatore non vengono stampati, anche se presenti nella memoria dell'array.
La funzione printf stampa i caratteri fino al terminatore '\0'.
12. Stampa di una stringa in ordine inverso
Questo programma stampa una stringa in ordine inverso utilizzando un array di caratteri in C.
Codice
#include<stdio.h> #define MAX 10
intmain() { int i; char Parola[MAX];
// Legge una stringa da input scanf("%s", Parola);
// Trova la lunghezza della stringa (fino al carattere terminatore '\0')
i = 0; while (i < MAX - 1 && Parola[i] != '\0') {
i++;
}
// Riduce l'indice di uno per escludere il terminatore if (Parola[i] == '\0') {
i--;
}
// Stampa la stringa in ordine inverso while (i >= 0) { printf("%c", Parola[i]);
i--;
}
return0;
}
Funzionamento
Input: La stringa viene letta tramite scanf("%s", Parola). La funzione legge i caratteri fino al primo spazio o carattere non valido e li memorizza nell'array Parola.
Individuazione della lunghezza: Il primo ciclo while determina l'indice dell'ultimo carattere valido nella stringa, ignorando il terminatore '\0'.
Stampa inversa: Il secondo ciclo while stampa i caratteri partendo dall'ultimo fino al primo.
Esempio di Esecuzione
Input:
bisio
Output:
oisib
11.2 Inversione di una stringa all'interno di un array
Questo esempio mostra come invertire una stringa direttamente all'interno di un array di caratteri in C.
Codice
#include<stdio.h> #define MAX 10
intmain() { int i, j; char Parola[MAX], temp;
// Legge una stringa da input scanf("%s", Parola);
// Trova la lunghezza della stringa (fino al carattere terminatore '\0')
i = 0; while (i < MAX - 1 && Parola[i] != '\0') {
i++;
}
// Riduce l'indice per posizionarsi sull'ultimo carattere utile if (Parola[i] == '\0') {
i--;
}
// Invertire la stringa utilizzando due indici
j = 0; // inizio della stringa while (i > j) { // Scambio degli elementi
temp = Parola[i];
Parola[i] = Parola[j];
Parola[j] = temp;
// Aggiorna gli indici
i--;
j++;
}
// Stampa la stringa invertita printf("\n%s\n", Parola);
return0;
}
Spiegazione del funzionamento
Lettura della stringa:
Utilizza scanf("%s", Parola) per leggere una stringa fino al primo spazio o carattere non valido.
La stringa viene salvata nell'array Parola.
Determinazione della lunghezza:
Il ciclo while individua l'ultimo carattere della stringa valido, ignorando il terminatore '\0'.
Inversione della stringa:
Utilizza due indici:
j parte dall'inizio della stringa.
i parte dalla fine della stringa.
Scambia i caratteri agli estremi con una variabile temporanea temp.
Continua a scambiare i caratteri finché i due indici non si incontrano o si incrociano.
Stampa della stringa invertita: L'array Parola ora contiene la stringa invertita.
Esempio di Esecuzione
Input:
bisio
Output:
oisib
11.3 Verifica di una stringa palindroma
La verifica di una stringa palindroma si basa sul confronto dei caratteri simmetrici, utilizzando due indici: uno che parte dall'inizio della stringa e l'altro dalla fine. Una stringa è considerata palindroma se può essere letta allo stesso modo da sinistra a destra e da destra a sinistra, come nel caso della parola "anna".
Strategia e Fasi
1° FASE: Posizionamento degli Indici
L'obiettivo è determinare la posizione iniziale (i) e finale (j) della stringa. Questo viene fatto iterando sull'array di caratteri che rappresenta la stringa:
int j = 0; while (j < MAX && Str[j] != '\0') {
j++;
}
j--; // L'indice `j` viene spostato sull'ultimo carattere utile int i = 0; // Inizio della stringa
2° FASE: Verifica dei Caratteri Simmetrici
Confronta i caratteri agli estremi della stringa (ai due indici i e j) e avanza verso il centro.
while (i < j && Str[i] == Str[j]) {
i++; // Avanza da sinistra verso il centro
j--; // Avanza da destra verso il centro
} // Se `i` >= `j`, la stringa è palindroma
Caso Pratico
Input:"anna"
Posizionamento degli indici:
i = 0 (inizio).
j = 3 (fine).
Verifica dei caratteri:
Confronto Str[0] con Str[3] → 'a' == 'a' → Avanza: i = 1, j = 2.
Confronto Str[1] con Str[2] → 'n' == 'n' → Avanza: i = 2, j = 1.
Gli indici si incrociano (i >= j): la stringa è palindroma.
Implementazione Completa
#include<stdio.h> #define MAX 100
// Funzione per calcolare la lunghezza della stringa int string_length(const char *str) { int length = 0; while (str[length] != '\0') {
length++;
} return length;
}
// Funzione per verificare se la stringa è palindroma int is_palindrome(const char *str) { int length = string_length(str); int i = 0; int j = length - 1;
while (i < j) { if (str[i] != str[j]) { return0; // Non è palindroma
}
i++;
j--;
} return1; // È palindroma
}
intmain() { char str[MAX];
printf("Inserisci una stringa: "); scanf("%s", str);
if (is_palindrome(str)) { printf("La stringa \\"%s\\" è palindroma.\\n", str);
} else { printf("La stringa \\"%s\\" non è palindroma.\\n", str);
}
return0;
}
Spiegazione del Codice
Funzione string_length: Calcola la lunghezza della stringa contando i caratteri fino a '\0'.
Funzione is_palindrome: Confronta i caratteri dalla fine e dall'inizio della stringa, avanzando verso il centro. Restituisce:
0 (falso) se la stringa non è palindroma.
1 (vero) se la stringa è palindroma.
Funzione main:
Legge una stringa dall'utente.
Verifica se la stringa è palindroma chiamando is_palindrome.
Stampa il risultato.
Esempio di Esecuzione
Input:
anna
Output:
La stringa "anna" è palindroma.
13. Individuazione dei Massimi Locali in un Array
Per individuare i massimi locali in un array, è necessario confrontare ciascun elemento con i suoi vicini immediati. Un elemento è considerato un massimo locale se il suo valore è maggiore di quello dei suoi vicini.
Definizione di Massimo Locale
Un massimo locale in un array è un elemento che è maggiore dei due elementi che lo precedono (se presenti) e dei due elementi che lo seguono (se presenti). Ad esempio, nell'array [3, 5, 4, 6, 3, 2, 9], i massimi locali sono:
6 (che è maggiore di 5, 4, 3, 2).
9 (che è maggiore di 3, 2).
Algoritmo per Trovare i Massimi Locali
Inizializzazione:
Definire un array A contenente gli elementi da analizzare.
Determinare la lunghezza dell'array N.
Controllo del Primo Elemento:
Se il primo elemento è maggiore del secondo, è un massimo locale.
Controllo degli Elementi Interni:
Iterare sugli elementi dall'indice 1 a N-2.
Per ciascun elemento A[i], confrontarlo con i suoi vicini A[i-1] e A[i+1].
Se A[i] è maggiore di entrambi, è un massimo locale.
Controllo dell'Ultimo Elemento:
Se l'ultimo elemento è maggiore del penultimo, è un massimo locale.
Implementazione in C
#include<stdio.h> #define N 7
intmain() { int A[N] = {3, 5, 4, 6, 3, 2, 9}; int i;
// Controllo del primo elemento if (A[0] > A[1]) { printf("Massimo locale: A[0] = %d\\n", A[0]);
}
// Controllo degli elementi interni for (i = 1; i < N - 1; i++) { if (A[i] > A[i - 1] && A[i] > A[i + 1]) { printf("Massimo locale: A[%d] = %d\\n", i, A[i]);
}
}
// Controllo dell'ultimo elemento if (A[N - 1] > A[N - 2]) { printf("Massimo locale: A[%d] = %d\\n", N - 1, A[N - 1]);
}
return0;
}
Spiegazione del Codice
Controllo del Primo Elemento: Si verifica se il primo elemento A[0] è maggiore del secondo A[1]. Se sì, viene stampato come massimo locale.
Controllo degli Elementi Interni:
Si itera sugli elementi dall'indice 1 a N-2.
Per ciascun elemento A[i], si confronta con il precedente A[i-1] e il successivo A[i+1].
Se A[i] è maggiore di entrambi, viene stampato come massimo locale.
Controllo dell'Ultimo Elemento: Si verifica se l'ultimo elemento A[N-1] è maggiore del penultimo A[N-2]. Se sì, viene stampato come massimo locale.
Per la fusione di due array ordinati, l'obiettivo è unire i due array in un unico array ordinato mantenendo l'ordine crescente. Questo processo è particolarmente utile in algoritmi di ordinamento come il Merge Sort.
Approccio e Algoritmo
Dati
Due array ordinati:
A con dimensione NA.
B con dimensione NB.
Un array C con dimensione totale NA + NB per memorizzare l'output.
Passaggi dell'Algoritmo
Inizializzazione:
Definire gli indici:
iA = 0: punta al primo elemento di A.
iB = 0: punta al primo elemento di B.
k = 0: indice per l'array C.
Confronto degli elementi:
Confrontare A[iA] e B[iB].
Inserire il valore minore in C[k].
Avanzare l'indice del valore utilizzato (iA o iB) e k.
Gestione degli elementi rimanenti:
Se uno dei due array ha ancora elementi non processati, copiali direttamente in C.
Termine:
Ripetere i passi finché tutti gli elementi di A e B sono stati processati.
Codice in C
#include<stdio.h> #define NA 10 #define NB 5
intmain() { int A[NA] = {2, 4, 5, 8, 11, 13, 18, 23, 29, 37}; int B[NB] = {3, 5, 9, 12, 15}; int C[NA + NB]; int iA = 0, iB = 0, k = 0;
// Fusione while (iA < NA && iB < NB) { if (A[iA] <= B[iB]) {
C[k++] = A[iA++];
} else {
C[k++] = B[iB++];
}
}
// Copia degli elementi rimanenti di A while (iA < NA) {
C[k++] = A[iA++];
}
// Copia degli elementi rimanenti di B while (iB < NB) {
C[k++] = B[iB++];
}
// Stampa dell'array fuso printf("Array fuso:\\n"); for (int i = 0; i < NA + NB; i++) { printf("%d ", C[i]);
} printf("\\n");
return0;
}
Esempio di Esecuzione
Input:
A = {2, 4, 5, 8, 11, 13, 18, 23, 29, 37}
B = {3, 5, 9, 12, 15}
15. Conta i caratteri letti in ingresso fino a una stringa di terminazione
Per contare i caratteri letti in ingresso fino a una stringa di terminazione in un programma C, si utilizza un algoritmo che legge carattere per carattere e tiene traccia del conteggio totale. Il ciclo si interrompe quando la sequenza dei caratteri coincide con la stringa terminatrice.
Algoritmo
Inizializzazione:
Definire una variabile per contare i caratteri (cont).
Utilizzare una variabile ausiliaria (n) per monitorare i caratteri che corrispondono alla stringa terminatrice.
Lettura carattere per carattere:
Leggere un carattere e incrementare il contatore.
Confrontare il carattere letto con il prossimo carattere previsto nella stringa terminatrice.
Se corrisponde, incrementare n.
Se non corrisponde:
Se il carattere è uguale al primo carattere della stringa terminatrice, reimpostare n a 1.
Altrimenti, reimpostare n a 0.
Uscita dal ciclo:
Il ciclo termina quando tutti i caratteri della stringa terminatrice sono stati trovati consecutivamente.
Stampa del risultato:
Stampare il conteggio totale dei caratteri letti.
Codice Esempio
#include<stdio.h> #define LMAX 15
intmain() { char Term[LMAX + 1] = "fine"; int cont = 0; int n = 0; char carletto;
printf("Inserisci caratteri, termina con la stringa 'fine':\\n");
while (Term[n] != '\0') { scanf("%c%*c", &carletto); // Legge un carattere
cont++;
if (carletto == Term[n]) {
n++; // Avanza nella verifica della stringa terminatrice
} else if (carletto == Term[0]) {
n = 1; // Riprendi dal primo carattere della stringa terminatrice
} else {
n = 0; // Reimposta il controllo
}
}
printf("\\nNumero di caratteri letti: %d\\n", cont); return0;
}
Esempio di Esecuzione
Input:
a b c f i n e
Output:
Numero di caratteri letti: 7
16. Visibilità di edifici allineati
Per risolvere il problema della visibilità di edifici allineati, dobbiamo determinare quali edifici di una sequenza sono visibili rispetto a una fonte di luce posta in una direzione. Gli edifici non visibili sono quelli coperti dall'ombra di edifici più alti precedenti.
Algoritmo
Dati di input:
Un array Sequenza[] che contiene le altezze degli edifici in ordine.
Un array Illuminati[] di uguale lunghezza per indicare quali edifici sono visibili.
Concetti principali:
La visibilità di un edificio è determinata confrontandone l'altezza con l'altezza massima (ombra) che proietta un'ombra sulla destra.
Passaggi:
Primo edificio: Il primo edificio è sempre visibile, quindi viene copiato in Illuminati e la sua altezza inizializza l'ombra.
Edifici successivi:
Per ciascun edificio:
Se la sua altezza supera quella dell'ombra, è visibile e la sua altezza aggiorna il valore dell'ombra.
Altrimenti, non è visibile e si registra un valore 0 in Illuminati.
Output: L'array Illuminati con le altezze degli edifici visibili e 0 per quelli non visibili.
Codice in C
#include<stdio.h>
#define L 7
intmain() { int Sequenza[L] = {36, 32, 43, 71, 68, 56, 74}; int Illuminati[L]; int ombra, i;
// Primo edificio: sempre visibile
ombra = Sequenza[0];
Illuminati[0] = Sequenza[0];
// Analizza gli edifici successivi for (i = 1; i < L; i++) { if (Sequenza[i] > ombra) {
Illuminati[i] = Sequenza[i];
ombra = Sequenza[i];
} else {
Illuminati[i] = 0;
}
}
// Stampa l'array risultato printf("Edifici visibili:\\n"); for (i = 0; i < L; i++) { printf("%d ", Illuminati[i]);
} printf("\\n");
printf("Lunghezza della più lunga sequenza crescente: %d\\n", max_len); printf("Elementi della sequenza: "); for (int i = start_max; i < start_max + max_len; i++) { printf("%d ", A[i]);
} printf("\\n");
return0;
}
Spiegazione
Variabili utilizzate:
max_len: Lunghezza della più lunga sequenza crescente trovata finora.
current_len: Lunghezza della sequenza crescente corrente.
start_max: Indice di inizio della più lunga sequenza crescente.
start_current: Indice di inizio della sequenza corrente.
Logica del ciclo:
Confronta ogni elemento con il successivo:
Se il successivo è maggiore, aumenta la lunghezza della sequenza corrente.
Se non lo è:
Confronta la sequenza corrente con quella più lunga trovata.
Aggiorna i parametri della sequenza più lunga se necessario.
Risultati: La sequenza crescente più lunga viene individuata e stampata con i suoi elementi.