miércoles, 7 de septiembre de 2011

por Fidel de la Cruz Rodríguez ;)

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.




Recursividad

La recursividad es una técnica muy empleada en la programación informática y consiste en que una función se llame a sí misma. El ejemplo clásico es la función que calcula el factorial de un número. Un factorial consiste en multiplicar un número natural por el número anterior, y este a su vez por el anterior, y así sucesivamente hasta llegar al número 1. Por ejemplo, el factorial de 8 sería el resultado de multiplicar 8 por 7, luego por 6 y así sucesivamente hasta llegar a uno.
Una función recursiva que hiciera este cálculo multiplicaría el número que se le pasa por el resultado de llamar a la función restando uno a ese número. En nuestro ejemplo, multiplicar 8 por el factorial de 7. Cuando el número que se le pasa es un 1, pues devuelve ese 1. Es la llamada "condición de salida", y es esencial para impedir que la función se esté llamando a sí misma eternamente.





En el siguiente programa muestra el calculo del factorial de un número
con la aplicación de recursividad

Programa recursivo

 int Factorial(int x)//metodo recursivo
{
  if (x == 0)
    return 1;
  return x * Factorial(x-1);//aqui el metodo se llama asi mismo(aplica recursividad)
}
    void imprimir() {//metodo que utilizamos para imprimir
        Scanner teclado=new Scanner (System.in);
        System.out.println("Ingrese el numero del cual desee obtener su factorial ");
       int n=teclado.nextInt();//variable "n"  es el número al con el cual trabajaremos
        System.out.println("El factorial de el numero es: "+Factorial(n));//imprimer el resultado
        return;
    }
    public static void main(String[] args) {
       clasefactorial resultadofactorial=new clasefactorial();//declaracion del objeto
       resultadofactorial.imprimir();//creamos el objeto solo llamando el metodo de la imprecion
    }


Listas


Listas enlazadas

Una lista enlazada es una colección lineal(esdecir, una secuencia) de objetos de una clase autorreferenciada, conocidos como nodos, que están conectados por enlaces de referencia; es por ello que se utiliza el termino lista “enlazada”.
Los datos se almacenan de forma dinámica en una lista enlazada; el programa crea cada nodo según sea necesario.
Listas doblemente enlazadas
llas listas doblemente enlazadas son aquellas que pueden recorrerse en ambas direcciones gracias a que los nodos que la componen están formados por 3 campos:
a) Campo informático
b) Un campo puntero o enlace que apunta al nodo anterior.
(Este puntero nos permite retroceder o recorrer la lista hacia atrás, de derecha a izquierda)
c) Un segundo campo puntero o enlace que apunta al nodo de la siguiente lista.

la desventaja que representan este tipo de listas es que , aun conteniendo la misma información que por ejemplo una lista simplemente enlazada, cada nodo ocupa más espacio en memoria al estar constituido por un segundo campo puntero.


Listas Circulares
las 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 así en una estructura circular. La ventaja que este tipo de listas ofrece, es la de permitir el acceso a un nodo a partir de cualquier otro nodo perteneciente a la misma lista. Por el contrario, el inconveniente que presentan este tipo de listas es el de mantener un nodo que se diferencie del resto y que sea identificado como un nodo cabecera, para evitar que se produzcan bucles infinitos en el tratamiento de dicha estructura de datos.











Operadores de una lista
clasificar los elementos de la lista en orden creciente o decreciente.
Buscar un elemento
añadir un nuevo elemento a la lista
insertar un nuevo elemento a la lista
eliminar un elemento existente en la lista
destruir o borrar la lista por completo
copiar una lista origen en otra destino
dividir una lista en n sublistas.
Concatenar dos o más listas obteniendo como resultado una única lista
Bibliografía
Sistemas operativos y lenguajes de programación
 Escrito por Enrique Quero Catalinas


Pila

Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.




Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de "push" y "pop":
Push: Añadir un elemento al final de la pila.
Pop: Leer y eliminar un elemento del final de la pila.





Colas

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.
El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada.


Árboles

  • En términos matemáticos, un árbol ( tree ) es cualquier conjunto de puntos, llamados vértices, y cualquier conjunto de pares de distintos vértices, llamados lados ( edges ) o ramas ( branches ), tales que :
    1. Hay una secuencia de ramas, llamada paso ( path ) de cualquier vértice a cualquier otro vértice.
    2. No hay lazos ( circuits ), o sea, que no hay pasos que comiencen en un vértice y puedan volver al mismo vértice.
    Llamaremos a un árbol de tal generalidad, un árbol libre ( free tress ).
  • Los árboles que tienen un vértice o nodo ( node ) especial, llamado raíz ( root ), reciben el nombre de árboles enraizados ( rooted tree ). La particularidad del nodo raíz es que no puede ser hijo de otro nodo.
  • Un árbol A es un conjunto finito de uno o más nodos tales que :
    1. Existe un nodo especialmente designado y denominado RAIZ(v1) del árbol.
    2. Los nodos restantes ( v2, v3, ..., vn ) se dividen en m >= 0 conjuntos disjuntos denominados A1, A2, ..., Am, cada uno de los cuales es a su vez, un árbol. Estos árboles se llaman subárboles ( subtree ) del RAIZ. Observar la naturaleza recursiva de la definición de árbol.
  • Un árbol es una estructura de datos no lineal. Las estructuras de datos lineales se caracterizan por que a cada elemento le corresponde no más que un elemento siguiente. En las estructuras de datos no lineales, como el árbol, un elemento puede tener diferentes " siguientes elementos ", introduciendo una estructura de bifurcación, también conocidas como estructuras multi enlazada.
  • Un árbol es un conjunto finito de elementos no vacio en el cual un elemento se denomina raíz y los restantes se dividen en m >= 0 subconjuntos separados, cada uno de los cuales es por sí mismo un árbol. Cada elemento en un árbol se denomina nodo del árbol.
  • Un árbol ordenado ( ordened tree ) se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En una árbol ordenado podemos hablar del primero, segundo o último hijo de un nodo particular. El primer hijo de un nodo, en un árbol ordenado, se denomina con frecuencia el hijo más viejo de este nodo y el último hijo, se denomina el hijo más joven.
  • Un árbol desordenado ( desordened tree ) se define como un árbol en el que los subárboles de cada nodo no guardan órden alguno. No existe forma, en este tipo de árboles, determinar cual es el primero, segundo o último hijo.
  • La estructura de datos arboles es para mostrar datos jerarquicos.
















    No hay comentarios:

    Publicar un comentario