Estructuras lineales y no lineales

Estructuras primitivas y simples


Estructuras primitivas: No están compuestas por otras estructuras de datos. Algunos ejemplos son: enteros, booleanos y caracteres. Otras estructuras de datos se pueden construir de una o mas primitivas.

Estructuras de datos simples: Se construyen a partir de estructuras primitivas y son: cadenas, arreglos y registros.


Estructuras lineales y no lineales

Las estructuras de datos simples se pueden combinar de varias maneras para formar estructuras mas complejas. Las dos clases principales de estructuras de datos complejas son las lineales y las no lineales, dependiendo de la complejidad de las relaciones lógicas que representan. Las estructuras de datos lineales incluyen pilas, colas y listas ligadas lineales. Las estructuras de datos no lineales incluyen grafos y arboles.


-       Estructuras lineales
Una de las estructuras lineales de datos mas comunes es la pila. Las operaciones que definen una estructura de datos de tipo pila se presentan para dar paso a la declaración y manipulación de pilas.

Lista lineal: Es una estructura de datos formada por un conjunto de elementos ordenados; el numero de elementos en la lista puede variar. Se puede borrar un elemento o insertar en cualquier posición de la lista. Asi la lista puede crecer o decrecer al transcurrir el tiempo.

Pila

Una pila (stack) es un caso especial de una lista lineal en el cual, la inserción y supresión son operaciones que solo pueden ocurrir en un extremo de la pila, el cual se denomina como tope de la pila. Si se meten varios elementos en la pila y después se sacan de esta, el ultimo elemento en entrar será el primero en salir. (LIFO: last in first out).




Existen cuatro operaciones básicas que son validas para el tipo de datos pila:

1.    Crear (pila)
2.    Está-vacía (pila)
3.    Meter (elemento, pila)
4.    Sacar (pila)

El operador Crear regresa una pila vacia con el nombre P. Por definición: Numel (crear(P)) es 0 y Tope (crear(P)) es nulo.
El operador determina cuando una pila esta vacia o no. El operando es la pila; el resultado es booleano. Está-vacía(P) es verdadero si la pila P esta vacia ( si Numel(p) =0) y falso en caso contrario.
A la operación de añadir un elemento a la pila se le llama meter a la pila. Meter(E,P), agrega un elemento E en el tope de la pila P, aumentando de tamaño la pila.
A la operación de remover un elemento de la pila se le llama sacar de la pila. Sacar(P) remueve un elemento del tope de la pila P disminuyendo el tamaño de la pila. Si el elemento extraido debe conservarse se deberá tomar alguna acción antes de la operación de sacar.


Colas

Es otro caso especial de la estructura de datos de lista lineal. Mientras que en las pilas se restringe la adicion y supresión de elementos a través de un solo extremo, llamado tope de la lista, a las colas se les restringe a que los elementos se supriman por el frente y se agreguen por atrás.

En una cola la inserción se hace estrictamente por un extremo de la lista, al cual podemos llamar fondo; la supresión solo puede hacerse por el otro extremo de la lista, al cual llamamos frente.








Operaciones de colas

Existen cuatro operaciones básicas validas para los datos tipo cola:

1.    Crear (cola)
2.    Está-vacía(cola)
3.    Insertar(elemento, cola)
4.    Eliminar(cola)

Crear(C) produce una cola vacia cuyo nombre es C. Por definición:

Numel (crear(C )) es 0
Frente (crear(C )) es indefinido
Fondo (crear(C )) es indefinido.

El operador Esta-vacia (C ) determina si la cola esta o no vacia. El operando es la cola; el resultado es un valor booleano. Esta-vacia ( C) es verdadero si la cola C esta vacia y falso en caso contrario.

Insertar (E,C) es el operador que inserta el elemento E en la cola C. Por definición E es colocado al final de la cola, el resultado de la operación incrementa la cola. (Fondo es E)

Eliminar ( C), saca el elemento del frente de la cola C, lo cual produce el decrecimiento de la cola. Si se debe conservar este primer elemento, se deberá tomar alguna acción antes de la operación de eliminar.


Listas ligadas

En una línea lineal ligada se representan elementos unidos mediante nodos. Hay un apuntador para el primer nodo de la lista, y cada nodo tiene una liga al siguiente nodo. El ultimo nodo tiene un apuntador NULO, el cual indica que no hay ningún nodo siguiente. Cada nodo tiene dos secciones: el contenido de datos y el campo del apuntador.
Una lista vacia es aquella que no contiene nodos. La representación de lista ligada para una lista vacia es solo un apuntador nulo, al que llamamos “primero”. La operación para crear una lista vacia es:

Primero := Nulo
Operaciones básicas en una lista ligada

Notacion
Sea P una variable apuntadora, cuyo valor es una dirección ( la localidad de alguna otra variable). Las operaciones validas para las variables apuntadoras son las siguientes:

1.    Examinar si un apuntador es Nulo
2.    Examinar la igualdad con otra variable apuntadora
3.    Inicializar con Nulo
4.    Asignar a un apuntador la dirección de un nodo.

Estas son las únicas operaciones que podemos hacer con apuntadores. Denotamos por:

Nodo(P)  el nodo apuntado por P;
Info(P)     el valor de la porción de información del nodo apuntado por P;
Sig(P)      el valor de la liga del nodo apuntado por P.


