EXPOSICION.
                                DEFINICION.

Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

*UTILIZACION*

Si tenemos un vector ya definido con los siguientes datos:

["aarona","aashta","abelarda","abelia","abigail","abril"] , todos de

tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:

public class BSecuencial {

public static void main(String[] args) throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aash

vSe utiliza cuando algún elemento no está ordenado o no puede ser ordenado previamente.

v Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final.

v La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo .

*VENTAJAS Y DESVENTAJAS*

 

v DESVENTAJA.- en un vector de N posiciones este algoritmo va a buscar posición a posición hasta dar con el dato solicitado y en el caso de que no exista pues también va a recorrer todo el arreglo.

v VENTAJA.- Lo bueno de este tipo de búsqueda es que es muy sencillo de implementar.

 

******EJEMPLO********

 

Si tenemos un vector ya definido con los siguientes datos:

["aarona","aashta","abelarda","abelia","abigail","abril"] , todos de

tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:

public class BSecuencial {

public static void main(String[] args) throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar
 

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

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}

if(encontrados == 1 ){System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{System.out.println("Fin de busqueda, encontrados "+encontrados+" elementos iguales");
}
}
}

BURBUJA.
Este método puede trabajar de dos maneras diferentes. Llevando los elementos mas pequeños hacia la parte izquierda del arreglo o bien llevando los elementos mas grandes hacia la parte derecha del mismo.
La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre si hasta que todos se encuentren ordenados. Se realizan (n-1)pasadas, transportando en cada una de las mismas el menor o mayor elemento a su pocision ideal. Al final de las (n-1)pasadas los elementos del arreglo estarán ordenados.




ORDENACIÓN POR INSERCIÓN DIRECTA.
Es el que generalmente utilizan los jugadores de cartas cuando ordenan estas, de ahí que también se le conoce con el nombre del método de la baraja.
La idea central de este algoritmo consiste en insetar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada. Este proceso este proceso se repite desde el segundo hasta el n-esimo elemento.




ORDENACIÓN POR EL MÉTODO SHELL.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así, los elementos quedaran ordenados en el arreglo mas rápidamente.


ANÁLISIS DE EFICIENCIA DEL MÉTODO SHELL.
No se ha podido establecer hasta el momento la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario correr el algoritmo para analizar el tiempo de ejecución.

                               

ORDENACIÓN POR EL MÉTODO QUICKSORT.
La idea central de este algoritmo consiste en lo siguiente:
1-. Se toma un elemento x de  una pocision cualquiera de un arreglo.
2-. Se trata de ubicar a X en  la pocision correcta del arreglo, de tal forma que todos elementos que se encuentren  a su izquierda sean menor o iguales a X y todos los elementos que se encuentren a su derecha sean mayor o iguales.
3-. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la pocision correcta de X en el arreglo.
4-. El proceso termina cuando todos los elementos se encuentran en su pocision correcta en el arreglo.

GRAFOS.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarios entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Tipos de grafos.

Existen dos tipos de grafos los no dirigidos y los dirigidos.

• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

                                                   grafo dirigido

grafo no dirigido                                            

Un árbol se puede definir como una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, antecesor, sucesor, ancestro etc.

Formalmente se define un árbol de tipo T como una estructura homogenea resultado de concatenación de un elemento de tipo T con un numero finito de arboles

disjuntos, llamados subárboles. Una forma particular de un árbol es el árbol vació.

APLICACIONES.

Los arboles se pueden aplicar para la solución de una gran cantidad de problemas. Se pueden utilizar para representar formulas matemáticas, para registrar la historia de un campeonato de tenis,para construir un árbol genealógico etc.

                            

PROPIEDADES.

Todos los nodos son descendientes directos hijos de un mismo nodo padre, son hermanos.

• Todo nodo que no tiene ramificaciones hijo se conoce con el nombre de terminal u hoja.
• Grado. Numero de descendientes directos de un determinado nodo.
• Grado de árbol. Es el max grado de todos los nodos del árbol.
• Nivel. Es el numero de arcos que pueden ser recurridos para llegar a un determinado nodo.

LONGITUD DE CAMINO INTERNO.

Es la suma de longitudes de camino de todos los nodos de el árbol.

i= nivel del árbol.

h=altura

ni=numero de nodos en el nivel.

