martes, 5 de noviembre de 2013

Estructura de Datos

Es una forma de organizar un conjunto  de datos elementales con el objetivo de facilitar su manipulacion  un dato elemental es la minima informacion  que se tiene en un sistema

una estructura de datos define la organizacion e interrelacion de estos y un conjunto de operaciones que se pueden realizar sobre ellos.

  • Es una agregacion de tipos de datos compuestos y atomicos en un conjunto.
  • Una estructura sigue un conjunto de reglas que contienen los datos juntos

  • Un conjunto de datos unidos entre si que puede tomar diferentes formas

  • Un conjunto de asociasiones o relaciones que implica a los elementos combinados

  • Busca todos los caminos o vias posibles y se esta actualizando constantemente

  • Un tipo de datos es un conjunto de valores operaciones asociadas a esos valores

Tipos de Datos
un tipo de dato es un conjunto de valores operaciones asociadas a esos valores
Entero                         valores             -3,-2,-1,0,1,2,3
                       operaciones       *,+,-,/

Caracter                   valores            "A","B","C",
                       operaciones     <,>




Tipo de Dato Primitivo

Son aquellos que no se construyen a partir de otros tipos y son entidades unicas;
Reprecentan un unico dato simple que puede ser de tipo char,short,int,long,float,double,boolean,false
cada tipo de dato presenta un conjunto de valores o constantes literales. 



Tipos de Datos Compuestos
Son tipos de datos cuyos valores constan de colecciones de elementos de datos como:
  • Arreglos
  • secuencias(arboles,listas)
  • registros(bases de datos)

Unidades de Almacenamiento

Abstraccion de Datos 

Tecnica para inventar nuevos tipos de datos que sean mas adecuados a una aplicacion y por consiguiente: 
  • facilitar la escritura del programa.
  •    inventar nuevas formas de registro
  • programas mas cortos
  • mas legibles
  • flexibles
  •  
la informacion que procesas en un programa es una abstraccion del mundo real 



Abstraccion en Lenguaje de Programacion

abstracciones de control(Nivel Sentncia)
sentencias de bifuracion:(if) y bucles( for, while,loop,etc)

abstracciones de control(nivel por procedimiento): procedimientos,metodos o funciones.


 Tipos de Datos Abstractos 

  • los tipos de datos son abstracciones
  • proceso deconstruir nuevos datos
  • los nuevos tipos de datos definidos por el usuario

Modularidad

Es la posobilidad de dividir una aplicacion en piezasnmas pequeñas.

 

TAD

Reprecentacion (datos)+Operaciones(funciones y procedimientos)



Uso de TDA

  • Listas
  • Colas 
  • Arboles
  • Grafos  

Manejo de Memoria Estatica

Es el uso de estructura de datos de tamaño fijo, como los arreglos de uno o dos subindices

Manejo de Memoria Dinamica 

son quellas que crecen o se ecrementan durante la ejecucion de los programas



 Pilas
son importantes en los compiladores y sistemas operativos, las insercciones se realizan en un extremo de la pila

  • El primer elemento en entrar sera el ultimo en salir

 


 Cola o Fila
Representan filas de espera; Las intersecciones se realizan por la parte final y las eliminaciones por la parte inicial

  • el primero que entro sera el primeo en salir




Listas 
  • sencilla
  • circular
  • doble 





Lista Sencilla



Lista Doble 

 
 Lista circular
 

 Arboles Binarios
facilitan la busqueda y ordenamiento de datos de alta velocidad, la eliminacion eficiente de elementos de informacion duplicados
 




COLA Y TIPOS DE COLAS
Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola.

File:Cola.svg

Operaciones Básicas

  • Crear: se crea la cola vacía.
  • Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
  • Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
  • Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.


PILA

Expresion Aritmetica
(Aplicacion pila)




1º.Efectuar las operaciones entre paréntesis, corchetes y llaves( ).
2º.Calcular las potencias y raíces
3º.Efectuar los productos y cocientes.
4º.Realizar las sumas y restas. 
 














Colas o Filas
es una estructura de datos, caracterizada por ser una secuencia de elementos en  la que la operacion de inserccion se realiza por un extremo y la extraccion por otro. tambien se le llama estructura FIFO(First)debido a que el primer elemento sera el primero en salir.