Remocion de nodos

El algoritmo para remover de una lista ligada el nodo que sigue al apuntado por P, donde Q es un apuntador auxiliar usado para apuntar al nodo que debe ser removido, es el siguiente:

a)    Q:= Sig(P)
b)    Sig(P) := Sig(Q)
c)    Liberar el espacio del nodo apuntado por Q para reusarlo.











Insercion de un nodo

El algoritmo para insertar el contenido de una variable NOMBRE en una lista ligada, de tal forma que siga al nodo apuntado por P es el que sigue. Nuevamente se utiliza el apuntador auxiliar Q y otro mas llamado NUEVO.

a)    Asignar espacio para el nuevo nodo y hacer que NUEVO apunte a este.
b)    Info(NUEVO) := NOMBRE
c)    Q:= Sig(P)
d)    Sig(P) := NUEVO
e)    Sig (NUEVO) :=Q



ESTRUCTURAS DE DATOS NO LINEALES

En estas estructuras cada elemento puede tener varios elementos “siguientes”, lo cual introduce el concepto de estructuras de ramificación. Estas estructuras de datos de ramificación son llamadas grafos y arboles.

Un grafo es un conjunto de puntos y un conjunto de líneas, con cada línea se une un punto a otro. Los puntos se llaman los nodos del grafo, y las líneas se llaman aristas. Un grafo nulo es un grafo con orden cero.
Una arista esta determinada por los nodos que conecta. Un grafo esta completamente definido por sus conjuntos de nodos y aristas. La posición real de estos elementos en la pagina no tiene importancia. Algunas aristas pueden conectar un nodo a si mismo,  a estas aristas se les llama bucles.

Un grafo G se llama grafo simple si las siguientes condiciones son validas.

1.    No tiene ciclos (no existe una arista en E de la forma (v,v), donde V esta en V)
2.    No hay mas de una arista uniendo un par de nodos, esto es, no existe mas de una arista en E de la forma (v1,v2), para cualquier par de elementos v y v en VG

Un grafo que no es simple algunas veces es llamado multígrafo. Encontrara, que a las aristas también se les conoce como arcos y a los nodos como vértices.
Un grafo conexo es una grafica que no se puede dividir en dos graficas, sin eliminar por lo menos una de las aristas.


Trayectorias

Una trayectoria en un grafo es una secuencia de una o mas aristas que conecta a dos nodos.  La longitud de la trayectoria es el numero de aristas que la componen.


Ciclos

Un ciclo es una trayectoria sobre la cual se cumple con las siguientes dos condiciones:
1.    Ninguna arista puede aparecer mas de una vez en una secuencia de aristas.
2.    El nodo inicial de la trayectoria es el mismo que el nodo terminal. (P(v,v)).
Un grafo sin ciclos se dice que es aciclico.


Grafos dirigidos

En el grafo dirigido se les asigna dirección a las aristas de la grafica. Cada arista del grafo dirigido incluye una flecha para indicar la dirección.
El grado interno de un nodo en un grafo es el numero de aristas que terminan en ese nodo; el grado externo de un nodo, es el numero de aristas que salen de ese nodo. El grado de un nodo es la suma de sus grados internos y externos.


ARBOLES
Un árbol es un grafo conexo, simple y aciclico. Un árbol no contiene  ni ciclos ni bucles; existe una sola arista entre cualquier par de nodos.


Arboles Generales
Un árbol se dice que esta enraizado si tiene un nodo (llamado raíz), el cual se distingue de los demás nodos. La raíz del árbol T es denotada por raíz (T).

1.    Hay un nodo especialmente designado llamado Raiz
2.    Los nodos restantes son particionados en >= 0 conjuntos disjuntos, llamados T1, T2, …, TM tales que, cada Ti es por si mismo un árbol. Estos conjuntos son llamados subarboles de la Raiz. Un árbol sin nodos es un árbol nulo.
La raíz de un árbol no esta simplemente seleccionaa de manera aleatoria; mas bien es un nodo que se distingue por la propiedad de:

Grado interno (v) = 0 para v = Raiz(T)
La raíz no tiene ramificaciones de entrada. Debido a que un árbol es un grafo conexo, no puede haber mas de un nodo con esta propiedad.. Una colección de arboles enraizados se llama bosque.

Arboles Binarios

Un árbol binario es un conjunto finito de nodos, el cual puede ser vacio o, puede contener un par de arboles binarios disjuntos, que son llamados subárbol izquierdo y subárbol derecho.
Se dice que dos arboles binarios son similares si tienen la misma estructura.
Los arboles binarios se representan frecuentemente por listas ligadas. Cada nodo puede tener tres campos elementales: un area de información y los apuntadores a los subarboles izquierdo y derecho.







 Estructura de datos y organización de archivos – Mary E. S. Loomis - 2da edición

http://robotica.uv.es/pub/Libro/PDFs/CAPI5.pdf
Publicado por No comments:

Aplicaciones de listas

APLICACIONES
Dos de las aplicaciones mas conocidas de listas son:
  • Representación de polinomios
  • Resolución de colisiones (Hash)
En general puede decirse que las listas son muy útiles para aquellas aplicaciones en las cuales se necesite dinamismo en el crecimiento y reducción de las estructuras de datos

