Fundamentos de estructuras de datos: septiembre 2013

Fundamentos de estructuras de datos

Estructura de datos

una estructura es una serie de reglas que tienen los datos juntos, o también se puede definir como una combinación de elementos en la que cada uno es bien un tipo de dato u otra estructura de datos.

Datos primitivos

son lo que no se construyen a partir de otros tipos y son entidades únicas.

enteros
coma flotante
caracter
lógico

datos compuestos

Tipos de datos que los valores se conforman de colecciones de elementos de datos

arreglos

secuencias(listas, arboles)

Registros(bases de datos)

Abstracción de datos

es inventar nuevos tipos de datos para que la estructura del programa sea mas fácil, y así sean programas mas cortos, legibles y flexibles.

modularidad

es dividir una aplicación o programa en partes mas chicas

Abstracciones en lenguajes de programación

abstracción de control(nivel por procedimientos)

procedimientos
métodos
funciones

sentencias de bifurcación

sentencias de bucle

for
while
etc

Estructuras de Datos Lineales y no Lineales

Estructura de Datos Lineales:

Existen tres estructuras lineales especialmente importantes:

1.-Las pilas

2.-Las colas

3.-Las listas

Su importancia radica en que son muy frecuentes en los esquemas algorítmicos.

Las operaciones básicas para dichas estructuras son:

• Crear la secuencia vacía

• Añadir un elemento a la secuencia

• Borrar un elemento a la secuencia

• Consultar un elemento de la secuencia

• Comprobar si la secuencia está vacía

La diferencia entre las tres estructuras vendrá dada por la posición del elemento a añadir, borrar y consultar:

• Pilas: Las tres operaciones actúan sobre el final de la secuencia

• Colas: Se añade por el final y se borra y consulta por el principio

• Listas: Las tres operaciones se realizan sobre una posición privilegiada de la secuencia, la cual puede desplazarse.

Estructura de Datos No Lineales:

Se caracteriza por no existir una relación de sus elementos es decir que un elemento puede estar con cero uno o mas elementos.

Las estructuras no lineales de datos mas general son los árboles donde no existe ninguna relación de orden Predefinida.

Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos , como por ejemplo registros.

programa de pila estática original

package estructura_organizacion;

import java.util.Scanner;

public class Pila_Estatica {
public static int op;
public static int tope;
int pila[]= new int[10];
public void insertar(){
if(tope==10)
System.out.println("Pila llena");
else
{
System.out.println("Proporciona el dato para la pila");
System.out.println("dato" + tope);
Scanner cap= new Scanner(System.in);
pila[tope]=cap.nextInt();
tope++;
}
}
public void imprimir(){
if(tope>=10){
for(int topeM=tope-1;topeM>=0;topeM--){
System.out.println("\n\n" + pila [topeM]);
}
}
else
System.err.println("pila vacia no hay nada que mostrar");
}
public void eliminar(){
if(tope<0){
System.out.println("pila vacia");
}
else
if(tope==10){//Esto se usa cuando la pila esta totalmente llena,
//ya que se incremento en insertar y quedo en 10, de lo contrario
//noz arrojara un error de array
tope--;
pila[tope]=0;
tope--;//se vuelve a decrementar para que este en la pocision correcta, porque
//tenia un numero de mas
}
else{
pila[tope]=0;
tope--;
}
}
public static void main(String[] args) {
Pila_Estatica p = new Pila_Estatica();
String r;
Scanner cap1=new Scanner(System.in);
Scanner cap=new Scanner(System.in);
tope=0;
do{
System.out.println("Menu principal:\n¿Que desea hacer con la pila?");
System.out.println("1.-insertar");
System.out.println("2.- eliminar");
System.out.println("3.- imprimir");
System.out.println("4.-salir");
op=cap.nextInt();
switch(op){
case 1:
p.insertar(); break;
case 2:
p.eliminar(); break;
case 3:
p.imprimir(); break;
case 4:
System.out.println("Adios!!!!"); break;
default:
System.out.println("Selecion erronea, teclea otra opcion!!!");
}
System.out.println("deseas Realizar Otra Operacion con tu pila? /(S/N)");
r=cap1.nextLine();
} while(r.equalsIgnoreCase("S"));
}
}

