Gli esercizi
Testi e soluzioni di alcuni esercizi
Eliminazione di intersezioni fra intervalli
/*
** elimina_intersezioni.c
**
** Leggere una lista di coppie di numeri interi (x1,y1), (x2,y2), ...,
** (xn,yn) tali che xi<yi per ogni i=1,...,n; ogni coppia (xi,yi)
** rappresenta un intervallo sulla retta. Riordinare gli elementi della
** lista in modo tale che x1<=x2<=...<=xn. Costruire una nuova lista
** che rappresenti gli intervalli della prima lista, ma privi di
** intersezioni (fatta eccezione per gli estremi degli intervalli);
** gli eventuali intervalli nulli (tali che xi=yi, o xi>yi) prodotti
** dalla rielaborazione degli intervalli originali devono essere
** eliminati.
**
** Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999
*/
#include <stdlib.h>
#include <stdio.h>
struct nodo {
int x;
int y;
struct nodo *next;
};
/*
** leggi_lista
**
** legge la lista di n coppie di interi e restituisce il puntatore
** (l'indirizzo di memoria) al primo elemento della lista.
*/
struct nodo *leggi_lista(void) {
struct nodo *primo, *p;
int x, y, i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
primo = NULL;
for (i=0; i<n; i++) {
printf("inserisci x%d e y%d: ", i, i);
scanf("%d %d", &x, &y);
p = malloc(sizeof(struct nodo));
p->x = x;
p->y = y;
p->next = primo;
primo = p;
}
return(primo);
}
/*
** stampa_lista
**
** stampa la lista partendo dall'elemento puntato da p.
*/
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("(%d,%d) ", p->x, p->y);
p = p->next;
}
printf("\n");
return;
}
/*
** ordina
**
** ordina la lista utilizzando l'algoritmo di bubble sort.
*/
void ordina(struct nodo *primo) {
int appx, appy, flag;
struct nodo *p;
flag = 1;
while (flag == 1) {
flag = 0;
p = primo;
while (p->next != NULL) {
if (p->x > (p->next)->x) {
appx = p->x;
appy = p->y;
p->x = (p->next)->x;
p->y = (p->next)->y;
(p->next)->x = appx;
(p->next)->y = appy;
flag = 1;
}
p = p->next;
}
}
return;
}
/*
** elabora
**
** crea la nuova lista e restituisce il puntatore al primo elemento.
** Per eliminare le intersezioni fra gli intervalli (nel caso in cui
** x[i+1]<y[i]) pone x[i+1]=y[i].
*/
struct nodo *elabora(struct nodo *primo) {
struct nodo *p, *p2, *primo2;
p = primo;
primo2 = NULL;
while (p != NULL) {
if (p->x < p->y) {
p2 = malloc(sizeof(struct nodo));
p2->x = p->x;
p2->y = p->y;
p2->next = primo2;
primo2 = p2;
}
if ((p->next != NULL) && ((p->next)->x < p->y)) {
(p->next)->x = p->y;
if ((p->next)->y < (p->next)->x) {
(p->next)->y = (p->next)->x;
}
}
p = p->next;
}
return(primo2);
}
/*
** main
**
** funzione principale che richiama le altre.
*/
int main(void) {
struct nodo *primo, *primo2;
primo = leggi_lista();
ordina(primo);
primo2 = elabora(primo);
stampa_lista(primo2);
return(0);
}