6.1. Aplicacion´ de Listas: Recoleccion´ de Basura y Compactaci´on
En un ambiente de computadores multi-procesos, muchos programas residen en memoria al mismo
tiempo. Diferentes programas tiene diferentes requerimientos de memoria. As´ı un programa puede
requerrir 60K o 300K de memoria. En cualquier momento que el sistema necesite memoria, necesita
localizar memoria continua del tamano˜ deseado. Cuando la ejecuci´on de un programa es terminada,
la memoria que ha sido ocupada debe ser liberada y disponible para otro programa. Mas´ aun, ´
bloques de memoria pueden ser liberados en una secuencia diferente a la que fueron solicitados.
Suponga por ejemplo el siguiente caso:
Se tiene una memoria de 100000 palabras y 5 programasa P1, P2, P3, P4, y P5 que requieren
bloques de memoria de tamanos ˜ 10000, 15000, 6000, 8000 y 20000. La vista de la memoria al
localizar el programa P5 ser´ıa:
10000 310000 59000 100000
P1   P2          P3      P4     P5      Free Space
Figura 12: Memoria con 5 procesos en ejecucion´
Asuma ahora que el programa P4 y P2 completaron su ejecuci´on y que por lo tanto la memoria es
liberada:
10000 310000 59000 100000
P1   Free      P3      Free  P5      Free Space
Figura 13: Memoria con 2 procesos terminados
Ahora se tienen 3 bloques de memoria contigua libres y tres ocupados. Con el propos ´ ito de seguir
permitiendo la localizacion´ de memoria, es necesario mantener registro de los bloques que no est´an
en uso. Para eso se usa un lista de bloques de memoria que no est´an en uso.
El proceso de recolecci´on de basura es llevado a cabo en dos pasos: (1) marcacion´ de los bloques
que est´an en uso y (2) compactaci´on de los bloques libres a memoria disponible. Este segundo paso
es trivial si los bloques son de igual tamano˜ llegando a ser de O(n), siendo n el numero ´ de nodos.
Cuando existe un taman˜o variable por nodo, es deseable compactar la memoria de manera que
todos los nodos libres queden en memoria contigua, lo que se llama compactaci´on de memoria. La

compactaci´on de memoria reduce el tiempo de recuperacion.
Publicado por 1 comment:
Los siguientes enlaces te dirigen al tema al que quieras recurrir:



LISTAS
PILAS
COLAS
RECURSIVIDAD
ARBOLES
GRAFOS
ORDENAMIENTO
BUSQUEDA



LISTAS:


Una lista es una estructura de datos dinámica que cumple las siguientes características:


  1. Dispone de un numero variable de elementos (desde cero hasta "n"). Su tamaño únicamente se limita por la cantidad de memoria que haya disponible en el sistema. Si la lista tiene cero elementos recibe el nombre de "Lista vacía".
  2. El primer elemento de la lista, cuando ésta no está vacía es conocido y se puede acceder a él siempre que se desee.
  3. Los elementos de la lista guardan una relación de orden (o precedencia), de forma que para cada uno de ellos es posible saber cual es su "elemento siguiente".

TIPOS DE LISTAS:
  • Lista simplemente enlazada
  • Lista doblemente enlazada
  • Lista circular


LISTA SIMPLEMENTE ENLAZADA

Las listas enlazadas o encadenadas son aquellas listas cuyos elementos se encuentran almacenados en posiciones de memoria no contiguas. En este tipo de listas, los nodos tienen la estructura de auténticos registros divididos en unidades de tratamiento mas pequeñas denominadas campos.

Cada nodo está formado por un mínimo de dos campos:
a) Campo información (Campo que contiene el dato)
b) Campo indicador o puntero (Campo que actúa de enlace con el siguiente nodo de la lista en secuencia lógica).


Por convenio: 
a) Cuando se crea una lista, esta debe estar inicialmente vacía.
b) El campo puntero correspondiente al ultimo nodo de la lista apunta a un valor Nulo.
c) Para acceder a un nodo de la lista, se parte del nodo inmediatamente anterior, a excepción del primer nodo, al cual se accede a través de un enlace especial o puntero externo a la lista.


LISTA DOBLEMENTE ENLAZADA

Son aquellas que pueden recorrerse en amabas direcciones gracias a que los nodos que la componen están formados por tres campos:
a) Campo información
b) Campo enlace que apunta al nodo anterior ( el cual nos permite retroceder o recorrer la lista hacia atrás).
c) Un segundo campo enlace que apunta al nodo siguiente de la lista.




LISTAS CIRCULARES

Se caracterizan porque el campo puntero del último nodo, en lugar de apuntar a un valor Nulo, apunta al primer nodo o elemento de la lista, convirtiéndose en una estructura de datos circular.


OPERACIONES CON LISTAS

a) Crear una lista.

Lista = Nulo

b) Insertar un nodo a la lista


c) Eliminar un elemento de la lista






Aplicación de Listas: Recolección de Basura y Compactación


