Estructura.
Estructura de datos.
Es una agregación de tipos de datos compuestos y atómicos en un conjunto con relaciones bien definidas.
Una estructura significa un conjunto de reglas que contienen los datos juntos.
Un conjunto de asociaciones o relaciones (estructura) que implica a los elementos combinados.
Una estructura significa un conjunto de reglas que contienen los datos juntos.
Un conjunto de asociaciones o relaciones (estructura) que implica a los elementos combinados.
Tipo de dato.
Un tipo de dato es un conjunto de valores u operaciones asociadas a estos valores.
Enteros Valores -3, -2, -1, 0, 1, 2, 3
Operaciones *, +, -, /
Caracter Valores ´A´,´B´, ´C´, ´D
Operaciones >, <
Tipo de dato Primitivo
Son aquellos que no se construyen a partir de otros tipos y son entidades únicas.
- Enteros.
- Coma flotante.
- Caracter.
- Lógico.
Tipo de datos Compuesto.
Son tipos de datos cuyos valores constan de colecciones de elementos de datos.
- Arreglos.
- Secuencias (árbol, listas).
- Registros (base de datos).
Abstracción de datos.
Es la técnica para inventar nuevos tipos de datos que sean más adecuados a una aplicación y, por consiguiente faciliten la escritura del programa.
- Programas más cortos, más legibles y flexibles.
Modularidad.
·Es la posibilidad de dividir una aplicación en piezas más pequeñas.
Abstracción en lenguaje de programación.
- Abstracciones de control (nivel sentencia): Sentencias de Bifurcación: (if) y Bucles: (for, while, etc).
- Abstracciones de control (nivel por procedimientos): Procedimientos, métodos o funciones.
Estructuras de Datos Lineales y no Lineales.
Estructura de Datos Lineales:
Existen tres estructuras lineales especialmente importantes:
1.- 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 secuencias vacía.
- Añadir un elemento a la secuencia.
- Eliminar 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 elementos puede estar con cero, uno o más elementos. Las estructuras no lineales de datos más generales 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, árboles genealógicos y tablas de contenidos.Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición re-cursiva, un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.
Nodo padre: nodo que contiene un puntero al nodo actual.
Programa Pila Dinámica.
package estructura_organizacion;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Pila_Dinamica {
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);
}
}
Programa Pila Estática.
package estructura_organizacion;
import java.util.Scanner;
public class Estructura_Organizacion {
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) {
Estructura_Organizacion p = new Estructura_Organizacion();
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 Pila Estática modificado.
package estructura_organizacion;
import java.util.Scanner;
public class Primer_Programa {
public static int op;
public static int tope;
int pila[]= new int[10];
public static int dato;
public void insertar()
{
for(int to=0;to<pila.length;to++ ){
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"+pila[topeM]);
}
}
else{
System.out.println("Pila vacia no hay nada que mostrar");
}
}
public void eliminar(){
if (tope<0){
System.out.println("pila vacia");
}
else if(tope==10){
tope--;
pila[tope]=0;
tope--;
}
else{
pila[tope]=0;
tope--;
}
}
public static void main(String[] args)
{
Primer_Programa p=new Primer_Programa();
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 pila?");
System.out.println("1-Insetar");
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"));
{
if ("n".equals(r))
{
p.imprimir();
}
}
}
}
![[larga fila de personas[68].jpg]](http://lh3.ggpht.com/_Xu_olVDMyMs/TYQtwjV01lI/AAAAAAAAALc/I7kNu1lCEvE/s1600/larga+fila+de+personas%5B68%5D.jpg)
Tipos de Colas.
Cola Simple.
Estructura lineal donde los elementos salen en el mismo orden en el que llegan.
Cola Circular.
Representación lógica de una cola simple de un arreglo.
Cola Doble (Bicola).
Estructura lineal en la que los elementos se pueden añadir o quitar por cualquier extremo de la cola.
Programa Cola Estática.
package estructura_organizacion;
import java.util.Scanner;
public class Cola_Estática {
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 topeM=0;topeM<10;topeM++){
System.out.println("\n\n" + cola [topeM]);
}
}
else {
System.err.println("cola vacia no hay nada que mostrar");
}
}
public void eliminar(){
if(tope>0) {
for(int topeM=0;topeM<10;topeM++){
cola[topeM]=0;
} }
else {
{
System.out.println("cola vacia");
}
}
}
public static void main(String[] args) {
Cola_Estática p = new Cola_Estática();
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);
}
}
Árboles.
Estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos.
Aplicaciones.
- Fórmulas.
- Circuitos eléctricos.
- Árbol genealógico.
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 elnombre de terminal y hoja.
Grado. Número de descendientes directos de un determinado nodo.
Grado árbol. Es el máximo grado de todos los nodos del árbol.
Nivel. Es el número de arcos que pueden ser recorrido para llegar a un determinado nodo.
Longitud de camino Interno.
La longitud de camino internop es la suma de las longitudes de camino de todos los nodos del árbol.
i=nivel de árbol. n=altura. ni=númerode nodos en el nivel i.
--------------------------------------------------------------
Longitud de camino Externo.
- Árbol Extendido. Es aquel en el que el número de hijos de cada nodo es igual al grado del árbol, de no cumplir con esta característica se deben incorporar nodos especiales.
- Nodos Especiales. Reemplazan las ramas vacías o nulas.
- LCE. Es la suma de todos los nodos especiales.
Árbol Binario.
Estructura homogénea, resultado de la concatenación de un tipo elemento tipo T, llamado raíz, con dos árboles binarios disjuntos, llamados subárbol izquiero¿do y subárbol derecho.
Es un árbol ordenado, en el cual cada nodo puede tener como máximo dos subárboles
Árboles Distintos. Árboles Similares.
Árboles Equivalentes.
Árbol General.
Árbol General- Árbol Binario.
- Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
- Relacionar en forma vertical el nodo padre con el hijo que se encuentre más a la izquierda. Además, se debe eliminar el vínculo de esepadre con el resto de los hijos.
- Rotar el diagrama resultante, aproximadamente 45 grados hacía la izquierda y así se obtendrá un árbol binario correspondiente.
Bosque.
Representa un conjunto normalmente ordenado de uno o más árboles generales.
-------------------------------------------------------------------------------
Conversióna árbol binario.
- Enlazar en forma horizontal las raíces de los dintistos árboles generales.
- Relacionar los hijos de cada nodo (los hermanos) en forma horizontal.
- Enlazar en forma vertical el nodo padrecon el hijo que se encuentra más a la izquierda. Además se debe eliminar el vínculo del padre con el resto de sus hijos.
- Rotar el diagrama resultante aproximadamente 45° hacía la izquierda y así obtendrá el árbol binario correspondiente.
Ejemplo de aplicaciones de arboles.
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 á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 ();
}
}
Recorridos de un árbol.
Recorrido Inorden (I,R,D).
- Inorden: (izquierdo, raìz, derecho). Para recorrer un árbol vinario 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.
- 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.
- Posorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en posorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
- Atraviese el sub-árbol izquierdo.
- Atraviese el sub-árbol derecho.
- Visite la raíz.
Árbol Genealógico.
Ejemplo de JTree.
El JTree es un componente de Java visual que nos permite visualizar un árbol, se le denomina "la vista", que es la clase que se ve. También está el "Modelo de datos", esta clase de Java puede ser cualquier clase que implemente la interface TreeModel, pero java nos ofrece ya implementada la clase DefaultTreeModel. Esta es la clase que contiene los datos que queremos visualizar en la "vista". Contiene los datos que visualizaremos en el JTree.Como se utiliza en un árbol, se admite datos que se puedan asociar entre sí como padres e hijos. No valen datos cualesquiera. Esos datos deben implementar la interface TreeNode. Cualquier clase que implemente esta interface, tendrá métodos para interrogarle sobre quién es su padre, si tiene hijos, etc. Estos métodos será los que acabe usando JTree para saber que debe pintar, quién es hijo de quien y quién es padre de quien.
Existe otro tipo de dato también importante, el Mutable TreeNode. Este es igual que el anterior, pero además tiene métodos para modificar las asociaciones entre padres e hijos, Permite añadir nuevos hijos a los padres, cambiar el padre de los hijos y cualquier otro tipo de indecencia que se ocurra. Si el árbol va a cambiar sobre la marcha, interesa usar datos (nodos) que implementen esta interface.
Java nuevamente ofrece una clase que ya implementa MutableTreeNode y por tanto tiene todos los métodos necesarios para saber quién es hijo de quién y los métodos necesarios para cambiar estas asociaciones. Esta clase es DefaultMutableTreeNode. Tiene además un método interesante, que es seUserObjetc(). Éste método nos permite guardar dentro la información que queremos. Esta información será nuestro dato real, lo que realmente nos interesa. DefaultMutableTreeNode únicamente nos ahorrará escribir el código necesario para mantener asociaciones entre padres e hijos, además de hacer de almacén de nuestro dato.
Métodos de Ordenamiento.
Bubble Sort.
La ordenación de burbuja (Bubble Sort) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.
Bubble Sort en Java.
public class burbuja {
int[] vector ;
int elementos=0;
boolean bandera=true;
public burbuja (int[] v){
this.vector=v;
}
public int[] ordenar(){
int p1;
int p2;
int y=0;
bandera=true;
elementos = vector.length;
while((elementos > 1) && (bandera==true) )
{
y=0;
p1 = vector[y];
p2 = vector[y+1];
elementos--;
bandera=false;
for(int i=0; i < elementos; i++){
if (p1>p2){
vector[i]=p2;
vector[i+1]=p1;
bandera=true;
}//fin de si
System.out.println("ordenando: "+ Mostrar(vector));
y++;
if (y < elementos){
p1 = vector[y];
p2 = vector[y+1];
}
}//fin for
}//fin de mientras
return vector;
}
//para imprimir el array
public String Mostrar(int[] v){
String s=" | ";
for (int i=0; i < v.length; i++){
s += v[i] + " | ";
}
return s;
}
}
package javaapplication12;
import java.util.Random;
public class main {
public static void main(String[] args) {
//creamos un array y llenamos este con numeros al azar
int[] c = null ;
c = generarlista(5);
//creamos el objeto burbuja y mostramos
burbuja b = new burbuja(c);
System.out.println("ORIGINAL : "+ b.Mostrar(c));
System.out.println("ORDENADO : "+ b.Mostrar(b.ordenar()));
}
//genera un array de n elementos
public static int[] generarlista(int n){
int[] v = new int[n];
Random rand = new Random();
for (int i=0; i<v.length; i++){
v[i]=rand.nextInt(1000);
}
return v;
}
}
CORRIDA DEL PROGRAMA.
run:
ORIGINAL : | 446 | 141 | 731 | 991 | 241 |
ordenando: | 141 | 446 | 731 | 991 | 241 |
ordenando: | 141 | 446 | 731 | 991 | 241 |
ordenando: | 141 | 446 | 731 | 991 | 241 |
ordenando: | 141 | 446 | 731 | 241 | 991 |
ordenando: | 141 | 446 | 731 | 241 | 991 |
ordenando: | 141 | 446 | 731 | 241 | 991 |
ordenando: | 141 | 446 | 241 | 731 | 991 |
ordenando: | 141 | 446 | 241 | 731 | 991 |
ordenando: | 141 | 241 | 446 | 731 | 991 |
ordenando: | 141 | 241 | 446 | 731 | 991 |
ORDENADO : | 141 | 241 | 446 | 731 | 991 |
BUILD SUCCESSFUL (total time: 1 second).
Quick Sort.
El ordenamiento rápido (Quick Sort) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Ejemplo de Quick Sort en Java.
package javaapplication12;
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);
}
}
CORRIDA DEL PROGRAMA.
run:
Quick Sort
Valores antes de QuickSort:
12 9 4 99 120 1 3 10 13
Valores despues de QuickSort:
1 3 4 9 10 12 13 99 120
BUILD SUCCESSFUL (total time: 0 seconds).
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.
Ejemplo de Shell Sort en Java.
package javaapplication12;
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;
}
} }
}
CORRIDA DEL PROGRAMA.
run:
1 4 5 6 123 213 234 321
BUILD SUCCESSFUL (total time: 0 seconds).
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.
Métodos de Búsqueda.
Método Secuencial:
Este método 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.
Ejemplo de Búsqueda Secuencial en Java.
Método Binario:
Es un método que 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.
No hay comentarios:
Publicar un comentario