Gli esercizi
Testi e soluzioni di alcuni esercizi
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(0);
}