Cola sencilla o simple 
 Estructura lineal donde los elementos salen en el mismo orde en que llegan

Cola doble


Cola circulante
Representacion logica de una cola simple en un arreglo en las que el ultimo elemento y el primero estan unidos.
 

ESTRUCTURAS NO LINEALES
Arboles
Estructura jerarquica aplicada sobre una coleccion de elementos u objetos llamados nodos; uno de los cuales es conocido como raiz.
La informacion queda ordenada en forma general



Aplicaciones:
  • Formulas Matematicas
  • Circuitos Electronicos
  • Arbol genealogico(ejemplo facebook,directorio)
Se dice que todos los nodos que son desendientes directos hijos de un mismo padre, son hermanos.
Todo nodo que no tiene ramificaciones hijos se conoce con el nombre de terminal u hoja.
Propiedades
GRADO: numero de descendientes directos de un determinado nodo.
GRADO ARBOL: es el maximo grado de los nodos del arbol.
NIVEL: es el numero de arcos que pueden ser recorridos para llegar a un determinado nodo por definicion raiz tiene nivel 1.
 
LONGITUD DE CAMINO INTERNO
La longitud de camino interno es la suma de longitudes de camino de todos los nodos del arbol.
i=Nivel  del arbol
h=Altura
ni=Numero de nodos en el nivel i
Lci=1*1+2*2+3*4=17(longitud de camino interno)

LONGITUD DE CAMINO EXTERNO
Arbol Extendido: es aquel en el que el numero de hijos de cada nodo es igual al grado del arbol, de no cumplir con esta caracteristica se deben incorporar nodos es peciales.
Nodos Especiaes:remplazan las ramas vacias o nulas.
LCE: es la suma de todos los nodos especiales.

i=Nivel del arbol
h=Altura
nei=Numero de nodos especiales
ARBOL BINARIO

Es un arbol ordenado, en el cual cada nodo puede tener como maximo dos subarboles.




ARBOL GENERAL- ARBOL BINARIO
  • Enlazar los hijos de cada nodo en forma horizontal(los hermanos)
  • Relacionar en forma vertical el nodo padre con el hijo que se encuentraa mas a la izquierda. Ademas,se debe eliminar el vinculo es padre con el resto de los hijos.
  • Rotar el diagrama resultante, aproximadamente grados hacia la izquierda y asi obtendra un arbol binario correspondiente.
CONVERSION A ARBOL BINARIO
  • Enlazar en forma horizontal las raices de los distintos arboles generales
  • Relacionar los hijos de cada nodo(los hermanos en forma horizontal)
  • Enlazar en forma vertical el nodo padre con el hijo que se encuentra mas a la izquierda.Ademas se debe eliminar el vinculo del padre con el resto de sus hijos
  •  Rotar el diagrana resultante aproximadamente 45 grados hacia la izquierda y ai obtendra el arbol binario correspondiente.

ARBOL GENEALOGICO

APLICACION DE ARBOL EN JAVA

public class Arbolp {
class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;
    int cant;
    int altura;
    public Arbol() {
        raiz=null;
    }
    public void insertar (int info) {
        if (!existe(info)) {
            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.izq = null;
              nuevo.der = null;
            if (raiz == null)
                raiz = nuevo;
            else {
                Nodo anterior = null, reco;
                reco = raiz;
                while (reco != null)  {
                    anterior = reco;
                    if (info < reco.info)
                        reco = reco.izq;
                    else
                        reco = reco.der;
                }
                if (info < anterior.info)
                    anterior.izq = nuevo;
                else
                    anterior.der = nuevo;
            }
        }
    }
    public boolean existe(int info) {
        Nodo reco=raiz;
        while (reco!=null) {
            if (info==reco.info)
                return true;
            else
                if (info>reco.info)
                    reco=reco.der;
                else
                    reco=reco.izq;
        }
        return false;
    }
    private void imprimirEntre (Nodo reco)  {
        if (reco != null)  {
            imprimirEntre (reco.izq);
            System.out.print(reco.info + " ");
            imprimirEntre (reco.der);
        }
    }
    public void imprimirEntre () {
        imprimirEntre (raiz);
        System.out.println();
    }