LCI= 1*1+2*2+3*4+4*4=33.

LONGITUD DE CAMINO EXTERNO.

X árbol extendido: Es aquel en el que el numero de hijos de cada nodo es igual al grado del árbol de no cumplir con estas características se deben incorporar nodos especiales.

Nodo especiales: reemplazan las ramas vacías o nulas.

LCE: es la suma de tos los nodos especiales.

 Árboles binarios.

Los árboles de grado 2 tienen una especial importancia. Se les conoce con el nombre de árboles binarios. Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formado por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz.
En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.

Ejemplo:

Operaciones básicas.- Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol.Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, orden central y postorden.
Preorden: Raíz, subárbol izquierdo y subárbol derecho.
Orden central: Subárbol izquierdo, raíz, subárbol derecho.
Postorden: Subárbol izquierdo, subárbol derecho, raíz.

Ejemplo:
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20
Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa

Estructura de datos
Variables
Las variables son estructura de datos usados para almacenar información. Hay dos tipos de información que puede ser almacenada: Números y texto. Antes de usar una variable ésta, deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String

 Transformación de un Árbol Gral. en un Árbol Binario.

---

1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos.
3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente.

BOSQUE.

Rpresentacion de un conjunto normalmente ordenado de uno o mas arboles generales.



PILA.

Una pila representa una estructura lineal de datos en la que se puede agregar o quitar elementos únicamente por uno de los extremos. En consecuencia, los elementos de una pila se eliminan en orden inverso al que se insertaron; es decir, el ultimo elemento que se mete a la pila es el primero que se saca. Debido a esta característica, se le conoce como estructura LIFO, (el ultimo en entrar es el primero en salir).

Existen numerosos casos prácticos en los que se utiliza el concepto de pila; por ejemplo, una pila de platos, una pila de latas, una pila de libros etc.

Una pila se define formalmente como una colección de datos a los cuáles se puede acceder mediante un extremo, que se conoce generalmente como tope.

OPERACIONES CON PILAS.

La definición de una estructura de datos queda completa al incluir las operaciones que se pueden realizar en ella. Para el caso de las pilas, las operaciones básicas que se pueden llevar a cabo son:

• Insertar un elemento---push---en la pila.
• Eliminar un elemento---pop---en la pila.

Y las operaciones auxiliares:

• pila_vacía.
• pila_llena.

 Pila_vacía (PILA, TOPE, BAND)

{Este algoritmo verifica si una estructura tipo pila esta vacía, asignando a BAND el valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional. TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo booleano}

1. si (TOPE=0) {verifica si no hay elementos almacenados en la pila}

 entonces

                Hacer BAND--verdadero {la pila esta vacía}

si no

               Hacer BAND--falso {la pila no esta llena}

     2. { fin del condicional del paso 1} 

  

pila_llena (PILA, TOPE, MAX, BAND)

{ Este algoritmo verifica si una estructura tipo pila esta llena, asignando a BAND el valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional de MAX elementos. TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo booleano}

1. si (TOPE=MAX)

         entonces

                     Hacer BAND----verdadero {la pila esta llena}

          si no

                  Hacer BAND---falso{la pila no esta llena}

2. {fin del condicional del paso 1}

Llamada a Subprogramas.

Cuando se tiene un programa que llama a subprograma, también conocido como modulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como las instrucciones pendientes de ejecución del subprograma, los valorea almacenados en la pila se recuperan  para continuar con la ejecución del programa en el punto en el cual fue interrumpido.  Además de las variables se recupera la dirección del programa en la que se hizo la llamada, por que a esa pocisión se regresa el control del proceso.

 

RECURSIVIDAD.

La recursion es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante recordad que no todos los problemas son naturales recursivos; algunos si lo son y otros no.

La recursion se puede presentar de dos maneras diferentes:

a)  Directa: el programa o subprograma se llama directamente así mismo.

b) Indirecta: el subprograma llama a otro subprograma y este en algún momento, llama nuevamente a primero.

TRATAMIENTO DE EXPRESIONES ARITMÉTICAS.

Un problema interesante en computación consiste en convertir expresiones en notación infija a su equivalente en notación prefija o postfija o prefija.

* Dada la expresión A+B se dice que esta se encuentra en notación infija, porque el operador (+) se encuentra entre dos operadores ( A y B).

