Un file di testo,
punti1.txt
, contiene le coordinate di alcuni punti del piano cartesiano (espresse in centimetri). Ciascuna coordinata è rappresentata da una struttura di due interi positivi, che rappresentano l'ascissa x e l'ordinata y.
Si realizzi un programma C, organizzato in almeno tre funzioni:
funzioneA:
a partire dal file
punti1.txt
identifichi le coordinate dei punti che si trovano sopra la bisettrice del primo quadrante (valore di ascissa strettamente minore dell'ordinata, cioè le coordinate con x < y) e le inserisca in una lista L, ordinata sul campo ascissa, e a parità di ascissa sul campo ordinata; la funzioneA riceve come parametri il puntatore al file, il puntatore a L (inizializzato a
NULL
nel
main
),
più eventuali parametri a scelta, e restituisce il puntatore alla radice della lista L;
funzioneB:
accedendo a L, stampi a video l'elenco delle coordinate contenute in L; questa funzione (funzioneB) riceve il puntatore radice L, più eventuali parametri a scelta, e restituisce
void
;
funzioneC:
accedendo a L, calcoli in modo ricorsivo qual è la lunghezza della lista. Il main stampi a video il valore ottenuto.
Questa funzione (funzioneC) riceve il puntatore radice L, più eventuali parametri a scelta, e restituisce un intero.
Per chi svolge il compito A+B (Ulteriori punti 20 su tot. di 63 per A+B; tempo +30 min):
Nel file
punti1.txt
ci le coordinate di, al massimo, 100 punti.
Si inseriscano i dati contenuti nel file in un opportuno vettore V di strutture.
Ordinare il vettore V tramite una opportuna chiamata della funzione qsort sul campo ascissa, e a parità di ascissa sul campo ordinata (si noti che è la stessa relazione d'ordine adottata per l'inserimento ordinato nella lista).
Stampare poi tutte le coordinate del vettore V ordinato, una coordinata per riga, su file di testo outputAB.txt, da consegnare con il codice sorgente;
questa funzione (funzioneAB) riceve come parametri il vettore V e il puntatore al file, più eventuali parametri a scelta, e restituisce void.
NOTA BENE:
Si consegnino i sorgenti, eseguibile e i file di uscita generati.
È possibile utilizzare librerie C (ad esempio per le stringhe). Nel caso si strutturi a moduli l'applicazione qualunque libreria utente va riportata nello svolgimento.
Esercizio 2 (Punti 3 su 31) (+15 min)
Sia data la seguente funzione
fun
che riceve un carattere e un albero binaro di ricerca di caratteri
int fun(char i, tree T)
{ if (T==NULL) return 0;
else if (i==T->value) return 1 + fun(i,T->left);
else
if (i<T->value) return fun(i,T->left);
else return fun(i,T->right);
}
Si indichi cosa fa la funzione
fun
e se ne valuti la complessità asintotica come numero di test
i==T->value
, nel caso in cui il valore
char i
passato alla funzione non sia presente nell'albero
tree T
, e sia:
minore di tutti quelli presenti o
maggiore di tutti quelli presenti.
NOTA BENE:
Si consegni la soluzione in un file
teoria.txt
.