Curso de algoritmos y programación a fondo. Implementaciones en C++ 2ED

Descripción

Curso de Algoritmos y Programación a Fondo es un libro diseñado para enseñar a programar desde cero, que propone crear algoritmos tejiendo capas progresivas de software. Entendiendo que un programa se erige sobre una construcción previa, la cual se apoya sobre una base anterior, y así sucesivamente.
Cada capítulo está dividido en lecciones. Cada lección es una clase del curso, cuyo contenido tiene doble soporte: el libro en sí mismo, y un video donde el propio autor explica los temas de la lección.
El hecho de comenzar desde cero no será un impedimento para avanzar hasta cubrir cuestiones verdaderamente complejas, como el desarrollo de un programa compresor/descompresor de archivos basado en el algoritmo de Huffman.
A lo largo de los diferentes capítulos se estudian recursos y técnicas de programación, y se desarrollan funciones y TAD para conformar una biblioteca (API) que el estudiante podrá utilizar para resolver una gran cantidad de ejercicios y problemas.
El lector podrá validar los conocimientos adquiridos respondiendo las autoevaluaciones que se proponen al final de cada lección, recibiendo un feedback que le permitirá determinar si debe releer la lección (o parte de ésta) antes de pasar a la siguiente.
En esta nueva edición se profundiza especialmente el análisis y la resolución de problemas. Para esto se propone un caso testigo y diversas variantes de éste, que permiten identificar diferentes tipos de problema para estudiar y discutir estrategias de solución según cuál sea el tipo de problema identificado.

Pablo Augusto Sznajdleder es Ingeniero en Sistemas de Información y Magister en la misma materia. Su tesis de maestría propone una metodología para implementar transferencias de conocimiento mediadas por tecnologías informáticas.
Es profesor universitario en las asignaturas de “Algoritmos y estructura de datos” y “Patrones algorítmicos para estructuras avanzadas”, ambas en la Universidad Tecnológica Nacional, Facultad Regional Buenos Aires (UTN.BA).
Además de la presente obra, es autor de “Algoritmos a fondo”, “JEE a fondo”, “Programación estructurada a fondo” y “Programación orientada a objetos a fondo” entre otras.
Desde 1996 se desempeña como instructor y consultor en tecnologías Java proveyendo servicios de capacitación, desarrollo y coaching a las principales empresas del país.

Prólogo XV

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. La computadora 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? 145

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. Archivos de novedades y consultas 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 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.1. Ordenamiento en memoria 162
4.3.2. Ordenamiento por indexación 163
4.3.1. Ordenamiento en memoria 162
4.4. Algoritmos Tools 163
4.5. Caso testigo 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 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 directa, con corte de control (versión 13) 216
4.5.14. Indexación directa 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

CAPÍTULO 5
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 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? 289

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