Estructuras de datos - Un enfoque orientado a objetos

APUNTES DE ESTRUCTURAS DE DATOS

Un enfoque orientado a objetos

RODOLFO E. ARANA GONZALES

SASCI

01/01/2009

APUNTES DE ESTRUCTURAS DE DATOS

Un enfoque orientado a objetos

RODOLFO E. ARANA GONZALES

APUNTES DE ESTRUCTURAS DE DATOS

Un enfoque orientado a objetos

RODOLFO E. ARANA GONZALES

SASCI

01/01/2009

APUNTES DE ESTRUCTURAS DE DATOS

Un enfoque orientado a objetos

RODOLFO E. ARANA GONZALES

Prefacio

Este material ha sido escrito en forma paralela al desenvolvimiento de cursos de Estructuras de datos dictados en las universidades de Santa Cruz de la Sierra, con el afán de proporcionar al estudiante una guía para aprender estructuras de datos en forma práctica. Asimismo, se quiere presentar y dar a entender conceptos, que a menudo, no se abordan con la claridad necesaria, como ser el manejo de punteros. También se aborda la temática de las estructuras de datos desde un enfoque orientado a objetos, explicando que esta metodología es una especie de “evolución natural” de los Tipos Abstractos de Datos en cuanto a su implementación.

Estos apuntes están dedicados a todos aquellos que están dispuestos a sacrificar horas de descanso o diversión, con el fin de superarse permanentemente, hacerse mejores para hacer un mundo mejor.

El autor

Tabla de contenido

PREFACIO 3

1. ESTRUCTURAS Y ABSTRACCIÓN DE DATOS 6

1.1. INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS 6

1.2. ABSTRACCIÓN DE DATOS 6

1.2.1 ESTRUCTURA DE DATOS 2

1.3. CLASIFICACIÓN DE LAS ESTRUCTURAS DE DATOS (VILLALOBOS, 1996) 3

1.4. TIPOS ABSTRACTOS DE DATOS 4

Operaciones con arreglos 6

1.6 BÚSQUEDA Y CLASIFICACIÓN DE ARREGLOS 6

Búsqueda secuencial 6

Búsqueda binaria 7

Clasificación 8

Método de intercambio o de Burbuja 9

Método de la Baraja 9

Metodo QuickSort 10

1.7 COMPLEJIDAD DE ALGORITMOS 11

MOTIVACIÓN 13

INSTRUCCIONES DE CONTEO 13

ANÁLISIS WORST-CASE O DEL PEOR CASO 15

ASYMPTOTIC BEHAVIOR O COMPORTAMIENTO ASINTÓTICO 15

COMPLEJIDAD 18

2. ESTRUCTURA DE LENGUAJES DE PROGRAMACIÓN ORIENTADOS A OBJETO. 23

2.1 . ASPECTOS GENERALES DE LOS LENGUAJES 23

2.2 LENGUAJES ORIENTADOS A OBJETO 25

PROGRAMACIÓN ORIENTADA A OBJETO 26

2.2. ESTRUCTURAS DE DATOS ORIENTADAS A OBJETOS 27

2.4. RECURSIVIDAD Y LENGUAJES DE PROGRAMACIÓN OO 28

Concepto de Recursividad 28

CASO BASE 28

CASO GENERAL 29

1. Cálculo de la potencia 31

2. La suma de forma recursiva 31

3. Búsqueda lineal recursiva (con dos casos base) 31

4. Búsqueda Binaria recursiva 32

3. ALMACENAMIENTO ESTÁTICO EN SECUENCIA – LISTAS 33

3.1 ASPECTOS GENERALES DE LISTAS 33

3.2. PILAS 33

APLICACIÓN DE PILA: EVALUACIÓN DE EXPRESIONES 34

PROCESO PARA EVALUACIÓN DE UNA EXPRESIÓN ARITMÉTICA 35

TRANSFORMACIÓN DE INFIJA A POSTFIJA 35

3.3. COLAS 37

OPERACIONES BÁSICAS 38

IMPLEMENTACIÓN DE LA OPERACIONES 38

Aplicaciones 39

IMPLEMENTACIÓN DE COLAS EN C++ 39

Tipos de colas 40

3.4. PROBLEMAS DE APLICACIÓN DE PILAS, COLAS Y LISTAS 41