Programa de pila estática modificado

package javaapplication8;

import java.util.Scanner;

public class JavaApplication8 {

public static int op;
public static int tope;
int pila[]= new int[10];
public void insertar(){
if(tope==10)
System.out.println("Pila llena");
else
{
for(int i=0;i<pila.length;i++ ){
System.out.println("Proporciona el dato para la pila");
System.out.println("dato " + tope);
Scanner cap= new Scanner(System.in);
pila[tope]=cap.nextInt();
tope++;
} }
}
public void imprimir(){
if(tope!=0){
for(int topeL=tope-1;topeL>=0;topeL--){
System.out.println("\n\n" + pila [topeL]);
}
}
else
System.err.println("pila vacia no hay nada que mostrar");
}
public void eliminar(){
if(tope<0){
System.out.println("pila vacia");
}
else
if(tope==10){//Esto se usa cuando la pila esta totalmente llena,
//ya que se incremento en insertar y quedo en 10, de lo contrario
//noz arrojara un error de array
tope--;
pila[tope]=0;
tope--;//se vuelve a decrementar para que este en la pocision correcta, porque
//tenia un numero de mas
}
else{
pila[tope]=0;
tope--;
}
}
public static void main(String[] args) {
JavaApplication8 p = new JavaApplication8();
String r;
Scanner cap1=new Scanner(System.in);
Scanner cap=new Scanner(System.in);
tope=0;
do{
System.out.println("Menu principal:\n¿Que desea hacer con la pila?");
System.out.println("1.-insertar");
System.out.println("2.- eliminar");
System.out.println("3.- imprimir");
System.out.println("4.-salir");
op=cap.nextInt();
switch(op){
case 1: p.insertar();break;
case 2:if(tope==10)
p.eliminar();
else
System.out.println("no hay nada que eliminar :) ");
break;
case 3:p.imprimir();break;
case 4:break;
default:
System.out.println("opcion no valida");break;
}
}while(op!=4);

}
}

Cambiando el for para que pidiera los datos sin necesidad de preguntar si quiere insertar otro, esta diseñado para tener 10 elementos. Por lo tanto al momento de imprimir, va imprimir los 10 elementos forzosamente, si se quieren insertar datos que se deseen , por ejemplo 3, y quererlos imprimir, no se podría , por lo tanto , si se quiere hacer eso se tendría que hacer unas series de modificaciones en el programa.

Lista

Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos

referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los

array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de

almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de

almacenamiento.

cola

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación

de inserción se realiza por un extremo y la operación de extracción por el otro.

vector colas

Bicola

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.
Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.

Cola circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

cola prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

pila

Es un lugar donde se almacenan datos, al igual que en un Array, pero una Pila tiene una filosofía de entrada y salida de datos, esta filosofía es la LIFO (Last In First Out, en español, ultimo en entrar, primero en salir). Esta estructura de datos tiene muchas aplicaciones debido a su simplicidad.

Cola estatica

package cola_estatica;
import java.util.Scanner;
public class cola_estatica {
public static int op;
public static int tope;
    int cola[]= new int[10];
    public void insertar(){
        if(tope==10)
            System.out.println("Cola llena");
        else
    {
       for(int i=0;i<cola.length;i++ ){
        System.out.println("Proporciona el dato para la Cola");
        System.out.println("dato " + tope);
        Scanner cap= new Scanner(System.in);
        cola[tope]=cap.nextInt();
        tope++;
    } }
}
    public void imprimir(){
       if(tope>0){
            for(int topeL=0;topeL<10;topeL++){
                System.out.println("\n\n" + cola [topeL]);
                System.out.println(tope);
            }
        }
        else
            System.err.println("cola vacia no hay nada que mostrar");
    }
    public void eliminar(){
        if(tope<0){
            System.out.println("cola vacia");
        }
        else
                for(int topeL=0;topeL<10;topeL++){
                     cola[topeL]=0;
            }
            }
    public static void main(String[] args) {
       cola_estatica p = new cola_estatica();
       String r;
       Scanner cap1=new Scanner(System.in);
       Scanner cap=new Scanner(System.in);
       tope=0;
       do{
           System.out.println("Menu principal:\n¿Que desea hacer con la pila?");
           System.out.println("1.-insertar");
           System.out.println("2.- eliminar");
           System.out.println("3.- imprimir");
           System.out.println("4.-salir");
           op=cap.nextInt();
           switch(op){
               case 1: p.insertar();break;
               case 2:p.eliminar();break;
               case 3:p.imprimir();break;
               case 4:break; default:
                   System.out.println("opcion no valida");break;
           }
    }while(op!=4);
}}

