ORDENAMIENTO DE LISTA EN ALGORITMO

// Se ingresa una lista de nombres (la lista termina
// cuando se ingresa un nombre en blanco) no permitiendo
// ingresar repetidos y luego se ordena y muestra

Proceso OrdenaLista

Dimension lista[200];

Escribir "Ingrese los nombres (enter en blanco para terminar):";

// leer la lista
cant<-0;
//AQUI GUARDA EL NOMBRE
Leer nombre;
Mientras nombre<>"" Hacer
cant<-cant+1;
lista[cant]<-nombre;
Repetir // leer un nombre y ver que no este ya en la lista
Leer nombre;
se_repite<-Falso;
Para i<-1 Hasta cant Hacer
Si nombre=lista[i] Entonces
se_repite<-Verdadero;
FinSi
FinPara
Hasta Que NO se_repite
FinMientras

// ordenar la lista
Para i<-1 Hasta cant-1 Hacer
// busca el menor entre i y cant
pos_menor<-i;
Para j<-i+1 Hasta cant Hacer
Si lista[j] pos_menor<-j;
FinSi
FinPara
// intercambia el que estaba en i con el menor que encontro
aux<-lista[i];
lista[i]<-lista[pos_menor];
lista[pos_menor]<-aux;
FinPara

// mostrar como queda la lista
Escribir "La lista ordenada es:";
Para i<-1 Hasta cant Hacer
Escribir " ",lista[i];
FinPara

FinProceso

ESTRUCTURA DE DATOS

ESTRUCTURA DE UN ARBOL

COLA DE PRIORIDAD EN JAVA

/**
* Clase enumerada que representa la
* urgencia de un cliente
*/
public enum Urgencia
{
baja, media, alta
}
import java.util.*;
/public class ColaEsperaConUrgencia
{
/**
* Clase interna para almacenar los datos
* de un cliente con urgencia
*/
private static class DatosCliente
implements Comparable
{
Cliente c;
Urgencia urg;
/**
* Constructor de DatosCliente
*/
DatosCliente (Cliente c, Urgencia urg) {
this.c=c;
this.urg=urg;
}
/*
* Comparación de clientes por su urgencia
*/
public int compareTo(DatosCliente otro) {
return this.urg.compareTo(otro.urg);
}
// cola del servicio
private Queue colaEspera;
/**
* Constructor de ColaEspera
*/
public ColaEsperaConUrgencia()
{
colaEspera=new
PriorityQueue();
}
/**
* Nuevo cliente; se mete en la cola de espera
*/
public void nuevoCliente
(Cliente c, Urgencia urg)
{
DatosCliente datos=new DatosCliente(c,urg);
colaEspera.add(datos);
}
/**
* Atender cliente: se saca de la cola de
* espera; retorna el cliente atendido
*/
public Cliente atenderCliente()
throws NoSuchElementException
{
DatosCliente datos=colaEspera.remove();
return datos.c;
}
/**
* Mostrar el estado de la cola de espera
*/
public void muestraEstado() {
System.out.println();
System.out.println("--Estado de la cola--");
System.out.println("No atendidos "+
colaEspera.size());
if (colaEspera.size()>0) {
for (DatosCliente datos:colaEspera) {
System.out.println(datos.c+" urgencia:
"+datos.urg);
}
}
}
/**
* Num clientes en espera
*/
public int numClientesEnEspera() {
return colaEspera.size();
}
}

COLA DE ESPERA EN JAVA

import java.util.*;
public class ColaEspera {
/** Clase interna para almacenar todos los datos de un cliente*/
private static class DatosCliente {
Cliente c;
long entrada, salida; // milisegundos
/** Constructor; pone la hora de entrada*/
DatosCliente (Cliente c) {
this.c=c;
entrada=Reloj.ahora();
}
void atiende() {
salida=Reloj.ahora();
}
}
// colas del servicio
private Queue colaEspera;
private Queue colaAtendidos;
/**Constructor de ColaEspera */
public ColaEspera() {
colaEspera=new LinkedList();
colaAtendidos=new
LinkedList();
}
/**
* Nuevo cliente; se mete en la cola de espera
*/
public void nuevoCliente(Cliente c)
{
DatosCliente datos=new DatosCliente(c);
colaEspera.add(datos);
}
/**
* Atender cliente: se saca de la cola de
* espera y se mete en la de atendidos;
* retorna el cliente atendido
*/
public Cliente atenderCliente()
throws NoSuchElementException
{
DatosCliente datos=colaEspera.remove();
datos.atiende();
colaAtendidos.add(datos);
return datos.c;
}
public double tiempoEsperaNoAtendidos()
{
long tiempo=0;
int num=0;
long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) {
tiempo=tiempo + ahora-datos.entrada;
num++;
}
if (num==0) {
return 0.0;
} else {
return (((double) tiempo)/num)/1000.0;
}
}
public double tiempoEsperaNoAtendidos()
{
long tiempo=0;
int num=0;
long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) {
tiempo=tiempo + ahora-datos.entrada;
num++;
}
if (num==0) {
return 0.0;
} else {
return (((double) tiempo)/num)/1000.0;
}
}

EJEMPLO DE COLAS EN JAVA

import java.io.*;

//Declaramos la clase calculatorTest
public class ejecutar_cola{


//Declaramos el metodo principal
public static void main (String args[])throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int Espacios = 0;
char Resp, op;
String aux;

//--- Imprimir Menu ---- \\

System.out.println("\n :: XROM RELOADED :: 19/07/07 \n");

System.out.print("\t Cuantos espacios quiere en la Cola (entre 3 y 30 recomendable)? :");
Espacios = Integer.parseInt(entrada.readLine());

Cola Ejecutar = new Cola(Espacios);

//--- Imprimir Menu ---- \\

System.out.println("\n\n\t ------------ //-------- Menu Cola Simple --------\\\\------------ \n ");

do {

System.out.println("\n\n1.- Imprimir Cola"); // Mostrar
System.out.println("2.- Agregar Elemento a la Cola"); // Push
System.out.println("3.- Quitar Elemento de la Cola"); // Pop


System.out.print("\n\n Elija una Opcion : ");

aux = entrada.readLine();
op = aux.charAt(0);



//---- Elegir opcion ---\\


switch (op) {

case '1':

Ejecutar.Imprimir();

break;

case '2':


Ejecutar.Push();


break;

case '3':

Ejecutar.Pop();

break;


default:

System.out.println("opcion fuera de rango !!");



} // Fin del switch


System.out.print("Desea hacer otra operacion ?? S / N ");
aux = entrada.readLine();
Resp = aux.charAt(0);


} while (Resp == 'S' Resp == 's');


} // Fin del metodo main

} // Fin de la calse
Cola.java(Clase y Metodos de la Cola)

