Programmazione I a.a. 2004/2005 (Canale P-Z)
R. Silvestri e I. Salvo
Prova scritta del 9 febbraio 2005
Per superare la prova è necessario (ma
non sufficiente) ottenere almeno 7 punti per la soluzione dell'esercizio
obbligatorio. Gli altri tre esercizi sono a scelta. Il voto è
la somma dei punti ottenuti.
Avvertenze: non usare variabili globali; definire tutte
le eventuali funzioni ausiliarie usate; è consentito usare
le
funzioni della libreria standard; se una
soluzione non è scritta in modo chiaro ed ordinato
non sarà presa
in considerazione.
Esercizio Obbligatorio (max 10 punti)
Si consideri il seguente tipo:
typedef
struct Elem {
int
cod;
struct Elem *next;
} Elem, *List;
Scrivere una funzione, con prototipo int *extract(List
*pL, int *nE), che elimina dalla lista
*pL gli elementi x per
i quali esiste un elemento successivo y tale che y.cod < x.cod, alloca dinamicamente
un vettore che contiene i valori dei campi
cod degli elementi eliminati, restituisce in *pL il puntatore al primo elemento
della lista modificata, in *nE
il numero degli elementi
eliminati e ritorna il vettore. Se non ci sono elementi eliminati la funzione
ritorna NULL.
Si assume che i valori dei campi cod siano
tutti distinti. L'ordine dei valori nel vettore deve essere quello che avevano
nella lista. La memoria degli elementi eliminati deve essere
rilasciata e il vettore non deve usare più memoria del necessario.
Ad esempio se la lista è 5 -> 12 -> 7 -> 10 ->
9 allora
è modificata così 5 -> 7 -> 9 il vettore
creato è [12, 10]
e in *nE è restituito
2.
Soluzione Esercizio Obbligatorio
/* Funzione
ausiliaria che ritorna vero se c'e' un elemento nella lista L con il
valore del campo cod minore di d.
*/
short Less(List L, int
d)
{
while (L != NULL && L->cod >= d) L = L->next;
return (L != NULL);
}
int *extract(List *pL, int *nE)
{
List L = *pL;
*nE = 0;
while (L != NULL) {
//Calcola il numero degli elementi
if (Less(L->next,
L->cod)) (*nE)++; //da eliminare.
L = L->next;
}
if (*nE == 0) return NULL;
int *v = malloc((*nE)*sizeof(int)); //Alloca il vettore
int i = 0;
List pre = NULL;
//Per mantenere il puntatore all'elemento
L = *pL;
//precedente.
while (L != NULL) {
List next = L->next;
//Salva
il puntatore al prossimo elemento
if (Less(next,
L->cod)) { //Se
e' un elemento da eliminare...
v[i++] = L->cod;
//Scrivi il valore del campo cod nel vet
if (pre == NULL) *pL
= next; //Se non ci sono elementi
precedenti
else pre->next = next;
//aggiorna il puntatore iniziale.
free(L);
//Rilascia la memoria dell'elemento
} else
pre = L;
L = next;
}
return v;
}
Esercizio 1 (max 8 punti)
Scrivere una funzione, con prototipo void
pd(char *str), che modifica la stringa
str spostando i caratteri
nelle posizioni
pari (0, 2, 4, ecc.) all'inizio della stringa e quelli nelle posizioni dispari
(1, 3, 5, ecc.) in coda. Ad esempio se la stringa str è
"icnctiroe" allora la
funzione la modifica così "intreccio".
Soluzione Esercizio 1
void
pd(char *str)
{
int i, n = strlen(str);
if (str == NULL || n == 0) return;
char aux[n];
//Vettore ausiliario
int p = (n + 1)/2;
//Numero di caratteri nelle
posizioni pari
for (i = 0 ; i < p ;
i++) //Copia in aux i caratteri nelle posizioni
pari
aux[i] = str[2*i];
for (i = 0 ; i < n -
p ; i++) //Accoda in aux i caratteri
nelle posizioni
aux[p + i] = str[2*i + 1];
//dispari.
for (i = 0 ; i < n ;
i++) //Copia aux in str
str[i] = aux[i];
}
Esercizio 2 (max 10 punti)
Scrivere una funzione, con prototipo void
Even(char *fname, char
*out), che crea un nuovo file di tipo testo con nome
dato dalla stringa out
e vi scrive, nell'ordine, ogni carattere c del file fname (cioè, il cui
nome è nella stringa fname)
tale che il numero
di occorrenze dello stesso carattere che precedono c è un intero pari
(0, 2, 4, ecc.). Siccome il file fname può essere molto
grande la
funzione non deve copiarne il contenuto in memoria (in tutto o in gran parte).
Ad esempio se il contenuto del file fname è
esame del 9 febbraio 2005 allora
nel file out verrà
scritto esam del9 fbrio205.
Soluzione Esercizio 2
/*
Funzione ausiliaria che ritorna il carattere in posizione k del file f */
char Kth(FILE
*f, long k)
{
rewind(f);
while (k > 0) {
fgetc(f);
k--;
}
return fgetc(f);
}
/* Funzione ausiliaria che ritorna vero se il numero
di occorrenze del carattere c
nei primi k caratteri del file f e' un numero pari.
*/
short Pre(FILE
*f, char c, long
k)
{
rewind(f);
long nOcc = 0;
while (k > 0) {
if (fgetc(f) == c) nOcc++;
k--;
}
return (nOcc % 2 == 0);
}
void Even(char
*fname, char *out)
{
FILE *f = fopen(fname, "r"); //Apri il file in lettura
FILE *fout = fopen(out,
"w+"); //Crea ed apri il nuovo file
long k, n = 0;
while (fgetc(f) != EOF) n++;
//Conta il numero di caratteri del file
for (k = 0 ; k < n ;
k++) {
char
c = Kth(f, k);
//Leggi il carattere in posizione
k e se il numero
if (Pre(f,
c, k)) //di occorrenze precedenti dello stesso carattere
fputc(fout, c);
//sono in numero pari, allora
scrivi il carattere
//nel nuovo file.
}
fclose(f);
fclose(fout);
}
Esercizio 3 (max 12 punti)
Si consideri il seguente tipo:
typedef
struct Dat {
long
coD;
char *
descr; //stringa allocata dinamicamente
struct Dat *next;
} Dat, *LDat;
Scrivere una funzione, con prototipo LDat Mod(LDat L, LDat M),
che modifica la lista L
nel seguente modo: per ogni elemento
d della lista M
se d.coD è negativo
elimina da L, se esiste,
l'elemento con campo coD
uguale a -d.coD, se invece
d.coD è positivo
inserisce (se un elemento con lo stesso valore del campo coD non esiste in L) un nuovo elemento in L uguale a d. La funzione ritorna il
puntatore alla lista modificata (che può anche essere NULL). Le
modifiche indotte dagli elementi di M devono essere effettuate
seguendo
l'ordine degli elementi in M,
è quindi possibile che, ad esempio, un elemento venga prima inserito
e poi eliminato (o viceversa).
Si assume che i valori dei campi coD degli elementi di L siano interi positivi distinti
e che gli elementi siano ordinati in senso crescente
rispetto al campo coD.
L'inserimento di nuovi elementi deve rispettare tale ordinamento. La memoria
degli elementi inseriti deve essere
interamente allocata e di quelli eliminati interamente rilasciata. Ad esempio
se la lista L è
{4, "libro"} -> {6, "mela"} -> {7, "piede"} -> {9, "mano"} e
la lista M è
{3, "a"} -> {-4, ""} -> {-3, "b"} -> {5, "poi"} -> {7, "per"}
-> {8, "re"} -> {-2, "se"}
allora la lista è così modificata {5, "poi"} -> {6, "mela"} ->
{7, "piede"} -> {8, "re"} -> {9, "mano"}.
Soluzione Esercizio 3
/*
Funzione ausiliaria che ritorna il puntatore all'elemento di L che ha il
valore del
campo coD massimo tra quelli che hanno valori strettamente minori
di cd. Se non
esiste ritorna NULL.
*/
LDat Find(LDat L, long cd)
{
if (L != NULL && L->coD < cd) {
while
(L->next != NULL && L->next->coD
< cd) L = L->next;
return
L;
} else return NULL;
}
LDat Mod(LDat L, LDat M)
{
while (M != NULL) {
//Per ogni elemento
di M trova
LDat p = Find(L, (M->coD < 0
? -M->coD : M->coD)); //il predecessore in L
del punto
LDat e = (p != NULL ? p->next : L);
//interessato alla modifica.
if (M->coD < 0) {
//Se eliminazione...
if (e != NULL &&
e->coD == -M->coD) { //Se c'e' l'elemento da eliminare
if (p != NULL)
p->next = e->next; //Eliminazione con predecessore
else L = e->next;
//Eliminazione in testa alla lista
free(e->descr);
//Rilascia la memoria della stringa
free(e);
//e della
struct.
}
} else
{
//Se inserimento...
if (e == NULL || e->coD
!= M->coD) { //Se non e' gia' presente
LDat new = malloc(sizeof(Dat));
//Alloca memoria per
la nuova
new->coD = M->coD;
//struct e per la stringa.
new->descr = malloc((strlen(M->descr) + 1)*sizeof(char));
strcpy(new->descr, M->descr);
new->next = e;
if (p != NULL)
p->next = new;
//Inserimento con predecessore
else L = new;
//Inserimento in testa alla
lista
}
}
}
return L;
}