lunes, 31 de octubre de 2011

Colas (Informatica)

Concepto

Una cola 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.





Utilizacion

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.
Una cola 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.
Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.


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ó.


Codificacion de Colas
Colas en C++

#ifndef COLA
  #define COLA // Define la cola
  template <class T>
  class Cola{
      private:
        struct Nodo{
            T elemento;
            struct Nodo* siguiente;  // coloca el nodo en la segunda posición
        }* primero;
        struct Nodo* ultimo;
        unsigned int elementos;
      public:
        Cola(){
            elementos = 0;
        }
        ~Cola(){
            while (elementos != 0) pop();
        }
        void push(const T& elem){
            Nodo* aux = new Nodo;
            aux->elemento = elem;
            if (elementos == 0) primero = aux;
            else ultimo->siguiente = aux;
            ultimo = aux;
            ++elementos;
        }
        void pop(){
            Nodo* aux = primero;
            primero = primero->siguiente;
            delete aux;
            --elementos;
        }
        T consultar() const{
            return primero->elemento;
        }
        bool vacia() const{
            return elementos == 0;
        }
        unsigned int size() const{
            return elementos;
        }
    };
    #endif

 

 Colas en JAVA

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }



Vide de Programa  Colas en C++   (1/2)




 Parte  2



viernes, 21 de octubre de 2011

Arbol (informatica)




Arboles Binarios

    El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación.
   
    Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.
   La definición de un árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.



TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOL GENERAL
La representación y terminología de los arboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. 



RAIZ: Todos loa árboles que no esta vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de el. El nodo Raíz no tiene Padre es decir no es hijo de ningún elemento



PADRE: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

HIJO: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

HERMANO: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

HOJA. Se le llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO. Son los Vértices o elementos del Árbol.

NODO INTERIOR. Es un nodo que no es raíz ni Terminal.

GRADO. Es el número de descendientes directos de un determinado nodo.

GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.

NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

ALTURA. Es el máximo número de niveles de todos los nodos del árbol. Equivale al nivel más alto de los nodos más 1.

PESO. Es el número de nodos terminales del árbol

LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
Operaciones de los Arboles Binarios

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:
  • El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos A_1, A_2 \dots A_k en orden previo.
  • El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos A_2 \dots A_k en orden simétrico.
  • El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos A_1, A_2 \dots A_k en orden posterior y por último la raíz.
Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).


Codigo de Arbol
import java.io.*;

class TreeNode {
     String word;               // Word being stored.
     int count = 1;             // Count of words seen in text.
     TreeNode left;             // Left subtree reference.
     TreeNode right;            // Right subtree reference.

     public TreeNode (String word) {
            this.word = word;
            left = right = null;
     }

     public void insert (String word)  {
            int status = this.word.compareTo (word);

            if (status > 0) {    // word argument precedes current word

                    // If left-most leaf node reached, then insert new node as 
                    // its left-most leaf node. Otherwise, keep searching left.
                    if (left == null)
                            left = new TreeNode (word);
                    else
                            left.insert (word);
            }
            else
                if (status < 0) {    // word argument follows current word     

                    // If right-most leaf node reached, then insert new node as
                    // its right-most leaf node. Otherwise, keep searching right.

                    if (right == null)
                            right = new TreeNode (word);
                    else
                            right.insert (word);
                }
                else
                    this.count++;
     }
}

class WC {
     public static void main (String [] args) throws IOException  {
            int ch;

            TreeNode root = null;

            // Read each character from standard input until a letter
            // is read. This letter indicates the start of a word.

            while ((ch = System.in.read ()) != -1) {
                 // If character is a letter then start of word detected.

                 if (Character.isLetter ((char) ch)) {
                         // Create StringBuffer object to hold word letters.

                         StringBuffer sb = new StringBuffer ();

                        // Place first letter character into StringBuffer object.
                         sb.append ((char) ch);

                         // Place all subsequent letter characters into StringBuffer
                         // object.
                         do {
                                ch = System.in.read ();
                                if(Character.isLetter ((char) ch))
                                        sb.append((char) ch);
                                else
                                        break;
                         }
                         while (true);
                         // Insert word into tree.
                         if (root == null)
                                root = new TreeNode (sb.toString ());
                         else
                                 root.insert (sb.toString ());
                 }
            }
            display (root);
     }

