Estructuras y Organización de Datos Ver 2.0

Estructuras y Organización de Datos Ingeniería en Tecnologías de la Información y Comunicaciones

Objetivo general del curso:

Aplicar estructuras de datos en la elaboración de programas.

Utilizar listas enlazadas para la solución de problemas computacionales.

Manipular diversos tipos de árboles para clasificar datos.

Comparar los diversos algoritmos de ordenamiento.

Comparar los diversos algoritmos de búsqueda.

Aplicar la recursividad como estrategia de solución de problemas.

Analizar las estrategias de recuperación de información perdida o dañada en dispositivos de almacenamiento secundario.

Esta asignatura aporta al perfil del Ingeniero en Tecnología de la Información y Comunicaciones las siguientes competencias:

Conocimiento y manejo de tecnologías y herramientas actuales y emergentes acordes a las necesidades del entorno.

Concientizarlo de la importancia de la estructuras de datos, para implementarlas en el desarrollo de sistemas de información utilizando una metodología basada en la programación de componentes e implementando tecnología web.

Identificar las especificaciones, aplicaciones e implementaciones de las principales estructuras de datos.

Implementar eficientemente las principales estructuras de datos.

Utilizar correctamente las estructuras de datos adecuadas para resolver distintos problemas.

Competencias previas

Aplicar algoritmos computacionales.

Aplicar técnicas de modelado para la solución de problemas.

Aplicar la sintaxis de un lenguaje orientado a objetos.

Aplicar un lenguaje orientado a objetos para la solución de problemas.

Utilizar el modelado de objetos.

Crear programas en algún lenguaje computacional.

Competencias a desarrollar

Competencias específicas:

Aplicar las estructuras de datos en la elaboración de programas.

Utilizar listas enlazadas para la solución de problemas computacionales.

Manipular diversos tipos de árboles para clasificar datos.

Comparar los diversos algoritmos de ordenamiento.

Comparar los diversos algoritmos de búsqueda.

Aplicar la recursividad como estrategia de solución de problemas.

Analizar las estrategias de recuperación de información perdida o dañada en dispositivos de almacenamiento secundario

Retícula Ingeniería en Tecnologías de la Información y Comunicaciones ITIC-2010-225.pdf

Reticula%20%20Ingeniería%20en%20Tecnologias%20de%20la%20Informacion%20y%20Comunicaciones%20ITIC-2010-225.pdf

Temario:

1. Fundamentos de estructura de datos

1.1. Definición. 1.2. Clasificación. 1.3. Estructuras lineales y no lineales. 1.4. Estructuras dinámicas y estáticas.

2. Estructuras lineales

2.1. Pilas estáticas y dinámicas. 2.2. Colas estáticas y dinámicas. 2.3. Aplicaciones

3. Estructuras no lineales

3.1. Recursividad. 3.2. Árboles. 3.3. Grafos.

4. Métodos de ordenamiento y búsqueda

4.1. Algoritmos de ordenamiento. 4.2. Métodos de búsqueda. 4.3. Recuperación de datos.

Unidades de aprendizaje del curso y su respectiva bibliografía.

Unidad 1: Fundamentos de estructuras de datos

Competencia específica a desarrollar Actividades de Aprendizaje

Identificar los conceptos básicos de las estructuras de datos. Identificar las diferentes estructuras de datos, respecto a su implementación.

Investigar los conceptos fundamentales de las estructuras de datos.

Identificar las estructuras de datos lineales y no lineales de acuerdo al problema a resolver.

Identificar las estructuras de datos estáticas y dinámicas de acuerdo al problema a resolver.

Unidad 2: Estructuras lineales


Aplicar las principales estructuras de datos lineales.

Elaborar mapas conceptuales para comprender los conceptos básicos, el funcionamiento y las aplicaciones que tienen las estructuras de datos lineales.

Realizar ejercicios implementando estructuras de datos lineales.

Unidad 3: Estructuras no lineales


Aplicar las principales estructuras de datos no lineales.

Elaborar mapas conceptuales para comprender los conceptos básicos, el funcionamiento y las aplicaciones que tienen las estructuras de datos no lineales.

Realizar ejercicios de conversión de soluciones recursivas a soluciones iterativas y viceversa.

Realizar ejercicios implementando estructuras de datos no lineales.

Unidad 4: Métodos de ordenamiento y búsqueda


Clasificar técnicas para recuperación de información en dispositivos de almacenamiento primario y secundario. Gestionar datos de forma óptima, para facilitar su procesamiento y la toma de decisiones.

Discutir el uso de los métodos de ordenamiento, búsqueda y recuperación de datos en memoria principal y secundaria.

Investigar los diversos algoritmos de los métodos de ordenamiento, búsqueda y recuperación de datos según el tipo de problema que se desea resolver.

Elaborar un mapa conceptual que visualice las diferencias entre los métodos en cuestión.

Aplicar los algoritmos investigados en dos lenguajes orientados a objeto y anotar observaciones.

Elaborar una aplicación informática donde se implementen archivos y aplicar métodos de ordenamiento, búsqueda y recuperación de datos en memoria principal y secundaria.

Bibliografía

1. Joyanes Aguilar, Luis. Estructura de Datos en Java. Primera edición. Ed. McGraw Hill. 2007. 2. Lewis, John. Estructura de Datos con JAVA: Diseño de estructuras y algoritmos. Primera

edición. Ed. Pearson. 2007. 3. Guardati Buemo, Silvia. Estructura de Datos orientada a objetos: Algoritmos con C++. Primera

edición. Ed. Pearson. 2007. 4. Allen, Marc. Estructura de Datos con JAVA: Compatible con JAVA 2. Ed. Prentice Hall. 5. Cairo, Osvaldo. Estructura de Datos. Tercera edición. Ed. McGraw Hill; 2006.

Estrategias didácticas a seguir.

Exámenes 60%

Productos de Aprendizaje 40%

Puntos Extra por otras actividades

Los criterios de evaluación y acreditación respectiva.

Fechas de Exámenes

Examen Fecha Unidades Productos de

Aprendizaje

1er Viernes 6 de Septiembre I 6

2º. Viernes 11 de Octubre II 16

3er Viernes 8 de Noviembre III 5

4º. Jueves 5 de Diciembre IV 3

2ª Oportunidad 9 de Diciembre

Calificación Final 17 de Diciembre

Otras Observaciones:

Personificador

Hora de entrada

Asistencia a clase

Examenenes

Revisión equitativa

Calendarización del trabajo semestral.

En cada unidad se desarrollaran prácticas que involucren la resolución de problemas utilizando lenguajes de programación orientados a objetos de los temas vistos en clase.

Arturo López Ponce

Crear una cuenta en y seguir a los siguientes contactos: Tecnológico de Aguascalientes: @TecAgs Directora del ITA: @Director_ita Jefatura de Sistemas: @ArturoLP

1ª. Oportunidad

2ª. Oportunidad

1. Fundamentos de estructura de datos En la práctica, la mayor parte de información útil no aparece aislada en forma de datos simples, sino que lo hace de forma organizada y estructurada. Los datos de los diccionarios o enciclopedias son colecciones de datos y serian inútiles si no estuvieran organizadas de acuerdo con unas determinadas reglas. Además bajo esta estructura de organización la información supone ventajas adicionales al facilitar el acceso y el manejo de datos. Como tendremos ocasión de ver, la selección de una estructura de datos frente a otra, a la hora de programar es una decisión importante, ya que ellos influyen decisivamente en el algoritmo que se vaya a utilizar para la resolución del problema.

Programación = Estructura de Datos + Algoritmos 1.1. Definición. En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Bit Acrónimo de Binary digit. (dígito binario). Un bit es un dígito del sistema de

numeración binario (0, 1). Byte Unidad básica de almacenamiento de información, equivale a ocho bits

(octeto).

Nombre Abrev. Factor Tamaño

Kilo K 210 = 1024 103 = 1000

Mega M 220 = 1 048 576 106 = 1 000 000

Giga G 230 = 1 073 741 824 109 = 1 000 000 000

Tera T 240 = 1 099 511 627 776 1012 = 1 000 000 000 000

Peta P 250 = 1 125 899 906 842 624 1015 = 1 000 000 000 000 000

Exa E 260 = 1 152 921 504 606 846 976 1018 = 1 000 000 000 000 000 000

Zetta Z 270 = 1 180 591 620 717 411 303 424 1021 = 1 000 000 000 000 000 000 000

Yotta Y 280 = 1 208 925 819 614 629 174 706 176 1024 = 1 000 000 000 000 000 000 000 000

Bronto B 290 = 1 237 940 039 285 380 274 899 124 224 1027 = 1 000 000 000 000 000 000 000 000 000

Geop Ge 2100 = 1 267 650 600 228 229 401 496 703 205 376 1030 = 1 000 000 000 000 000 000 000 000 000 000

Carácter Cualquier signo tipográfico. Puede ser una letra, un número, un signo de

puntuación o un espacio.

Palabra En el contexto de la informática, una palabra es una cadena finita de bits que son manejados como un conjunto por la máquina. Las computadoras modernas normalmente tienen un tamaño de palabra de 16, 32 ó 64 bits. Muchos otros tamaños se han utilizado en el pasado, como 8, 9, 12, 18, 24, 36, 39, 40, 48 y 60 bits. Algunas de las primeras computadoras utilizaron una longitud de palabra del tipo decimales en vez de binarios, típicamente teniendo un tamaño de palabra de 10 ó 12 dígitos decimales y algunas otras computadoras no tenían una longitud de palabra fija.

1.2. Clasificación.

1.3. Estructuras lineales y no lineales. Estructura de datos lineales, los datos o elementos se almacenan en posiciones de memoria consecutivas. Por ejemplo los Arreglos y las Listas. Estructura de datos no lineales, los datos o elementos no se almacenan en posiciones de memoria consecutivas. Por ejemplo los árboles y grafos; y se pueden representar estructuras jerárquicas, direcciones o etiquetas de una manera organizada.

Simple

Estructurados

o Complejos

Predefinidos

Definidos por

el usuario

String StringBuffer

Arreglos Registros Listas Conjuntos Árboles Grafos Archivos

Estructura de Datos

Ordinal

No Ordinal

Enteros Carácter Lógicos

Enumerados

Subrango

Reales Cronológicos Apuntador, punteros o referencias

float double

Cadenas

Arrays ArrayList Vector

byte short int long char boolean

LinkedList

File

JTree

Abstractos abstract class

Tipo de datos en Java

Tipo Tamaño en bits Rango de valores

boolean 1 true o false Nota: El No. de bits puede variar según la

plataforma

char 16 ‘\u0000’ hasta ‘\uFFFF' Conjunto Unicode de ISO

byte 8 -128 a +127 -27 a 27 – 1

short 16 -32,768 a +32,767

-215 a 215 – 1

int 32 -2,147,483,648 a +2,147,483,647

-231 a 231 – 1

long 64 -9,223,372,036,854,775,808 a +9,223,372,036,854,775,807

-263 a 263 – 1

float 32

Rango negativo: -3.4028234663852886E+38 hasta -1.40129846432481707E-45

Rango positivo: 1.40129846432481707E-45 hasta 3.4028234663852886E+38

double 64

Rango negativo: -1.797693134862157E308 hasta -4.94065645841246544E324

Rango positivo: 4.94065645841246544E324 hasta 1.797693134862157E308

Tokens elementos léxico de los programas Existen 5 clase de tokens: identificadores, palabras reservadas, literales, operadores y otros. Identificadores Los identificadores pueden representar variables, constantes, métodos, nombres de archivos, etc. Diagrama de contexto de los identificadores:

Regla para formar un identificador:

1. Debe comenzar por una letra 2. Después de la 1er. Letra puede contener letras, dígitos o guion de piso 3. No están permitidos los espacios en blanco 4. No deben formar palabras reservadas 5. Java es sensibles a las mayúsculas y minúsculas 6. En Java la longitud de los identificadores no tiene límite.

Arreglos

Una de las características de Java es que los temas complejos como punteros o apuntadores lo hacen de una forma sencilla. Las referencias no son más que apuntadores, pero manejados de una forma simplificada. Los arreglos son referencia o apuntadores. Definición. - Un arreglo (vector o tabla) es una secuencia de objetos del mismo tipo. A

los objetos se les llama elementos del arreglo y se enumeran del 0 al n-1, además se almacenan linealmente en posiciones de memoria consecutivas.

Unidimensionales. Los corchetes pueden colocarse de dos formas:

o Los corchetes colocados después del tipo de dato, esto indica que todos los identificadores son arreglos.

o Los corchetes colocados después del identificador, indica que solo el

identificador que tenga los corchetes es un arreglo. Ejemplo: int enteros[], x, y; enteros en un arreglos de tipo int, x y y son variables

tipo int. float [] cal1, cal2, cal3, prom; cal1, cal2, cal3 y prom son arreglos

unidimensionales.

Tipo [ ] identificador

,

;

Tipo identificador [ ]

,

;

char [] letra1, letra2[], letra3; letra1 y letra3 son arreglos de una dimensión del tipo char y letra2 es una arreglo de arreglos de tipo char (una matriz).