En un ambiente de computadores multi-procesos, muchos programas residen en memoria al mismo tiempo. Diferentes programas tiene diferentes requerimientos de memoria. Así un programa puede requerrir 60K o 300K de memoria. En cualquier momento que el sistema necesite memoria, necesita localizar memoria continua del tamaño deseado. Cuando la ejecución de un programa es terminada, la memoria que ha sido ocupada debe ser liberada y disponible para otro programa. Más aún, bloques de memoria pueden ser liberados en una secuencia diferente a la que fueron solicitados.
Suponga por ejemplo el siguiente caso:
Se tiene una memoria de 100000 palabras y 5 programasa P1, P2, P3, P4, y P5 que requieren bloques de memoria de tamaños 10000, 15000, 6000, 8000 y 20000. La vista de la memoria al localizar el programa P5 sería:





Asuma ahora que el programa P4 y P2 completaron su ejecución y que por lo tanto la memoria es liberada:


Ahora se tienen 3 bloques de memoria contigua libres y tres ocupados. Con el propósito de seguir permitiendo la localización de memoria, es necesario mantener registro de los bloques que no están en uso. Para eso se usa un lista de bloques de memoria que no están en uso.
El proceso de recolección de basura es llevado a cabo en dos pasos: (1) marcación de los bloques que están en uso y (2) compactación de los bloques libres a memoria disponible. Este segundo paso es trivial si los bloques son de igual tamaño llegando a ser de O(n), siendo n el número de nodos.
Cuando existe un tamaño variable por nodo, es deseable compactar la memoria de manera que todos los nodos libres queden en memoria contigua, lo que se llama compactación de memoria. La compactación de memoria reduce el tiempo de recuperación.



ALGORITMO PROGRAMA DE LISTA ENLAZADA SIMPLE


Empezaremos creando la clase que nos permitira recorrer la lista, a esta le asignaremos el nombre de Nodo
1
2
3
4
5
6
7
8
9
10

public class Nodo {
 Nodo nodoDer;
 int  dato;
 
public  Nodo(int dato) {
 this.dato = dato;
 this.nodoDer = null;
 }
 
}
Nesesitaremos un nodo para agregar a la lista este metodo ira agregando todo al final de la misma:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public  ListaS addLast(int dato) {
 if(siVacio()) {
 Nodo nuevo = new Nodo(dato);
 primero = nuevo;
 ultimo = nuevo;
 nuevo.nodoDer =  nuevo;
 }
 else {
 Nodo nuevo = new Nodo(dato);
 nuevo.nodoDer =  null;
 ultimo.nodoDer =  nuevo;
 ultimo = nuevo;
 }
 this.tamano++;
 return  this;
 }
De igual forma se nesesita un metodo para borrar datos de la lista:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public  Nodo deleteLast() {
 Nodo eliminar = null;
 if(siVacio()) {
JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
 return  null;
 }
 if(primero == ultimo) {
 primero = null;
 ultimo = null;
 }
 else {
 Nodo actual = primero;
 while(actual.nodoDer !=  ultimo) {
 actual = actual.nodoDer;
 }
 eliminar = actual.nodoDer;
 actual.nodoDer =  null;
 
ultimo = actual;
 }
 this.tamano--;
 return  eliminar;
 }
Nuestro codigo completo quedaria de la siguiente manera:
Classe principal:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

import javax.swing.JOptionPane;
 
public class ListaS {
    private Nodo primero;
    private Nodo ultimo;
    private int tamano;
 
    public ListaS() {
        this.primero = null;
        this.ultimo = null;
        this.tamano = 0;
    }
 
//Metodo utilizado para denotar que la lista se encuentra vacia.
    public boolean siVacio() {
        return (this.primero == null);
    }
 
//Metodo para agregar al final de la lista.
    public ListaS addLast(int dato) {
        if(siVacio()) {
            Nodo nuevo = new Nodo(dato);
            primero = nuevo;
            ultimo = nuevo;
            nuevo.nodoDer = nuevo;
        }
        else {
            Nodo nuevo = new Nodo(dato);
            nuevo.nodoDer = null;
            ultimo.nodoDer = nuevo;
            ultimo = nuevo;
        }
        this.tamano++;
        return this;
    }
 
//Metodo para borrar al final de la lista.
    public Nodo deleteLast() {
        Nodo eliminar = null;
        if(siVacio()) {
            JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
            return null;
        }
        if(primero == ultimo) {
            primero = null;
            ultimo = null;
        }
        else {
            Nodo actual = primero;
            while(actual.nodoDer != ultimo) {
                actual = actual.nodoDer;
            }
            eliminar = actual.nodoDer;
            actual.nodoDer = null;
 
            ultimo = actual;
        }
        this.tamano--;
        return eliminar;
    }
 
//Metodo que imprime el tamaño de la lista.
    public void tamano() {
        JOptionPane.showMessageDialog(null, "El tamaño es:\n " + this.tamano);
    }
 
//Metodo que imprime la lista y los valores ingresados.
    public void imprimir() {
        if(tamano != 0) {
            Nodo temp = primero;
            String str = "";
            for(int i = 0; i < this.tamano; i++) {
                str = str + temp.dato + "\n";
                temp = temp.nodoDer;
            }
            JOptionPane.showMessageDialog(null, str);
        }
    }
}
Clase Nodo:
1
2
3
4
5
6
7
8
9
10

public class Nodo {
 Nodo nodoDer;
 int  dato;
 
public  Nodo(int dato) {
 this.dato = dato;
 this.nodoDer = null;
 }
 
}



PILAS


