Hola

Escuela Polit´ cnica Superior de Alcoy e

Ingenier´a T´ cnica en Inform´ tica de ı e a Gesti´ n o

Estructuras de Datos y Algoritmos

Apuntes Teor´a ı
Francisco Nevado, Jordi Linares

´ Indice general
1. Tipos Abstractos de Datos 1.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 1.2. Ejemplo: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.Gesti´ n Din´ mica de Memoria. Punteros o a 2.1. Gesti´ n din´ mica de memoria. . . . . o a 2.1.1. Variables est´ ticas . . . . . . a 2.2. Punteros . . . . . . . . . . . . . . . . 2.2.1. Punteros y vectores . . . . . . 2.3. Variables din´ micas . . . . . . . . . . a 2.4. Ejercicios . . . . . . . . . . . . . . . 5 5 6 8 8 8 9 11 13 19 20 20 20 21 22 24 26 27 28 32 34 34 35 38 42 46

. . . . . .. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3. Estructuras de Datos Lineales 3.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 3.2. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.1. Operaciones sobre pilas . . . . . . . . . . . . . . . . . 3.2.2. Representaci´ n vectorial de pilas . . . . . . . . . . . . . o 3.2.3. Representaci´ n enlazada de pilas con variable din´ mica o a 3.3. Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. Operaciones sobre colas . . . . . . . . . . . . . . . . . 3.3.2. Representaci´ n vectorial de colas . . . . . . . . . .. . o 3.3.3. Representaci´ n enlazada de colas con variable din´ mica o a 3.4. Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1. Operaciones sobre listas . . . . . . . . . . . . . . . . . 3.4.2. Representaci´ n vectorial de listas . . . . . . . . . . . . o 3.4.3. Representaci´ n enlazada de listas con variable din´ mica o a 3.4.4. Representaci´ n enlazada de listas convariable est´ tica . o a 3.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

1

4. Divide y vencer´ s a 4.1. Esquema general de “Divide y Vencer´ s” . . . . . a 4.2. Algoritmos de ordenaci´ n . . . . . . . . . . . . . . o 4.2.1. Inserci´ n directa . . . . . . . . . . . . . . o 4.2.2. Selecci´ n directa . . . . . . . . . . . . . . o 4.2.3.Ordenaci´ n por mezcla o fusi´ n: Mergesort o o 4.2.4. Algoritmo por partici´ n: Quicksort . . . . o 4.2.5. Comparaci´ n emp´rica de los algoritmos . o ı 4.3. B´ squeda del k-´ simo menor elemento . . . . . . . u e 4.3.1. An´ lisis de la eficiencia . . . . . . . . . . a 4.4. B´ squeda binaria . . . . . . . . . . . . . . . . . . u 4.4.1. Eficiencia del algoritmo . . . . . . . . . . 4.5. C´ lculo dela potencia de un n´ mero . . . . . . . . a u 4.5.1. Algoritmo trivial . . . . . . . . . . . . . . 4.5.2. Algoritmo “divide y vencer´ s” . . . . . . . a 4.6. Otros problemas . . . . . . . . . . . . . . . . . . . 4.7. Ejercicios . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . .. . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

67 67 68 68 72 74 82 93 94 95 98 99 101 101 102 103 104 114 114 116 117 117 119 122 122 125 128 129 131 140 140 140 140 141 141 143 143 144

´ 5. Arboles 5.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 5.2.Recorrido de arboles . . . . . . . . . . . . . . . . . . . . . . . . ´ 5.3. Representaci´ n de arboles . . . . . . . . . . . . . . . . . . . . . o 5.3.1. Representaci´ n mediante listas de hijos . . . . . . . . . . o 5.3.2. Representaci´ n “hijo m´ s a la izquierda − hermano dereo a cho” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 5.4. Arboles binarios . . . . . . . . . . . . . . . . . ....