• Author / Uploaded
• Marco De Alba Gonzalez

• Categories
• Estructura de datos de matriz
• Java (Lenguaje de programación)
• Puntero (Programación de computadoras)
• Matriz (Matemáticas)
• Áreas de la informática

Citation preview

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

Reticula Ingeniería en Tecnologias de la Informacion y Comunicaciones ITIC-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 • Investigar los conceptos fundamentales de las estructuras de datos. Identificar los conceptos básicos de las • Identificar las estructuras de datos lineales y estructuras de datos. no lineales de acuerdo al problema a Identificar las diferentes estructuras de datos, resolver. respecto a su implementación. • Identificar las estructuras de datos estáticas y dinámicas de acuerdo al problema a resolver. Unidad 2: Estructuras lineales Competencia específica a desarrollar Actividades de Aprendizaje • Elaborar mapas conceptuales para comprender los conceptos básicos, el funcionamiento y las aplicaciones que tienen Aplicar las principales estructuras de datos las estructuras de datos lineales. lineales. • Realizar ejercicios implementando estructuras de datos lineales. Unidad 3: Estructuras no lineales Competencia específica a desarrollar Actividades de Aprendizaje • Elaborar mapas conceptuales para comprender los conceptos básicos, el funcionamiento y las aplicaciones que tienen las estructuras de datos no lineales. Aplicar las principales estructuras de datos no • Realizar ejercicios de conversión de lineales. soluciones recursivas a soluciones iterativas y viceversa.  • Realizar ejercicios implementando estructuras de datos no lineales.

Unidad 4: Métodos de ordenamiento y búsqueda Competencia específica a desarrollar Actividades de Aprendizaje • 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 Clasificar técnicas para recuperación de problema que se desea resolver. información en dispositivos de almacenamiento • Elaborar un mapa conceptual que visualice primario y secundario. las diferencias entre los métodos en cuestión. Gestionar datos de forma óptima, para facilitar • Aplicar los algoritmos investigados en dos su procesamiento y la toma de decisiones. 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%

Los criterios de evaluación y acreditación respectiva. Fechas de Exámenes Examen 1er 2º. 3er Regularización o 2ª Oportunidad Calificación Final

Fecha

Unidades

Otras Observaciones: • • •

Personificador Hora de entrada Asistencia a clase

•

Derecho a examen

•

Revisión equitativa

Regularización Extraordinario I

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.

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

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

Palabra

Factor

Tamaño

Cualquier signo tipográfico. Puede ser una letra, un número, un signo de puntuación o un espacio. En gramática tradicional es cada uno de los segmentos limitados por pausas o espacios en la cadena hablada o escrita que puede aparecer libremente en cualquier posición y que está dotada de una función.

1.2.

Clasificación.

Predefinidos

Enteros Carácter Lógicos

Definidos por el usuario

Enumerados Subrango

float double

No Ordinal

Reales Cronológicos Apuntador, punteros o referencias

Cadenas

String StringBuffer

Estructura de datos

Arreglos Registros Listas Conjuntos Árboles Grafos

Ordinal

byte short int long char boolean

Simple

Tipos de datos Compuesto o Complejo

Abstractos

1.3.

Arrays Vector Class

abstract class

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 son estructura de datos no lineales y se pueden representar estructuras jerárquicas, direcciones o etiquetas de una manera organizada.

Tipo de datos en Java

Tipo

Tamaño en bits

boolean

1

char

16

byte

8

Rango de valores true o false Nota: El No. de bits puede variar según la plataforma ‘\u0000’ hasta ‘\uFFFF' Conjunto Unicode de ISO -128 a +127 -27 a 27 – 1

Tipo

Tamaño en bits

short

16

int

32

long

64

float

32

double

64

Rango de valores -32,768 a +32,767 -215 a 215 – 1 -2,147,483,648 a +2,147,483,647 -231 a 231 – 1 -9,223,372,036,854,775,808 a +9,223,372,036,854,775,807 -263 a 263 – 1 Rango negativo: -3.4028234663852886E+38 hasta -1.40129846432481707E-45 Rango positivo: 1.40129846432481707E-45 hasta 3.4028234663852886E+38 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 guión 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 mas 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. Tipo [ ]

identificador

; 

, Tipo

identificador [ ]

; 

, 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; float [] cal1, cal2, cal3, prom; char [] letra1, letra2[], letra3;

enteros en un arreglos de tipo int, x y y son variables tipo int. cal1, cal2, cal3 y prom son arreglos unidimensionales. letra1 y letra3 son arreglos de una dimension del tipo char y letra2 es una arreglo de arreglos de tipo char (una matriz).

Esto solo esta 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 multidimencionales 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; float [ ][ ] cal1, cal2, cal3, prom;

puestos en un arreglos de dos dimensiones del tipo int, x y y son variables tipo int. cal1, cal2, cal3 y prom son arreglos bidimensionales.

Como ya se menciono 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} }

tabla1[ ][ ]

int tabla1[ ][ ] = { {51, 24, 33}, {32, 23, 45} };

int tabla2[ ][ ] = { { 1, 2, 3, 4}, { 5, 6, 7, 8}, { 9, 10, 11, 12} };

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

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. 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 Fila 0 Fila 1 Fila 2

Columna 0 a[0][0] a[1][0] a[2][0]

Columna 1 a[0][1] a[1][1] a[2][1]

Columna 2 a[0][2] a[1][2] a[2][2]

Columna 3 a[0][3] a[1][3] 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];       4 

   

    3                             

               

              x 

               

        y 

     

5 

                 

            z 

   

                 

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) void println(cadena)

Despliega una cadena en pantalla. 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) Donde: 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) Donde: componentePadre

Mensaje Titulo TipodeMensaje

Determina la ventana en que se desplegara el mensaje, si es null, se despliega en la ventana por defecto. Objeto a desplegar Cadena de characters de la caja de dialogo Valor entero que determina que imagen se despliega según la siguiente tabla:

Tipo de cuadro de diálogo de mensaje

JOptionPane.ERROR_MESSAGE

JOptionPane.INFORMATION_MESSAGE JOptionPane.WARNING_MESSAGE

Icono

Descripción

Ventana de Error

Ventana Informativa Ventana de Advertencia

Tipo de cuadro de diálogo de mensaje

Icono

Descripción

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

JOptionPane.QUESTION_MESSAGE

JOptionPane.PLAIN_MESSAGE Clase Math

Sin Icono

Ventana estándar

La Clase Math proporciona una gran variedad matemáticos al igual que algunas constantes útiles. Campos

de

métodos

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

Métodos static double cos(double d)

Descripción Regresa el coseno del ángulo especificado en radianes. Regresa ed. Ejemplo:

static double exp(double d)

Math.exp(1.0) 2.71828 Math.exp(2.0) 7.38906 Regresa el entero más grande, menor o igual a d. Ejemplo:

static double floor(double d) Math.floor(9.3) Math.floor(-9.3)

static double log(double d)

9.0 -10.0

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:

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:

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

Regresa baseexp. Ejemplo: 52

static double random()

Math.max(2.3,12.7) Math.max(-2.3,-12.7)

Math.min(2.3,12.7) Math.min(-2.3,-12.7)

12.7 -2.3

2.3 -12.7

Regresa un número aleatorio comprendido entre 0.0 y 1.0. 0.0