    private void cantidad(Nodo reco) {
        if (reco!=null) {
            cant++;
            cantidad(reco.izq);
            cantidad(reco.der);
        }
    }
    public int cantidad() {
        cant=0;
        cantidad(raiz);
        return cant;
    }
    private void cantidadNodosHoja(Nodo reco) {
        if (reco!=null) {
            if (reco.izq==null && reco.der==null)
                cant++;
            cantidadNodosHoja(reco.izq);
            cantidadNodosHoja(reco.der);
        }
    }
    public int cantidadNodosHoja() {
        cant=0;
        cantidadNodosHoja(raiz);
        return cant;
    }
    private void imprimirEntreConNivel (Nodo reco,int nivel)  {
        if (reco != null) {
            imprimirEntreConNivel (reco.izq,nivel+1);
            System.out.print(reco.info + " ("+nivel+") - ");
            imprimirEntreConNivel (reco.der,nivel+1);
        }
    }
    public void imprimirEntreConNivel () {
        imprimirEntreConNivel (raiz,1);
        System.out.println();
    }
    private void retornarAltura (Nodo reco,int nivel)    {
        if (reco != null) {
            retornarAltura (reco.izq,nivel+1);
            if (nivel>altura)
                altura=nivel;
            retornarAltura (reco.der,nivel+1);
        }
    }
    public  int retornarAltura () {
        altura=0;
        retornarAltura (raiz,1);
        return altura;
    }
    public void mayorValorl() {
        if (raiz!=null) {
            Nodo reco=raiz;
            while (reco.der!=null)
                reco=reco.der;
            System.out.println("Mayor valor del įrbol:"+reco.info);
        }
    }
    public void borrarMenor() {
        if (raiz!=null) {
            if (raiz.izq==null)
                raiz=raiz.der;
            else {
                Nodo atras=raiz;
                Nodo reco=raiz.izq;
                while (reco.izq!=null) {
                    atras=reco;
                    reco=reco.izq;
                }
                atras.izq=reco.der;
            }
        }
    }
    public static void main (String [] ar)
    {
        Arbol abo = new Arbol ();
        abo.insertar (100);
        abo.insertar (50);
        abo.insertar (25);
        abo.insertar (75);
        abo.insertar (150);
        System.out.println ("Impresion entreorden: ");
        abo.imprimirEntre ();
        System.out.println ("Cantidad de nodos del įrbol:"+abo.cantidad());
        System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
        System.out.println ("Impresion en entre orden junto al nivel del nodo.");
        abo.imprimirEntreConNivel();
        System.out.print ("Artura del arbol:");
        System.out.println(abo.retornarAltura());
        abo.mayorValorl();
        abo.borrarMenor();
        System.out.println("Luego de borrar el menor:");
        abo.imprimirEntre ();
    }
}


JAVA CLASE TREE 

Clase Tree
Los métodos, propiedades y eventos de la clase Tree permiten administrar y manipular objetos Tree.
Resumen de métodos de la clase Tree
En la tabla siguiente, se enumeran los métodos de la clase Tree.


Insertar
ublic void insertNode(int key) {
    Node temp = new Node(key);

    if(root == null) root = temp;

    else insertNode(temp);
}

public void insertNode(Node temp) {
    if(root == null)
        root = temp;

    else if(temp.getKey() <= root.getKey())
        insertNode(root.getLeft());

    else insertNode(root.getRight());
}
Borrar

FileUtils.deleteDirectory(new File("directory"));

Recorrido

public static Stack depthFirstOrder(final T treeRoot)
{
   // Main stack, where the important stuff go
   Stack mainStack = new Stack();

   // Temp child stack, where we store children of before it gets put to the mainStack
   Stack tempChildStack = new Stack();

   mainStack.push(treeRoot);   // Put the tree root
   tempChildStack.addAll(treeRoot.getChildren()); // Put the children to the temp

   // Loop until no more children in the temp stack
   while (!tempChildStack.isEmpty())
   {
      T node = (T) tempChildStack.pop();   // Keep popping from the temp stack..
      mainStack.push(node);   // .. and Push to the main stack..
      tempChildStack.addAll(node.getChildren()); // .. while adding children to temp
   }

   // Now temp stack is empty and mainStack has things in DFS order!
   return mainStack;
}



Publicado por en No hay comentarios:
Suscribirse a: Comentarios (Atom)