Spese e mesi dell'anno

/*
**	spese_mesi.c
**
**	Legge in input una serie di periodi dell'anno (mese iniziale
**	e mese finale) e l'importo di una spesa effettuata in quel
**	periodo. Memorizza le informazioni lette in input in una lista.
**	Crea una nuova lista in cui per ogni mese dell'anno in cui
**	siano state effettuate delle spese, riporta il totale delle
**	spese effettuate.
**
**	Marco Liverani (liverani@mat.uniroma3.it) - Febbraio 1999
*/

#include <stdlib.h>
#include <stdio.h>


/*
**	struttura nodo1 per memorizzare le informazioni in input:
**	mese di inizio periodo, mese di fine periodo, importo
**	della spesa del periodo e puntatore al "record" successivo.
*/

struct nodo {
	int m1, m2, importo;
	struct nodo *next;
};

/*
**	struttura nodo2 per memorizzare le informazioni in output:
**	mese dell'anno, importo della spesa e puntatore all'elemento
**	successivo.
*/

struct nodo2 {
	int m, importo;
	struct nodo2 *next;
};


/*
**	input
**
**	legge in input le informazioni, crea una lista di
**	strutture nodo1 e restituisce il puntatore al primo
**	elemento della lista.
*/

struct nodo *input(int n) {
	int i, m1, m2, importo;
	struct nodo *p, *primo;

	primo = NULL;
	for (i=0; i<n; i++) {
		scanf("%d %d %d", &m1, &m2, &importo);
		p = malloc(sizeof(struct nodo));
		p->m1 = m1;
		p->m2 = m2;
		p->importo = importo;
		p->next = primo;
		primo = p;
	}
	return(primo);
}


/*
**	trovamese
**
**	scorre la lista di output (composta di strutture
**	di tipo nodo2) alla ricerca del mese ricevuto come
**	parametro (m). Se lo trova restituisce il puntatore
**	a quell'elemento, altrimenti restituisce NULL.
*/

struct nodo2 *trovamese(struct nodo2 *primo, int m) {
	struct nodo2 *p;

	p = primo;
	while (p != NULL && p->m != m) {
		p = p->next;
	}
	return(p);
}


/*
**	calcola
**
**	scorre la lista in input e costruisce la lista di
**	output.
*/

struct nodo2 *calcola(struct nodo *primo) {
	struct nodo *p;
	struct nodo2 *p2, *primo2;
	int i;

	p = primo;
	primo2 = NULL;

	while (p != NULL) {
		for (i=p->m1; i<=p->m2; i++) {
			p2 = trovamese(primo2, i);
			if (p2 == NULL) {
				p2 = malloc(sizeof(struct nodo2));
				p2->importo = 0;
				p2->m = i;
				p2->next = primo2;
				primo2 = p2;
			}
			p2->importo = p2->importo + p->importo/(p->m2 - p->m1 + 1);
		}
		p = p->next;
	}

	return(primo2);
}


/*
**	scambia
**
**	scambia i valori degli elmenti della lista di tipo
**	nodo2 di cui riceve in input i puntatori.
*/

void scambia(struct nodo2 *p1, struct nodo2 *p2) {
	int m, importo;

	m = p1->m;
	importo = p1->importo;
	p1->m = p2->m;
	p1->importo = p2->importo;
	p2->m = m;
	p2->importo = importo;
	return;
}


/*
**	bubble_sort
**
**	ordina, utilizzando l'algoritmo "bubble sort", gli
**	elementi della lista di output, sulla base della
**	spesa.
*/

void bubble_sort(struct nodo2 *primo) {
	struct nodo2 *p, *ultimo;
	int flag;

	flag = 1;
	ultimo = NULL;
	while (flag == 1) {
		flag = 0;
		p = primo;
		while (p->next != ultimo) {
			if (p->importo < (p->next)->importo) {
				scambia(p, p->next);
				flag = 1;
			}
			p = p->next;
		}
		ultimo = p;
	}
	return;
}


/*
**	stampa
**
**	stampa la lista di output.
*/

void stampa(struct nodo2 *primo2) {
	printf("mese\timporto\n");
	while (primo2 != NULL) {
		printf("%d\t%d\n", primo2->m, primo2->importo);
		primo2 = primo2->next;
	}
	return;
}


/*
**	main
**
**	funzione principale che richiama tutte le altre.
*/

int main(void) {
	struct nodo *primo;
	struct nodo2 *primo2;
	int n;

	scanf("%d", &n);
	primo = input(n);
	primo2 = calcola(primo);
	bubble_sort(primo2);
	stampa(primo2);
	return(1);
}