ARBOL BINARIO DE BUSQUEDA EN JAVA

public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}

public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}

public void visitarInorden()
{
inorden(null, true);
}

public void visitarPosorden()
{
posorden(null, true);
}

public void visitarPreorden()
{
preorden(null, true);
}
}

PROGRAMA DE ARBOLES CON JPANEL EN JAVA

import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;

static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {

//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){

Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};

if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );

}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada

rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);

}

}

ARBOL GENERICO

public class Arboles {

public Arboles() {
System.out.println("Un árbol genérico");
}

public Arboles(String tipo) {
System.out.println("Un árbol tipo " + tipo);
}

public Arboles(int altura) {
System.out.println("Un árbol de " + altura + " metros");
}

public Arboles(int altura,String tipo) {
System.out.println("Un " + tipo + " de " + altura + " metros");
}

public static void main(String args[]) {
Arboles arbol1 = new Arboles(4);
Arboles arbol2 = new Arboles("Roble");
Arboles arbol3 = new Arboles();
Arboles arbol4 = new Arboles(5,"Pino");
}
}

mapa conceptual estructuras

ALGORITMOS ARBOLES

Inor(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprmir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Temp → Izq[Temp]
Fin del ciclo
Temp → Pila[Top]
Top → Top - 1
Mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Temp → Der[Temp]
Ir a Etiqueta
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo

Salir
----------------------------------------------

PostOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → - (Der[Temp])
Temp → Izq[Temp]
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Mientras Temp ≥ 0
Imprimir Arbol[Temp]
Si Arbol[Temp] = Info[Raiz]
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Si Temp < 0 Temp = -(Temp)
Ir a Etiqueta

Salir

----------------------------------------------
PreOrd(Arbol, Der, Izq, Pila, Raiz)

Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Árbol Vació…” y Salir
Repetir mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → Der[Temp]
Si Izq[Temp] ≠ Nulo
Temp → Izq[Temp]
Si no:
Temp → Pila[Top];
Top → Top - 1
Fin del ciclo

Salir
----------------------------------------------

Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem)

Si Raiz = Nulo
Imprimir “Arbol Vacio”
Pos → Nulo
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem = Arbol[Raiz]
Imprimir “Elemento Encontrado”
Pos → Raiz
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem < Arbol[Raiz]
Temp → Izq[Raiz]
Temp2 → Raiz
Si no:
Temp → Der[Raiz]
Temp2 → Raiz
Mientras Temp ≠ Nulo
Si Elem = Arbol[Temp]
Imprimir “Elemento Encontrado…”
Pos → Temp
Pad → Temp2
Regresar Pos y Pad
Salir
Si Elem < Arbol[Temp]
Temp2 → Temp
Temp → Izq[Temp]
Si no:
Temp2 → Temp
Temp → Der[Temp]
Fin del ciclo
Imprimir “Elemento no Encontrado…”
Pos → Nulo
Pad → Temp2
Regresar Pos y Pad

Salir

RECORRIDOS DE UN ARBOL

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden • Visitar el raíz • Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

ARBOLES BINARIOS

COMO UTILIZAR ARBOLES

Podemos utilizar árboles con la clase JTree, se puede mostrar un árbol de datos. JTree realmente no contiene datos, simplemente es un vista de ellos. Aquí tienes una imagen de un árbol.

Como muestra la figura anterior, JTree muestra los datos verticalmente. Cada fila contiene exactamente un ítem de datos (llamado un nodo). Cada árbol tiene un nodo raíz. Los nodos que no pueden tener hijos se llaman nodos leaf (hoja). En la figura anterior, el aspecto-y-comportamiento marca los nodos hojas con una Flecha.

Los nodos que no sean hojas pueden tener cualquier número de hijos, o incluso no tenerlos. En la figura anterior, el aspecto-y-comportamiento marca los nodos que no son hojas con un carpeta. Normalmente el usuario puede expandir y contraer los nodos que no son hojas -- haciendo que sus hijos sean visibles o invisibles -- pulsando sobre él.