Estructura De Datos

INSTITUTO TECNOLOGICO DE ESTUDIOS SUPERIORES DE LOS CABOS

“Antología y Practicas de la Materia de Estructura de Datos AED - 1026”
MC. ALFREDO ARCEO DE LA CRUZ 15 DE DICIEMBRE DEL 2011

INDICE
I INTRODUCCION A LAS ESTRUCTURAS DE DATOS
1.1. 1.2. 1.3. 1.4. 1.5. TIPOS DE DATOS ABSTRACTOS (TDA) MODULARIDAD USO DE LOS TDA MANEJO DE LA MEMORIA ESTATICA MANEJO DE LA MEMORIA DINAMICA 1 3 3 8 10II RECURSIVIDAD
2.1 DEFINICION 2.2 PROCEDIMIENTOS RECURSIVOS 2.3 EJEMPLOS DE CASOS RECURSIVOS 11 11 13

III ESTRUCTURAS LINEALES
3.1 LISTAS 3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 3.1.6 3.2 PILAS 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 3.3 COLAS 3.3.1 3.3.2 3.3.3 3.3.4 REPRESENTACION EN MEMORIA ESTATICA Y DINAMICA OPERACIONES BASICAS CON COLAS TIPOS DE COLAS: COLAS SIMPLE, COLA CIRCULAR Y COLAS DOBLESAPLICACIONES: COLAS DE PRIORIDAD 50 51 51 52 REPRESENTACION EN MEMORIA ESTATICA Y DINAMICA OPERACIONES BASICAS CON PILAS APLICACIONES NOTACION INFIJA O POSTFIJA RECURSIVIDAD CON AYUDA DE PILAS 41 42 46 48 50 OPERACIONES BASICAS TIPOS DE LISTAS LISTAS SIMPLEMENTE ENLAZADAS LISTAS DOBLEMENTE ENLAZADAS LISTAS CIRCULARES APLICACIONES 16 16 16 28 35 35

IV ESTRUCTURAS NO LINEALES
4.1 ÁRBOLES 4.1.1 4.1.24.1.3 4.1.4 4.1.5 GRAFOS 4.2.1 4.2.2 CONCEPTO DE ÁRBOL CLASIFICACIÓN DE ÁRBOLES OPERACIONES BÁSICAS SOBRE ÁRBOLES BINARIOS APLICACIONES ARBOLES BALANCEADOS TERMINOLOGIA DE GRAFOS OPERACIONES BÁSICAS SOBRE GRAFOS 59 60 61 65 68 70 71

4.2

V METODOS DE ORDENAMIENTO
5.1 Algoritmos de Ordenamiento Interno
5.1.1 Burbuja 5.1.2 QuickSort 5.1.3 ShellSort 5.1.4 Radix 5.2 Algoritmos de OrdenamientoExterno 5.2.1 Intercalación 5.2.2 Mezcla Directa 5.2.3 Mezcla Natural 78 81 82 84 87 90 91

VI METODOS DE BUSQUEDA
6.1 BUSQUEDA SECUENCIAL 6.2 BUSQUEDA BINARIA 6.3 BUSQUEDA POR FUNCIONES DE HASH 93 93 94

VII ANALISIS DE LOS ALGORITMOS
7.1 COMPLEJIDAD EN EL TIEMPO 7.2 COMPLEJIDAD EN EL ESPACIO 7.3 EFICIENCIA DE LOS ALGORITMOS 97 99 99

INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS

1.1 TIPOS DEDATOS ABSTRACTOS Con mucha frecuencia se utilizan los términos TDA y Abstracción de Datos de manera equivalente, y esto es debido a la similitud e interdependencia de ambos. Sin embargo, es importante definir por separado los dos conceptos. Los Lenguajes de Programación Orientados a Objetos son lenguajes formados por diferentes métodos o funciones y que son llamados en el orden en que el programalo requiere, o el usuario lo desea. La abstracción de datos consiste en ocultar las características de un objeto y obviarlas, de manera que solamente utilizamos el nombre del objeto en nuestro programa. Esto es similar a una situación de la vida cotidiana. Cuando yo digo la palabra “perro”, usted no necesita que yo le diga lo que hace el perro. Usted ya sabe la forma que tiene un perro y tambiénsabe que los perros ladran. De manera que yo abstraigo todas las características de todos los perros en un solo término, al cual llamo “perro”. A esto se le llama ‘Abstracción’ y es un concepto muy útil en la programación, ya que un usuario no necesita mencionar todas las características y funciones de un objeto cada vez que éste se utiliza, sino que son declaradas por separado en el programa ysimplemente se utiliza el término abstracto (“perro”) para mencionarlo. En el ejemplo anterior, “perro” es un Tipo de Dato Abstracto y todo el proceso de definirlo, implementarlo y mencionarlo es a lo que llamamos Abstracción de Datos. Vamos a poner un ejemplo real de la programación. Supongamos que en algún Lenguaje de Programación Orientado a Objetos un pequeño programa saca el área de unrectángulo de las dimensiones que un usuario decida. Pensemos también que el usuario probablemente quiera saber el área de varios rectángulos. Sería muy tedioso para el programador definir la multiplicación de ‘base’ por ‘altura’ varias veces en el programa, además que limitaría al usuario a sacar un número determinado de áreas. Por ello, el programador puede crear una función denominada ‘Área’, la cual...