SoloCodigo

Programación General => Java => Mensaje iniciado por: SFRJ en Martes 14 de Octubre de 2008, 22:32

Título: Algoritmos y Estructura de Datos
Publicado por: SFRJ en Martes 14 de Octubre de 2008, 22:32

Hola a todos colegas.
Escribo este post, porque me estoy preparando para mi primer examen de estructura de datos.

Tengo como objetivo crear  una estructura de datos estatica y que utilice una tecnica de acceso a los elementos directo(Osea que no sea ni LIFO ni FIFO, sino que cuando yo quiera sacar un elemento pueda sacar el que me de la gana), que organice de menor a mayor los objetos que en ella se introducen, para que luego el denominado proceso binarySearch sea posible. Les voy a mandar una clase que he recibido de mi Profesora de Belgrado en la cual ella implementa esta estructura, tengo grandes problemas entendiendo el metodo add().
Me gustaria saber que pensais sobre esta clase y tambien si existe alguna forma mas simple de hacer el metodo add() de alguna manera mas rapida que me organice inmediatamente los balores en el array con algun metodo de las libraries, o algo por el estilo...

Bueno yo ai os mando este pequeno trozo de codigo haber que pensais:
//CODIGO

public class SortedArrayList implements ISortedList {
   private Comparable[] array;
   private int counter;   
   public SortedArrayList(int size) {
      if ( size < 0 ) {
         System.err.println("Kapacitet listemorabiti pozitivan broj");
         size = 20;
      }      
      array = new Comparable[size];
      counter = 0;
   }   
   @Override
   public void add(Comparable c) {
      if ( isFull() ) {
         System.err.println("Lista je vec puna, operacija se ne moze izvrsiti");
         return;
      }
      if ( isEmpty() ) {//Ako je niz prazan ulazni argument dodijeljujese prvoj poziciji
         array[counter++] = c;
         return;//kraj!
      }      
      int index = 0;
   //Vrijednost manje od 0 dobijemo od metoda compareTo(Comparable c), kada je array[index] < od zadat argument.      
   //Dobicemo vrijednost 1 od metoda compareTo, kada zadat argument bude veci nego onaj vrijednost s kojim smo uporedili   
//Jel pozicija array[index] manja do vrijednost ulaznog argumenta? Ako da       
      while ( index < counter && array[index].compareTo(c) < 0) {
         index++;//Ako da onda uvecamo index jer treba da bude sortirano od manje do vece
      }
      for(int i = counter; i > index; i--) {
         array = array[i-1];
      }
      array[index] = c;
      counter++;
   }
   @Override
   public int exists(Comparable c) {      
      int lowerBound = 0;
      int upperBound = counter - 1;      
      while ( lowerBound <= upperBound ) {         
         int currentIndex = (lowerBound + upperBound)/2;
         if ( array[currentIndex].compareTo(c) == 0 )
            return currentIndex;
         if ( array[currentIndex].compareTo(c) < 0 )
            lowerBound = currentIndex + 1;
         else //array[currentIndex].compareTo(c) > 0
            upperBound = currentIndex - 1;         
      }      
      return -1;      
   }

   @Override
   public boolean isEmpty() {
      return counter == 0;
   }

   @Override
   public boolean isFull() {
      return counter == array.length;
   }

   @Override
   public void print() {      
      System.out.println("Prikaz elemenate niza:");
      for (int i = 0; i < counter; i++) {
         System.out.println( array );
      }
   }

   @Override
   public Comparable remove(Comparable c) {      
      if ( isEmpty() ) {
         System.err.println("Lista je prazna; operacija se ne moze izvrsiti");
         return null;
      }      
      int toRemoveIndex = exists(c);
      Comparable temp = array[toRemoveIndex];      
      for (int i = toRemoveIndex; i < counter - 1 ; i++) {
         array = array[i+1];
      }      
      counter--;
      return temp;
   }

}

Título: Re: Algoritmos y Estructura de Datos
Publicado por: m0skit0 en Miércoles 15 de Octubre de 2008, 10:25

Hola SFRJ, veo que dominas muy bien el español para ser balcánico! Como yo!  ^_^ Te agradecería que usaras las etiquetas de código así tu código será más legible, queda más bonito y todos tan contentos, jeje...

Cita de: "SFRJ"

una tecnica de acceso a los elementos directo

Es decir, arrays/vectores/arreglos.

Cita de: "SFRJ"

que organice de menor a mayor los objetos que en ella se introducen

Código: Java

1.  
2. public void add(Comparable c) {
3.     if ( isFull() ) {
4.         System.err.println("Lista je vec puna, operacija se ne moze izvrsiti");
5.         return;
6.     }
7.  
8.     if ( isEmpty() ) {
9.         array[counter++] = c;
10.         return;
11.     }
12.  
13.     int index = 0;
14.     while ( index < counter && array[index].compareTo(c) < 0) {
15.         index++;
16.     }
17.  
18.     for(int i = counter; i > index; i--) {
19.         array[i] = array[i-1];
20.     }
21.  
22.     array[index] = c;
23.     counter++;
24. }
25.  