-Concepto de pila
Una pila es una estructura de datos lineal en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.
Trabajan con filosofía LIFO (Last In- First Out ).

-Tipos de pilas
*Estatica
*Dinamica








-Operaciones con pilas


PUSH (insertar).- Agrega un elementos a la pila en el extremo llamado tope.

POP (remover).- Remueve el elemento de la pila que se encuentra en el extremo llamado tope.

VACIA.- Indica si la pila contiene o no contiene elementos.

LLENA.- Indica si es posible o no agregar nuevos elementos a la pila. 



-Aplicaciones de pilas



Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas. Se utiliza en compiladores, sistemas operativos y en programasde aplicación. Su implementación se puede hacer mediante Arrays Y Mediante listas enlazadas.

Un ejemplo de sus aplicaciones podrían ser los siguientes:
Los Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados.
Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estadoanterior del documento.


-Programa con operaciones de pilas


Public class Pilaestatica{

Public static void main (String [] args){
Int dato;
Int pila[] = new int [5];
Scanner captura = new Scanner(System.in);
For(int tope=0; tope<4; tope++)
{
System.out.println(“Proporcione datos para la pila:”);
Dato=  captura.nextInt();
Pila[tope]=dato;
}
For int(tope=4; tope>=0; tope--)
System.out.println(“La pila tiene los siguientes datos:” +pila[tope]);
}
}


COLAS:

Las colas también son llamadas FIFO (First In First Out), que quiere 
decir “el primero que entra es el primero que sale”. 




COLAS SIMPLES:

Se inserta por un sitio y se saca por otro, en el caso de la cola simple se 
inserta por el final y se saca por el principio. Para gestionar este tipo de cola 
hay que recordar siempre cual es el siguiente elemento que se va a leer  y cual 
es el último elemento que se ha introducido.  


COLAS CIRCULARES:


En las colas circulares se considera que después del último elemento se 
accede de nuevo al primero. De esta forma se reutilizan las posiciones 
extraídas, el final de la cola es a su  vez el principio, creándose un circuito 
cerrado. 


APLICACIONES DE COLAS:

Las colas se utilizan en muchos algoritmos y en situaciones en las que el rendimiento de dos sistemas que se cruzan datos entre sí es más eficiente cuando no se intercambian indicativos y señales de control (handshaking) en cada transferencia.
• También almacenan temporalmente la transferencia de información, lo que permite procesarla en origen y en destino a tasas independientes.
- Se utilizan en los slideshows de imagenes.




RECURSIVIDAD


Es una técnica de programación muy potente que permite definir un objeto
(problemas, estructuras de datos) en términos de si mismo.

•Una función o procedimiento recursivo es aquel que se llama a si mismo.



TIPOS DE RECURSIVIDAD



  • Recursividad Directa: Cuando un método P contiene dentro de si un llamado a si mismo.
  • Recursividad Indirecta: Cuando un método P contiene dentro de si un llamado a otro método Q que contiene llamados (directos o indirectos) a P.






Ejemplo de Recursividad. Programa Fibonacci



import java.util.Scanner;
public class FibonacciR {
public static long fib(int n){
    if(n<=1) return n;
    else return fib(n-1)+fib(n-2);
}
    public static void main(String[] args) {
        int n;
        Scanner teclado = new Scanner(System.in);
        System.out.println("Ingrese el numero");
        n= teclado.nextInt();
        System.out.println("------------");
        for(int i =1; i<= n;i++){
            System.out.println(i +": "+fib(i));
        }
    }
}






Ejemplo de Recursividad. Programa Factorial



import java.util.*;
public class factorial {
public static double n, h;
public static double factorial(double n){
    if(n==0){
        return 1;
    }
 else
     h=1;
    return n*factorial(n-1);


    }
public static void main(String[] args) {
    System.out.println("¿Cuál es el número?");
    Scanner cap = new Scanner(System.in);
    n= cap.nextDouble();
    if(n==0){
        System.out.println("\nFactorial:1");
    }
    factorial f = new factorial();
    f.factorial(n);
    if(h==1){
        System.out.println("\n Factorial="+n*factorial(n-1));
    }
}
}




ARBOLES


Un árbol es una estructura de datos no lineal jerarquizada, cada dato reside en un nodo, y existen relaciones de parentesco entre nodos en la que cada nodo puede apuntar a uno o varios nodos.

*Una coleccion de dos o mas arboles se llama BOSQUE.

Los árboles constituyen estructuras de datos jerarquizados, y tienen multitud de aplicaciones, como 
por ejemplo: 
• Análisis de circuitos, Representación de estructuras de fórmulas matemáticas
• Organización de datos en bases de datos
• Representación de la estructura sintáctica en compiladores.
• En muchas otras áreas de las ciencias del computador.
Un árbol está constituido por una colección de elementos denominados nudos, uno de los cuales se 
distingue con el nombre raíz, junto con una relación de 'parentesco' que establece una estructura jerárquica 
sobre los nudos. Cada nudo tiene un padre (excepto el raíz) y puede tener cero o más hijos. Se denomina 
hoja a un nudo sin hijos. Como ejemplo se muestra en la figura superior la tabla de contenidos de un libro.




Se definen varios conceptos:
  • 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'.
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'.
  • 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 árbol orientado y ordenado, en el que cada nodo puede tener un hijo izquierdo y un hijo derecho.