Los datos que se introducen al darle a la opción eliminar, son eliminados todos juntos.

Pila dinamica

package PILAS;
import java.util.*;

public class PilaDinamica {
    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 Menuº \t");
            System.out.println("Operaciones con pilas");
            System.out.println("1.- Insertar");
            System.out.println("2.- Borrar");
            System.out.println("3.- Mostrar la pila");
            System.out.println("4.- 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.addLast(num);
                break;
            case 2:
                System.out.println("SE borrará el nodo final");
                lista.removeFirst();
                break;
            case 3:
                System.out.println("La lista es la siguiente");
                 List lista2 = new ArrayList (lista);
                 Iterator it = lista2.iterator();//añade otro nodo ,es un ciclo
                 //sirve para recorrer la lista
                 while (it.hasNext()){
                     System.out.println(it.next() + "");
                 }
                 break;
            case 4:
                System.out.println("Al rato");
                break;
            }
        }
        while(op != 4);
    }
}

Árboles

Un árbol, es una estructura jerarquica aplicada sobre una colección de elementos u objetos llamados nodos.

Aplicaciones:

Formulas matematicas
Circuitos electricos
árbol genealogico

Propiedades:

Se dice que todos los nodos que son descendientes directos hijos de un mismo nodo padre, son hermanos.

Todo nodo que no tiene ramificaciones hijos, se conoce con el nombre de terminal u hoja.

Grado:

Número de desciendentes directos de un determinado nodo.

Grado de árbol:

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

Nivel:

Es el número de arcos que pueden ser recorridos para llegar a un determinado nodo.

Por definición raíz tiene nivel 1.

Longitud de camino interno:

Es la suma de longitudes de camino de todos los nodos del árbol

LCI=Σni * i

i=1

i=nivel del árbol

h=altura

ni=número de nodos en el nivel i

Lci=número de nivel*número de nodos+número de nivel*número de nodos...

ejemplo(1*1+2*2+4*3+4*4=33)

Árbol extendido:

Aquel en el que el número de hijos de cada nodo es igual al grado del árbol, que no cumplir con esta caracteristica se deben incorporar nodos especiales.

Nodos especiales:

Reemplazan las ramas vacías o nulas.

LCE:

Es la suma de todos los nodos especiales.

Calcular la longitud de camino externo:

n+1

LCE=Σnei* i

i=2

i=Nivel del árbol
h=altura
nei=número de nodos especiales

Árbol binario:

En un árbol binario cada nodo puede tener como máximo dos subárboles; y siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho

árboles distintos

árboles equivalentes

