sabato 2 gennaio 2010

Ordinamento di una lista (Java)

Ultimamente a causa degli impegni tra cui la prova in itinere di Programmazione 1, della quale oggi ho avuto l'esito! Non ho più postato nulla sui miei esercizi in java!(nonostante ne abbia fatti a bizzeffe).

L'altro giorno studiando un altra materia di informatica ho provato ad implementare alcuni algoritmi di cui conosco qualche cenno.

Ho scritto quindi un programma che presa una lista di stringe (un array) in cui l'ordine delle stringhe è casuale,lo riordina secondo un principio lessicografico. (clicca per approfondire su Wikipedia.)

Dato l'utilizzo massiccio dei metodi durante la preparazione per la prova in itinere ormai ho preso l'abitudine di dividere in queste "camere stagne" il mio programma...

Cosa c'è da sapere?
parola1.compareTo(parola2) : Supponiamo che parola1 e parola2 siano due stringhe, questo metodo restituisce un intero che indica quale stringa viene prima in ordine lessicografico,
Se da un numero negativo, parola 1 va posta prima di parola 2, se positivo, viceversa.
Se invece si ottiene 0, le due parole sono esattamente uguali.

Descrizione dei metodi

Partiamo dai metodi "fondamentali"... il metodo find è una di quelle camere stagne di cui parlavo sopra (per metodo si intende una parte di codice "stagna", cioè che dati dei parametri restituisce un risultato, il programmatore quindi non si deve occupare di verificare cosa faccia esattamente il metodo, gli basta sapere cosa vuole sapere(parametri in ingresso) e cosa da(parametri in uscita))
questo metodo data un'arrai di stringhe ed una parola, restituisce l'indice in cui la parola andrebbe inserita, ad esempio se l'array contiene le parole(le parentesi indicano gli indici): barca(0),casa(1),mare(2) e noi inseriamo la parola "dattero" ci restituisce il numero 2.

Il metodo inserisci invece preso un indice, una stringa ed un array di stringhe, da in output un array di stringhe dove nell'indice dato è stata inserita la parola e le parole che stavano a partire da quel indice, vengono spostate di un posto (di volta in volta l'ultima parola viene persa)

Adesso possiamo passare al metodo centrale che è il metodo ordina, questo metodo prende un'array di stringhe e ne restituisce uno ordinato facendo uso dei due metodi utilizzati sopra.

Eccovi il codice... dovreste capirci qualcosa in più:

  1. public class Ordinamentok

  2. {

  3.     public static void main (String[]args)

  4.     {

  5.         String[] disordinato ={"Rossi","Iemolo","Cavallaro","Di Natale"

  6.                                        ,"Carrubba","Dimauro","Lanza","no name"};

  7.         String[] ordinato = ordina(disordinato);

  8.         for(int i=0;i<ordinato.length;i++)

  9.         {

  10.             System.out.println(ordinato[i]);

  11.         }

  12.     }

  13.     public static String[] ordina (String[] A)

  14.     {

  15.         String[]B= new String [A.length];

  16.         for(int j =0;j<B.length;j++)

  17.         {

  18.             B[j]="~~";

  19.         }

  20.         for (int i=0;i<A.length;i++)

  21.         {

  22.             int indice=find(B,A[i]);

  23.             B=inserisci(A[i],B,indice);

  24.         }

  25.         return B;

  26.     }

  27.     public static String[] inserisci(String parola, String[]A, int c)

  28.     {

  29.         String[]out=new String[A.length];

  30.         if(c>0)

  31.         {

  32.             for(int i=0;i<c;i++)

  33.             {

  34.                 out[i]=A[i];

  35.             }

  36.         }

  37.         out[c]=parola;

  38.         for(int j=c+1;j<out.length;j++)

  39.         {

  40.             out[j]=A[j-1];

  41.         }

  42.         return out;

  43.     }

  44.     public static int find(String[] lista, String parola)

  45.     {

  46.         int sup=lista.length;

  47.         int inf=0;

  48.         while(((sup-(inf))/2)>=1)

  49.         {

  50.             int a=((sup-(inf))/2)+inf;

  51.             if((parola.compareTo(lista[a]))<0)

  52.             {

  53.                 sup=a;

  54.             }

  55.             else

  56.             {

  57.                 inf=a;

  58.             }

  59.         }

  60.         if(parola.compareTo(lista[sup])<0)

  61.             return inf;

  62.         return sup;

  63.     }

  64. }



per qualsiasi chiarimento sono a vostra disposizione!
P.S. la prova è andata abbastanza bene! ho preso 30 ;-p

Nessun commento:

Posta un commento