CURSO DE ALGORITMOS Y PROGRAMACIÓN A FONDO 2ED

Prólogo ......................................................... XV
Agradecimientos ......................................... XVII
CAPÍTULO 1
Introducción al diseño de algoritmos y
programación .............................................. 1
1.1. Lección 1 ............................................... 1
1.1.1. ¿Qué es un algoritmo? .................... 1
1.1.2. Lenguaje algorítmico ....................... 4
1.1.3. Recursos de programación ............. 4
1.1.3.1. El ordenador .................................. 4
1.1.3.2. Operaciones aritméticas
y expresiones lógicas .................................. 4
1.1.3.3. Lenguaje de programación .......... 5
1.1.3.4. Programa ....................................... 5
1.1.3.5. Variables y tipos de dato .............. 6
1.1.3.6. Convención de nombres
de variables .................................................... 7
1.1.3.7. Consola .......................................... 8
1.1.3.8. Compilador .................................... 8
1.1.3.9. Entorno Integrado de
desarrollo ..................................................... 9
1.1.4. Teorema de la programación
estructurada ................................................ 9
1.1.4.1. Acción simple ................................ 10
1.1.4.2. Acción condicional ........................ 11
1.1.4.3. Acción iterativa ............................. 15
1.1.4.4. Acciones de única entrada
y única salida ............................................... 19
1.1.5. Más recursos de programación ...... 20
1.1.5.1. Contadores y acumuladores ........ 20
1.1.5.2. Prueba de escritorio ..................... 20
1.1.5.3. Operadores aritméticos ................ 21
1.1.5.4. Otras operaciones matemáticas .. 23
1.1.5.5. Operadores y expresiones
lógicas ........................................................... 24
1.1.5.6. Operadores relacionales ............... 25
1.1.5.7. Operadores relacionales
y cadenas de caracteres ............................. 26
1.1.6. Análisis de ejercicios y problemas ... 27
1.1.6.1. Datos de entrada, de contexto
y de salida ..................................................... 27
1.1.6.2. Procesos para transformar
la entrada en salida ..................................... 28
1.1.7. Tipos de problema ............................ 28
1.1.7.1. Problemas de registro simple y
problemas de múltiples registros ............... 29
1.1.7.2. Multiplicidad ................................... 30
1.1.7.3. Registros y tablas .......................... 30
1.1.7.4. Problemas de procesamiento
horizontal y procesamiento vertical ............ 32
1.1.7.5. Problemas de corte de control ..... 33
1.1.8. Autoevaluación y ejercicios .............. 35
1.2. Lección 2 ............................................... 35
1.2.1. Tipo de dato ....................................... 36
1.2.1.1. Tipos enteros ................................. 37
1.2.1.2. Tipos flotantes ............................... 38
1.2.1.3. Tipos alfanuméricos ...................... 39
1.2.1.4. Tipos lógicos ................................... 40
1.2.1.5. Tipo de dato nulo ........................... 40
1.2.1.6. Tipos de dato primitivos y tipos
definidos por el programador ...................... 40
1.2.2. Alcance de una variable ................... 41
1.2.3. Metodología Top-Down ..................... 43
1.2.3.1. Funciones ....................................... 43
1.2.3.2. Prototipo de una función .............. 46
1.2.3.3. Compilar un programa que
invoca funciones .......................................... 47
1.2.3.4. Reusabilidad del código ................ 48
1.2.3.5. Legibilidad del código fuente ........ 51
1.2.3.6. Bibliotecas de funciones ............... 51
1.2.3.7. Convención de nombres de
funciones ......................................................... 51
1.2.3.8. Parámetros y argumentos ............ 52
1.2.3.9. Parámetros por valor y
referencia ...................................................... 52
1.2.3.10. Variables locales ......................... 54
1.2.4. Autoevaluación y ejercicios .............. 54
1.3. Lección 3 ............................................... 55
1.3.1. Estructuras ........................................ 55
1.3.1.1. Inicialización de una estructura ... 56
1.3.1.2. Convención de nombres de
estructuras ................................................... 57
1.3.1.3. Función de inicialización
de una estructura......................................... 57
1.3.1.4. Estructuras anidadas .................... 58
1.3.2. Tipo Abstracto de Dato (TAD) .......... 59
1.3.2.1. Usuario del TAD ............................ 62
1.3.2.2. Inicialización de un TAD ............... 62
1.3.2.3. Sobrecarga de funciones ............. 62
1.3.3. Autoevaluación y ejercicios .............. 63
1.4. ¿Qué sigue? .......................................... 63
CAPÍTULO 2
Cadenas de caracteres y estructura
de datos ....................................................... 65
2.1. Lección 4 ............................................... 65
2.1.1. Carácter ............................................. 65
2.1.2. Cadena de caracteres ...................... 67
2.1.2.1. Caracteres especiales y
carácter de escape ...................................... 67
2.1.2.2. Carácter nulo que indica
el final de una cadena ................................. 68
2.1.2.3. Acceso directo a los caracteres
de una cadena ............................................. 68
2.1.2.4. Longitud de una cadena ............... 69
2.1.2.5. Operadores aritméticos unarios ... 69
2.1.2.6. Ciclo iterativo for ............................ 70
2.1.2.7. Concatenar cadenas de
caracteres .................................................... 71
2.1.2.8. Operadores relacionales
aplicados a cadenas .................................... 71
2.1.2.9. Función de comparación .............. 72
2.1.2.10. If-inline ......................................... 74
2.1.3. Biblioteca de funciones y API ........... 76
2.1.3.1. Tratamiento de cadenas
de caracteres ................................................ 77
2.1.3.2. Actividad práctica: API de
tratamiento de cadenas de caracteres ...... 77
2.1.4. Argumentos en línea de
comandos ..................................................... 79
2.1.5. Autoevaluación y ejercicios .............. 80
2.2. Lección 5 ............................................... 81
2.2.1. Tratamiento de tokens ..................... 81
2.2.2. Actividad práctica: API de
tratamiento de tokens ................................. 81
2.2.3 Autoevaluación y ejercicios ............... 84
2.3. Lección 6 ............................................... 84
2.3.1. Funciones como argumentos
de otras funciones ....................................... 85
2.3.2. Tipo de dato genérico (template) .... 87
2.3.3. Autoevaluación y ejercicios .............. 93
2.4. Lección 7 ............................................... 93
2.4.1. Colecciones ....................................... 94
2.4.2. TAD Coll .............................................. 95
2.4.2.1. Ejemplo de uso .............................. 96
2.4.2.2. Estructura del TAD Coll ................. 98
2.4.2.3. Actividad práctica: API del
TAD Coll ........................................................ 98
2.4.3. Autoevaluación y ejercicios .............. 101
2.5. Lección 8 ............................................... 101
2.5.1. Ordenamiento ................................... 101
2.5.1.1. Ordenamiento por inserción
simple ............................................................ 101
2.5.1.2. Ordenamiento por burbujeo ......... 102
2.5.1.3. Ordenamiento por burbujeo
mejorado ....................................................... 103
2.5.1.4. Ordenamiento por inserción
avanzado ....................................................... 104
2.5.2. Búsqueda........................................... 105
2.5.2.1. Búsqueda lineal ............................ 105
2.5.2.2. Búsqueda binaria ......................... 106
2.5.3. Autoevaluación y ejercicios ............. 108
2.6. Lección 9 ............................................... 108
2.6.1. Estructura de datos (parte 1) ........... 109
2.6.1.1. Estructuras estáticas y
dinámicas ..................................................... 109
2.6.1.2. Estructura de datos como
cimiento del algoritmo ................................. 110
2.6.1.3. Colección de estructuras .............. 110
2.6.1.4. Colección de colecciones .............. 116
2.6.1.5. Colecciones de estructuras
que tienen colecciones ................................ 119
2.6.2. Autoevaluación y ejercicios .............. 122
2.7. ¿Qué sigue? .......................................... 122
CAPÍTULO 3
Archivos ......................................................... 123
3.1. Lección 10 ............................................ 123
3.1.1. Introducción ....................................... 123
3.1.1.1. Archivo ............................................ 123
3.1.1.2. Tipos de archivo ............................. 124
3.1.1.3. Archivos binarios ........................... 124
3.1.1.4. Archivos de texto ........................... 124
3.1.2. Gestión de archivos .......................... 125
3.1.2.1. Funciones de biblioteca ................ 125
3.1.2.2. Grabar y leer datos ........................ 125
3.1.2.3. Archivo secuencial ......................... 127
3.1.2.4. Archivos de registros de
longitud fija ................................................... 127
3.1.2.5. Big-endian y Little-endian ............. 128
3.1.2.6. Archivos de registros de
longitud variable ........................................... 129
3.1.2.7. Archivos de estructuras ................ 129
3.1.2.8. Posicionamiento directo ............... 132
3.1.2.9. Posicionamiento directo
en registros ................................................... 133
3.1.2.10. Eliminar registros físicamente ... 134
3.1.2.11. Eliminar registros lógicamente .. 134
3.1.2.12. Modificar registros ...................... 136
3.1.2.13. Longitud de un archivo ............... 137
3.1.2.14. Cantidad de registros .................. 137
3.1.2.15. Restricciones ............................... 137
3.1.3. Actividad práctica: API para el
tratamiento de archivos de registros ......... 138
3.1.4. Ejemplos de uso de las funciones
de la API ........................................................ 139
3.1.4.1. Escribir y leer caracteres .............. 139
3.1.4.2. Escribir y grabar números
enteros (short) .............................................. 139
3.1.4.3. Escribir y leer estructuras
(Persona) ...................................................... 139
3.1.4.4. Baja lógica ...................................... 140
3.1.5. Autoevaluación y ejercicios .............. 141
3.2. Lección 11 ............................................ 141
3.2.1. Operadores de bit ............................. 141
3.2.1.1. Operadores de desplazamiento ... 141
3.2.1.2. Bases numéricas 8 (octal)
y 16 (hexadecimal) ...................................... 142
3.2.1.3. Operadores lógicos ........................ 143
3.2.1.4. Máscara de bit ............................... 144
3.2.2. Actividad práctica: TAD BitWriter y
BitReader ...................................................... 145
3.2.3. Autoevaluación y ejercicios .............. 146
3.3. ¿Qué sigue? .......................................... 146
CAPÍTULO 4
Resolución de problemas ........................... 147
4.1. Cómo analizar un problema ................ 148
4.1.1. Contexto, relevamiento y
enunciado del problema.............................. 148
4.1.2. Datos persistentes ............................ 149
4.1.2.1. Archivos de consulta ..................... 149
4.1.2.2. Archivos de novedades ................. 149
4.1.3. Estrategia ........................................... 150
4.2. Tipos de problema ................................ 150
4.2.1. Problemas de corte de control ......... 150
4.2.2. Problemas de apareo de archivos ... 151
4.2.3. Problemas de procesamiento
directo ........................................................... 153
4.3. Gestión de archivos y persistencia
de datos ........................................................ 154
4.3.1. Restricciones ..................................... 154
4.3.2. Búsqueda sobre archivos ................. 154
4.3.2.1. Subir el archivo a la memoria,
en una colección de objetos ....................... 155
4.3.2.2. Búsqueda binaria sobre
un archivo ..................................................... 157
4.3.2.3. Indexar un archivo ......................... 159
4.3.3. Ordenar archivos ............................... 162
4.3.3.1. Ordenamiento en la memoria....... 162
4.3.3.2. Ordenamiento por indexación ...... 163
4.4. Algoritmos Tools ................................... 164
4.5. Caso de prueba .................................... 165
4.5.1. Corte de control (versión 1) ............. 165
4.5.2. Corte de control, con salida
bufferizada (versión 2) ................................. 168
4.5.3. Descubrimiento (versión 3) .............. 170
4.5.4. Archivos de consultas en la
memoria (versión 4) ..................................... 175
4.5.5. Descubrimiento, otro caso
(versión 5) ..................................................... 181
4.5.6. Actualizar registros (versión 6) ........ 183
4.5.7. Colección de colecciones
(versión 7) ..................................................... 188
4.5.8. Colección de colecciones, con
descubrimiento (versión 8) ......................... 192
4.5.9. Apareo de archivos (versión 9) ........ 197
4.5.10. Apareo de archivos, con corte
de control (versión 10) ................................ 202
4.5.11. Búsqueda binaria sobre el
archivo de consulta (versión 11) ................ 208
4.5.12. Indexación directa (versión 12) ..... 213
4.5.13. Indexación indirecta, con corte
de control (versión 13) ................................ 216
4.5.14. Indexación indirecta múltiple
(versión 14) .................................................. 220
4.5.15. Ordenar y depurar un archivo
(versión 15) .................................................. 225
4.6. Autoevaluación y ejercicios ................. 230
4.7 ¿Qué sigue? ........................................... 231
Estructuras indexadas, lineales y
gestión de memoria .................................... 233
5.1. Lección 12 ............................................ 233
5.1.1. Array ................................................... 233
5.1.1.1. Capacidad del array ...................... 234
5.1.1.2. Inicializar un array a partir de
un conjunto de valores ................................ 235
5.1.1.3. Inicialización programática ........... 235
5.1.1.4. Longitud del array.......................... 236
5.1.1.5. Arrays de estructuras .................... 236
5.1.1.6. Arrays multidimensionales ........... 238
5.1.2. Operaciones sobre arrays ................ 239
5.1.2.1. Agregar un elemento al final
de un array ................................................... 239
5.1.2.2. Determinar si el array contiene
un elemento especificado ........................... 240
5.1.2.3. Insertar un elemento en una
determinada posición .................................. 241
5.1.2.4. Eliminar el elemento ubicado
en una determinada posición ..................... 242
5.1.3. Actividad práctica: API de
operaciones sobre arrays ............................ 244
5.1.4. Autoevaluación y ejercicios .............. 245
5.2. Lección 13 ............................................ 245
5.2.1. Gestión de memoria ......................... 245
5.2.1.1. Punteros ......................................... 246
5.2.1.2. Operador de dirección (&) ............. 247
5.2.1.3. Operador de dirección
o contenido (*) ............................................. 247
5.2.1.4. Funciones que reciben punteros
como parámetros ......................................... 248
5.2.1.5. Punteros a punteros ...................... 249
5.2.1.6. Punteros a estructuras y
operador -> (flecha) ..................................... 249
5.2.1.7. Punteros y arrays ........................... 250
5.2.1.8. Aritmética de direcciones ............. 251
5.2.1.9. Memoria estática ........................... 252
5.2.1.10. Memoria dinámica ...................... 252
5.2.1.11. Crear arrays dinámicamente ..... 255
5.2.1.12. Redimensionar un array ............. 256
5.2.1.13. Crear matrices
dinámicamente ............................................ 257
5.2.2. Actividad práctica: TAD Array ........... 258
5.2.3. Actividad práctica: TAD Map ............ 259
5.2.4. Autoevaluación y ejercicios .............. 260
5.3. Lección 14 ............................................ 261
5.3.1. Nodo ................................................... 261
5.3.2. Lista enlazada (linked list) ............... 262
5.3.2.1. Recorrer una lista enlazada .......... 262
5.3.2.2. Agregar un valor al final de
una lista enlazada ........................................ 264
5.3.2.3. Liberar la memoria que ocupa
la lista ............................................................ 266
5.3.2.4. Determinar si la lista contiene
un valor especificado ................................... 267
5.3.2.5. Insertar un valor en una lista
ordenada ....................................................... 267
5.3.2.6. Eliminar un elemento de la lista... 270
5.3.3. Actividad práctica: API de
operaciones sobre listas enlazadas ........... 271
5.3.4. Pila (stack) ......................................... 273
5.3.4.1. Apilar un elemento (push)............. 273
5.3.4.2. Desapilar un elemento (pop) ........ 274
5.3.4.3. Determinar si la pila tiene
elementos ..................................................... 275
5.3.4.4. Ejemplo de uso .............................. 275
5.3.5. Actividad práctica: API de
operaciones sobre pilas (extensión) ........... 275
5.3.6. Cola (queue) ...................................... 275
5.3.6.1. Encolar un elemento (enqueue) ... 276
5.3.6.2. Desencolar un elemento
(dequeue) ...................................................... 277
5.3.6.3. Determinar si la cola tiene
elementos ..................................................... 278
5.3.6.4. Implementación sobre una
lista circular .................................................. 279
5.3.7. Actividad práctica: API de
operaciones sobre colas (extensión) .......... 281
5.3.8. Actividad práctica: TAD List,
Stack y Queue............................................... 282
5.3.9. Autoevaluación y ejercicios .............. 283
5.4. Lección 15 ............................................ 283
5.4.1. Estructura de datos (parte 2) ........... 284
5.4.1.1. Colección de estructuras .............. 284
5.4.1.2. Colección de colecciones .............. 285
5.4.1.3. Colección de estructuras que
tienen colecciones ....................................... 286
5.4.2. Autoevaluación y ejercicios .............. 288
5.5. ¿Qué sigue? .......................................... 288
CAPÍTULO 6
Algoritmo de Huffman. Ejercicio
integrador .................................................... 289
6.1. Lección 16 ............................................ 289
6.1.1. Introducción ....................................... 289
6.1.2. Alcance del ejercicio ......................... 291
6.1.3. Algoritmo de Huffman....................... 291
6.1.3.1. Paso 1 ? Contar cuántas veces
aparece cada byte ....................................... 293
6.1.3.2. Paso 2 ? Crear una lista
enlazada ....................................................... 294
6.1.3.3. Paso 3 ? Convertir la lista en
un árbol binario (Árbol Huffman) ................ 294
6.1.4. Árbol Huffman ................................... 297
6.1.4.1. Características ............................... 297
6.1.4.2. Códigos Huffman ........................... 297
6.1.4.3. Longitud máxima de un código
Huffman ........................................................ 298
6.1.5. Implementación del ejercicio ........... 298
6.1.5.1. Setup .............................................. 299
6.1.5.2. TAD HuffmanTree .......................... 299
6.1.5.3. Estructura HuffmanTreeInfo ......... 300
6.1.5.4. Recopilación de los códigos
Huffman ........................................................ 300
6.1.5.5. Compresión .................................... 301
6.1.5.6. Estructura del archivo
comprimido (.huf) ......................................... 302
6.1.5.7. Descompresión .............................. 302
6.1.6. Ejemplo .............................................. 303
6.2. ¿Qué sigue? .......................................... 304