Esto solo está declarando el nombre del arreglo y el tipo de datos que se van a almacenar en él (referencia), para declarar el número de elementos del arreglo se hace por medio del operador new. Ejemplo:

float [] CalificacionFinal; CalificacionFinal = new float [45];

La primera sentencia declara un arreglo CalificacionFinal que manejara tipos de datos float. La segunda sentencia declara que manejara 45 elementos (del 0 al 44). Otra forma de hacer la declaración del arreglo, así como de los elementos es:

float [] CalificacionFinal = new float [45]; Para almacenar datos en un arreglo basta con poner el nombre del arreglo, el subíndice, el símbolo igual y la expresión que se quiere almacenar y finalmente punto y coma. CalificacionFinal[5] = 70; System.out.println(“La Calificación Final 6 es: “ + CalificacionFinal[5]); Otra forma de introducir datos en un arreglos es inicializándolo desde la declaración. int enteros[] = {5, 4, 9 ,8, 7, 6, 2 , 1, 3, 0}; Tamaño de los arreglos (length) Java considera cada arreglo un objeto, debido a ello se pude conocer el número de elementos de un arreglo por medio del campo length.

Bidimensionales. Los arreglos vistos anteriormente se conocen como arreglos unidimensionales y se caracterizan por tener un solo subíndice. Los arreglos multidimensionales son aquellos que tienen más de una dimensión y, en consecuencia, más de un índice. Los arreglos más usuales son los de dos dimensiones, conocidos como matrices. Un arreglo de dos dimensiones equivale a una tabla con filas y columnas:

n 0 1 2 3

0

1

2

3

4

m

Declaración de arreglos bidimensionales (matriz) Ejemplo:

Tipo [ ] [ ] identificador

,

;

Tipo identificador [ ] [ ]

,

;

int puestos[ ][ ], x, y; puestos en un arreglos de dos dimensiones del tipo int, x y y son variables tipo int.

float [ ][ ] cal1, cal2, cal3, prom; cal1, cal2, cal3 y prom son arreglos bidimensionales.

Como ya se mencionó estas declaraciones son simplemente referencias, para declarar el número de elementos del arreglo se hace por medio del operador new. Ejemplo:

float [ ][ ] Calificaciones; Calificaciones = new float [45][4];

La primera sentencia declara un arreglo Calificaciones que manejara tipos de datos float. La segunda sentencia declara que manejara 45 filas (del 0 al 44) y 4 columnas (del 0 al 3). Otra forma de hacer la declaración del arreglo, así como de los elementos es:

float [ ][ ] Calificaciones = new float [45][3]; Inicialización de arreglos multidimensionales Al igual que los arreglos unidimensionales, los arreglos multidimensionales se pueden inicializar desde la declaración. Ejemplo:

int tabla1[ ][ ] = { {51, 24, 33}, {32, 23, 45} }; Se define una matriz de 2 filas por 3 columnas También se puede utilizar otros formatos como los siguientes: int tabla1[ ][ ] = { {51, 24, 33}, {32, 23, 45} } int tabla1[ ][ ] = { {51, 24, 33}, {32, 23, 45} }; int tabla2[ ][ ] = { { 1, 2, 3, 4}, { 5, 6, 7, 8}, { 9, 10, 11, 12} }; Java trata los arreglos de dos o más dimensiones como un arreglo de arreglos, por tanto puede crear arreglos no proporcionales. Por ejemplo:

a) double datos[ ][ ] = { {1.5, -2.5}, {5.0, 0.0, 1.5} }; Se ha creado un arreglo con dos filas, la 1ª con dos columnas y la 2ª con 3.

tabla1[ ][ ]

0 1 2

0 51 24 33

1 32 23 45

tabla2[ ][ ]

0 1 2 3

0 1 2 3 4

1 5 6 7 8

2 9 10 11 12

b) int [ ] a = { 1, 3, 5 }, b = { 2, 4, 6, 8, 10 }; int z[ ][ ] = { a, b };

Primero se definió el arreglo a con 3 elementos y después el arreglos b con 5 elementos, posteriormente se define la matriz z con dos filas, la primera con 3 elementos (los del arreglo a) y la segunda con 5 elementos (los del arreglo b). Método length con los arreglos bidimensionales Para saber la longitud de la última dimensión se debe especificar los subíndices de los subíndices precedentes, por ejemplo para una matriz:

Acceso a los elementos del arreglo bidimensional Por ejemplo si tenemos el siguiente matriz:

int [ ][ ] a = new int [3][4];

a Columna 0 Columna 1 Columna 2 Columna 3

Fila 0 a[0][0] a[0][1] a[0][2] a[0][3]

Fila 1 a[1][0] a[1][1] a[1][2] a[1][3]

Fila 2 a[2][0] a[2][1] a[2][2] a[2][3]

Índice de la columna Índice de la fila Nombre del arreglo

Para almacenar datos en una matriz basta con poner el nombre del arreglo, el subíndice de las filas y el subíndice de las columnas, el símbolo igual y la expresión que se quiere almacenar y finalmente después punto y coma. Por ejemplo:

a[1][3] = Expresión; Multidimensionales. Java proporciona la probabilidad de almacenar varias dimensiones, aunque raramente los problemas del mundo real se manejan más tres dimensiones, esto porque para los seres humanos es difícil representar gráficamente arreglos con más de tres dimensiones. Para representar un arreglo de tres dimensiones lo haremos por medio de un cubo. int cubo [ ][ ][ ] = new int [4][5][3];

3

4

y

z

x

5 Almacenar datos en el arreglo multidimensional: Al igual que en los anteriores arreglos, se deben poner los subíndices al cual se quiere acceder y posteriormente la expresión a asignar. cubo[2][3][1] = 15; Objetos que permiten E/S por consola. En Java, la entrada y salida se lee y escribe en flujos (streams). La fuente básica de entrada de datos es el teclado y la fuente de salida es pantalla. La clase System define dos referencias a objetos static para la gestión de entrada (in) y salida (out). Salida (System.out) El objeto out definida en la clase System está asociado con el

flujo de salida, que dirige los datos a consola y permite visualizarlos en pantalla, por ejemplo:

System.out.println(“Esta es una cadena”); Se visualizará en pantalla: Esta es una cadena.

Descripción del método print: void print(cadena) Despliega una cadena en pantalla. void println(cadena) Despliega una cadena en pantalla y al final un carácter de nueva

línea (‘\n’).

Con estos métodos se puede escribir cualquier cadena o dato de los tipos primitivos, como por ejemplo:

System.out.println( "Valores de las Variables: \n" + "a=" + a +"\n" + "b=" + b +"\n" + "x=" + x +"\n" + "y=" + y );

Entrada (System.in) Por medio de un objeto Scanner se puede leer datos desde un programa, esta clase pertenece al paquete java.util y debe ser importada. Para poder utilizarlo instancie un objeto de la siguiente forma:

Sacanner identificador = new Scanner (System.in); Esta expresión crea un objeto Scanner y determina que leerá los datos desde teclado mediante los siguientes métodos:

identificador.nextBoolean() Para Booleanos identificador.nextByte() Para números Enteros tipo byte identificador.nextShort() Para números Enteros tipo short identificador.nextInt() Para números Enteros tipo int identificador.nextLong() Para números Enteros tipo long identificador.nextFloat() Para números flotantes identificador.nextDouble() Para números doubles identificador.next() Para el siguiente token identificador.nextLine() Para una línea

El siguiente ejemplo lee dos números enteros desde Windows, los suma y muestra el resultado en una ventana.

Al convertir datos tipo String a tipo int (con Integer.parseInt()) manda una excepción de formato de numero si ocurre un error.

El método showMessageDialog de la clase JOptionPane tiene varias formas de enviarles parámetros: public static void showMessageDialog(Component componentePadre, Object Mensaje)

Dónde: componentePadre Determina la ventana en que se desplegara el

mensaje, si es null, se despliega en la ventana por defecto.

Mensaje Objeto a desplegar

public static void showMessageDialog(Component componentePadre, Object Mensaje, String Titulo, int TipodeMensaje) Dónde:

componentePadre Determina la ventana en que se desplegara el mensaje, si es null, se despliega en la ventana por defecto.

Mensaje Objeto a desplegar Titulo Cadena de characters de la caja de dialogo TipodeMensaje Valor entero que determina que imagen se despliega

según la siguiente tabla:

Tipo de cuadro de diálogo de mensaje Icono Descripción

JOptionPane.ERROR_MESSAGE

Ventana de Error

JOptionPane.INFORMATION_MESSAGE

Ventana Informativa

JOptionPane.WARNING_MESSAGE

Ventana de Advertencia

JOptionPane.QUESTION_MESSAGE

Ventana de introducción de datos o selección de alguna

alternativa

JOptionPane.PLAIN_MESSAGE Sin Icono Ventana estándar

Clase Math La Clase Math proporciona una gran variedad de métodos matemáticos al igual que algunas constantes útiles.

Campos Descripción

final static double E Constante e: 2.7182818284590452354

final static double PI Constante pi: 3.14159265358979323846

Métodos Descripción

static double abs(double d) static float abs(float f) static long abs(long l) static int abs(int i)

Regresa el valor absoluto especificado.

static double acos(double d) Regresa el inverso del coseno del ángulo especificado en radianes.

static double asin(double d) Regresa el inverso del seno del ángulo especificado en radianes.

static double atan(double d) Regresa el inverso de la tangente del número especificado.

static double atan2(double d1, double d2) Regresa el ángulo definido por las coordenadas rectangulares (d1, d2)

static double ceil(double d)

Regresa el entero más pequeño, mayor o igual d. Ejemplo: Math.ceil(9.3) 10.0 Math.ceil(-9.3) -9.0

static double cos(double d) Regresa el coseno del ángulo especificado en radianes.

static double exp(double d)

Regresa ed. Ejemplo: Math.exp(1.0) 2.71828 Math.exp(2.0) 7.38906

static double floor(double d) Regresa el entero más grande, menor o igual a d. Ejemplo:


Math.floor(9.3) 9.0 Math.floor(-9.3) -10.0

static double log(double d)

Regresa el logaritmo natural de d (base e). Ejemplo: Math.log(Math.E) 1.0

static double max(double d1, double d2) static float max(float f1, float f2) static long max(long l1, long l2) static int max(int i1, int i2)

Regresa el valor más grande. Ejemplo: Math.max(2.3,12.7) 12.7 Math.max(-2.3,-12.7) -2.3

static double min(double d1, double d2) static float min(float f1, float f2) static long min(long l1, long l2) static int min(int i1, int i2)

Regresa el valor más pequeño. Ejemplo: Math.min(2.3,12.7) 2.3 Math.min(-2.3,-12.7) -12.7

static double pow(double base, double exp) throws AritmeticException

Regresa baseexp. Ejemplo: 52

static double random() static double random(int i)

Regresa un número aleatorio comprendido entre 0.0 y 1.0 o 0 e i -1. 0.0 <= Math.random() <= 1.0 o 0 <= Math.random(int i) <= i -1

El programa anterior genera 10 números aleatorios comprendidos entre 15 y 35.

Producto de Aprendizaje: 1.1 (15 puntos)

A. Investigar

1) Diferencias entre estructuras de datos lineales y no lineales 2) Representación gráfica de las estructuras lineales 3) Representación gráfica de las estructuras no lineales

B. Elabore un programa de los que se muestra a continuación: Vectores

1) Elabore un programa que declare y cargue un arreglo de 100 elementos de forma aleatoria (el rango de valores estará entre 100 a 999), imprima los números en 4 grupos de 25, calcule e imprime su media aritmética.

2) Elabore un programa que declare y cargue un arreglo de 100 elementos de forma aleatoria (el rango de valores estará entre 100 a 999), imprima los números en 4 grupos de 25 e imprima la mediana.

3) Elabore un programa que declare y cargue un arreglo de 100 elementos de forma aleatoria (el rango de valores estará entre 100 a 999), imprima los números en 4 grupos de 25 e imprima la moda.

C. Elabore un programa de los que se muestra a continuación: Matrices

1) Elabore un programa que declare y cargue en forma aleatoria una matriz de 5 por 5 (el rango de valore estará entre 10 y 30) y sume los elementos de la diagonal principal e imprima la matriz y el resultado.

2) Elabore un programa que declare y cargue en forma aleatoria una matriz de 5 por 5 (el rango de valore estará entre 50 y 70) y obtenga el producto de la diagonal invertida e imprima la matriz y el resultado.

3) Elabore un programa que declare y cargue en forma aleatoria una matriz de 5 por 5 (el rango de valore estará entre 70 y 90) e imprima los elementos que no se encuentran en la diagonal principal y a diagonal invertida.

Clases para la implementación de arreglos. La clase Vector es una estructura que nos permite almacenar una colección de objetos, pero a diferencia de los arreglos, la estructura va creciendo conforme se añaden elementos, y a su vez se reduce conforme se quitan elementos de la colección. Un Vector permite añadir elementos al comienzo, en medio o al final de dicha colección. Esta clase se encuentra en java.utils.Vector. Si se desea declarar un Vector es necesario hacer lo siguiente:

Vector elVector; elVector = new Vector( );

Vector elVector = new Vector( );

No es necesario especificar su tamaño ya que éste varía conforme se van agregando elementos. Un vector almacena objetos. No puede almacenar tipos de datos primitivos.