Aplicacion de árboles en Java
(Inorden,Posorden,Preorden)
package aplicacionarboles;
class NodoArbol {
//miembros de acceso
NodoArbol nodoizquierdo;
int datos;
NodoArbol nododerecho;
//iniciar dato y hacer de este nodo un nodo hoja
public NodoArbol(int datosNodo)
{
  datos = datosNodo;
  nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
}
//buscar punto de insercion e insertar nodo nuevo
public synchronized void insertar(int valorInsertar)
{
  //insertar en subarbol izquierdo
  if (valorInsertar < datos){
   //inserta nuevo nodoarbol
   if (nodoizquierdo == null)
    nodoizquierdo = new NodoArbol(valorInsertar);
   else //continua recorriendo subarbol izquierdo
    nodoizquierdo.insertar(valorInsertar);
  }
  //insertar nodo derecho
  else if(valorInsertar > datos){
  //insertar nuevo nodoarbol
  if (nododerecho == null)
   nododerecho = new NodoArbol(valorInsertar);
  else //continua recorriendo subarbol derecho
   nododerecho.insertar(valorInsertar);
  }
} //fin del metodo insertar
} //fin clase nodoarbol
//---------- CLASE ARBOL------------------
class Arbol{
private NodoArbol raiz;
//contruir un arbol vacio
public Arbol()
{
  raiz = null;
}
//insertar un nuevo nodo en el arbol de busqueda binaria
public synchronized void insertarNodo(int valorInsertar)
{
  if(raiz == null)
   raiz = new NodoArbol(valorInsertar); //crea nodo raiz
  else
   raiz.insertar(valorInsertar); // llama al metodo insertar
}
//--------------- EMPEZAR EL RECORRIDO EN PREORDEN-----------------------
public synchronized void recorridoPreorden()
{
  ayudantePreorden(raiz);
}
//metodo recursivo para recorrido en preorden
private void ayudantePreorden(NodoArbol nodo)
{
  if (nodo == null)
   return;
  System.out.print(nodo.datos + " "); // mostrar datos del nodo
  ayudantePreorden(nodo.nodoizquierdo); //recorre subarbol izquierdo
  ayudantePreorden(nodo.nododerecho); //recorre subarbol derecho
}
//--------------EMPEZAR RECORRIDO INORDEN-----------------------------------
public synchronized void recorridoInorden()
{
  ayudanteInorden(raiz);
}
// metodo recursivo para recorrido inorden
private void ayudanteInorden(NodoArbol nodo)
{
  if (nodo == null)
   return;
  ayudanteInorden(nodo.nodoizquierdo);
  System.out.print(nodo.datos + " ");
  ayudanteInorden(nodo.nododerecho);
}
//-----------------------------EMPEZAR RECORRIDO POSORDEN---------------------------------
public synchronized void recorridoPosorden()
{
  ayudantePosorden(raiz);
}
//metodo recursivo para recorrido posorden
private void ayudantePosorden(NodoArbol nodo)
{
  if (nodo == null)
   return;
  ayudantePosorden(nodo.nodoizquierdo);
  ayudantePosorden(nodo.nododerecho);
  System.out.print(nodo.datos + " ");
}
}//fin clase arbol
//programa para probar la clase arbol-------------------------------------------------------------------------------------
MAIN DE APLICACION DE JAVA
package aplicacionarboles;
import java.util.Scanner;
public class PruebaArbol {
public static void main(String args[])
{
  Arbol arbol = new Arbol();
  int valor;
                Scanner leer=new Scanner(System.in);
  System.out.println( "Insertando los siguientes valores: ");
  //insertando 10 numeros aleatorios del 0 al 99 en el arbol
  for (int i = 1; i<=10 ; i++)
  {
                    //valor = (int) (Math.random() * 100);
             System.out.println("Inserte valor");
                    valor=leer.nextInt();
                   // System.out.print(valor + "");
                    arbol.insertarNodo(valor);
  }
  System.out.println("\n\nRecorrido preorden");
  arbol.recorridoPreorden();
  System.out.println("\n\nRecorrido inorden");
  arbol.recorridoInorden();
  System.out.println("\n\nRecorrido posorden");
  arbol.recorridoPosorden();
}
}

árbol genealógico

Tipos de recorridos en un àrbol binario
Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

Visite la raíz
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

Atraviese el sub-árbol izquierdo
Visite la raíz
Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Visite la raíz

Analizando clase tree y métodos

package arbol;

import java.awt.*;

import java.awt.event.*;

import javax.swing.*;

import javax.swing.tree.*;

import java.util.*;

