Gli esercizi

Testi e soluzioni di alcuni esercizi

Ordinamento di una lista con l'algoritmo Bubble sort

Data in input una lista di numeri, la ordina utilizzando l'algoritmo Bubble sort.

/*
**  lista_bubble_sort.c
**
**  Legge in input una sequenza di numeri e la memorizza in una lista.
**  Quindi applica l'algoritmo di "bubble sort" per ordinare la
**  lista in ordine crescente.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999
*/

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


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


/*
**  leggi_lista
**
**  legge in input una sequenza di numeri interi fino a quando
**  l'utente non digita "-1". I numeri letti vengono man mano
**  memorizzati in una lista. La funzione restituisce un puntatore
**  al primo elemento della lista (l'indirizzo di memoria del
**  primo elemento della lista).
*/

struct nodo *leggi_lista(void) {
  int a;
  struct nodo *p, *primo;
  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
**
**  visualizza in output una lista di adiacenza; si aspetta come
**  parametro l'indirizzo di memoria (il puntatore) del primo
**  elemento della lista.
*/

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


/*
**  bubble_sort
**
**  Accetta come parametro il puntatore al primo elemento
**  della lista; la ordina utilizzando l'algoritmo "bubble
**  sort" e restituisce il puntatore al primo elemento
**  della lista.
*/

struct nodo *bubble_sort(struct nodo *primo) {
  struct nodo *p, *ultimo;
  int flag, appo;

  ultimo = NULL;

  flag = 1;
  while (flag == 1) {
    p = primo;
    flag = 0;
    while (p->next != ultimo) {
      if (p->info > (p->next)->info) {
        appo = p->info;
        p->info = (p->next)->info;
        (p->next)->info = appo;
        flag = 1;
      }
      p = p->next;
    }
    ultimo = p;
  }

  return(primo);
}


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

int main(void) {
  struct nodo *primo;
  printf("Inserisci gli elementi (-1 per terminare): ");
  primo = leggi_lista();
  primo = bubble_sort(primo);
  stampa_lista(primo);
  return(0);
}