C14 #14
Puntatori e file.
Il problema
dell’ordinamento.
Debug.
Piero Scotto - C14
1
Finalità del corso
Finalità del corso
Finalità del corso
Finalità del corso
Finalità del corso
Piero Scotto - C14
2
Piero Scotto - C14
3
Piero Scotto - C14
4
Piero Scotto - C14
5
Piero Scotto - C14
6
Piero Scotto - C14
7
Algoritmi di ordinamento
- Per inserimento (cerco ogni volta il più piccolo e lo inserisco)
- Per selezione (cerco l’elemento di valore minore e lo sposto all’inizio)
- Bubble sort (scorro il vettore e confronto a due a due gli elementi)
- ricorsivi (quick sort)
Piero Scotto - C14
8
L’ordinamento. La
funzione qsort
Piero Scotto - C14
9
La funzione qsort (algoritmo di Quick sort)
Nel linguaggio C è presente la funzione qsort di libreria (stdlib.h) che
permette di ordinare un vettore di elementi a un costo O(N log N),
buono in termini di prestazioni.
La funzione ha il seguente prototipo:
int qsort(void *v, size_t dimV, size_t dimE,
int (*cmp)(const void *a,const void *b))
dove v è l’indirizzo del vettore da ordinare,
dimV è la dimensione del vettore,
dimE è la dimensione di un singolo elemento del vettore e
cmp è la funzione che contiene il criterio con cui si può dire che un
elemento è minore, maggiore o uguale di un altro. La funzione è
progettata per poter agire su vettori contenenti qualsiasi tipo di
dato, anche quelli definiti dal programmatore.
Piero Scotto - C14
10
Come primo esempio supponiamo di voler ordinare un
vettore di 10 interi: in questo caso la chiamata alla
funzione qsort, supponendo che il vettore si chiami
appunto vettore, sarà la seguente:
qsort(vettore,10,sizeof(int),cmp);
Ovviamente per realizzare l’ordinamento dovrà essere
definita la funzione cmp, che risulta essere la parte più
“complicata”. La funzione cmp deve comportarsi come la
funzione strcmp di confronto tra stringhe nel C, cioè
dovrà restituire un valore positivo se il primo elemento
da confrontare è maggiore del secondo, minore di zero
se il primo elemento è minore del secondo e uguale a
zero se i due elementi sono uguali. In questo caso la
funzione cmp dovrà essere così definita:
Piero Scotto - C14
11
int cmp(const void *a, const void *b)
{
int primo = *(int *)a;
int secondo = *(int *)b;
if (primo > secondo) return 1;
if (primo < secondo) return -1;
return 0;
}
Come si può facilmente notare la funzione fa esattamente quanto detto in precedenza; qualche difficoltà di interpretazione la potrebbero dare le prime due righe, che in
effetti non fanno altro che assegnare i valori degli interi
da confrontare alle variabili primo e secondo, attraverso
l’operatore di casting e la dereferenziazione dei puntatori.
Piero Scotto - C14
12
L’operatore di dereferenziazione (il simbolo e’ un asterisco)
applicato a un puntatore restituisce il valore memorizzato nella
variabile a cui punta. E’ l’inverso dell’operatore &, che fornisce
l’indirizzo.
Se il vettore fosse un vettore di double basterebbe sostituire alla
parola int la parola double e tutto funzionerebbe senza altre
modifiche. Se poi si volesse ordinare in ordine discendente anziché
ascendente basterebbe invertire” la definizione della funzione cmp.
Cosa succede se invece di voler ordinare un vettore formato da tipi
predefiniti (int, float, double, ecc.) ci fosse l’esigenza di ordinare un
vettore di strutture dati costruite ad hoc per il programma?
In realtà le modifiche da fare sono minime, una volta capito come
funziona qsort e la funzione di comparazione. Se ad esempio fosse
stata definita una struttura per contenere i dati di peso e altezza di
una persona in questo modo:
Piero Scotto - C14
13
struct persona{
int peso;
int altezza;
};
allora la chiamata di qsort risulterebbe fatta in questo modo
qsort(vettore,10,sizeof(persona),cmp);
e la funzione di comparazione avrebbe questa dichiarazione
int cmp(const void *a, const void *b) {
persona primo = *(persona *)a;
persona secondo = *(persona *)b;
if (primo.peso > secondo.peso) return 1;
if (primo.peso < secondo.peso) return -1;
if (primo.altezza > secondo.altezza) return 1;
if (primo.altezza < secondo.altezza) return -1;
return 0;
}
Piero Scotto - C14
14
Piero Scotto - C14
15
Per analizzare il funzionamento di un programma o per trovare errori un ottimo
strumento è l’analisi dettagliata attraverso il DEBUG (F8)
- Si seleziona una riga (del codice) di interesse
- Si esegue fino al cursore
- Step successivo
- Nuova osservazione (new watch) nome variabile
Si può analizzare step by step il programma e indagare il contenuto delle varibili
Piero Scotto - C14
16
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXPERSONE 100
#define LUNGNOME 32
/* definizione esterna perche' sia visibile anche nel prototipo */
struct persona
{
char nome[LUNGNOME];
char cognome[LUNGNOME];
int eta;
int salario;
};
void ordina(struct persona pe[], int n);
int main()
{
struct persona pers, persone[MAXPERSONE] = {"","",0,0};
FILE *fp;
char file[FILENAME_MAX];
int i;
int numPersone; /* numero di persone lette */
Piero Scotto - C14
17
printf("Nome del file da leggere: ");
gets(file);
if ((fp=fopen(file,"r")) == NULL)
{
fprintf(stderr, "Non posso aprire il file: %s\n", file);
return EXIT_FAILURE;
}
i=0;
while (i<MAXPERSONE &&
fscanf(fp, "%s%s%d%d", pers.nome, pers.cognome,
&pers.eta, &pers.salario) == 4)
persone[i++] = pers;
if (!feof(fp))
fprintf(stderr, "Ci sono piu' di %d righe (ignorate)\n",
MAXPERSONE);
fclose(fp);
numPersone = i; /* numero persone lette dal file */
ordina(persone, numPersone);
Piero Scotto - C14
18
printf("Nome del file da scrivere: ");
gets(file);
if ((fp=fopen(file,"w")) == NULL)
{
fprintf(stderr, "Non posso aprire il file: %s\n", file);
return EXIT_FAILURE;
}
for (i=0; i<numPersone; i++)
{
pers = persone[i];
fprintf(fp, "%s %s %d %d\n", pers.nome, pers.cognome,
pers.eta, pers.salario);
}
fclose(fp);
return EXIT_SUCCESS;
}
Piero Scotto - C14
19
void ordina(struct persona pe[], int n)
{
struct persona temp;
int i, j, jmin;
/* ordinamento selection sort con chiave il campo cognome */
for (i=0; i<n-1; i++)
{
jmin = i;
for (j=i+1; j<n; j++)
if (strcmp(pe[j].cognome,pe[jmin].cognome) < 0)
jmin = j;
temp = pe[jmin];
pe[jmin] = pe[i];
pe[i] = temp;
}
}
/* Note. Si preferisce verificare se la fscanf() restituisce 4 e non EOF perche' EOF viene restituito solo se
NESSUN elemento viene letto arrivando alla fine del file; se invece per qualche motivo (es. sono rimasti da 1 a
3 valori) vengono letti meno di 4 valori, la fscanf() restituisce il numero di valori letti. La scanf() avrebbe potuto
leggere i valori e collocarli subito nei membri: scanf(... persone[i].nome, persone[i].cognome, &persone[i].eta,
&persone[i].salario) ma usare una variabile intermedia e' piu' chiaro e veloce (non deve calcolare ogni volta la
posizione dell'elemento i del vettore) */
Piero Scotto - C14
20
File salari.txt
PAOLO ZANCHI 43 23000
ANTONIO LOMONACO 67 35000
LUCIANO AIELLO 35 15000
MARIO SALVETTI 56 45000
Salari_ord.txt
LUCIANO AIELLO 35 15000
ANTONIO LOMONACO 67 35000
MARIO SALVETTI 56 45000
PAOLO ZANCHI 43 23000
Piero Scotto - C14
21