/**

* @author alumno

public class Main {

/**

* @param args the command line arguments

public static void main(String[] args)

{ JFrame frame = new MainTreeFrame();

frame.show();

}

class MainTreeFrame extends JFrame// aquì crea la clase de maintreeframe que es de tipo JFrame, asignando después varios nodos al árbol, también poniéndole raíces en este caso con el nombre de "Mundo".

{

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 MainTreeFrame()

{ 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

}

//Al ultimo enumera y ordena todos los nodos del programa por preorden, posorden e inorden.

Aplicación de árboles

import java.util.Scanner;

public class arbol {
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 arbol:"+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 ();
int a,b,c,d,e;
Scanner leer= new Scanner(System.in);
System.out.println("Inserte el primer valor");
a=leer.nextInt();
abo.insertar (a);
System.out.println("Inserte el segundo valor");
b=leer.nextInt();
abo.insertar (b);
System.out.println("Inserte el tercer valor");
c=leer.nextInt();
abo.insertar (c);
System.out.println("Inserte el cuarto valor");
d=leer.nextInt();
abo.insertar (d);
System.out.println("Inserte ultimo valor");
e=leer.nextInt();
abo.insertar (e);
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Cantidad de nodos del arbol:"+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 ();
}
}

APLICACIÓN DE RECURSIVIDAD ( TORRES DE HANOI )

package hanoi;

import java.util.*;

public class Hanoi {

public static void main(String[] args) {

Scanner leer = new Scanner(System.in);

int n;

System.out.println("Numero de discos: ");

n = leer.nextInt();

Hanoi(n,1,2,3); //1:origen 2:auxiliar 3:destino

//Se aplica la recursividad

}

public static void Hanoi(int n, int origen, int auxiliar, int destino){

if(n==1)

System.out.println("mover disco de " + origen + " a " + destino);

else{

Hanoi(n-1, origen, destino, auxiliar);//Se aplica la recursividad

System.out.println("mover disco de "+ origen + " a " + destino);

Hanoi(n-1, auxiliar, origen, destino);//Se aplica la recursividad

}

(normalmente se juega con 3 discos)

Métodos de ordenamiento

Método burbuja

Es un sencillo algoritmo de ordenamiento, el cual funciona revisando o comparando cada elemento de la lista, intercambiando posiciones si estan mal ordenados. Se hace este método cuantas veces sea necesario para que los elementos esten ordenados correctamente.

Una de las ventajas es que tiene un código reducido y eficaz, pero a su vez tiene la desvenaja es que consume bastante tiempo computarizado, requiere de muchas escrituras en memoria.

PROGRAMA JAVA

public class array2{

public static void main(String[]args){

int[]nums={34,25,13,24,8,1,11};

int aux;

for(int i=0;i<nums.lenght;i++){

for(int j=i+1;j<nums.lenght;j++){

if(nums[j]<nums[i]){

aux=nums[i];

nums[i]=nums[j];

nums[j]=aux;

}

System.out.pintln("La matriz ordenada es");

for(int i=0;i<nums.lenght;i++){

System.out.pint(nums[i]+" ");

}

Método Quick sort

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

La idea central de este algoritmo consiste en los siguiente:

Se toma un elemento x de una posición cualquiera del arreglo.

Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.

Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

PROGRAMA JAVA

public class QuickSort{

public static void main(String a[]){

int i;

int array[] = {12,9,4,99,120,1,3,10,13};

System.out.println(" Quick Sort\n");

System.out.println("Valores antes de QuickSort:\n");

for(i = 0; i < array.length; i++)

System.out.print( array[i]+" ");

System.out.println();

quick_srt(array,0,array.length-1);

System.out.print("\n\n\nValores despues de QuickSort:\n\n");

for(i = 0; i <array.length; i++)

System.out.print(array[i]+" ");

System.out.println();

}

public static void quick_srt(int array[],int low, int n){

int lo = low;

int hi = n;

if (lo >= n) {

return;

}

int mid = array[(lo + hi) / 2];

while (lo < hi) {

while (lo<hi && array[lo] < mid) {

lo++;

}

while (lo<hi && array[hi] > mid) {

hi--;

}

if (lo < hi) {

int T = array[lo];

array[lo] = array[hi];

array[hi] = T;

}

if (hi < lo) {

int T = hi;

hi = lo;

lo = T;

}

quick_srt(array, low, lo);

quick_srt(array, lo == low ? lo+1 : lo, n);

}

Método Shell Sort.
El ordenamiento Shell (Shell Sort) es un algoritmo de ordenamiento. El Shell Sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
1.- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2.- El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell Sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada.

Programa en Java Shell sort

public class ShellSort {

public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; //Este es el array de elementos que vamos a ordenar

shellSort(arrayEntrada); //llamada al metodo shellSort
for (int i=0;i < arrayEntrada.length;i++){ //Este bucle imprime el contenido del array
System.out.print(arrayEntrada[i]+" ");
}//fin del for
}//fin del main

public static void shellSort( int a[ ]){
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < a.length; i++ ){
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){
a[ j ] = a[ j - gap ];
}
a[ j ] = tmp;
}
} }
}

Método de ordenamiento Radix

El ordenamiento Radix (Radix Sort) es un algoritmo que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

Código Java de método Radix
Solo funciona con números positivos

import java.lang.;

import java.io.;

public class RadixSort{

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 ;-)");

}

}

Métodos de búsqueda

Método secuencial

Se usa para buscar un elemento de un vector; es explorar secuencialmente el vector, es decir; recorrer el vector desde el primer elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a "Fin de la búsqueda" o "Elemento encontrado" y otro que diga "Posición=" en caso contrario, visualizar un mensaje similar a "Elemento no existe en la lista". Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que se consiga o se termine de leer el vector completo.

Código Java de Búsqueda secuencial

public class secuencialdesordenado {

public void buscar()
{
Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++)
{

System.out.println("introduce los datos del arreglo");

v[c]=leer.nextInt();

}

System.out.println("introduzca elemento a buscar");

x=leer.nextInt();

do{

if(v[i]==x)

{

bandera=true;

}

else {

bandera=false;

}

i++;

}while(i<v.length && bandera==false);

if(bandera==true)

{

System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false)
{
System.out.println("el elemento no esta en la lista");
}
}

Búsqueda Binaria

Se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado. Esta búsqueda utiliza un método de "divide y vendrás" para localizar el valor deseado, Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

Código Java método de búsqueda Binaria
El método ya tiene agregado un método de ordenamiento para que su funcionamiento sea el optimo.

public class BusquedaBinaria

{ public static int busquedaBinaria(int[] Arreglo, int elemento)

{

int i = 0, centro = 0, posicion = 0, inferior = 0, superior = Arreglo.length-1; while(inferior <= superior)

{

centro = (superior + inferior) / 2; if (Arreglo[centro] == elemento)

{

return centro;} else{ if (Arreglo[centro] > elemento)

{ superior = centro - 1;

}

else

{

inferior = centro + 1;

}

return -1;

}
public static void main (String[] args)

{

java.util.Scanner Leer = new java.util.Scanner(System.in);

System.out.print("Tamanio del arreglo:");

int tamanioArreglo = Leer.nextInt();

int[] Arreglo = new int[tamanioArreglo];

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

{

System.out.println("Introduce elemento:"); Arreglo[i] = Leer.nextInt();

}

int A;

for(int i=0;i<Arreglo.length-1;i++)

{

for(int j=0;j<Arreglo.length-i-1;j++)

{

if(Arreglo[j+1]<Arreglo[j])

{

A=Arreglo[j+1];

Arreglo[j+1]=Arreglo[j];

Arreglo[j]=A;

}

} System.out.print("Elemento a buscar:" );

int elemento = Leer.nextInt();

System.out.println("dato");

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

System.out.println(Arreglo[i]);

}

int posicion = busquedaBinaria(Arreglo, elemento);

if(posicion == -1) System.out.println("\nElemento no encontrado");

else

System.out.println("\nElemento " + elemento + " encontrado en la posicion " + posicion);

}

Fundamentos de estructuras de datos

miércoles, 4 de septiembre de 2013