RECORRIDOS 

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 9, 4.



CONVERSIÓN DE UN ÁRBOL GENERAL EN ÁRBOL BINARIO
Dado que los árboles binarios son de estructura fundamental en la teoría de los árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en árbol binario.
“Los árboles binarios son más fáciles de programar que los generales”. En esto es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla.
Afortunadamente, existe una técnica para convertir un árbol general a formato de un árbol binario. Ejemplo:
Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El árbol de conversión tiene 3 pasos fáciles:
1. - La raíz de B es la raíz de A
2. -
a) Enlazar un nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo).
,. b) Enlazar éste nodo con los restantes descendientes del nodo raíz en su camino con lo que se forma el nivel 1.
c) A continuación, repetir los pasos a y b con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos (descendientes del mismo nodo). Repetir estos pasos hasta llegar al nivel más alto.
3.- Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdos y derecho.




CLASE JTREE EN JAVA

. El JTree nos permite mostrar información jerárquica, es excelente para mostrar datos como un árbol familiar o la estructura del sistema de archivos.
El JTree es el componente java visual (como los botoncitos, listas, menús, etc) que nos permite visualizar un árbol. En él podemos ver el típico árbol de datos en el que podemos abrir cada uno de los nodos para ver qué tiene dentro, cerrarlos, etc.

Clases Java implicadas

Por un lado tenemos "la vista", que es la clase java que se ve. Esta clase es el JTree y es lo que se ve en la pantalla, en nuestra ventana.
Por otro lado tenemos el "modelo de datos". Esta clase de java puede ser cualquier clase que implemente la interface TreeModel, pero java nos ofrece ya implementada la clase DefaultTreeModel. Esta clase es la que contiene los datos que queremos visualizar en "la vista". Contiene los datos que visualizaremos en el JTree.
¿Qué datos admite el DefaultTreeModel?. Puesto que vamos a hacer un árbol, admite datos que se puedan asociar entre sí como padres e hijos. No valen datos cualesquiera. Esos datos deben implementar la interface TreeNode. Cualquier clase que implemente esta interface, tendrá métodos para interrogarle sobre quién es su padre, si tiene hijos, etc. Estos métodos será los que acabe usando JTree para saber qué debe pintar, quién es hijo de quién y quién es padre de quién.
Existe otro tipo de dato también importante, el MutableTreeNode. Este es igual que el anterior, pero además tiene métodos para modificar las asociaciones entre padres e hijos. Permite añadir nuevos hiijos a los padres, cambiar el padre de los hijos y cualquier otro tipo de indecencia que se nos ocurra. Si nuestro árbol va a cambiar sobre la marcha, nos interesa usar datos (nodos) que implementen esta interface.
Java nuevamente nos ofrece una clase que ya implementa MutableTreeNode y por tanto tiene todos los métodos necesarios para saber quién es hijo de quién y los métodos necesarios para cambiar estas asociaciones. Esta clase es DefaultMutableTreeNode. Tiene además un método intereseante, que es setUserObject(). Este método nos permite guardar dentro la información que queramos. Esta información será nuestro dato real, lo que realmente nos interesa. DefaultMutableTreeNode únicamente nos ahorrará escribir el código necesario para mantener asociaciones entre padres e hijos, además de hacer de almacén de nuestro dato.
Ejemplo de visualizacion:



PROGRAMA - ARBOLES 

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class SimpleTree
{  public static void main(String[] args)
   {  JFrame frame = new SimpleTreeFrame();
      frame.show();
   }
}
class SimpleTreeFrame extends JFrame
{
   DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
   DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
   DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
   DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
   DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
   DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
   DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
   DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
   DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
   DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
   DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
   DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
   DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
   DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
   public SimpleTreeFrame()
   {  setTitle("SimpleTree");
      setSize(300, 200);
      addWindowListener(new WindowAdapter()
         {  public void windowClosing(WindowEvent e)
            {  System.exit(0);
            }
         } );
      root.add(arge);                                                   // Enlazado de nodos
      arge.add(sant);                                                   // Enlazado de nodos
      sant.add(rafa);                                                   // Enlazado de nodos
      sant.add(rosa);                                                   // Enlazado de nodos
      sant.add(safe);                                                   // Enlazado de nodos
      sant.add(vena);                                                   // Enlazado de nodos
      sant.add(vill);                                                   // Enlazado de nodos
      arge.add(cord);                                                   // Enlazado de nodos
      cord.add(codo);                                                   // Enlazado de nodos
      cord.add(cbro);                                                   // Enlazado de nodos
      cord.add(rcua);                                                   // Enlazado de nodos
      arge.add(chac);                                                   // Enlazado de nodos
      chac.add(resi);                                                   // Enlazado de nodos
      chac.add(vang);                                                   // Enlazado de nodos
      root.add(chil);                                                   // Enlazado de nodos
      chil.add(regi);                                                   // Enlazado de nodos
      regi.add(schi);                                                   // Enlazado de nodos
      JTree tree = new JTree(root);
      Container contentPane = getContentPane();
      contentPane.add(new JScrollPane(tree));
      Enumeration hijos = sant.children();                              // Enumeracion de hijos
      while ( hijos.hasMoreElements() )                                 // Enumeracion de hijos
      {                                                                 // Enumeracion de hijos
        System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos
      }                                                                 // Enumeracion de hijos
      boolean hoja = vena.isLeaf();                                     // Consulta Hoja
      System.err.println("Es Venado Tuerto hoja : "+hoja);              // Consulta Hoja
      Enumeration breadth = root.breadthFirstEnumeration();             // Enumeracion Nodos
      while ( breadth.hasMoreElements() )                               // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Breadth First : "+breadth.nextElement());   // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration depth = root.depthFirstEnumeration();                 // Enumeracion Nodos
      while ( depth.hasMoreElements() )                                 // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Depth First : "+depth.nextElement());       // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration preorder = root.preorderEnumeration();                // Enumeracion Nodos
      while ( preorder.hasMoreElements() )                              // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Pre Order : "+preorder.nextElement());      // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration postorder = root.postorderEnumeration();              // Enumeracion Nodos
      while ( postorder.hasMoreElements() )                             // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Post Order : "+postorder.nextElement());    // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
   }
}



