miércoles, 30 de noviembre de 2011

colas en jav

package colas;


import java.util.*;

public class Colas {


  
    public static void main(String[] args) {

                            Scanner leer = new Scanner(System.in);

                    int num;
                  
 int op;
                   
LinkedList lista = new LinkedList();
   
                do{
                        System.out.println( "\t Menú \t" );
  
                     System.out.println( "Operaciones con listas" );
             
          System.out.println( "1.- Insertar el elemento" );
                
       System.out.println( "2.-  remover el elemento" );
 
                     System.out.println( "3.- Mostrar la cola" );
      
                System.out.println( "4.- Borrar toda la cola" );
     
                 System.out.println( "5.- Salir" );
        
       
      System.out.println( "\n" );
          
            System.out.println( "Elija la operación que desee" );
        
              op = leer.nextInt();
 switch(op){
 case 1:
     
 System.out.println( "Inserte numero" );
     
  num = leer.nextInt();
       
lista.addFirst(num);
     
  break;
case 2:
      
   System.out.println( "Se borrara el primer nodo" );
  
        lista.removeLast();
       
   break;
 case 3:
  
    System.out.println( "La cola es la siguiente" );
  
    List lista2 = new ArrayList(lista);
    
  Iterator it = lista2.iterator();
    
   while (it.hasNext()){
       
 System.out.println(it.next()+"");
 
              }
       
  break;
 case 4:
      
          System.out.println( "Se borraran toda la cola" );
  
              lista.clear();
     
           break;

 case 5:
           
         System.out.println( "Al rato" );
      
               break;
 }
                    }
        
     while( op != 7 );

             
  }

         
  }


      
            
       
           

martes, 29 de noviembre de 2011

Busqueda Binaria

CONCEPTO1.- Es un metodo que permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de busqueda binaria. Es un algoritmo muy eficiente ya que requiere de poco tiempo para realizar una busqueda CONCEPTO2.- La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo.
CARACTERISTICAS.- Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
  • Los datos deben estar contenido en un estructura de datos tipo vector
  • Los datos del vector deben estar ordenados 
Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18).

OPERACIONES.-Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.
 Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.

Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente:
Int BinarySearch ([ ] m. tipo clave)
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera
  1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
  2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
  3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
  4. Si son distintos, evaluamos si vector[Icentro] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.
  5. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.
PROGRAMA.-