     static void display (TreeNode root) {
            // If either the root node or the current node is null,
            // signifying that a leaf node has been reached, return.
            if (root == null)
                    return;

            // Display all left-most nodes (i.e., nodes whose words
            // precede words in the current node).
            display (root.left);

            // Display current node's word and count.
            System.out.println ("Word = " + root.word + ", Count = " +
                                                    root.count);

            // Display all right-most nodes (i.e., nodes whose words
            // follow words in the current node).
            display (root.right);
     }
}

Sintaxis de un arbol en Java

martes, 4 de octubre de 2011

Pilas












Concepto


 Las pilas son estructuras de datos que tienes dos operaciones básicas:
push (para insertar un elemento) y  pop (para extraer un elemento). Su
característica fundamental es que al extraer se obtiene siempre el último
elemento que acaba de insertarse. Por esta razón también se conocen como
estructuras de datos LIFO (del inglés  Last  In  First  Out).

Aplicaciones

Las pilas se utilizan en muchas  aplicaciones que utilizamos con
frecuencia. Por ejemplo, la gestión de ventanas en Windows (cuando cerramos
una ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la
evaluación general de cualquier expresión matemática para evitar tener que
calcular el número de variables temporales que hacen falta. Por ejemplo:

                                         3 + 4 * (8 – 2 * 5)


  5                
 -2                           -10            
  8                              8                               - 2    
  4                              4                                 4                             -8  
  3                              3                                 3                               3                   -5




Operaciones básicas de las pilas

Vamos a estudiar las principales operaciones a realizar sobre una pila, insertar y borrar.

Insertar

En primer lugar hay que decir que esta operación es muy comúnmente denominada push.
La inserción en una pila se realiza en su cima, considerando la cima como el último elemento insertado. Esta es una de las particularidades de las pilas, mientras el resto de estructuras de datos lineales se representan gráficamente en horizontal, las pilas se representan verticalmente. Por esta razón es por lo que se habla de cima de la pila y no de cola de la cima. Aunque en el fondo sea lo mismo, el último elemento de la estructura de datos.
Las operaciones a realizar para realizar la inserción en la pila son muy simples, hacer que el nuevo nodo apunte a la cima anterior, y definir el nuevo nodo como cima de la pila.
Vamos a ver un ejemplo de una inserción:
Pila: Cabeza 3, 76, -6
Al insertar sobre esta pila el elemento 0, la pila resultante sería:
Pila: Cabeza 0, 3, 76, -6

Borrar

Esta operación es normalmente conocida como pop.
Cuando se elimina un elemento de la pila, el elemento que se borra es el elemento situado en la cima de la pila, el que menos tiempo lleva en la estructura.
Las operaciones a realizar son muy simples, avanzar el puntero que apunta a la cima y extraer la cima anterior.
Si aplicamos la operación pop a la pila de 4 elementos representada arriba el resultado sería:
Pila: Cabeza 3, 76, -6. Eliminado el 0




lunes, 3 de octubre de 2011

Listas Circulares

Definicion

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

-- Los tipos de datos que definiremos normalmente para manejar
listas son:

*tipoNodo: es el tipo para declarar nodos
*pNodo: declarar punteros a un nodo.



Operaciones basicas

Insertar elemento en la lista vacía
  • lista apunta a nodo.
  • lista->siguiente apunte a nodo.



Insertar elemento en una lista no vacía
1.Hacemos que nodo = siguiente apunte a lista = siguiente.
2.Después que lista = siguiente apunte a nodo.
Eliminar el único nodo de la lista.
1.lista = siguiente mientras lista = siguiente sea distinto de nodo.
2.Hacemos que lista = siguiente apunte a nodo = siguiente.
3.Eliminamos el nodo.