Bueno, debido a que no sé serbio he quitado los comentarios. Los dos primeros if son los casos triviales de vector vacío y vector lleno. En el caso de que el vector no esté ni lleno ni vacío, busca la posición en que encaja el nuevo valor, mueve los anteriores valores (menores que él) a direcciones más bajas e inserta el valor. No creo que se pueda hacer de una forma más sencilla.

Por cierto,

Cita de: "SFRJ"

balores

valores y

Cita de: "SFRJ"

haber que pensais

a ver qué pensáis  :P  

Saludos!

Título: Re: Algoritmos y Estructura de Datos
Publicado por: SFRJ en Miércoles 15 de Octubre de 2008, 13:23

He estado analizando el ejemplo, me sigue pareciendo un poquillo complicado para entenderlo, asi que he decidido intentar algo mas simple.
Mira veras:

tengo un array-->    [ ]  [ ]  [ ]  [ ]  [ ]  [ ]  length = 6

Si este array estuviese lleno, entonces no podria utilizar el metodo add() o insert() o cualquiera que intentase introducir un elemento. Hasta aki ok!

Si este array estuviese vacio, entonces el elemento introducido se colocara en la primera posicion, ya que no hay ninguna necesidad para organizar nada.

Ahora viene el problema :)
si tenemos esta situacion:

                               [5]  [6]  [7]  [9]  [10]  [ ] <-- Este ultimo esta vacio para que sea posible desplazar a la derecha.

Ahora que tengo que hacer, si quiero introducir el elemento [8].
Tengo que desplazar los elementos en las posiciones [9]  [10] a la derecha 1 y en la posicion 3(donde estaba inicialmente el elemento [9]) , escribir el elemento [8]

Entiendo lo que tengo que hacer en teoria, pero en la practica me lio un poco.
 Me podrias echar un cable para hacer un pequeno metodo que solucionase este problemilla?
-Tengo que buscar el elemento mayor que [8] osea([9]) y cuando lo encuentre apartir de el desplazarlo para poder a la posicion del array[3] dar el valor 8 (array[3] = 8) .

Yo he pensado algo asi:

//Imaginemos que el array es asi -->
                   private int[] array = new int[n];
                   private int pointer = -1; //Marka en que posicion nos encontramos

                  public void add(int e) {
                         
                            if(isFull()) {
                               System.out.println("No se puede introducir el array esta lleno!");
                               return;
                            }
                           
                           if(isEmpty()) {
                              array[0] = e;
                              return;
                           }

//AKI NECESITO AYUDA COMO IMPLEMENTARIA ESTA PARTE.
//TENGO UN LIO ENORME EN LA CABEZA :) hehe...
                         // for(int i = pointer; i >= 0; i-- ) {
                         //          if(e > array) {                        
                         //                 array[]
                                   }
                          }
                  }


Muchas gracias por tu ayuda.
Por cierto tu de donde eres?

Título: Re: Algoritmos y Estructura de Datos
Publicado por: m0skit0 en Miércoles 15 de Octubre de 2008, 15:41

Como te he comentado, usa etiquetas de código para el código...

En el código que has puesto en tu primer post (el de tu profesora de Belgrado, que ha sido el que copiado en el mío) parece que está bien el método add(), que te explico anteriormente. ¿Qué es exactamente lo que no entiendes?

(Hay una banderita al lado de mi info de ubiación...  :rolleyes: )

Título: Re: Algoritmos y Estructura de Datos
Publicado por: SFRJ en Miércoles 15 de Octubre de 2008, 16:35

El problema es el siguiente y es que no se como organizar el array segun voy introducioendo los argumentos:
Mira este codigo que he escrito poco despues de mi ultimo post.
Estoy intentando simplificar al maksimo para lograr entenderlo :)

Código: Text

1. public class ManualSorting {
2.  
3.     private int[] organizedNumbers;
4.     private int counter2 = 0;
5.    
6.     public ManualSorting(int size) {
7.         organizedNumbers = new int[size];
8.     }
9.    
10.    
11.     public void addAnumInBunchOfOrganizedNumbers(int num) {        
12.         //isFull()
13.         if(counter2 == organizedNumbers.length -1) {
14.             System.out.println("Array full!");
15.             return;
16.         }
17.         //isEmpty()
18.         if(counter2 == 0) {
19.             organizedNumbers[counter2] = num;
20.             counter2++;
21.             return;
22.         }  
23.        
24.         int index = 0;
25.        
26.         for (index = 0; index < organizedNumbers.length; index++) {
27.               if(!( organizedNumbers[index] < num) ) { break; }
28.             }
29.        
30.         index--;
31.         for (int i = organizedNumbers.length; i > index; i-- ) {
32.               organizedNumbers[i+1] = organizedNumbers[i];
33.             }
34.        
35.         organizedNumbers[index] = num;
36.        
37.         counter2++;
38.     }  
39.    
40.     public void printSorted() {
41.         for (int i = 0; i < organizedNumbers.length; i++) {
42.            
43. //          if(numbers[i] == 0) {
44. //              continue;
45. //          }
46.            
47.             System.out.print(numbers[i] + " ");        
48.         }      
49.         System.out.println();
50.     }
51. }
52.