Vector() Crea un objeto Vector con capacidad de 10 elementos. Si el vector necesita crecer, lo hará al doble de su tamaño.

Vector(int capacidadInicial)

Crea un objeto Vector con la capacidadInicial especificada. Si el vector necesita crecer, lo hará al doble de su tamaño.

Vector(int capacidadInicial, int capacidadIncrementa)

Crea un objeto Vector con capacidadInicial y cuando el vector necesite crecer, lo hará en capacidadIncrementar.

void add(int index, Object o) Agrega el objeto o en la posición indicada por index. Recorre los elementos hacia la derecha.

add(Object o) Agrega el objeto o al final del vector.

int capacity() Regresa la capacidad actual del vector.

boolean contains(Object o) Regresa true si existe el objeto o dentro del vector, false de otra manera.

Object elementAt(int index) Regresa el objeto contenido en la posición indicada por index.


Object get(int index) Regresa el objeto contenido en la posición indicada por index.

int indexOf(Object elem)

Busca la primer ocurrencia del objeto elem y devuelve su posición dentro del vector. Regresa –1 si el objeto no existe dentro de la lista.

void insertElementAt(Object o, int index) Inserta el objeto o en la posición indicada por index. Similar a la función add()

bolean isEmpty() Regresa true si el Vector está vacío y falso en caso contrario.

boolean remove(int index) Remueve el elemento ubicado en la posición indicada por index.

boolean remove(Object o) Remueve la primera ocurrencia del objeto o dentro del vector. Recorre los demás.

Object set(int index, Object o)

Remplaza el elemento ubicado en la posición index por el objeto o. Devuelve el elemento que anteriormente se encontraba en esa posición.

void setElementAt(Object o, int index) Remplaza el elemento ubicado en la posición index por el objeto o.

int size() Regresa el número de componentes ocupados del vector.

Object [] toArray() Regresa un arreglo conteniendo todos los elementos del vector en el mismo orden.

toString()

Regresa una representación en String del vector, conteniendo la representación en string de cada elemento del vector.

La clase Arrays proporciona métodos estáticos para manipular arreglos. Esta clase maneja arreglos a alto nivel, como los métodos: sort para ordenar arreglos, binarySearch para buscar en un arreglo ordenado, equals para comparar arreglos y fill guardar valores en todos los elementos de un arreglo.


static int binarySearch(char[ ] a, char bu) static int binarySearch(double[ ] a, double bus) static int binarySearch(float[ ] a, float bus) static int binarySearch(int[ ] a, int bus) static int binarySearch(Object[ ] a, Object bus)

Busca en el arreglo a el elemento bus y regresa la posición donde lo encontró, si regresa -1 es que no fue localizado. El arreglo debe estar ordenado.

static boolean equals(char[ ] a, char[ ] a2) static boolean equals(double[ ] a, double[ ] a2) static boolean equals(float[ ] a, float[ ] a2 static boolean equals(int[ ] a, int[ ] a2) static boolean equals(Objeto[ ] a, Object[ ] a2)

Regresa true si los dos arreglos son iguales uno a uno y false en caso contrario.

static void fill(boolean[ ] a, boolean val) static void fill(char[ ] a, char val) static void fill(double[ ] a, double val) static void fill(float[ ] a, float val) static void fill(int[ ] a, int val) static void fill(Object[ ] a, Object val)

A cada elemento del arreglo le asigna el val.

static void sort(char[ ] a) static void sort(double[ ] a) static void sort(float[ ] a) static void sort(int[ ] a) static void sort(Object[ ] a)

Ordena ascendentemente el arreglo especificado.

static void sort(char[ ] a, int inicio, int fin) static void sort(double[ ] a, int inicio, int fin) static void sort(float[ ] a, int inicio, int fin) static void sort(int[ ] a, int inicio, int fin) static void sort(Object[ ] a, int inicio, int fin)

Ordena ascendentemente de inicio a fin el arreglo especificado.


De los siguientes programas elabore uno del 1 al 3 y el número 4:

1. Elabore un método que reciba como parámetro un arreglo y un valor numérico y regrese la posición en donde se localiza ese elemento en el arreglo, si no lo encuentra regrese el valor -1. Los valores que puede recibir el método pueden ser int, long, float y double.

2. Elabore un programa que lea 10 nombres desde teclado y los inserte ordenadamente

en uno objeto tipo Vector. 3. Elabore un método que reciba como argumento un arreglo y un valor booleano, si el

valor booleano es true ordene el arreglo ascendente y si es false lo ordene descendente.

4. Elabore un programa que lea los nombres y tres calificaciones de los alumnos de la

materia Estructura y Organización de datos, por cada alumno calcule el promedio, así como también el promedio general de la materia e imprima en pantalla Nombre de Alumno, Calificación 1, Calificación 2, Calificación 3 y Promedio. Al final despliegue cuantos aprobaron, reprobaron y el promedio general.

1.4. Estructuras dinámicas y estáticas. Estructuras Estáticas Las estructura de datos estática, el espacio que va a ocupar está determinado en tiempo de compilación. Puede que ese espacio se ubique al principio de la ejecución (variables globales) o en la invocación a métodos o funciones (variables locales), pero en cualquier caso, no es responsabilidad del programador ocuparse de su gestión. Características de las estructuras estáticas:

Se reserva memoria en tiempo de compilación.

Su contenido puede cambiar durante la ejecución.

Su tamaño y forma no cambia durante la ejecución.

Posibles problemas:

o Sobre dimensionamiento ‘desperdicio’ de memoria o Infla dimensionamiento falta de memoria

Las estructuras de datos estáticas son principalmente los arreglos unidimensionales, matrices y arreglos multidimensionales. Estructuras Dinámicas Las estructura de datos dinámica, el espacio que ocupa en memoria puede variar durante la ejecución del programa, y no está determinado en tiempo de compilación.

Características de las estructura de datos dinámicos:

Su tamaño y forma es variable.

Se crean y se destruyen en tiempo de ejecución.

La estructura de datos se dimensiona de forma precisa.

La memoria se gestiona de manera más eficiente. Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos:

Lineales: listas enlazadas, pilas, colas

No lineales: árboles, grafos


A. Investigar

1) Diferencias entre las estructuras de datos estáticas y dinámicas 2) Ventajas y desventajas de las estructuras lineales 3) Ventajas y desventajas de las estructuras no lineales

2. Estructuras lineales

2.1. Pilas estáticas y dinámicas. Una pila (stack) es una colección ordenada de elementos en la cual se puede insertar elementos por un extremo y retirarlo por el mismo extremo; ese extremo se llama parte superior de la pila o cima de la pila. Cuando se dice que una pila esta ordenada, lo que se quiere decir es que hay un elemento al que se puede accesar primero (el que está en la cima de la pila, elemento F de la siguiente figura), el segundo elemento al cual se puede accesar es el que esta después de la cima de la pila (es el elemento E).

Si deseamos inserta un nuevo elemento a la pila (elemento G), la pila quedara como se muestra en la figura 2.

Ahora si deseamos retirar un elemento de la pila, se retirara el que está en la cima.

La pila sigue la filosofía LIFO (last-in, first-out) o UEPS (último en entrar, primero en salir). Las operaciones mas frecuentes en una pila son Insertar y Quitar. La operación Insertar (push) añade un elemento a la pila, colocándolo en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la cima de la pila. La pila se puede implementar mediante arreglos, en cuyo caso su dimensión o longitud es fija; otra forma de implementarla es mediante listas enlazadas, en cuyo caso se utiliza memoria dinámica y el límite es la memoria RAM de la computadora. Una pila puede estar vacía (no tiene elementos) o llena (en el caso de tener tamaño fijo y no caben más elementos en la pila). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error, debido a que esta operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila llena se producirá un error llamado desbordamiento (overflow). Para evitar estas situaciones se diseña funciones, que comprueben si la pila está llena o vacía.

Operaciones. Antes de poder utilizar una pila debemos estipulas que tipo de datos almacenara (int, float, char, etc).

Operaciones básicas Las operaciones básicas de una pila son:

Tamaño de la pila Número de elementos máximos que puede contener la pila.

Crear Pila Crear una pila vacía.

Inicializar la Pila Inicializar la pila en vacía.

Insertar (push) Poner un elemento en la pila.

Quitar (pop) Retirar un elemento en la pila.

Pila vacía (stackempty) Comprobar si la pila no está vacía.

Pila llena (stackfull) Comprobar si la pila está llena.

Limpiar pila (stackclear) Eliminar todo lo elementos de la pila.

Cima (stacktop) Obtener el elemento que está en la cima de la pila. Al utilizar un arreglo para contener los elementos de una pila hay que tener en cuenta que el tamaño de la pila no debe de exceder el número de elementos del arreglo, por lo que el método pilallena() es importante en el diseño. El método más común para introducir elementos en una pila nueva es definir el fondo de la pila en la posición -1, es decir, crear una pila vacía. Posteriormente se van introduciendo elementos en el arreglo, de modo que el primero se agregara en la posición 1, el siguiente en la posición 2 y así sucesivamente. Por tal motivo los algoritmos de Insertar (push) y Quitar (pop) se define como sigue: Insertar (push)

1. Verificar si la pila no está llena. 2. Incrementa en 1 el apuntador de la pila (cima). 3. Almacenar el elemento en la nueva posición del apuntador.

Quitar (pop)

1. Verificar si la pila no está vacía. 2. Leer el elemento que se encuentra en la cima de la pila. 3. Decremento en 1 el apuntador de la pila (cima).

Pila Vacía

elementoun menos lopor tieneP si falso

elementos tieneno P si verdadero().pilavaciaPila

Cima La operación P.cima() devuelve el valor del elemento en la cima de la pila P. Para hacer esta operación escribiremos: d=P.cima() Al ejecutar esta sentencia en realidad se hacen dos operaciones, primero se hace d=P.quitar(), luego un P.insertar(d), porque después de la operación cima, la pila P queda sin cambios. Supongamos ahora la expresión ((5+6)*4)/(17+9), una de las condiciones para que sea una expresión aritmética correcta en que tengas sus paréntesis balanceados, así que deseamos saber si el número de paréntesis que abres es el mismo número de paréntesis que cierran. Para resolver este problema usaremos el concepto de pila. La idea es simple. Vamos a leer cada elemento de la expresión, si se trata de un paréntesis que abre, entonces lo insertaremos en una pila; si se trata de un paréntesis que cierra, entonces sacamos un elemento de la pila. Al terminar de leer la expresión revisaremos si la pila está vacía, en cuyo caso habremos concluido que el número de paréntesis que abre es el mismo que el número de paréntesis que cierra y la expresión tiene paréntesis balanceados.

La representación en Java las operaciones de una pila Definir el tipo de dato de la pila Se debe seleccionar que tipo de dato va a manejar la pila. Por ejemplo char. Tamaño de la pila final static int MAX_ELEMENTOS = 100;

9 9 9 9 9 9 9

8 8 8 8 8 8 8

7 7 7 7 7 7 7

6 6 6 6 6 6 6

5 5 5 5 5 5 5

4 4 4 4 4 4 4

3 3 3 3 3 3 3

2 2 2 2 2 2 2