* Dada la expresión AB+ se dice que esta se encuentra en notación postfija, porque el operador (+) se encuentra después de los operadores (A y B).

* Dada la expresión +AB se dice que esta se encuentra en notación prefija, porque el operador (+) esta precediendo a los dos operandos.

ORDENACIÓN.

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica.

PROGRAMA PILA ESTÁTICA.

Import java. util.scanner;

public classs pilaestatica{

public static void main (string argss []){

   int dato;

   int pila []= new int [5];

scanner captura= new scanner (system.in);

for (int tope=0; tope<4; tope++) 

{

system.out.print\n (proporciones de datos para pila);

dato=captura.next\n+();

pila[tope]=dato;

}

for (int tope=4; tope>4; tope-) 

system.out.print\n (la pila tiene los siguientes datos¨+ pila

[tope]);

}

}

LISTAS.
Es un tipo de estructura lineal y dinámica de datos. Lineal porque a cada elemento le puede seguir solo otro elemento;  dinámica porque se puede manejar la memoria de manera flexible, sin necesidad de reserva de espacio con antelación.
La principal ventaja de manejar un tipo dinámico de datos es que se pueden adquirir posiciones de memoria a medida que se necesitan; estas se liberan cuando ya no se requieren.

• LISTAS LIGADAS.

Son colecciones de elementos llamdos nodos; el orden entr estos se establece por medio de un tipo de datos denominado punteros, apuntadores, direcciones o referencias a otros nodos.
En general un noda consta de dos partes:

• Un campo de INFORMACION que sera del tipo de datos que se quieran almacenar en la lista.
• Un campo LIGA, de tipo puntero que se utiliza para establecer la liga o enlace con otro nodo de la lista. Si el nodo fuera el ultimo de la lista, esta campo tendra como valor NIL-vacio-. Al emplearse el campo liga para relacionar dos nodos, no sera necesario almacenar fisicamente a los nodos en espacios contiguos.

Las operaciones que pueden efectuarse en una lista simplemente ligada son:

• Recorrido de la lista: Consiste en visitar cada uno de los nodos que forman la lista.
• Inserccion de un elemento: Consiste en agregar un nuevo nodo a la lista.
• Borrado de un elemento: Consiste en eliminar un nodo de la lista y liberar espacio de la memoria correspondiente.
• Busqueda de un elemento:  Se debe ir recorriendo los nodos hasta encontrar el que estemos buscando o hasta que llegue al final de la lista.

LISTAS CICULARES.

Tiene la caracterstica de que el ultimo elemento de la lista apunta al primero, en lugar de apuntar al vacio o NIL.
Se define una lista simplemente ligada circular como una coleccion de elementos llamados nodos en la cual el ultimo nodo apunta al primero.
La operacion de recorrido de listas circulares se necesita considerar algun criterio para detectar cuando se han visitado todos los nodos de la lista.
Este ultimo con el proposito de evitar caer en ciclos infinitos. Una posible solucion al problema planteado consiste en usar un nodo extra llamado nodo de cabecera, para indicar el inicio de la lista. Este nodo contendra informacion especial de tal manera que se distinga de los demas y asi podra hacer referencia al pricipio de la lista.

LISTAS DOBLEMENTE LIGADAS. 

Es una coleccion de nodos, en la cual cada uno de ellos tiene dos apuntadores, uno apuntando a su predecesor (LIGAIZQ) y otra a su sucesor (LIGADER). Por medio de estos punteros se podra entonces avanzar o retroceder a traves de la lista, segun se tomen las direcciones de uno u otro

apuntador.

Las operaciones que se pueden llevar a cabo con este tipo de estructuras son las mismas que con listas simplemente ligadas. En esta seccion se presentaran las operaciones de:

• Recorrido de la lista: Al tener cada nodo  una doble liga, la lista se puede recorrer tanto del inicio al final, mediante la ligas derechas, com en sentido inverso; es decir del final al principio, con las ligas izquierdas.
• Inserccion de un elemento: Agrgar un nuevo nodo a la lista y establecer los apuntadores correspondientes.
• Borrado de un elemento: Eliminar un elemento de la lista, redefiniendo los apuntadores correspondientes y liberando el espacio de memoria ocupado por el nodo.

 

Listas Enlazadas