Problema Insertion_Sort String

di
sballus
il
28 risposte
S
sballus
Pochi posts
Iscritto da
mag, 2014
Messaggi:
24

Problema Insertion_Sort String

Salve a tutti , ho bisogno d'aiuto. Non riesco ad utilizzare l'algoritmo insertion sort x stringhe.
Vedo negli esempi sempre l'utilizzo di int e di array, io invece voglio utilizzare string e list.

28 Risposte

  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    Ciao,
    rieccoci!

    Il principio è sempre lo stesso: prendi l'algoritmo (il metodo che ti avevo postato per l'esercizio precedente) e fai i confronti con la funzione compareTo della classe String, anziché con gli operatori > e <.
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Ti faccio vedere cosa ho scritto finora: 
    
public class GestioneStringhe 
{
	public List<String> listaDiStringhe;
	
	public GestioneStringhe()
	{
		listaDiStringhe = new LinkedList<String>();
		
	}
	
	public void leggiStringhe()
	{
		 // creo un oggetto Scanner per leggere input da tastiera
        Scanner sc = new Scanner(new InputStreamReader(System.in));

        String line;
       

        // ciclo potenzialmente infinito
        while(true)           //(1 != 0) 
		{
            System.out.print("Inserire parola: ");

            // leggo la riga inserita dall'utente
            line = sc.nextLine();

            // se la riga e' vuota allora smetto di leggere
            if(line.equals("")) break;

                 

            // aggiungo il numero alla lista
            listaDiStringhe.add(line);
		}
        // chiudo lo scanner
        sc.close();
	}

	 /**
     * Metodo che stampa la lista
     */
    public void stampaLista() 
	{
        for(int i=0; i<list.size(); i++) 
		{
            System.out.println(list.get(i));
        }
    }
	
	public List<String> getListaDiStringhe() {
		return listaDiStringhe;
	}

	public void setListaDiStringhe(List<String> listaDiStringhe) {
		this.listaDiStringhe = listaDiStringhe;
	}
	
	//metodo per l'ordinamento di una lista di stringhe con insertion sort
	public void insertionSort(List<String> listaDiStringhe)
	{
		for( int i=1;i.;i++)
			
			
		
	}
	
	//metodo che, data una stringa in input, restituisce la stringa invertita
	public static String invertiStringa(String daInvertire)
	{
			return daInvertire;
	}
	
	public LinkedList<String> generaListaInvertita()
	{
		
	}
	
	
    public static void main(String[] args)
    {
    	GestioneStringhe gs = new GestioneStringhe();
    	gs.leggiStringhe();
         System.out.println("Lista non ordinata:");
         gs.stampaLista();
         gs.insertionSort(listaDiStringhe);;
         System.out.println("Lista ordinata:");
         gs.stampaLista();
        
    	
	}
}
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Ma come devo sostituire il tipo di valore da int a string in questo metodo?: 
    
  // Metodo InsertionSort 
 	public void insertionSort() {
 		int tmp;
 		int j;
 		for(int i=1; i<list.size(); i++) {
 			j=i-1;
 			tmp = list.get(i);
 			while(j >= 0 && list.get(j) > tmp) {
 				// "scorrimento"
 				list.set(j+1, list.get(j));
 				j--;
 			}
 			// inserimento
 			list.set(j+1, tmp);
 		}
 	}
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    Secondo me è meglio partire dal metodo che avevamo scritto per gli interi:
    
	public void insertionSort() {
		int tmp;
		int j;
		for(int i=1; i<list.size(); i++) {
			j=i-1;
			tmp = list.get(i);
			while(j >= 0 && list.get(j) > tmp) {
				// "scorrimento"
				list.set(j+1, list.get(j));
				j--;
			}
			// inserimento
			list.set(j+1, tmp);
		}
	}
    Ora con qualche modifica dovresti riuscire ad adattarlo per le stringhe...
    Cambia i tipi di dato e il modo di fare i confronti: tutto il resto è uguale!
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    sballus ha scritto:

    ma come devo sostituire il tipo di valore da int a string in questo metodo?:
    Sicuramente la variabile tmp (variabile di appoggio) dovrà diventare String...
    Poi come cambiano i confronti? Abbiamo detto che devi utilizzare il metodo compareTo...
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Ho scritto questo ma è sbagliato. Non capisco xke mi viene cosi difficile 
    
