Un esercizio apparentemente semplice: dati un certo numero di parole, ordinarle in ordine alfabetico. Vediamo come farlo usando il selection sort e qualche stratagemma dei vettori di char. La struttura dati candidata a gestire tutto è ovviamente una matrice.
Indice dei contenuti
La struttura dati
Partiamo dalla matrice iniziale. La costruiamo di 3 parole di lunghezza massima 255 caratteri per fare test più agevoli. Possiamo usare la direttiva #define o le variabili const per inizializzare i valori a livello globale e cambiare i valori successivamente.
Lettura e stampa
A questo punto possiamo inserire le parole. Qui scegliamo di usare una funzione per tenere il codice più pulito. La funzione inserisciPArole non torna nulla se non void ma prende in ingresso la nostra matrice. Ricordo al lettore che vettori e metrici passati come parametro alle funzioni sono gli unici che sono passati in automatico per riferimento: se modifico vettore o matrice nella funzione, nel main o programma chiamante otterrò la stessa variabile modificata, non una sua copia. Stampiamo le parole inserite per controllo con l’opportuna funzione stampaParole.
Ordinamento
Veniamo al cuore del nostro algoritmo: l’ordinamento. Sfruttiamo il più classico e semplice degli algoritmi, il selection sort. Trovate molto materiale e spiegazione sui manuali scolastici o in rete, ad esempio qui su wikipedia. In sostanza, con un doppio ciclo, ogni parola del nostro set viene confrontata con le sue successive, ed eventualmente scambiata se risponde ai requisiti. Qui abbiamo semplificato tutto l’iter suddividendo in funzioni sia il confronto che lo scambio. Occhio allo scambio in c tra stringhe: richiede l’uso di strcpy!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PAROLE 3
#define LUNGHEZZA 255
void inserisciParole(char [][LUNGHEZZA]);
void stampaParole(char [][LUNGHEZZA]);
void ordina(char [][LUNGHEZZA]);
int confrontaParole(char [], char []);
void scambiaParole(char [], char []);
int main()
{
char parole[PAROLE][LUNGHEZZA];
inserisciParole(parole);
printf("\n----------------------------\n");
printf(" Parole inserite \n");
printf("----------------------------\n");
stampaParole(parole);
ordina(parole);
printf("\n----------------------------\n");
printf(" Parole ordinate \n");
printf("----------------------------\n");
stampaParole(parole);
return 0;
}
void inserisciParole(char _parole[][LUNGHEZZA])
{
int i;
for (i=0; i < PAROLE; i++)
{
printf("Inserisci la %d° parola: ",i+1);
scanf("%s",_parole[i]);
}
}
void stampaParole(char _parole[][LUNGHEZZA])
{
int i;
for (i=0; i < PAROLE; i++)
{
printf("%d° parola: %s\n",i+1, _parole[i]);
}
}
void ordina(char _parole[][LUNGHEZZA])
{
int i,j, indicemin;
for (i=0; i < PAROLE-1; i++)
{
indicemin = i;
for(j=i+1; j < PAROLE; j++)
{
if (confrontaParole(_parole[j], _parole[indicemin]) == 1)
indicemin = j;
}
scambiaParole(_parole[indicemin], _parole[i]);
}
}
int confrontaParole(char _parola1[], char _parola2[])
{
int i;
int daScambiare = 0;
int len1 = strlen(_parola1);
int len2 = strlen(_parola2);
int minLen = len1 > len2 ? len2 : len1;
for (i=0; i < minLen; i++)
{
if (_parola1[i] > _parola2[i])
return 1; //scambiare
if (_parola1[i] == _parola2[i])
daScambiare = 0;
if (_parola1[i] < _parola2[i])
daScambiare = -1; //usi futuri
}
//scambio metto la più corta
if (len1 > len2 && daScambiare == 0)
{
daScambiare = 1;
}
return daScambiare;
}
void scambiaParole(char _parola1[], char _parola2[])
{
char tmp[LUNGHEZZA];
strcpy(tmp, _parola1);
strcpy(_parola1, _parola2);
strcpy(_parola2, tmp);
}
Ultima modifica 9 Giugno 2022
