Corso di Informatica Generale - Primo modulo IN1

Testi e soluzioni di 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(1);
}

Per informazioni e commenti: liverani@mat.uniroma3.it - Torna alla Home page - Ultima modifica: 18 Marzo 2001