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);
}