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