//Busqueda binaria
//en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constante
int busquedaBinaria(const int[], int, int); //arreglo, tamano, clave
void ordenarArreglo(int[], int); //prototipo que modifica y ordena el
arreglo
void intercambiar(int&, int&); //prototipo, intercambia
los valores de dos elementos
int main()
{
int clave =0;
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78…
//ordenamos el arreglo para que funcione la busquedaBinaria
ordenarArreglo(arreglo,tamano);
cout << "Elementos del arreglo: " << endl;
mostrarArreglo(arreglo,tamano);
cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
cin >> clave;
cout<< "Su valor se encuentra en arreglo["<<busquedaBinaria(arreglo,taman… << endl;
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo[" << i << "]=" << arreglo[i] << endl;
}
int busquedaBinaria(const int arreglo[], int tamano, int clave)
{
int Iarriba = tamano-1;
int Iabajo = 0;
int Icentro;
while (Iabajo <= Iarriba)
{
Icentro = (Iarriba + Iabajo)/2;
if (arreglo[Icentro] == clave)
return Icentro;
else
if (clave < arreglo[Icentro])
Iarriba=Icentro-1;
else
Iabajo=Icentro+1;
}
return -1;
}
void ordenarArreglo(int arreglo[], int tamano)
{
for (int i = 0; i< tamano -1 ; i++)
for (int j = 0; j< tamano -1 ; j++)
if (arreglo[j] > arreglo[j+1])
intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
int tmp = b;
b = a;
a = tmp;
}
video de busqueda binaria




 


 

jueves, 3 de noviembre de 2011

Arboles

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples.
En relación con otros nodos:
Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Arboles Binarios
Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:

El Árbol Binario es Vació si no tiene ningún elemento en el.

El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.

Los Árboles tiene 3 Recorridos Diferentes los cuales son:

Pre-Orden

In-Orden

Post-Orden

Pre-Orden

Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:

PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprimir “Árbol Vació…” y Salir

Repetir mientras Temp ≠ Nulo

Imprimir Arbol[Temp]

Si Der[Temp] ≠ Nulo

Top → Top + 1

Pila[Top] → Der[Temp]

Si Izq[Temp] ≠ Nulo

Temp → Izq[Temp]

Si no:

Temp → Pila[Top];

Top → Top - 1

Fin del ciclo

Salir


In-Orden

Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:

PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprmir “Arbol Vacio…” y Salir

Etiqueta:

Mientras Temp ≠ Nulo

Top → Top + 1

Pila[Top] → Temp

Temp → Izq[Temp]

Fin del ciclo

Temp → Pila[Top]

Top → Top - 1

Mientras Temp ≠ Nulo

Imprimir Arbol[Temp]

Si Der[Temp] ≠ Nulo

Temp → Der[Temp]

Ir a Etiqueta

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Salir



In-Orden

Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la Raiz.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Algoritmo:

PostOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz

Top →

Pila[Top] → Nulo

Si Raiz = Nulo

Imprimir “Arbol Vacio…” y Salir

Etiqueta:

Mientras Temp ≠ Nulo

Top → Top + 1

Pila[Top] → Temp

Si Der[Temp] ≠ Nulo

Top → Top + 1

Pila[Top] → - (Der[Temp])

Temp → Izq[Temp]

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Mientras Temp ≥ 0

Imprimir Arbol[Temp]

Si Arbol[Temp] = Info[Raiz]

Salir

Temp → Pila[Top]

Top → Top - 1

Fin del ciclo

Si Temp < 0

Temp = -(Temp)

Ir a Etiqueta

Salir

Búsqueda

Definición:

La Búsqueda es Similar a todas los Métodos anteriores de Búsqueda, simplemente efectúa un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos.

Detalle:

El Algoritmo de Búsqueda compara el Elemento a buscar con cada uno de los datos de nuestro Árbol, compara si el Elemento con el Nodo Raíz, si no se encuentra en la Raíz… compara Elemento contra la Raíz para empezar a viajar por el Árbol respectivamente, usa un método similar al anterior hasta encontrar el Elemento. De otra forma la búsqueda es fallida.

Algoritmo:

Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem)

Si Raiz = Nulo

Imprimir “Arbol Vacio”

Pos → Nulo

Pad → Nulo

Regresar Pos y Pad

Salir

Si Elem = Arbol[Raiz]

Imprimir “Elemento Encontrado”

Pos → Raiz

Pad → Nulo

Regresar Pos y Pad

Salir

Si Elem < Arbol[Raiz]

Temp → Izq[Raiz]

Temp2 → Raiz

Si no:

Temp → Der[Raiz]

Temp2 → Raiz

Mientras Temp ≠ Nulo

Si Elem = Arbol[Temp]

Imprimir “Elemento Encontrado…”

Pos → Temp

Pad → Temp2

Regresar Pos y Pad

Salir

Si Elem < Arbol[Temp]

Temp2 → Temp

Temp → Izq[Temp]

Si no:

Temp2 → Temp

Temp → Der[Temp]

Fin del ciclo

Imprimir “Elemento no Encontrado…”

Pos → Nulo

Pad → Temp2

Regresar Pos y Pad

Salir

Colas

Una cola es una colección de elementos homogéneos (almacenados en dicha estructura), en la misma se pueden insertar elementos por uno de los extremos, llamado frente, y retirar los mismos por el otro extremo, denominado final.

Es importante aclarar que, tanto el frente como el final de la cola, son los únicos indicados para retirar e insertar elementos, respectivamente. Esto nos indica que no podemos acceder directamente a cualquier elemento de la cola, sino solo al primero, o sea el que está o se encuentra en el frente, y no se pueden insertar elementos en cualquier posición sino solo por el final, así el elemento insertado queda como último

Operaciones
Las operaciones básicas que pueden efectuarse son:
Insertar un elemento en la cola

Eliminar un elemento de la cola

Las inserciones se llevaran a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE —recuerde que el primero en entrar es el primero en salir.

Considerando que una cola puede almacenar un máximo número de elementos y que además FRENTE indica la posición del primer elemento y FINAL la posición del último, se presentan a continuación los algoritmos correspondientes a las operaciones mencionadas.

aplicacion

se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).

Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".

Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.