Gli esercizi

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