public void insertionSort(List<String> listaDiStringhe)
	{
		    String tmp;
			String j;
			for(int i=1; j.compareTo(tmp); i++) 
			      {
			         j=i-1;
			         tmp = listaDiStringhe.get(i);
			         while(j = 0 && j.compareTo(tmp) ) 
			         {
			            // "scorrimento"
			        	 listaDiStringhe.set(j+1, listaDiStringhe.get(j));
			            j--;
			         }
			         // inserimento
			         listaDiStringhe.set(j+1, tmp);
			      }
	}
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    Purtroppo devo dirti che ci sono cose poco sensate nel codice che hai scritto.
    Ad esempio perché hai messo anche j come String? j serve solo per tenere traccia di una posizione, quindi è un int a prescindere dal tipo di dato che devi ordinare. Poi ovviamente non ha senso il j.compareTo.
    Inoltre while j=0...... ?

    Facciamo così: prova a guardare la soluzione e soprattutto prova a capire perché trovavi difficoltà.
    
	public void insertionSort() {
		String tmp;             // questo cambia!
		int j;                      // questo NO!
		for(int i=1; i<list.size(); i++) {
			j=i-1;
			tmp = list.get(i);
			while(j >= 0 && list.get(j).compareTo(tmp) > 0) {
				// "scorrimento"
				list.set(j+1, list.get(j));
				j--;
			}
			// inserimento
			list.set(j+1, tmp);
		}
	}
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Ho capito dove stavano gli errori. Per creare l'inversione della stringa devo utilizzare un ciclo condizionale di if else??
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Devo utilizzare il metodo charAt??
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Ho scritto qualcosa anche se non capisco come passargli le stringhe di input 
    
//metodo che, data una stringa in input, restituisce la stringa invertita
	public static String invertiStringa()
	{
		String a;
        int lunghezza,i;
        char b;
       a= listaDiStringhe; // PROBLEMA!!
        lunghezza=a.length();
        char[] inversa = new char[lunghezza];
        System.out.println("La stringa invertita e': ");
        for(i=0;i<a.length();i++)
        {
            b=a.charAt(i);
            inversa[lunghezza-1]=b;
            lunghezza=lunghezza-1;
        }
        String s=new String(inversa);
		System.out.println(s);
	    
    }
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    Dunque... nel metodo invertiStringa la lista di stringhe non c'entra nulla! Quel metodo deve semplicemente prendere in input una stringa e restituire la stringa invertita. Punto.
    Il metodo charAt è una buona idea, ma devi capire come utilizzarlo. Molto semplicemente devi partire dall'ultimo carattere e tornare indietro, concatenando i caratteri che leggi.
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Quindi il codice è sbagliato?? tu come hai fatto? Non hai utilizzato charAt??
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Problema Insertion_Sort String

    Certo che ho utilizzato charAt!
    Ma il tuo codice funziona? Perché se funziona è un conto, ma se non funziona allora è sbagliato! Non fa una piega...
  • S
    sballus
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    24

    Re: Problema Insertion_Sort String

    Il mio non funziona 
    
//metodo che, data una stringa in input, restituisce la stringa invertita
	public static String invertiStringa()
	{
		String a;
        int lunghezza,i;
        char b;
        System.out.print("Inserisci una parola: ");
        Scanner sc = new Scanner(System.in);
        a = sc.nextLine();
        lunghezza=a.length();
        char[] inversa = new char[lunghezza];
        System.out.println("La stringa invertita e': ");
        for(i=0;i<a.length();i++)
        {
            b=a.charAt(i);
            inversa[lunghezza-1]=b;
            lunghezza=lunghezza-1;
        }
        String s=new String(inversa);
		System.out.println(s);
		
		
		return s;
	
	}
Devi accedere o registrarti per scrivere nel forum
28 risposte