4. ALMACENAMIENTO DINÁMICO 44

4.1 MANEJO DINÁMICO DE LA MEMORIA – LOS PUNTEROS 44

¿Cómo se almacena una variable? 44

¿Qué son los punteros? 46

4.2. LISTAS ENCADENADAS 48

4.3 DISEÑO E IMPLEMENTACIÓN DINÁMICA DE LISTAS ENCADENADAS 49

Estructura de Nodo 49

Estructura de Lista encadenada 50

Esquema y diseño de una lista enlazada 50

Operación de Recorrido 52

Operación de Inserción 53

Operación de Borrado 54

Operación de Búsqueda 54

4.4. IMPLEMENTACIÓN DINÁMICA DE ESTRUCTURAS DE DATOS 54

Implementación de pilas con punteros 54

5. ARBOLES 55

5.1 ARBOLES BINARIOS 55

Definición de árbol 56

Formas de representación 56

Declaración de árbol binario 57

Recorridos sobre árboles binarios 57

Construcción de un árbol binario 59

5.2 ÁRBOL BINARIO DE BÚSQUEDA 61

Operaciones básicas sobre árboles binarios de búsqueda 62

Ejercicio resuelto 65

Aplicación práctica de un árbol binario de búsqueda 65

Ejercicios propuestos 66

5.3. ÁRBOLES B 68

Utilización de los Arboles B 68

Funcionamiento 69

¿Qué es un Arbol B? 71

Costos 75

Casos especiales 76

Conclusión 77

TRABAJOS PRACTICOS 78

BIBLIOGRAFÍA 82

1. Estructuras y abstracción de datos

1.1. Introducción a las estructuras de datos

Los programas están constituidos fundamentalmente por algoritmos y estructuras de datos. Esto significa que los algoritmos se ejecutan sobre estas estructuras de datos. Esto permite ver que las estructuras de datos son una parte fundamental de la programación de computadoras, en particular; y del procesamiento de información, en general

Una estructura de datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen sobre ella.

Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera para representar un comportamiento. Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estará muy relacionada.

1.2. Abstracción de datos

El procesamiento de información en una computadora requiere hacer una tarea llamada abstracción de datos, que consiste en “ver” las cosas del mundo real en una forma integral, en el sentido de que se ignoran algunas “propiedades irrelevantes” de los objetos reales, es decir, se simplifican. De este modo se hace una selección de los datos más representativos de la realidad a partir de los cuales se los pueda obtener un “modelo del objeto” para trabajar el computador y obtener determinados resultados.

Así los lenguajes de programación proporcionan una serie de tipos de datos simples, como son los números enteros, caracteres, números reales. En realidad los lenguajes suministran un modelo de datos que son un subconjunto finito de éstos, pues la memoria del ordenador es finita. Los punteros o apuntadores (si los tiene) son también un tipo de datos. El tamaño de cada tipo de datos depende de la máquina y del compilador sobre los que se trabaja (jaime, 2002)

En principio, conocer la representación interna de estos tipos de datos no es necesaria para realizar un programa, pero sí puede afectar en algunos casos al rendimiento. Sin embargo, cuando se trata con problemas donde el tiempo o el espacio de almacenamiento es primordial, habrá que entender en detalle no solo los alcances de los tipos de datos sino también de su forma de almacenamiento.

1.2.1 Estructura de datos

En términos formales, una Estructura de Datos d se define como una tripleta compuesta por un conjunto de dominios D, un conjunto de funciones u operaciones F y un conjunto de axiomas A.

donde:

D El conjunto de dominios consiste en los tipos de datos primitivos que utiliza la estructura

F Es el conjunto de funciones que manipulan los datos

A Describen el significado de las funciones

La definición de una Estructura de Datos posee un primer nivel de abstracción en donde simplemente se identifica la colección de elementos a agrupar y sus operaciones de acceso. En un segundo nivel, el de implementación, ya pensamos en un lenguaje de programación específico y es ahí donde surgen preguntas como ¿cuál es la estructura óptima? o ¿qué funciones y/o procedimientos definir? Finalmente la estructura de datos se define en un tercer nivel llamado de aplicación, donde se especifica como será utilizada en programas de aplicación .

Ejemplo: Suponga que se

...