Programmazione I a.a. 2004/2005 (Canale
P-Z) R. Silvestri e I. Salvo
Prova scritta del 15 giugno 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 EX {
int
count;
char *
val; //stringa allocata dinamicamente
struct EX * next;
} EX, *EXList;
Scrivere una funzione, con prototipo void Exp(EXList L, char C[], int k), che presa in
input la lista L la
modifica
sostituendo ogni elemento con campo count
uguale a k
con k
elementi aventi tutti campo count
uguale a k - 1 e
l'i-esimo
di tali
elementi ha campo val uguale
alla concatenazione della stringa val
dell'elemento originale con il carattere C[i - 1]. Se
k < 1
la
funzione non fa nulla. La funzione non deve modificare
il puntatore al primo elemento. La memoria non più usata deve
essere
rilasciata e i nuovi blocchi di memoria non devono essere più
grandi del necessario. Ad esempio se la lista è
{3, "aa"} -> {4, "bcd"} -> {3, "fgh"} -> {3, "xy"}, il
vettore C
è ['1', '2', '3']
e k = 3,
allora la funzione modifica la lista così {2, "aa1"} -> {2, "aa2"} -> {2, "aa3"} -> {4, "bcd"} ->
{2, "fgh1"} -> {2, "fgh2"} -> {2, "fgh3"} -> {2, "xy1"}-> {2, "xy2"}-> {2, "xy3"}.
Soluzione Esercizio Obbligatorio
void Exp(EXList L, char C[], int k)
{
if (k
< 1) return;
while
(L != NULL)
{
//Scorri
la lista
if
(L->count == k) {
//Se e' un elemento da modificare...
EX *next = L->next,
*prev = L;
int len = strlen(prev->val);
for (i = 2 ; i <= k ; i++)
{ //Inserisci i nuovi elementi...
EX *p = malloc(sizeof(EX));
//Alloca
memoria per l'elemento
prev->next
= p;
//Aggancialo
al precedente
p->count =
k - 1;
p->val = malloc((len + 2)*sizeof(char)); //Alloca la stringa
strcpy(p->val, L->val);
p->val[len] = C[i - 1];
p->val[len
+ 1] = '\0';
prev = p;
}
L->count = k -
1; //modifica il primo elemento
L->val = realloc(L->val, (len + 2)*sizeof(char)); //Rialloca la memoria
L->val[len] =
C[0];
//per la stringa
L->val[len + 1] =
'\0';
//modificata.
prev->next = next;
//Riaggancia il prossimo elemento
L = prev;
//all'ultimo
dei nuovi.
}
L = L->next;
}
}
Esercizio 1 (max 10 punti)
Scrivere una funzione, con prototipo void FSub(char *fname, char Ch, int *pR, int *pC), che cerca
nella
matrice
memorizzata nel file di tipo testo il cui nome è nella stringa fname la
prima occorrenza del carattere Ch, se
esiste lo sostituisce con il
carattere 'X'
e restituisce in *pR e *pC gli
indici di riga e colonna di tale occorrenza. La matrice è una
matrice di caratteri memorizzata
per righe, i primi due interi del file rappresentano, rispettivamente,
il numero di righe e il numero di colonne della matrice. I due interi
sono separati da un carattere spazio e il primo carattere dopo il
secondo intero è il primo carattere della matrice. La funzione
non deve
copiare la matrice in memoria. Ad esempio, se il file fname
contiene 4
3abcfghpqruqz (quindi una matrice con 4 righe e 3
colonne) e se Ch
= 'q' allora FSub
modifica il file così 4 3abcfghpXruqz e
restituisce 3 in *pR e 2 in *pC.
Soluzione Esercizio 1
/* Funzione ausiliaria che sostituisce
il carattere in riga r e colonna c con
il carattere
'X'.
*/
void Write(FILE *f, int r, int c)
{
int
nr, nc, i, j;
rewind(f);
fscanf(f, "%d",
&nr); //Leggi il numero di righe
fscanf(f,
"%d", &nc);
//Leggi il numero di
colonne
for
(i = 1 ; i < r ; i++)
//Scorri le prime r
- 1 righe
for
(j = 1 ; j <= nc ; j++) fgetc(f);
for
(j = 1 ; j < c ; j++) fgetc(f);
//Scorri i primi c - 1 elementi
fputc(f,
'X');
//della r-esima riga.
}
void FSub(char *fname, char Ch, int *pR, int *pC)
{
FILE
*f = fopen(fname,
"r+"); //Apri
il file in lettura e scrittura
int
nr, nc, r, c;
short
found = 0;
fscanf(f,
"%d", &nr);
//Leggi il numero di righe
fscanf(f,
"%d", &nc);
//Leggi il numero di
colonne
for
(r = 1 ; r <= nr && !found ; r++) {
//Scorri la matrice alla ricerca
for
(c = 1 ; c <= nc && ! found ; c++) { //del carattere Ch.
char x = fgetc(f);
if (x == Ch) {
//Se lo hai trovato,
Write(f, r,
c); //sostituiscilo con il carattere 'X'.
*pR = r;
*pC = c;
found = 1;
}
}
}
fclose(f);
}
Esercizio 2 (max 8 punti)
Scrivere una funzione, con prototipo void Exch(int V[],
long n, int k), che cerca nel
vettore V
di
dimensione n
il più
piccolo indice j > k
tale che V[j]
> V[k] e, se esiste, sposta gli elementi delle posizioni k+1, k+2,..., j-1
nelle ultime
posizioni del vettore e gli elementi delle posizioni j, j+1,..., n
nelle posizioni successive alla posizione k. Ad
esempio se
n = 10, k = 2
e V =
[3, 5, 8, 3, 5, 12, 9, 5, 9, 8] allora la funzione modifica il
vettore V
così
V = [3, 5, 8,
12, 9, 5, 9, 8, 3, 5].
Soluzione Esercizio 2
void Exch(int V[],
long n, int k)
{
long
j = k + 1;
while
(j < n && V[j] < = V[k]) j++; //Cerca l'indice j
if (j
< n) {
int
Aux[n];
long
i, h = j - k - 1; //In
h e' il numero di elementi da spostare in coda
for
(i = 0 ; i < h ; i++) Aux[i] = V[k + 1 + i];
for
(i = k + 1 ; i < n - h ; i++) V[i] = V[i + h];
for
(i = 0 ; i < h ; i++) V[n - h - 1 + i] = Aux[i];
}
}
Esercizio 3 (max 12 punti)
Si consideri il seguente tipo:
typedef struct VE {
int *
vet; //Vettore allocato dinamicamente
long
dimVet; //Dimensione del vettore
struct
VE *next;
}VE,
*VList;
Scrivere una funzione, con prototipo void Comp(VList L), che
modifica la lista L in modo
tale che per ogni elemento
ve di L se tutti
i valori del vettore ve.vet
già appaiono nei vettori vet di
elementi precedenti a ve allora ve è
eliminato e
i valori del vettore ve.vet sono
aggiunti al vettore vet
dell'elemento immediatamente precedente. La memoria non più
usata
deve
essere rilasciata e i nuovi blocchi di memoria non devono essere
più
grandi del necessario. Ad esempio, se la lista L è
{[2, 4], 2}
-> {[3, 2, 5], 3} -> {[4, 3], 2} -> {[2, 5], 2} -> {[2, 4,
6], 3} allora
è modificata così {[2, 4], 2} ->
{[3, 2, 5, 4, 3, 2, 5], 7} -> {[2, 4, 6], 3}.
Soluzione Esercizio 3
/*
Funzione ausiliaria che ritorna 1 o 0 a seconda che i valori del
vettore dell'
elemento ve appaiono nei vettori di elementi precedenti o
meno. */
short IsDel(VList L, VE *ve)
{
int *vet = ve->vet;
long i = 0, n =
ve->dimVet;
short found = 1;
for (i = 0 ; i < n
&& found ; i++) { //Per ogni valore del vettore...
VE *e;
found = 0;
for
(e = L ; e != ve && !found ; e = e->next) { //Scorri gli elementi
long j;
//precedenti
alla ricerca
for
(j = 0 ; j < e->dimVet && !found ; j++) //di quel valore.
if (e->vet[j] == vet[i])
found = 1;
}
}
return found;
}
void Comp(VList L)
{
if (L
== NULL) return;
VE *pre = L, cur = L->next;
while
(cur != NULL)
{ //Scorri la lista
if
(IsDel(L,
cur)) { //Se e' un elemento da eliminare...
long i, np = pre->dimVet, nc
= cur->dimVet;
pre->vet = realloc(pre->vet, (np +
nc)*sizeof(int)); //Rialloca il
vettore
for (i = 0 ; i < nc ; i++)
//dell'elemento precedente e
pre->vet[np + i] = cur->vet[i]; //aggiungi i valori dell'
pre->dimVet = np +
nc;
//elemento da eliminare.
pre->next =
cur->next;
//Sgancia
l'elemento e
free(cur->vet);
//rilascia
la memoria.
free(cur);
cur = pre->next;
} else cur = cur->next;
}
}