1 1 1 ( 1 1 1 1

0 0 ( 0 ( 0 ( 0 0 ( 0

-1 -1 -1 -1 -1 -1 -1

( (( ((5+6) ((5+6)*4) ((5+6)*4)/( ((5+6)*4)/(17+9)

Crear la pila TipoPila Pila = new TipoPila(); Inicializar la pila public void inicializapila() { cima = -1; } Función insertar (push) public void insertar(char d) { if (!pilallena()) elemento[++cima]= d; else System.out.println(“Pila llena”); }

Función quitar (pop) public char quitar() { if (!pilavacia()) return elemento[cima--]; else { System.out.println(“Pila llena”); return ' '; } }

Función pilavacia (stackempty)

public boolean pilavacia() { if (cima == -1) return true; else return false; }

Función pilallena (stacktop)

public boolean pilallena() { if (cima == (MAX_ELEMENTOS - 1)) return true; else return false; }

1 // Clase TipoPila

2 public class TipoPila {

3

4 final static int MAX_ELEMENTOS = 100;

5 private int error;

6 private int cima;

7 private char elemento[];

8 private char dato;

9

10 public TipoPila() {

11 error = 0;

12 cima = -1;

13 elemento = new char [MAX_ELEMENTOS];

14 }

15

16 public void insertar(char d) {

17 if (!pilallena())

18 elemento[++cima]= d;

19 else

20 error = 1;

21 }

22

23 public char quitar() {

24 if (!pilavacia())

25 return elemento[cima--];

26 else {

27 error = 2;

28 return ' ';

29 }

30 }

31

32 public boolean pilavacia() {

33 if (cima == -1)

34 return true;

35 else

36 return false;

37 }

38

39 public boolean pilallena() {

40 if (cima == (MAX_ELEMENTOS - 1))

41 return true;

42 else

43 return false;

44 }

45

46 public int muestraError() {

47 return error;

48 }

49 }

01 // Programa Ejemplo_Pila.java

02 import javax.swing.JOptionPane;

03

04 public class Ejemplo_Pila {

05 public static void main( String args[] ) {

06

07 String Expresion;

08 int i;

09 TipoPila Pila = new TipoPila();

10

11 Expresion = JOptionPane.showInputDialog

12 ("Teclear la expresion a validar:");

13 i=0;

14 while ((i < Expresion.length()) && (Pila.muestraError() == 0)) {

15 switch (Expresion.charAt(i)) {

16 case '(' : Pila.insertar(Expresion.charAt(i));

17 break;

18 case ')' : Pila.quitar();

19 break;

20 }

21 i++;

22 }

23

24 if ((!Pila.pilavacia()) && (Pila.muestraError() == 0))

25 mensaje(3);

26 Else

27 mensaje(Pila.muestraError());

28

29 System.exit( 0 );

30 }

31

32 public static void mensaje(int error) {

33 String Msg = "";

34 switch (error) {

35 case 0: Msg = "Paréntesis Equilibrados";

36 break;

37 case 1: Msg = "Pila llena";

38 break;

39 case 2: Msg = "Existen más paréntesis derechos que izquierdos";

40 break;

41 case 3: Msg = "Existen más paréntesis izquierdos que derechos";

42 break;

43 }

44 JOptionPane.showMessageDialog(null, Msg, "Resultado",

45 JOptionPane.PLAIN_MESSAGE );

46 }

47 }

Cambiemos un poco el problema anterior y supongamos que existen 3 tipos diferentes de delimitadores de ámbito, los cuales son paréntesis ( y ), los corchetes [ y ] y las llaves { y }. Con este cambio ahora se tiene que verificar que el ámbito que cierra sea del mismo tipo que el que abre. Por ejemplo evalúe:

])))[((/()]}[(*])[({ nlkjhcdcbayx

Producto de Aprendizaje 2.1:

Elabore un programa en Java que evalué una expresión con los 3 diferentes delimitadores de ámbito.

Notación infija, prefija y postfija Considere la siguiente expresión A + B, en la cual se puede observar dos operandos A y B, y un operador +.

BA

Operando

Operador

Operando

A este tipo de representación se le llama notación infija (o entre) y existen otras dos representaciones las cuales son: AB Notación prefija (o polaca en honor del Polaco

Jan Lukasiewicz) AB Notación postfija (o sufija) Los prefijos “in”, “pre” y “post” se refieren a la posición relativa del operador respecto a los operandos. En la notación infija el operador esta entre los operandos, mientras que en la notación prefija el operador precede a los operandos y finalmente la notación postfija el operador sucede a los operandos. Ahora consideremos la expresión A+B*C, primero debemos saber cuál es la prioridad de los operadores (+ y *), de antemano sabemos que la multiplicación (*) tiene la mayor prioridad, por tal motivo quedaran las notaciones de la siguiente forma:

infija prefija Postfija

A+B*C +A*BC ABC*+

La única regla que tiene que recordar durante la conversión es que primero se conviertan las operaciones que tienen los operadores con mayor prioridad y después considerarlo como un operador simple.

prefija A+[*BC] +A*BC

postfija A+[BC*] ABC*+

Antes de realizar conversión a alguna notación debemos establecer la prioridad de los operadores, considere la siguiente tabla y prioridad:

1º. ( ) Agrupación

2º. ^ Exponenciación

3ª. *, / Multiplicación y División

4ª. +, - Suma y Resta

infija prefija postfija

A+B-C

(A+B)*(C-D)

A^B*C-D+E/F/(G+H)

((A+B)*C-(D-E))^(F+G)

A-B/(C*D^E)

Evaluación de una expresión postfija Algoritmo para evaluar una expresión postfija:

Tipo de datos de la pila: int

Funciones:

void insertar(int d);

int quitar();

boolean pilavacia();

boolean pilallena();

boolean esoperador(char caracter);

int realizaoperacion(int op1, int op2,char caracter);

En estas funciones solo existen dos que no han sido definidas: boolean esoperador(char caracter) Regresa verdadero (true) si el

carácter es un operador (+, -, *, /, ^). int realizaoperacion(int op1, int op2, char caracter) Realiza la operación entre el

operador 1 (op1) y el operador 2 (op2) definida por el operando (carácter).

Algoritmo:

TipoPila Pila = new TipoPila();

Capturar la expresión a evaluar

while (mientras no lleguemos al final de la cadena a evaluar){

símbolo = siguiente carácter

if (Character.isDigit(símbolo)) {

Juntar los caracteres de los números en la variable dato

Pila.insertar(Integer.parseInt(dato));

}

else {

if (Pila.esoperador(símbolo)) {

op2 = Pila.quitar();

op1 = Pila.quitar();

valor = Pila.realizaoperacion(op1, op2, símbolo);

Pila.insertar(valor);

}

}

}

Desplegar el resultado Pila.quitar()

Suponga que se quiere evaluar la expresión: 6 2 3+-3 8 2/+*2^3+


Implemente el algoritmo de evaluación de una expresión postfija.

Conversión de una expresión infija a postfija Considere las expresiones siguientes:

CBA

CBA

*)(

*

Sus respectivas notaciones postfijas:

*

*

CAB

ABC

Al examinar la primera expresión el operando A se puede insertar directamente en la expresión postfija, pero el operador + no se puede insertar en su posición adecuada al examinar el operando B, el cual debe de ir directamente en la expresión postfija después del operando A. En este momento se puede recuperar el operador + pero no es correcto porque el operador * tiene mayor precedencia que el operador +. En el caso de la

segunda expresión debido al paréntesis indica que el operador + tiene mayor precedencia que el operador *. Dado que la prioridad desempeña un papel importante, se debe diseñar una función precedencia (op1, op2), donde op1 y op2 son caracteres que representan los operadores y debe de regresar un valor booleano que diga si el operador op1 tiene mayor precedencia que el operador op2. Ejemplo: precedencia(‘+’,’+’) Verdadero, porque el operador + que está a la izquierda, tiene

mayor precedencia que el operador + que está a la derecha. precedencia (‘+’,’*’) Falso, porque el operador + no tiene mayor precedencia que el

operador *. Algoritmo de conversión de una expresión infija a postfija (sin paréntesis): Tipo de datos de la pila: char

Funciones:

void insertar(char d);

char quitar();



boolean esoperador();

char cima();

boolean precedencia(char op1, char op2);

El método que falta de definir es: char cima() Regresa el elemento que se encuentra en la cima de la pila (quitar(),

insertar(char elemento)). Algoritmo:


Capturar la expresión infija

while (mientras no lleguemos al final de la expresión infija){


if (!Pila.esoperador(símbolo)

agregar el símbolo a la cadena postfija

else {

while (!Pila.pilavacia() &&

Pila.precedencia(Pila.cima(), símbolo)) {

elemento = Pila.quitar();

agregar el elemento a la cadena postfija

}

Pila.insertar(símbolo);

}

}

while (!Pila.pilavacia()) {



}

Desplegar la cadena postfija

Suponga que se quiere evaluar la expresión: A+B*C^D^E

Ahora debemos modificar el algoritmo para que acepte paréntesis, los cuales se deben tomar como operadores. Cuando se lee un paréntesis que abre, este debe insertarse a la pila y al leer un paréntesis que cierra se debe tratar como una subcadena, por tal motivo se tiene que rediseñar la función precedencia, agregando las siguientes opciones: precedencia(op1, ‘(‘) = falso precedencia(‘(‘, op1) = falso

precedencia(op1, ‘)‘) = verdadero En este caso es verdadero porque es un paréntesis que cierra y se tomara como una subcadena para determinar la prioridad de los operadores.

precedencia(‘(‘, ‘)‘) = falso precedencia(‘(‘, ‘(‘) = falso Algoritmo de conversión de una expresión infija a postfija (con paréntesis):

Tipo de datos de la pila:char.

Funciones:

void insertar(char d);

char quitar();



boollean esoperador(char caracter);

char cima();

boolean precedencia(char op1, char op2);

Algoritmo:


Capturar la expresión infija

while (mientras no lleguemos al final de la expresión infija){


if (!Pila.esoperador(símbolo))

agregar el símbolo a la cadena postfija

else {

while (!Pila.pilavacia() &&

Pila.precedencia(Pila.cima(), símbolo)) {



}

if (símbolo != ')')

Pila.insertar(símbolo);

else

Pila.quitar();

}

}

while (!Pila.pilavacia()) {



}

Desplegar la cadena postfija

Suponga que se quiere evaluar la expresión: ((A-(B+C))*D)^(E+F)


Implemente el algoritmo para convertir una expresión infija a postfija. Clases para la implementación de pilas. La clase Stack (java.util.Stack) es una extensión de la clase Vector. La clase Stack representa una pila de objetos bajo la filosofía LIFO. Esta clase cuenta con cinco operaciones que permite al Vector ser utilizado como una pila. Entre estas operaciones se encuentran push y pop, además el método peek que proporciona el objeto de la cima de la pila, asi como loe métodos empty y search.


Stack() Crea un objeto Stack vacío

boolean empty() Regresa true si el objeto Stak esta vacío y false en caso contrario.

Objeto peek() Regresa el objeto de la cima del Stack sin eliminar el objeto de la pila.

Objeto pop() Regresa el objeto de la cima del Stack eliminando el objeto de la pila.

Objeto push(Objeto elem) Inserta el objeto elem en la cima de la pila. Es similar a: Vector.addElement(Objeto);

int search(Object o) Regresa la posición del objeto o dentro de la pila o -1 si no lo encuentra.


Elabore un programa en Java que evalué una expresión con los 3 diferentes delimitadores de ámbito utilizando la clase Stack.

2.2. Colas estáticas y dinámicas. Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo y se retiran por el otro. Por esta razón las colas se rigen por la filosofía FIFO (first in, first out) o PEPS (primero en entrar primero en salir). Colas simples En una cola hay dos extremos, uno es llamado frente y el otro se llama final y es el que se encuentra en la parte trasera de la cola. En una cola, los elementos se retiran por la parte del frente y se agregan por la parte final o trasera de la cola.

Las operaciones básicas de una cola son insertar (agregar un elemento al final de la cola) y borrar (eliminar el elemento que está al frente de la cola).

Frente

a) A B C

Final

Frente

b) A B C D

Final

Frente

c) B C D

Final

Frente

X insetar X

Final

Frente

X Y insertar Y

Final

Frente

X Y Z insertar Z

Final

Frente

Y Z borrar X

Final

Colas circulares. Otra solución consiste en considerar la cola en forma circular, en lugar en forma lineal. Veamos el siguiente ejemplo e insertemos el elemento F.

Colas dobles. Una variación de las colas son la Bicolas o colas de doble entrada. Una Bicola es una cola en donde se puede insertar o eliminar elementos por los dos extremos. Se puede decir que una Bicola es una cola bidireccional. Operaciones. Antes de poder utilizar una cola debemos estipulas que tipo de datos almacenara (int, float, char, etc).

Operaciones básicas de colas simples Las operaciones básicas de una cola son:

Tamaño de la cola Número de elementos máximos que puede contener la cola.

Crear Cola Crear la cola.

Insertar Agregar un elemento al final de la cola.

Borrar Extraer el elemento del frente de la cola.

Cola vacía Comprobar si la cola no tiene elementos.

Cola llena Comprobar si la cola está llena. Al utilizar arreglos como una cola existe la posibilidad de desbordamientos (underflow u overflow). Si por el momento no tomamos en cuenta la posibilidad de desbordamiento las operaciones quedaran de la siguiente forma:

Insertar 1. Verificar que la cola no esté llena. 2. Incrementar en 1 el apuntador del final de la cola. 3. Almacenar el elemento en la nueva posición final.

Frente

0 1 2 3 4

C D E

Final

Frente

0 1 2 3 4

F C D E insertar F

Final

Borrar 1. Verificar si la cola no este vacía. 2. Leer el elemento que se encuentra la frente de la cola. 3. Incrementar en 1 el frente de la cola.

Cola vacía Al comenzar el final es igual a -1 y el frente es igual a 0. La cola está vacía siempre que el final < frente y el número de elementos se calcula final – frente + 1.

Cola llena La cola está llena cuando el final es igual al máximo de elementos – 1.

La representación en Java de las operaciones de una cola Definir el tipo de dato de la cola Se debe seleccionar que tipo de dato va a manejar la Cola (char, int, double, etc.)

Tamaño de la cola final static int MAX_ELEMENTOS = 100;

Crear una cola TipoCola Cola = new TipoCola();

Inicializar la cola frente = 0;

final = -1;

Función insertar public void insertar(char d){

if (!colallena())

elemento[++final]=d;

else

System.out.println("Cola llena");

}

Función borrar public char borrar() {

if (!colavacia())

return elemento[frente++];

else {

System.out.println("Cola vacia");

return ‘ ‘;

}

}

Función colavacia public boolean colavacia(){

if (final < frente)

return true;

esle

return false;

}

Función colallena public boolean colallena(){

if (final == MAX_ELEMENTOS - 1)

return true;

else

return false;

}

Ahora consideremos la posibilidad de desborde, supongamos el siguiente ejemplo:

Si se desea insertar el elemento F, no es posible porque Final == MAX_ELEMENTOS – 1, es decir la cola está llena (aunque calculando el número de elementos en la cola final – frente + 1 es igual a 3 y comprobando que la cola no está llena). Compactación Una solución es modificar la operación borrar de tal manera que cuando se elimine un elemento los demás se recorran al principio del arreglo, a este proceso se le llama compactación. La función borrar quedaría de la siguiente forma: public char borrar(){

char d;

if (!colavacia()) {

d = elemento[0];

for(int i=0; i< final; i++)

elemento[i] = elemento[i+1];

Frente

0 1 2 3 4

C

Final

Frente

0 1 2 3 4

C D Einsertar D

insertar E

Final

final--;

return d;

}

else

System.out.println("Cola vacía”);

}

Bajo esta técnica ya no es necesario el frente de la cola, debido a que el primer elemento siempre está en la posición 0. Sin embargo, este método es poco eficaz, porque cada vez que se borra un elemento se tiene que compactar los elementos restantes. Para poder solucionar este problema sería necesario realizar la compactación si y solo si:

((final == (MAX_ELEMENTOS-1)) && ((final – frente+1) != (MAX_ELEMENTOS)))

Operaciones básicas de colas circulares En las colas circulares es difícil determinar si la cola está llena o no. Para calcularla debemos utilizar la teoría de los residuos de tal modo que generemos posiciones entre 0 y MAX_ELEMENTOS-1.

TOSMAX_ELEMEN % 1)(finalfinal

TOSMAX_ELEMEN % 1)(frentefrente

Las operaciones de una cola circular quedarían como sigue: frente = 0;

final = MAX_ELEMENTOS – 1;

Cola vacía Para comprobar si una cola está vacía o está llena sacrificaremos un elemento de la cola, de tal forma que la capacidad real de la cola será MAX_ELEMENTOS – 1 y la condición de cola vacía quedara:

frente == siguiente(final); Donde la función siguiente regresa la posición de que le sigue al final, si esta es igual al frente se determina que la cola está vacía.

Frente

0 1 2 3 4

Final

Cola llena La cola está llena cuando: frente == siguiente(siguiente(final))

Recordemos que se está sacrificando un elemento, entonces si el frente es igual a la posición de las dos siguientes posiciones se supone que la cola está llena.

Insertar 1. Verificar que la cola no esté llena. 2. final = (final + 1) % MAX_ELEMENTOS 3. Almacenar el elemento en la nueva posición final.

Frente

0 1 2 3 4

Final

Frente

0 1 2 3 4

Final

Frente

0 1 2 3 4

a b c d

Final

Frente

0 1 2 3 4

f c d e

Final

Frente

0 1 2 3 4

f g h e

Final

Borrar 1. Verificar si la cola no este vacía. 2. Leer el elemento que se encuentra la frente de la cola. 3. frente = (frente + 1) % MAX_ELEMENTOS

Siguiente 1. A la posición que recibe como parámetro:

retrun (n + 1) % MAX_ELEMENTOS

La representación en Java de las operaciones de una cola circular

Inicializar la cola public void inicializarcola(){

frente = 0;

final = MAX_ELEMENTOS -1;

}

Función insertar public void insertar(char d){

if (!colallena()) {

final = siguiente(final);

elemento[final] = d;

}

else

System.out.println("Cola llena");

}

Función borrar public char borrar(){

char d;

if (!colavacia()) {

d= elemento[frente];

frente = siguiente(frente);

return d;

}

else {

System.out.println("Cola vacía");

return ‘ ‘;

}

}

Función colavacia public boolean colavacia(){

if (frente == siguiente(final))

return true;

else

return false;

}

Función colallena public boolean colallena(){

if (frente == siguiente(siguiente(final)))

return true;

else

return false;

}

Operaciones básicas de las colas dobles o bicolas Los extremos de la Bicola se pueden identificar como izquierdo y derecho respectivamente. Las operaciones básicas de una Bicola son:

Crear Bicola Crear la Bicola.

InsertarIzq Agregar un elemento en el extremo Izquierdo de la Bicola.

InsertarDer Agregar un elemento en el extremo Derecho de la Bicola.

BorrarIzq Extraer el elemento de la Izquierda de la Bicola.

BorrarDer Extraer el elemento de la Deracha de la Bicola.

Bicola vacía Regresa verdadero si la Bicola esta vacia.

Bicola llena Regresa verdadero si la Bicola esta llena Una Bicola con restricción de entrada es aquella que solo permite inserciones por uno de los extremos, pero que permite eliminar elementos por los dos extremos. Una Bicola con restricción de salida es aquella que solo permite inserciones por los dos extremos, pero solo permite eliminar elementos por un extremo.


Elabore un programa en Java que lea 7 nombres desde el teclado y los inserte en un objeto TipoCola con organización circular (Con capacidad de 10 elementos) y posteriormente saque 4 elementos, después solicite otros 5 elementos y al final imprima los datos de la cola. Clases para la implementación de colas. La interfaz Queue (java.util.Queue) representa una cola de objetos bajo la filosofía FIFO. Esta clase cuenta con los siguientes métodos:


boolena add (Object o) Inserta el elemento o en la cola si retornando true si hubo éxito y false en caso contrario.

Object element() Recupera el elemento de la cabeza de la cola pero no lo elimina.


boolean offer(Object o) Inserta el elemento o especificado en la cola (true), en caso de que no sea posible regresa false.

Object peek() Recupera el elemento de la cabeza de la cola pero no lo elimina, en caso de que la cola esté vacía devuelve null.

Object poll() Recupera el elemento y lo remueve de la cabeza de la cola o null si esta cola está vacía.

Object remove() Recupera y remueve la cabeza de la cola.


Implemente el ejercicio 2.5 mediante le interfaz Queue.

Listas Una lista es una colección o secuencia de elementos ordenados uno tras otro, en la que cada elemento se conecta por medio de un apuntador. A cada elemento de la lista se le llama nodo. Cada nodo está constituido por dos partes las cuales son:

Representación grafica

Debido a que el último elemento de la lista no está señalando a ningún elemento existe diferentes formas de representarlo gráficamente:

1a. Parte

Información

2a. Parte

Apuntador que señala

al siguiente nodo

Nodo 1 Nodo 2 ••• Nodo n /

Nod x / Nodo x Nodo x null

Listas enlazadas Listas Simples. Cada nodo contiene un único enlace que conecta al siguiente nodo. La lista se recorre solamente hacia adelante.

Apuntadores al inicio y al final de la lista Para poder manipular una lista de una manera eficiente es utilizar apuntadores al inicio de las lista y al final. Para poder lograr esto debemos utilizar un apuntador al frente o inicio de la lista y al final o cola.

Listas Dobles. Cada nodo contiene dos enlaces o apuntadores, el enlace izquierdo apunta al nodo predecesor y el enlace derecho apunta al nodo sucesor.

Circulares. El último nodo de la lista apunta al primer elemento de la lista.

Cada nodo esta enlazado a su predecesor y sucesor y el último apunta a primer elemento y el primero apunta al último. Multilistas. En las multilistas existen enlaces verticales y horizontales.

e1 e2 e3 ••• en /

inicio

e1 e2 e3 ••• en /

fin

……e3 en // e1 e2

……e2 e3e1 en

inicio

e10 / /

e6 / e8 / /e7 /

e4 / /

e3 / /

e2

e9 /

e5

e1

Clases para la implementación de listas.

Clase nodoSimple class nodoSimple { private String dato; private nodoSimple enlace; nodoSimple( String d ) { this( d, null ); } nodoSimple( String d, nodoSimple e ) { dato = new String(d); enlace = e; } String obtenDato() { return dato; } nodoSimple obtenEnlace() { return enlace; } void cambiaDato(String d) { dato = new String(d); } void cambiaEnlace(nodoSimple e) { enlace = e; } }

Operaciones en listas Las operaciones básicas sobre una lista son:

Tipo de datos de la lista

Declaración de un nodo

Crear la lista

Comprobar si la lista está vacía

Insertar un elemento

Eliminar un elemento

Buscar un elemento

Recorrer la lista

Tipo de datos de la lista En cada tipo de lista se debe definir el tipo de dato que se va a manejar, para nuestro ejemplo tomaremos el tipo String.

Declaración de un nodo nodoSimple nodo, inicio = null, fin = null;

Comprobar si la lista está vacía Para comprobar si la lista está vacía, simplemente se debe de preguntar si inicio es igual a null.

Insertar un elemento Existen tres formas de insertar un nodo en una lista, los cuales pueden ser:

Insertar al inicio de la lista

nodoSimple nodo, inicio = null, fin = null; ... .. . Capturar la información nodo = new nodoSimple(información); ... .. . nodo.cambiaEnlace(inicio); inicio = nodo;


Elabore un programa en Java que lea 5 nombres desde el teclado y los inserte al inicio en una lista ligada simple e imprima la lista final.

Insertar al final de la lista

inicio inicio

e0 e1 e2 ••• en /

fin

nodo

inicio

e1 e2 ••• en / e0 /

fin fin

nodo

nodoSimple nodo, inicio = null, fin = null; ... .. . Capturar la información nodo = new nodoSimple(información); ... .. . fin.cambiaEnlace(nodo); fin = nodo;


Elabore un programa en Java que lea 5 nombres desde el teclado y los inserte al final en una lista ligada simple e imprima la lista final.

Insertar entre elementos de la lista

nodoSimple nodo, inicio = null, fin = null; ... .. . Capturar la información nodo = new nodoSimple(información); ... .. . pre.cambiaEnlace(nodo); nodo.cambiaEnlace(suc);


Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple, posteriormente solicite un nuevo nombre y un valor numérico e inserte el nuevo nombre después del n-esimo nombre e imprima la lista final.

inicio suc

e1 e2 e3 ••• en /

pre fin

e0

nodo

Eliminar un elemento Así como existen tres formas de insertar un elemento, existen tres formas de eliminarlo.

Eliminar un elemento al inicio de la lista

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = inicio.obtenDato(); nodo = inicio; inicio = inicio.obtenEnlace(); nodo.cambiaEnlace(null); nodo = null;


Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al inicio en una lista ligada simple e imprima la lista, posteriormente elimine el primer nombre e imprima la lista final.

Eliminar un elemento al final de la lista

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = fin.obtenDato(); nodo = inicio; while (nodo.obtenEnlace() != fin) nodo = nodo.obtenEnlace(); nodo.cambiaEnlace(null); fin = nodo;

inicio inicio

e0 e1 e2 ••• en /

nodo fin

inicio

e1 e2 e3 ••• en /

fin fin

nodo


Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple e imprima la lista, posteriormente elimine el último nombre e imprima la lista final.

Eliminar un elemento en medio de la lista

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = nodo.obtenDato(); pre.cambiaEnlace(nodo.obtenEnlace); nodo.cambiaEnlace(null); nodo = null; Nota: En ninguno de los algoritmos anteriores, se ha validado si la lista está vacía o si

existe un solo elemento en la lista.


Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al inicio en una lista ligada simple e imprima la lista, posteriormente solicite un número entre 1 al 5 y elimine el n-esimo nombre, al final imprima la lista.

Buscar un elemento

Al realizar la búsqueda un elemento en una lista, se debe realizar este proceso hasta que se localice el elemento o hasta que se llegar al final de la lista. boolean buscarL(nodoSimple nodo, String x) { while (nodo != null && !x.equals(nodo.obtenDato())) nodo = nodo.obtenEnlace(); if (nodo != null && x.equals(nodo.obtenDato())) return true; else return false; }

inicio nodo

e1 e2 e3 ••• en /

pre fin

nodoSimple buscarN(nodoSimple nodo, String x) { while (nodo != null && !x.equals(nodo.obtenDato())) nodo = nodo.obtenEnlace(); return nodo; }


Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple e imprima la lista, posteriormente solicite un nuevo nombre y lo busque en la lista, si encuentra el nombre indique en qué posición se encuentra, en caso de no localizarlo imprima -1.

Recorrer la lista nodo = inicio; while (nodo != null) { System.out.print(nodo.ObtenDato() + "->"); nodo = nodo.obtenEnlace(); } Systema.out.println("/"); El siguiente programa solicita el número de elementos que se desea insertar en una lista, posteriormente mediante un menú solicita la forma de inserción (Inicio o Final) y al final despliegue la lista en pantalla.

1 // Ejemplo_Lista

2


4

5 class nodoSimple {

6 private String dato;

7 private nodoSimple enlace;

8

9 nodoSimple( String d ) {

10 this( d, null );

11 }

12

13 nodoSimple( String d, nodoSimple e ) {

14 dato = new String(d);

15 enlace = e;

16 }

17

18 String obtenDato() {

19 return dato;

20 }

21

22 nodoSimple obtenEnlace() {

23 return enlace;

24 }

25

26 void cambiaDato(String d) {

27 dato = new String(d);

28 }

29

30 void cambiaEnlace(nodoSimple e) {

31 enlace = e;

32 }

33 }

34

35 public class Ejemplo_Lista {

36 public static void main(String [] args) {

37 nodoSimple inicio = null, fin = null, nodo;

38 String inf = "";

39 int cuantos, tipo=0;

40 Object[] options = { "Inicio", "Final" };

41

42 cuantos = Integer.parseInt(

43 JOptionPane.showInputDialog("Cuantos elementos deseas:") );

44 if (cuantos > 0) {

45 tipo = JOptionPane.showOptionDialog(null,

46 "Insertar al", "Opción de inserción",

47 JOptionPane.DEFAULT_OPTION,

48 JOptionPane.QUESTION_MESSAGE,

49 null, options, options[0]);

50

51 for(int i=1; i<=cuantos; i++) {

52 inf = JOptionPane.showInputDialog

53 ("Dame el valor del nodo " + i + ":");

54 nodo = new nodoSimple(inf);

55 if (i == 1) {

56 inicio = nodo;

57 fin = nodo;

58 }

59 else {

60 if (tipo==0) {

61 nodo.cambiaEnlace(inicio);

62 inicio = nodo;

63 }

64 else {

65 fin.cambiaEnlace(nodo);

66 fin = nodo;

67 }

68 }

69 }

70

71 String Salida = "";

72 nodo = inicio;

73 while (nodo != null) {

74 Salida += nodo.obtenDato() + "->";

75 nodo = nodo.obtenEnlace();

76 }

77 Salida += "\\";

78 JOptionPane.showMessageDialog( null,Salida,

79 "Lista ligada simple",JOptionPane.PLAIN_MESSAGE);

80

81 System.exit(0);

82 }

83 } 84 }

Programa: Ejemplo_Lista.java 2/2

Inserción al inicio:

Inserción al final:


Elabore un programa en Java que mediante un menú despliegue si se quiere Insertar, Borrar, Mostrar o Salir en una lista ligada simple, si selecciona Insertar se despliegue un menú que indique si se inserta al Inicio, en Medio o al Final de la lista, si selecciona en Medio, capture la posición donde se desea insertar, después teclee el nombre y lo inserte en la opción indicada. Si selecciona Borrar se despliegue un menú que indique si se borra al Inicio, en Medio o Final, si selecciona en Medio, capture la posición del elemento a borrar y posteriormente borre el elemento según lo indicado. Si selecciona Mostrar despliegue la lista ligada simple. Solo puede terminar cuando en el menú principal seleccione Salir.

Listas doblemente ligadas Clase nodoDoble

class nodoDoble {

private nodoDoble enlaceIzq;

private String dato;

private nodoDoble enlaceDer;

nodoDoble( String d ) {

this( null, d, null );

}

nodoDoble(nodoDoble izq, String d, nodoDoble der ) {

dato = new String(d);

enlaceIzq = izq;

enlaceDer = der;

}

String obtenDato() {

return dato;

}

nodoDoble obtenEnlaceIzq() {

return enlaceIzq;

}

nodoDoble obtenEnlaceDer() {

return enlaceDer;

}

void cambiaDato(String d) {

dato = new String(d);

}

void cambiaEnlaceIzq( nodoDoble izq ) {

enlaceIzq = izq;

}

void cambiaEnlaceDer( nodoDoble der ) {

enlaceDer = der;

}

}

Insertar un elemento Existen tres formas de insertar un nodo en una lista doblemente ligada:

Insertar al inicio

inicio inicio

……

fin

// e0 / e3 ene1 e2

nododoble nodo, inicio = null, fin = null;

...

..

.

Capturar la información

nodo = new nodoDoble(información);

...

..

.

nodo.cambiaEnlaceDer(inicio);

inicio.cambiaEnlaceIzq(nodo);

inicio = nodo;

Insertar al final

nodoDoble nodo, inicio = null, fin = null;

...

..

.



...

..

.

fin.cambiaEnlaceDer(nodo);

nodo.cambiaEnlaceIzq(fin);

fin = nodo;

Insertar entre elementos de la lista


...

..

.


inicio

……

fin fin

/ e0 /e3 en/ e1 e2

inicio pre suc

……

fin

e0

e3 en // e1 e2

nodo


...

..

.

pre.cambiaEnlaceDer(nodo);

nodo.cambiaEnlaceIzq(pre);

nodo.cambiaEnlaceDer(suc);

suc.cambiaEnlaceIzq(nodo);

Eliminar un elemento Existen tres formas de eliminar un elemento en una lista doblemente ligada. Eliminar un elemento al inicio


String x;

...

..

.

x = inicio.obtenDato();

nodo = inicio;

inicio = inicio.obtenEnlaceDer();

inicio.cambiaEnlaceIzq(null);

nodo.cambiaEnlaceDer(null);

nodo = null;

Eliminar un elemento al final de la lista


String x;

...

..

.

x = fin.obtenDato();

nodo = fin;

fin = fin.obtenEnlaceIzq();

fin.cambiaEnlaceIzq(null);

nodo.cambiaEnlaceIzq(nell);

nodo = null;

inicio inicio

……

fin

en /e2 e3/ e1

nodo

inicio

……

fin fin

en // e1 e2 e3

nodo

Eliminar un elemento en medio


String x;

...

..

.

x = nodo.obtenDato();

pre.cambiaEnlaceDer(suc);

suc.cambiaEnlaceIzq(pre);

nodo.cambiaEnlaceIzq(null);

nodo.cambiaEnlaceDer(null);

nodo = null;


Elabore un programa en Java que mediante un menú despliegue si se quiere Insertar, Borrar, Mostrar o Salir en una lista doblemente ligada, si selecciona Insertar se despliegue un menú que indique si se inserta al Inicio, en Medio o al Final de la lista, si selecciona en Medio, capture la posición donde se desea insertar, después teclee el nombre y lo inserte en la opción indicada. Si selecciona Borrar se despliegue un menú que indique si se borra al Inicio, en Medio o Final, si selecciona en Medio, capture la posición del elemento a borrar y posteriormente borre el elemento según lo indicado. Si selecciona Mostrar despliegue la lista ligada simple. Solo puede terminar cuando en el menú principal seleccione Salir.

Clase LinkedList El paquete java.util contiene la clase LinkedList para implementar

y manipular listas enlazadas que crezcan y se reduzcan durante la ejecución del programa. La clase LinkedList es una implementación de listas doblemente ligadas.


LinkedList() Crea una lista vacia

void add(int index, Object o) Inserta el objeto o en la posición indicada por index

boolean add(Object o) Inserta el objeto o al final de la lista

inicio pre suc

……

fin

en/ e1 e2 /e3

nodo


void addFirst(Object o) Inserta el objeto o al inicio de la lista

void addLast(Object o) Inserta el objeto o al final de la lista

void clear() Elimina todos los elementos

boolean contains(Object o) Regresa verdadero si el objeto o está contenido en la lista

Object get(int index) Regresa el objeto almacenado en la posición indicada por index

Object getFirst() Regresa el objeto que esta al inicio de la lista

Object getLast() Regresa el objeto que esta al final de la lista

int indexOf(Object o) Regresa la posición de la primera ocurrencia del objeto o en la lista o -1 en caso de que no exista el elemento.

int lastIndexOf(Object o) Regresa la posición de la última ocurrencia del objeto o en la lista o -1 en caso de que no exista el elemento

Object remove(int index) Elimina y regresa el objeto indicado por index

boolena remove(Object o) Elimina la primera ocurrencia del objeto o de la lista.

Object removeFirst() Elimina y regresa el primer elemento de la lista

Object removeLast() Elimina y regresa el último elemento de la lista

Object set(int index, Object o) Remplaza el elemento indicado por index por el elemento o y regresa el objeto almacenado en esa posición


int size() Regresa el número de elementos de la lista

Object [ ] toArray() Regresa un arreglo de objetos que contiene todos los elementos de lista


Utilizando la clase LinkedList, elabore un programa en Java que mediante un menú despliegue si se quiere Insertar, Borrar, Mostrar o Salir en una lista doblemente ligada, si selecciona Insertar se despliegue un menú que indique si se inserta al Inicio, en Medio o al Final de la lista, si selecciona en Medio, capture la posición donde se desea insertar, después teclee el nombre y lo inserte en la opción indicada. Si selecciona Borrar se despliegue un menú que indique si se borra al Inicio, en Medio o Final, si selecciona en Medio, capture la posición del elemento a borrar y posteriormente borre el elemento según lo indicado. Si selecciona Mostrar despliegue la lista ligada simple. Solo puede terminar cuando en el menú principal seleccione Salir.

3. Estructuras no lineales 3.1. Recursividad. Definición: Un función recursiva es una función que se llama a si mismo ya sea directa

o indirectamente.

La recursividad directa es el proceso por el cual un método se llama asimismo desde el mismo cuerpo del programa:

int fn(…) { . . . fn(…); . . . }

La recursividad indirecta implica más de un método, por ejemplo:

int fn1(…) { . . . fn2(. . .); . . . } int fn2(…) { . . . fn1(. . .); . . . }

Uno de los requisitos que debe tener un proceso recursivo para considerarlo valido es que debe tener una condición de salida o condición base, para que garantice el no generará un secuencia infinita y agotara la memoria (Stack) – Pila). Por ejemplo: El factorial de un número no negativo n (denotado por n!) es el producto de:

n! = n * (n-1) * (n-2) …* 1 En el cual : 0! = 1 1! = 1 2! = 2 * 1 3! = 3 * 2 * 1 . . .

Si n es igual a 5 tendremos:

!...3*4*5)1*2*3*4(*5!4*51*2*3*4*5!5)!14()!15(

De modo que la función recursiva del factorial n sería:

n! = n * (n-1)! = n * (n-1) * ((n-1)-1)!...1

De tal manera que el factorial de un entero no negativo n mayor o igual a cero se calcularía de la siguiente forma:

)!1(*0

1 0!

nnn

nn

Implementando de la función recursiva:

long factorial (long n) { if (n == 0) return 1; else return n * factorial(n-1); }

La recursividad en el recorrido de las pilas

System.out.println( “Factorial de 5 es:” + factorial(5));

n=5 5*factorial(4)

n=4 4*factorial(3) 5*factorial(4)

n=3

3*factorial(2) 4*factorial(3) 5*factorial(4)

n=2

2*factorial(1) 3*factorial(2) 4*factorial(3) 5*factorial(4)

1*factorial(0)

n=1


1*1 = 1


2*1=2 3*factorial(2) 4*factorial(3) 5*factorial(4)

3*2=6 4*factorial(3) 5*factorial(4)

4*6=24 5*factorial(4)

5*24=120

Factorial de 5: 120 Ejemplos:

Deducir la función recursiva del producto de dos números naturales. El producto de a*b donde a y b son enteros positivos, tiene dos soluciones:

Solución iterativa:

vecesb

* aaaaaba

Solución recursiva:

)1(*0

1*

baab

abba

Por ejemplo 7 * 3 será:

7 * 3 = 7 + 7 * (3-1) = 7 + 7 + 7*(2-1) = 7 + 7 + 7=21

La función recursiva quedara: int producto (int a, int b) { if (b == 1) return a; else return a + a * (b - 1); }

Deducir la función recursiva de la serie fibonacci: 0 1 1 2 3 5 8 13 … La seria fibonacci comienzan con los números 0 y 1, y el los demás resultan de la suma de los dos últimos:

0 + 1 = 1 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 5 + 8 = 13 .. .

Entonces podemos deducir que:

fibonacci(0) = 0 fibonacci(1) = 1 … … fibonacci(n)= fibonacci(n-1) + fibonacci(n-2)

Solución recursiva:

)2()1(2

n1n || 0n)(

nfibonaccinfibonaccinnfibonacci

La función recursiva quedara: long fibonacci(long n) { if (n == 0 || n == 1) return n; else return fibonacci(n-1) + fibonacci(n-2); }


Escriba un programa que utilice una función recursiva mcd (máximo como un divisor) de dos números por el algoritmo de Euclides. El mcd de dos números a y b se define como el entero mayor que divide a ambos números. El mcd no está definido si tanto a como b son cero. Los valores negativos de a y b se sustituyen por sus valores absolutos. Siempre debe cumplirse la premisa a >= b. Si b = 0 el mcd es a. Por ejemplo el mcd(2970, 1265)

a b Operación

2970 1265 2990 % 1265=440

1265 440 1265 % 440 = 385

440 385 440 % 385= 55

385 55 385 % 55 = 0

55 0 El mcd es 55

) % ,(0!

0),(

babmcdb

abbamcd

Object[] options = { "Inicio", "Final" }; tipo = JOptionPane.showOptionDialog(null, "Insertar al", "Opción de inserción", JOptionPane.DEFAULT_OPTION, JOptionPane.QUESTION_MESSAGE, null, options, options[0]);


A. Implemente los métodos recursivos de producto de dos números naturales,

serie Fibonacci y Máximo Como un Divisor utilizando un menú basado en botones.

B. Elabore e implemente uno de los problemas siguientes programas

recursivos:

1. Programar un algoritmo recursivo que permita hacer la división por restas sucesivas.

2. Programar un algoritmo recursivo que permita invertir un número. Ejemplo: Entrada: 123 Salida: 321

3. Programar un algoritmo recursivo que permita sumar los dígitos de un número. Ejemplo: Entrada: 123 Resultado: 6

4. Programar un algoritmo recursivo que permita sumar los elementos de un vector.

5. Programar un algoritmo recursivo que permita multiplicar los elementos de un vector.

6. Programar un algoritmo recursivo que permita sumar los elementos de una matriz.

7. Programar un algoritmo recursivo que eleve a la potencia un número xn.

3.2. Árboles. Las listas enlazadas, pilas y colas son estructuras de datos lineales (es decir, secuenciales). Un árbol es una estructura bidimensional no lineal, con propiedades especiales. Por medio de los árboles se pueden representar estructuras jerárquicas, direcciones o etiquetas de una manera organizada.

Dentro de las ciencias computacionales, los árboles tienen muchas aplicaciones, entre estas se encuentran:

Organización de tablas de símbolos en los compiladores.

Representación de árboles de decisión.

Asignación de bloques de memoria de tamaño variable.

Ordenación de datos.

Búsqueda de datos.

Solución de juegos.

Teoremas.

Etc. Definición: Conjunto finito T de uno o más nodos tal que:

v1 es el nodo raíz.

vn-1 es el padre de vn.

v1, v2, …, vn-1 son ancestros de vn.

vn es un hijo de vn-1.

Si a es un ancestro de b, entonces b es un descendiente de a.

Si a y b son hijos de c, entonces a y b son hermanos.

Si a no tiene hijos, entonces a es un vértice terminal (o una hoja).

V1

V2

V7V6V5V4

V3

Si a no es un vértice terminal, entonces a es un vértice interno (o una rama).

Cada vértice o nodo puede tener un nombre y una información asociada.

Un arco es una conexión entre dos vértices o nodos.

Un camino es una lista de nodos diferentes en los que los nodos están conectados por medio de arcos. Una propiedad que se distingue a los árboles es que existe exactamente un camino entre el nodo raíz y cada uno de los nodos del árbol, por ejemplo el camino desde la raíz a la hoja v5, se representa v1, v2, v5 que incluye las ramas (v1, v2) y (v2, v5) y su longitud es 2.

La altura o profundidad es la longitud del camino más largo más uno.

El nivel de un nodo es su distancia al nodo raíz. El nodo raíz tiene distancia cero. Los hijos del nodo raíz están en el nivel uno, mientras que sus hijos están en el nivel 2 y así sucesivamente.

El grado de un nodo se determina por el número de hijos que tiene. Los nodos que tienen grado cero son hojas.

Ejemplo:

V1

V3

V4V5V6V7

V2

Nodo Raíz

Vértice

o

Nodo

Arco

Nivel 0

Nivel 1

Nivel 2

A

B C

D E F G H

M N OI J K L

¿Cuál es el camino de A-L?

¿Cuáles son los hijos de G?

¿Cuáles son los nodos de grado cero?

¿Cuáles son los nodos de grado dos?

¿Cuáles son los nodos de grado tres?

¿Cuál es la profundidad del árbol?

Representación de un árbol Existen varias formas de representación de un árbol en forma grafica: Niveles: 01 v1 02 v2 03 v4 03 v5 02 v3 03 v6 03 v7

Paréntesis anidados:

v1(v2(v4,v5), v3(v6,v7)) Grafos:

Diagrama de Venn:

Un árbol ordenado es aquel que está estructurado bajo una organización específica.

V1

V3

V4V5V6V7

V2

v1

v3 v2

v6 v7 v4 v5

Representación en memoria de árboles.

Árboles generales. También mediante los árboles podemos representar situaciones de la vida diaria tales como:

A

B C

D E / F / / H /

/ I / / J / / K / / L /

Vice-Presidente

para asuntos

Académicos

Vice-Presidente

para asuntos

Administrativos

Decano de

Artes y Ciencias

Decano de

Comercio

Director de

Plantación

Académica

Director de

Adquisiciones

Jefe de

Matemáticas

Jefe de

Ciencias de la

Computación

…Jefe de

Contaduría…

Presidente

Afrodita Cronos Atlas Prometeo

Eros Zeus Poseidón Hades Ares

Apolo Atenas Hermes Heracles

Urano

Árboles binarios. Definición: Es un árbol en el cual sus nodos no puede tener más de dos hijos. Un árbol binario puede tener cero, uno o dos hijos. Al nodo izquierdo se le llama hijo izquierdo y al nodo derecho hijo derecho.

Recorrido de árboles binarios. Existen tres formas de recorrer un árbol binario, las cuales son Preorden, Incorden Postorden. Preorden

Preorden

El recorrido es raíz, hijo izquierdo e hijo derecho.(rid)

Seles

Seles

Navratilova

Graf

Sabatini

Graf

Graf

A

B C

D E F

G H

Inorden

Inorden

El recorrido es hijo izquierdo, raíz e hijo derecho. (ird)

Postorden

Postorden

El recorrido es hijo izquierdo, hijo derecho y raíz. (idr)

Preorden: 20, 15, 10, 5, 12, 18, 17,

19, 33, 25, 21, 27, 50, 40, 70

Inorden: 5, 10, 12, 15, 17, 18, 19,

20, 21, 25, 27, 33, 40, 50, 70

Postorden: 5, 12, 10, 17, 19, 18, 15,

21, 27, 25, 40, 70, 50, 33, 20

Declaración de un nodoArbol class nodoArbol {

private nodoArbol hizq;

private int dato;

private nodoArbol hder;

nodoArbol( int dat ) {

this( null, dat, null );

}

nodoArbol( nodoArbol izq, int dat, nodoArbol der ) {

dato = dat;

hizq = izq;

hder = der;

}

int obtenDato() {

return dato;

}

nodoArbol obtenHIzq() {

return hizq;

}

nodoArbol obtenHDer() {

return hder;

}

void cambiaDato(int dat) {

dato = dat;

}

void cambiaHIzq(nodoArbol izq) {

hizq = izq;

}

void cambiaHDer(nodoArbol der) {

hder = der;

}

}

Algoritmo preorden utilizando pilas public static void preordenPila(nodoArbol r) {

tipoPila Pila = new tipoPila();

nodoArbol recorre;

Pila.insertar(null);

recorre = r;

while (recorre != null) {

procesar el nodo recorre

if (recorre.obtenHDer() != null)

Pila.insertar(recorre.obtenHDer());

if (recorre.obtenHIzq() != null)

recorre = recorre.obtenHIzq();

else

recorre = Pila.quitar();

}

}

Algoritmo preorden recursivo public static void preordenRecursivo(nodoArbol r) {

if (r != null) {

procesar el nodo r

preordenRecursivo(r.obtenHIzq());

preordenRecursivo(r.obtenHDer());

}

}

Algoritmo inorden utilizando pilas public static void inordenPila(nodoArbol r) {


nodoArbol recorre;


recorre = r;



Pila.insertar(recorre);


}



procesar el nodo recorre

if (recorre.obtenHDer() != null) {

recorre = recorre.obtenHDer();

break;

}


}

}

}

Algoritmo inorden recursivo public static void inordenRecursivo(nodoArbol r) {

if (r != null) {

inordenRecursivo(r.obtenHIzq());

procesar el nodo r

inordenRecursivo(r.obtenHDer());

}

}

Algoritmo postorden utilizando pilas public static void postordenPila(nodoArbol r) {


nodoArbol recorre;


recorre = r;



Pila.insertar(recorre);

if (recorre.obtenHDer() != null)

Pila.insertar((-1) * recorre.obtenHDer());


}


while (recorre > 0) {

procesa el nodo recorre


}

if (recorre < 0)

recorre = (-1) * recorre;

}

}

Algoritmo postorden recursivo public static void postordenRecursivo(nodoArbol r) {

if (r != null) {

postordenRecursivo(r.obtenHIzq());

postordenRecursivo(r.obtenHDer());

procesar el nodo r

}

}

El siguiente programa crea un árbol ordenado ascendentemente, mostrando los datos mediante el recorrido preorden y utiliza recursión. Primero solicita el número de nodos que se darán de alta, posteriormente solicita el valor de cada nodo y va creando el árbol binario, al final muestre la información.

1 // Ejemplo_Arboles

2


4

5 class nodoArbol {

6 private nodoArbol hizq;

7 private int dato;

8 private nodoArbol hder;

9

10 nodoArbol( int dat ) {

11 this( null, dat, null );

12 }

13

14 nodoArbol( nodoArbol izq, int dat, nodoArbol der ) {

15 dato = dat;

16 hizq = izq;

17 hder = der;

18 }

19

20 int obtenDato() {

21 return dato;

22 }

23 nodoArbol obtenHIzq() {

24 return hizq;

25 }

26

27 nodoArbol obtenHDer() {

28 return hder;

29 }

30

31 void cambiaDato(int dat) {

32 dato = dat;

33 }

34

35 void cambiaHIzq(nodoArbol izq) {

36 hizq = izq;

37 }

38

39 void cambiaHDer(nodoArbol der) {

40 hder = der;

41 }

42 }

43

44 class tipoPila {

45

46 final static int MAX_ELEMENTOS = 100;

47 private int error;

48 private int cima;

49 private nodoArbol elemento[];

50

51 public tipoPila() {

52 error = 0;

53 cima = -1;

54 elemento = new nodoArbol [MAX_ELEMENTOS];

55 }

56

57 public void insertar(nodoArbol d) {

58 if (!pilallena())

59 elemento[++cima]= d;

60 else

61 error = 1;

62 }

63

64 public nodoArbol quitar() {

65 if (!pilavacia())

66 return elemento[cima--];

67 else {

68 error = 2;

69 return null;

70 }

71 }

72

73 public boolean pilavacia() {

74 if (cima == -1)

75 return true;

76 else

77 return false;

78 }

79

80 public boolean pilallena() {

81 if (cima == (MAX_ELEMENTOS - 1))

82 return true;

83 else

84 return false;

85 }

86

87 public int muestraError() {

88 return error;

89 }

90 }

91

92 public class Ejemplo_Arbol {

93 public static void main(String [] args) {

94 int i,cuantos, inf;

95 nodoArbol nodo, recorre, raiz = null;

96

97 cuantos = Integer.parseInt(

98 JOptionPane.showInputDialog("Cuantos elementos deseas:") );

99

100 // Construcción del arbol ordenado

101 for (i=0; i < cuantos ; i++) {

102 inf = Integer.parseInt(

103 JOptionPane.showInputDialog("Dame el valor del nodo " + i + ":"));

104 nodo= new nodoArbol(inf);

105 if (raiz == null)

106 raiz = nodo;

107 else {

108 recorre = raiz;

109 while (true) {

110 if (nodo.obtenDato() > recorre.obtenDato())

111 if (recorre.obtenHDer() == null) {

112 recorre.cambiaHDer(nodo);

113 break;

114 }

115 else

116 recorre = recorre.obtenHDer();

117 else

118 if (recorre.obtenHIzq() == null) {

119 recorre.cambiaHIzq(nodo);

120 break;

121 }

122 else

123 recorre = recorre.obtenHIzq();

124 }

125 }

126 }

127 String Salida = "";

128

129 Salida += "Preorden:\n";

130 Salida += " Recursivo: " + preordenRecursivo(raiz) + "\n";

131

132 JOptionPane.showMessageDialog( null,Salida,

133 "Arbol Binario",JOptionPane.PLAIN_MESSAGE);

134 System.exit(0);

135 }

136

137 public static String preordenRecursivo(nodoArbol r) {

138 if (r != null) {

139 return r.obtenDato() + " " +

140 preordenRecursivo(r.obtenHIzq()) +

141 preordenRecursivo(r.obtenHDer());

142 }

143 else

144 return "";

145 }


1. Elabore un programa en java que crea un árbol binario ordenado

ascendentemente de números enteros y al final muestre los datos mediante el recorrido preorden utilizando pilas y recursión.


ascendentemente de números enteros y al final muestre los datos mediante el recorrido inorden utilizando pilas y recursión.


ascendentemente de números enteros y al final muestre los datos mediante el recorrido postorden utilizando pilas y recursión.


ascendentemente de cadena de caracteres e imprima cuantas hojas tiene el árbol. 5. Elabore un programa en java que crea un árbol binario ordenado

ascendentemente de cadena de caracteres e imprima cuantos nodos conforman sus ramas.

6. Elabore un programa en java que crea un árbol binario ordenado ascendentemente de cadena de caracteres e imprima cuantos nodos son abuelos.

7. Elabore un programa en java que crea un árbol binario ordenado ascendentemente de números enteros e imprima cuantos nodos son pares.

8. Elabore un programa en java que crea un árbol binario ordenado ascendentemente de números enteros e imprima cuantos nodos son impares.


ascendentemente de números enteros, solicite un número desde teclado e imprima si se encuentra ese valor en el árbol.

10. Elabore un programa en java que crea un árbol binario ordenado ascendentemente de números enteros, solicite un número desde teclado, posteriormente busque el número en el árbol y si lo encuentra regrese el nodo donde lo encontró, en caso contrario regrese null.

3.3. Grafos.

Definición. Un grafo está representado por un conjunto de vértices o nodos V y un conjunto de arcos A, representado por G=(V,A). Un arco o arista representa una relación entre dos nodos y se representa por (u, v), siendo u y v el par de nodos. Tipos de grafos. Un grafo no dirigido es aquel en que sus arcos son pares no ordenados o no dirigidos. Un grafo dirigido es aquel en el que sus arcos son pares ordenados o dirigidos (sus arcos tiene una flecha que indica la dirección de la relación). A un grafo dirigido también se le llama diagrafo.

G=(V,A) V={1, 4, 5, 7, 9}

A={(1, 4), (4, 1), (1, 5), (5, 1), (4, 9), (9, 4), (5, 7),

(7, 5), (7, 9), (9, 7)} (a)

G(V, A) V={C, D, E, F, H}

A={ (C, D), (D, F), (E, C) (E, H), (H, E) }

(b)

(a) Grafo no dirigido y (b) Grafo dirigido

En ocasiones las relaciones entre nodos tienen asociado una magnitud denominada factor o peso, y al grafo se le llama grafo ponderado. Por ejemplo, los pueblos que forman una comarca, los nodos están conformados por los pueblos, los arcos por los caminos y los pesos es la distancia en kilómetros.

1

7

4

5

9

11

77

44

55

99

C

D

E

H

F

CC

DD

EE

HH

FF

Grafo ponderado

Grado de un nodo En un grafo no dirigido el grado de un nodo v (grado(v)), es el número de arcos que contiene el nodo v. Por ejemplo en el primer ejemplo de grafo no dirigido en el inciso (a), el grado(9) = 2, ahora considerando grafo de la comarca tendremos que el grado(Lupiana) = 3. En un grafo dirigido se distingue entre grado de entrada y grado de salida; el grado de entrada de un nodo v (gradoEntrada(v)), es el numero de arcos que entran al nodo v y el grado de salida del nodo v (gradoSalida(v)), es el número de arcos que salen de v. Por ejemplo en el primer ejemplo de grafo no dirigido en el inciso (b) tendremos: gradoEntrada(E) = 1 y el gradoSalida(E) = 2.

Camino Un camino P de longitud n, desde el vértice v0 a vn, es un grafo G es la secuencia

de n+1 vértices v0, v1, v2,…, vn tal que (vi, vi+1) A(arcos) para 0 ≤ i ≤ n.

Matemáticamente el camino se representa por P=(v0, v1, v2,…, vn).

Grafo no dirigido

LupianaLupiana

El

Centenillo

El

Centenillo

San

Nicolas

San

Nicolas

ValleviejoValleviejo El NovilloEl Novillo

7

5

12

7

6

4

6

7

10

9

11

44

66

77

1010

99

1111

Por ejemplo camino del nodo 4 al nodo 7 se representa por P1 = (4, 6, 9, 7) con una longitud 3, otro camino seria P2=(10, 11). En el ejemplo de la comarca el camino P= (Lupiana, Valleviejo, El Novillo) tiene una longitud de 19 (12 + 7). Un camino P=(v0, v1, v2,…, vn) es simple si todos los nodos que forman el camino son distintos, pudiendo ser igual v0 y vn (los extremos del camino). Los caminos de P1 y P2 son caminos simples. En un grafo dirigido, un ciclo es un camino simple cerrado. Por tanto, un ciclo empieza y termina en el mismo nodo, v0 = vn,; debe tener más de un arco. Un grafo dirigido sin ciclos es llamado acíclico (GDA-Grafo Dirigido Acíclico). En general, un ciclo de longitud k se denomina k-ciclo.

Grafo dirigido con ciclos

En la figura anterior se muestra un grafo dirigido en el que los vértices (A, E, B, F, A) forman un ciclo de longitud 4, por lo tanto es de 4-ciclo. Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman el grafo y es fuertemente conexo si todos sus nodos están conectados.

(a) (b)

(a) Grafo conexo y (b) Grafo fuertemente conexo

Representación de grafos en memoria.

A

D

B C

E F

AA

DD

BB CC

EE FF

A

D

C

E

F

AA

DD

CC

EE

FF

A

D

C

F

AA

DD

CC

FF

Primero considere los vértices o nodos como números consecutivos empezando del índice cero. Tome en cuenta que el número de nodos son finitos. Se puede elegir una representación secuencial, mediante un arreglo bidimensional conocida como matriz de adyacencia; o bien una representación mediante una estructura multienlazada, denominada lista de adyacencia. La elección de una representación u otra depende del tipo de grafo y de las operaciones que se vayan a realizar sobre los vértices y arcos. Para un grafo denso lo menor es utilizar una matriz de adyacencia. Para un grafo disperso se suelen utilizar listas de adyacencia. Camino Sea G=(V, A) un grafo de n nodos, siendo V={v0, v1, v2,..,vn-1} el conjunto de nodos, y A={(vi, vj)} el conjunto de arcos. Los nodos se pueden representar por números consecutivos de 0 a n-1. La representación de los arcos se hace con una matriz M de n por n, denominada matriz de adyacencia, tal que cada elemento Mij puede tomar los valores:

)v,(v arcoun hay no si0

)v,(v arcoun hay si1

ji

ji

ijM

Por ejemplo de un grafo dirigido:

Matriz de adyacencia:

0 1 2 3 4

D F K L R

0 D 0 1 1 0 0

1 F 1 0 0 0 0

2 K 0 0 0 0 0

3 L 0 1 1 0 0

4 R 1 0 0 0 0

Lista de adyacencia:

Por ejemplo de un grafo no dirigido:

Matriz de adyacencia:

0 1 2 3 4

1 2 3 4 5

0 1 0 1 0 1 1

1 2 1 0 1 0 0

2 3 0 1 0 1 1

3 4 1 0 1 0 0

4 5 1 0 1 0 0


Por ejemplo de un grafo ponderado:

F K /

D /

F K /

D /

K

L

R

/

D

F

3

4

2

1

5

3

4

2

1

5

2 4 5 /

1 3 /

2 4 /

1 3 /

1 3 /

1

2

3

4

5

Matriz de adyacencia

0 1 2 3 4

A F L V W

0 A 0 0 0 0 0

1 F 5 0 5 5 0

2 L 0 0 0 0 9

3 V 8 0 0 0 0

4 W 0 4 0 0 0



De los siguientes grafos represéntelos en su matriz de adyacencia y lista de adyacencia.

F LA

VW

5 5

8 94 5

F LA

VW

F LA FF LLAA

VW VVWW

5 5

8 94 5

A 5 L 5 V 5 /

W 9 /

A 8 /

F 4 /W

L

V

A /

F

Futuro

Villa

Grande

San

Blass

El Rincon El

Rancho

10

6

5

8

64

8

FuturoFuturo

Villa

Grande

Villa

Grande

San

Blass

San

Blass

El RinconEl Rincon El

Rancho

El

Rancho

10

6

5

8

64

8


Elabore un programa en java que mediante teclado solicite el número de nodos de un grafo, capture los valores del grafo e imprima la matriz de adyacencia y su lista de adyacencia.

a

d

c

b

e

aa

dd

cc

bb

ee

v1 v2 v6

v4 v3 v5

v1v1 v2v2 v6v6

v4v4 v3v3 v5v5

4. Métodos de ordenamiento y búsqueda Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la clasificación u ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada. Cuando se analiza un método de ordenación, hay que determinar cuántas comparaciones realizo, cuantos intercambios hizo y cuánto tiempo tardo. La colocación en orden de una lista de valores se llama Ordenación y a la localización de un elemento de una lista se llama búsqueda.

4.1. Algoritmos de ordenamiento. Existen varios métodos para ordenamiento y clasificados en tres formas:

Intercambio

Selección

Inserción. En cada familia se distinguen dos versiones: un método simple y directo, fácil de comprender pero de escasa eficiencia respecto al tiempo de ejecución, y un método rápido, más sofisticado en su ejecución por la complejidad de las operaciones a realizar, pero mucho más eficiente en cuanto a tiempo de ejecución. En general, para arreglos con pocos elementos, los métodos directos son más eficientes (menor tiempo de ejecución) mientras que para grandes cantidades de datos se deben emplear los llamados métodos rápidos. Intercambio El método de intercambio se basa en comparar los elementos del arreglo e intercambiarlos si su posición actual o inicial es contraria inversa a la deseada. Pertenece a este método el de la burbuja. Aunque no es muy eficiente para ordenar listas grandes, es fácil de entender y muy adecuado para ordenar una pequeña lista de elementos. Una pasada por la ordenación de burbujeo consiste en un recorrido completo a través del arreglo, en el que se comparan los contenidos de las casillas adyacentes, y se cambian si no están en orden. La ordenación por burbujeo completa consiste en una serie de pasadas ("burbujeo") que termina con una en la que ya no se hacen cambios porque todo está en orden. Ejemplo:

Arreglo

0 7

1 4

2 9

3 2

4 5

5 10

6 1

7 6

8 8

9 3

Movimientos

Algoritmo:

Repite

Para I=0 hasta Arreglo.longitud – 1

Si Arreglo[I+1] < Arreglo[I]

Arreglo[I] <-> Arreglo[I+1] // Intercambiar

Contabilizar movimientos

Fin_Si

Fin_para

Hasta que no existan movimientos

Selección Los métodos de ordenación por selección se basan en dos principios básicos: Seleccionar el elemento más pequeño (o más grande) del arreglo. Colocarlo en la posición más baja (o más alta) del arreglo. A diferencia del método de la burbuja, en este método el elemento más pequeño (o más grande) es el que se coloca en la posición final que le corresponde. Ejemplo:

Algoritmo:

Para I=0 hasta Arreglo.longitud – 1

Para J= I+1 hasta Arreglo.longitud

Si Arreglo[J] < Arreglo[I]

Arreglo[I] <-> Arreglo[I+1] // Intercambiar

Fin_Si

Fin_para

Fin_para

Inserción El fundamento de este método consiste en insertar los elementos no ordenados del arreglo en subarreglos del mismo que ya estén ordenados. Dependiendo del método elegido para encontrar la posición de inserción tendremos distintas versiones del método de inserción.

Arreglo

0 7

1 4

2 9

3 2

4 5

5 10

6 1

7 6

8 8

9 3

Método shell El método de shell es una versión mejorada del método de inserción directa y recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. En el método de ordenación Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.

Ejemplo: Algoritmo:

Salto=Arreglo.longitud/2;

while (Salto>=1)

{

for (int Subarr = 0; Subarr < Salto; Subarr ++)

{

for (int i = Salto+Subarr ; i < Arreglo.Length; i += Salto)

{

int v = Arreglo[i];

int j = i - Salto;

while (j >= 0 && Arreglo[j] > v)

{

Arreglo[j + Salto] = Arreglo[j];

j-=Salto;

}

Arreglo[j + Salto] = v;

}

}

Salto /= 2;

}

Método QuickSort Es probablemente el más utilizado de los algoritmos de ordenación. Fue inventado por C.A.R. Hoare en 1960 y desde entonces se han propuesto mejoras. Es muy popular porque es relativamente fácil de implementar, ofrece buenos resultados generales, en muchos casos consume menos recursos otros método de ordenación, y está bien estudiado (ha sido expuesto a un minucioso análisis matemático que ha sido corroborado con amplia experiencia práctica).

0 1 2 3 4 5 6 7 8 9

Arreglo 7 4 9 2 5 10 1 6 8 3

El algoritmo consta de los siguientes pasos:

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. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

3. 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.

4. 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.

Ejemplo: Algoritmo:

//Recibe un vector de enteros y el índice del primer y último elemento

válido del mismo

Quicksort(int[] Arreglo, int primero, int ultimo){

int i=primero, j=ultimo

int pivote=Arreglo[(primero + ultimo) / 2]

int auxiliar

Realiza {

Mientras(Arreglo[i] < pivote){ i++ }

Mientras(Arreglo[j] > pivote){ j-- }

0 1 2 3 4 5 6 7 8 9

Arreglo 7 4 9 2 5 10 1 6 8 3

Si (i<=j)

Arreglo[i] <-> Arreglo[j]

i++

j--

Fin_Si

} mientras (i<=j);

Si (primero<j) Quicksort(Arreglo,primero, j)

Si (ultimo>i) Quicksort(Arreglo,i, ultimo)

}

Método Radix El método Radix es un algoritmo que ordena enteros procesando sus dígitos de forma individual. Radix no está limitado sólo a los enteros. La mayor parte de los métodos de ordenamiento representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.

radixSort(int[] arr){

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];

}

}


Elabore un programa en java que declare y cargue un arreglo de 10,000 elementos en forma aleatoria, lo ordene mediante los métodos:

Burbuja

Selección

Shell

Quicksort

Radix

Otro Y determine que algoritmo es mejor en base al que realice menos intercambios.

4.2. Métodos de búsqueda. Búsqueda Secuencial: La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado. 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. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero (o menos uno). Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo. El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Búsqueda Binaria La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.


Elabore un programa en java que declare y cargue en forma aleatoria dos arreglos, el primero de 10,000 elementos y el segundo de 1,000; y busque cada elemento del arreglo de 1,000 en el arreglo de 10,000 mediante la búsqueda Secuencia, Binaria y mediante el método BinarySearch; y determine que método es mejor en base al menor tiempo.

4.3. Recuperación de datos.


Investigar la recuperación de datos debido a:

Discos duros dañados o destruidos

Sistema de archivo dañado o corrupto

Borrado accidental

Reformateo accidental

Fallas en sistemas RAID

Pérdidas ocasionadas por Virus

Desastres Naturales (Inundación, fuego, rayos, etc.)

Estructuras y Organización de Datos Ver 2.0

Documents

Transcript of Estructuras y Organización de Datos Ver 2.0