GRAFOS

GRAFOS 
Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada 
arco en un grafo se especifica por un par de nodos.  
El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D),  (A, 
C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo  



Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o 
dígrafo.

TERMINOLOGÍA  
*.-Al número de nodos del grafo se le llama orden del grafo. 
*.-Un grafo nulo es un grafo de orden 0 (cero). 
*.-Dos nodos son adyacentes si hay un arco que los une. 
*.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A  
*.-Camino es una secuencia de uno o mas arcos que conectan dos nodos.  
*.-Un grafo se denomina conectado cuando existe siempre un camino que une dos   
     nodos cualesquiera y desconectado en caso contrario. 
*.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los   
     nodos restantes. 
*.-El camino de un nodo así mismo se llama ciclo. 



ORDENAMIENTO

¿Qué es ordenamiento?

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia, tal que represente un orden, el cual puede ser numérico, alfabético o alfanumérico, ascendente o descendente.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado.
El método de ordenamiento es conviene usar Cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Métodos de Ordenamiento
Existen diferentes métodos de ordenamiento de datos como lo son:


Método Burbuja:

El metodo de la burbuja es uno de los mas simples, es tan facil como comparar todos
los elementos de una lista contra todos, si se cumple que uno es mayor o menor a
otro, entonces los intercambia de posición.
Por ejemeplo, imaginemos que tenemos los siguientes valores:

Lo que haria una burbuja simple, seria comenzar recorriendo los valores de izq. a
derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3, si
es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se
intercambian de posicion. Luego continua con el siguiente, con el 6, y lo compara con
todos los elementos de la lista, esperando ver si se cumple o no la misma condicion
que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.


Programa de Burbuja :


class OrdenaAlgoritmo {




    public static void ordenarMejorado( int [] arreglo) {
 int pasadas = 0;
 int comparaciones = 0;
 boolean hayCambios = true;
 for (int i = 0; hayCambios ; i++) {
     ++pasadas;
     hayCambios = false;
     for (int j = 0; j < arreglo.length - 1; j++) {
  ++comparaciones;
  if (arreglo[j] > arreglo[j + 1]) {
      intercambiar(arreglo, j, j+1);
      hayCambios = true;
  }
     }
 }
 estadisticas(pasadas, comparaciones);
    }


    private static void intercambiar(int [] arreglo, int a, int b) {
 int tmp = arreglo[a];
 arreglo[a] = arreglo[b];
 arreglo[b] = tmp;
    }


    private static void estadisticas( int pasadas, int comparaciones) {
 System.out.println( "Pasadas: " + pasadas );
 System.out.println( "Comparaciones: " + comparaciones );
    }
}




public class OrdenaBurbuja {
    public static void  main (String args[]) {


 int [] valores = {15,35,01,05,04,03,19,45,13,02,55,8,
    78,997,451,546,12,16,24,103,99,784,
    4541,15};


 //OrdenaAlgoritmo.ordenar(valores);
 OrdenaAlgoritmo.ordenarMejorado(valores);
 // Mostrar arreglo.
 for (int i = 0; i < valores.length ; i++)
     System.out.println ( "valores["+i+"]: "+  valores[i]);


    }
}






Método Quicksort

Sin duda, este algoritmo es uno de los mas eficientes. Este metodo es el mas rapido
gracias a sus llamadas recursivas, basandose en la teoria de divide y vencerás.
Lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales,
indicando un elemento de inicio,  fin y un pivote (o comodin) que nos permitira
segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que
el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros
elementos estan ordenados.

En esta figura se ilustra de mejor manera un vector con mas elementos, usando como
pivote el primer elemento:







Programa de Quicksort



public class Ordenador {

    public int[] quicksort(int numeros[])
            //El metodo recibe los datos del arreglo
    {
        return quicksort(numeros,0,numeros.length-1);
        //Llama al metodo quicksort para ordenar los datos
    }
    public int[] quicksort(int numeros[],int izq,int der)
            //Recibe los valores del arreglo, el valor 0, y el tamano del arreglo
    {
        if(izq>=der)
            return numeros;
        /*Si izq que es igual a cero es mayor o igual a der que es el tamano del arreglo,
         * el metodo regresa el arreglo.
         */
        int i=izq,d=der;
        //Se le asignan los valores de izq (0) & der(tamano del arreglo) a las variables i & d.
        if(izq!=der)
            //Si izq es diferente a der entonces se realiza lo siguiente
        {
        int pivote;
        int aux;
        pivote = izq;
        while(izq!=der)
        {imprimeArreglo(numeros);
         while(numeros[der]>=numeros[pivote] && izq<der)
               der--;
           while(numeros[izq]<numeros[pivote] && izq<der)
               izq++;
         if(der!=izq)
         {
             aux = numeros[der];
            numeros[der]= numeros[izq];
            numeros[izq]=aux;}
        }
        if(izq==der){
            quicksort(numeros,i,izq-1);
            quicksort(numeros,izq+1,d);
        }
        }
        else
            return numeros;
       return numeros;
    }


    public void imprimeArreglo(int arreglo[])
    {
        String imp="";
        for(int i=0;i<arreglo.length;i++)
        {
            if(i!=arreglo.length-1)
            imp=imp+arreglo[i]+",";
            else
                imp=imp+arreglo[i]+"";
        }
        System.out.println(imp);
    }
    public static void main(String[] args) {
        int array[] ={4,2,5,7,6,1,3}; //Declaracion del arreglo
Ordenador a = new Ordenador();//Crea un objeto de la clase ordenador
a.quicksort(array);//Llama al metodo quicksort, con los datos del arreglo
    }
}


Método ShellSort
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.




Programa ShellSort

public class ShellSort
{
private long[] data;

  private int len;

  public ShellSort(int max) {
    data = new long[max];
    len = 0;
  }

  public void insert(long value)
  {
    data[len] = value;
    len++;
  }

  public void display()
  {
    System.out.print("Datos:");
    for (int j = 0; j < len; j++)
      System.out.print(data[j] + " ");
    System.out.println("");
  }

  public void shellSort()
  {
    int inner, outer;
    long temp;
    //find initial value of h
    int h = 1;
    while (h <= len / 3)
      h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

    while (h > 0) // decreasing h, until h=1
    {
      // h-sort the file
      for (outer = h; outer < len; outer++)
      {
        temp = data[outer];
        inner = outer;
        // one subpass (eg 0, 4, 8)
        while (inner > h - 1 && data[inner - h] >= temp)
        {
          data[inner] = data[inner - h];
          inner -= h;
        }
        data[inner] = temp;
      }
      h = (h - 1) / 3; // decrease h
    }
  }

  public static void main(String[] args)
  {
    int maxSize = 10;
    ShellSort arr = new ShellSort(maxSize);

    for (int j = 0; j < maxSize; j++)
    {
      long n = (int) (java.lang.Math.random() * 99);
      arr.insert(n);
    }
      System.out.println("Datos no Ordenados");
    arr.display();
    arr.shellSort();
    arr.display();
  }
}



BUSQUEDA




Este método puede considerarse como una generalización de la clasificación por urnas. Aprovecha
la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montones de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra, si es
alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de
nuevo en montones según el siguiente dígito de la clave.


Programa Radix

public class ORDENAMIENTO_RADIX{
   public static void radixSort(int[] arr){
       if(arr.length == 0)
           return;
       int[][] np = new int[arr.length][2];
       int[] q = new int[0x100];
       int i,j,k,l,f = 0;
       for(k=0;k<4;k++){
           for(i=0;i<(np.length-1);i++)
               np[i][1] = i+1;
           np[i][1] = -1;
           for(i=0;i<q.length;i++)
               q[i] = -1;
           for(f=i=0;i<arr.length;i++){
               j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
               if(q[j] == -1)
                   l = q[j] = f;
               else{
                   l = q[j];
                   while(np[l][1] != -1)
                       l = np[l][1];
                   np[l][1] = f;
                   l = np[l][1];
               }
               f = np[f][1];
               np[l][0] = arr[i];
               np[l][1] = -1;
           }
           for(l=q[i=j=0];i<0x100;i++)
               for(l=q[i];l!=-1;l=np[l][1])
                       arr[j++] = np[l][0];
       }
   }
   public static void main(String[] args){
       int i;
       int[] arr = new int[15];
       System.out.print("original: ");
       for(i=0;i<arr.length;i++){
           arr[i] = (int)(Math.random() * 1024);
           System.out.print(arr[i] + " ");
       }
       radixSort(arr);
       System.out.print("\nsorted: ");
       for(i=0;i<arr.length;i++)
           System.out.print(arr[i] + " ");
       System.out.println("\nDone ;-)");
   }
}





Búsqueda Secuencial 

Definición:
Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave.
En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector
se exploran (se examinan) en secuencia, uno después de otro. La búsqueda secuencial es necesaria,
por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfonos están organizados alfabéticamente
por el nombre del abonado en lugar de por números de teléfono, de modo que deben explorarse
todos los números, uno después de otro, esperando encontrar el número 958-220000.
El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda

Programa
public class BSecuencial {

public static void main(String[] args) throwsIOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar

for (int i=0; i<VectorNombres.length;i++){

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}

if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de búsqueda, encontrados "+encontrados+" elementos iguales");



Búsqueda Hash

Función Hash
En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo
Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.



Ir arriba

Read more »
Publicado por No comments:
Subscribe to: Posts (Atom)