Partizione di una lista

/*
**	partizione.c
**
**	Leggere una lista L di interi {x1,...,xn}. Letto in input un intero
**	X (maggiore di ogni xi) ripartire la lista L in k sotto-liste
**	L1,...,Lk tali che la somma degli elementi di ogni sotto-lista sia
**	minore o uguale ad X e sia massimale (l'aggiunta di un elemento ad
**	ogni sotto-lista, tranne al piu` l'ultima, fa superare la soglia X).
**	Stampare le sotto-liste generate.
**
**	Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999
*/

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

#define MAX 50

struct nodo {
	int info;
	struct nodo *next;
};


/*
**	leggi_lista
**
**	legge la lista di interi inseriti dall'utente.
*/

struct nodo *leggi_lista(void) {
	struct nodo *primo, *p;
	int a;

	printf("Inserisci gli elementi della lista (-1 per terminare):");
	primo = NULL;
	scanf("%d", &a);
	while (a != -1) {
		p = malloc(sizeof(struct nodo));
		p->info = a;
		p->next = primo;
		primo = p;
		scanf("%d", &a);
	}

	return(primo);
}


/*
**	stampa_lista
**
**	stampa una lista il cui primo elemento e` puntato da p
*/

void stampa_lista(struct nodo *p) {
	while (p != NULL) {
		printf("%d -> ", p->info);
		p = p->next;
	}
	printf("NULL\n");
	return;
}


/*
**	suddividi
**
**	seleziona i primi elementi della lista fino a quando la soglia X non
**	viene superata. Restituisce il puntatore al primo elemento della
**	sotto-lista estratta e modifica il puntatore al primo elemento della
**	lista originale.
*/

struct nodo *suddividi(struct nodo **primo, int x) {
	struct nodo *p, *primo1, *prec;
	int somma;

	p = *primo;
	primo1 = *primo;
	somma = 0;
	prec = NULL;
	do {
		somma = somma + p->info;
		prec = p;
		p = p->next;
	} while ((p != NULL) && (somma + p->info <= x));

	prec->next = NULL;
	*primo = p;
	return(primo1);
}


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

int main(void) {
	struct nodo *primo, *lista[MAX];
	int i, j, x;

	primo = leggi_lista();
	scanf("%d", &x);

	i = 0;
	while (primo != NULL) {
		lista[i] = suddividi(&primo, x);
		i++;
	}

	for (j=0; j<i; j++) {
		stampa_lista(lista[j]);
	}

	return(1);
}