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
sentencia de bifurcacion
- if
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 estatica modoficado
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);
}
}
Lista
consiste en uan secuencia de nodos en los que guardan de datos arbitrarios y una o dos referencias(punteros al nodos anterior o posterior. El principal beneficio de las listas enlazadas 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.
- 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 almacena datos, si igual que en un arrey, pero una pila tiene una filosofia de entrada y salida de datos, esta folosofia es la LIFO(Last in first Out). Esta estructura de datos tiene 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
h
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.
Á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
h=altura
nei=número de nodos especiales
Arboles Binario
Estactura homogenea resultado de la concatenacion de un element de tipo T llamado raiz con dos Arboles binaries distintos llamados subarbol izquierdo y subarbol derecho.
Arboles Distintos:
Arboles Similares:
Arboles Equivalentes:
Arboles General:
Arboles Familiar:
Programa de Arboles (Maestra):
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication3;
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
{
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
}
}
Programa de Arbol (Hecho Por Alumno ITCJ):
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 irbol:"+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 ();
Scanner leer =new Scanner(System.in);
int num, op;
do{
System.out.println("1.- Inserta un numero en el arbol");
System.out.println("2.- Salir");
op =leer.nextInt();
switch(op){
case 1:
System.out.println("Inserte Dato");
num =leer.nextInt();
abo.insertar(num);
break;
case 4:
System.out.println("Bye");
break;
}
}
while(op != 2);
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Cantidad de nodos del irbol:"+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 ();
}
}
Método Burbuja
La Ordenación de burbuja (Bubble Sort en inglés) 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 varias veces toda la lista hasta que no se necesiten más intercambios,
lo cual significa que la lista está ordenada.
Método de los más conocidos y más fáciles, pero a la vez es uno de
los menos eficaces que se basa en la ordenación por intercambio de elementos.
Historia:
Determinar con exactitud el origen del ordenamiento burbuja es un
poco complicado, ya que no existe información precisa sobre su origen.
Aunque en 1956 se encuentra expresado en un articulo al que lo
llamaron “ordenamiento por intercambio”.
Existe una amplia bibliografía de artículos del año 1962 donde
mencionan tipos de ordenamiento basados en este patrón, pero ninguno de ellos
usando el nombre como tal.
Ventajas:
•Bastante sencillo y mas utilizado por su fácil comprensión y
programación
•Código reducido
•Eficaz.
Desventajas:
•Consume bastante tiempo calculo computarizado.
•Requiere de muchas lecturas/escrituras en memoria
Código Del Método Burbuja:
public class Burbuja {
static int [] vec = {312, 614, 88, 22, 54};
void ordenar (int [] v, int cant) {
if (cant > 1) {
for (int f = 0 ; f < cant - 1 ; f++)//
if (v [f] > v [f + 1]) {
int aux = v [f];
v [f] = v [f + 1];
v [f + 1] = aux;
}
ordenar (v, cant - 1);
}
}
void imprimir () {
for (int f = 0 ; f < vec.length ; f++)
System.out.print (vec [f] + " ");
System.out.println("\n"); }
public static void main (String [] ar) {
Recursivdad r = new Burbuja();
r.imprimir ();
r.ordenar (vec, vec.length);
r.imprimir ();
}
}
static int [] vec = {312, 614, 88, 22, 54};
void ordenar (int [] v, int cant) {
if (cant > 1) {
for (int f = 0 ; f < cant - 1 ; f++)//
if (v [f] > v [f + 1]) {
int aux = v [f];
v [f] = v [f + 1];
v [f + 1] = aux;
}
ordenar (v, cant - 1);
}
}
void imprimir () {
for (int f = 0 ; f < vec.length ; f++)
System.out.print (vec [f] + " ");
System.out.println("\n"); }
public static void main (String [] ar) {
Recursivdad r = new Burbuja();
r.imprimir ();
r.ordenar (vec, vec.length);
r.imprimir ();
}
}
Metodo Quick Sort (Ordenamiento Rapido)
Es un algoritmo creado por el científico británico en computación C.A.R. Hoare 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.
Forma en que tabaja el algoritmo:
1-•Elegir
un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
2-•Resituar
los demás elementos de la lista a cada lado del pivote, de manera que a un lado
queden todos los menores que él, y al otro los mayores.
3-•Se comparan para ver si el número
pivote es mayor.
4-•Se vuelven a comparar para ver si es
mayor el número pivote
5-•Este sigue siendo el número pivote.
6-La
lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
7-•Repetir
este proceso de forma recursiva para cada sublista mientras éstas contengan más
de un elemento. Una vez terminado este proceso todos los elementos estarán
ordenados.
8-Elementos Ordenados.
Codigo de Quick Sort
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);
}
}
Metodo SHELL SORT
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.
Ventajas:
-No
requiere memoria adicional.
-Mejor
rendimiento que el método de inserción rápido.
-Fácil implantación.
Desventajas:
-Su
funcionamiento puede resultar confuso
-Suele
ser un poco lento.
-Realiza
numerosas comparaciones e intercambios.
Pasos del Shell Sort:
1.Obtener n.
2.Obtener k ( k=n/2)
3.Clarificar cada grupo por separado, comparando las parejas de elementos y si no están ordenados se intercambian
4.N se divide entre 2 y se vuelve a obtener k. Nuevamente se clasifica cada grupo por separado.
5.El algoritmo termina cuando el tamaño de k es igual a 1.
Código del SHELL SORT:
package Alumno ITCJ;
/**
*
* @author Alumno ITCJ-TIC'S
*/
public class shell_sort {
public static void shellSort( int b[ ])
{
for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2))
{
for(int i=k;i<b.length; i++ )
{
int tmp =b[i];
int j;
for(j=i; j>=k&&tmp<b[j-k]; j-=k)
{
b[j]=b[j-k];
}
b[j]=tmp;
}
}
}
public static void main(String args[]){
int a[]={321, 6, 1, 234, 213, 4, 5, 123}; //Este es el array de elementos que vamos a ordenar
System.out.println("Antes del ordenamiento");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
shellSort(a); //llamada al metodo shellSort
System.out.println("\n");
System.out.println("Ordenado por el método Shell");
for (int i=0;i < a.length;i++){ //Este bucle imprime el contenido del array
System.out.print(a[i]+" ");
}//fin del for
}//fin del main
}//class ShellSort
Método Búsqueda Secuencial
Consiste en recorrer el arreglo
elemento a elemento e ir comparando con el valor.
Pasos de la Búsqueda Secuencial:
1.Consiste en recorrer el arreglo
elemento a elemento e ir comparando con el valor
buscado.
2.Se empieza con la primera casilla
del arreglo y se observa una casilla tras otra hasta que se encuentra el
elemento buscado o se han visto todas las casillas.
3.El resultado de la búsqueda es un
solo valor, y será la posición del elemento buscado o cero.
4.El método de búsqueda lineal
funciona bien con arreglos pequeños o para arreglos no ordenados.
Código 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");
}
}
Método Búsqueda Binaria
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.
Ventajas:
uLa búsqueda binaria es un método eficiente siempre que el
vector esté ordenado.
uLa búsqueda binaria proporciona un medio para reducir el
tiempo requerido para buscar en una lista.
uEste método funciona a un 100%
Desventajas:
uSi los datos del arreglo no están ordenados no hará la
búsqueda
uEste método Necesita un método de ordenamiento como:
Burbuja, Quicksort, shell sort, etc. Para
que así funcione bien.
Codigo Metodo de Busqueda Binaria
Nota: "tiene que tener los elementos ordenados"
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();}
System.out.print("Elemento a buscar:" );
int elemento = Leer.nextInt();
int posicion = busquedaBinaria(Arreglo, elemento);
if(posicion == -1)
System.out.println("\nElemento no encontrado");
else
System.out.println("\nElemento " + elemento + " encontrado en la posici髇 " + posicion);
}
}
Código Método de Búsqueda Binaria
El código ya tiene un método de ordenamiento para que ordene los datos en caso de que no los introduzcas Ordenados.
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);
}
}
No hay comentarios.:
Publicar un comentario