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? .......................................... 304Si desea adentrarse en el mundo de la programación desde cero y avanzar progresivamente hasta cubrir los aspectos más complejos de la programación en C++, mediante el análisis y desarrollo de gran cantidad de problemas algorítmicos de todos los niveles, este libro será su gran aliado. Curso de algoritmos y programación a fondo presenta 16 lecciones, distribuidas en 6 capítulos, para estudiar los recursos y las técnicas de programación que le llevarán a tratar cuestiones avanzadas, como el desarrollo de un programa compresor/descompresor de archivos basado en el algoritmo de Huffman. Además, este libro desarrolla funciones y tipos abstractos de datos (TAD) para conformar una biblioteca (API) que podrá utilizar en la resolución de una gran cantidad de ejercicios y problemas. Asimismo, gracias a esta lectura: ' Aprenderá a programar ágilmente con los vídeos explicativos del autor que acompañan cada lección. ' Podrá validar los conocimientos adquiridos con las autoevaluaciones que se proponen y recibirá el feedback con el que determinará si debe releer la lección o parte de esta, antes de pasar a la siguiente. En esta nueva edición se profundiza especialmente en el análisis y la resolución de problemas. Se propone un caso testigo y diversas variantes de este, que le permitirán identificar distintos tipos de problemas que estudiar y discutir estrategias de solución. Sin duda, esta es una obra imprescindible si desea ser un futuro programador o busca afianzar y profundizar sus conocimientos en la materia.Si desea adentrarse en el mundo de la programación desde cero y avanzar progresivamente hasta cubrir los aspectos más complejos de la programación en C++, mediante el análisis y desarrollo de gran cantidad de problemas algorítmicos de todos los niveles, este libro será su gran aliado. Curso de algoritmos y programación a fondo presenta 16 lecciones, distribuidas en 6 capítulos, para estudiar los recursos y las técnicas de programación que le llevarán a tratar cuestiones avanzadas, como el desarrollo de un programa compresor/descompresor de archivos basado en el algoritmo de Huffman. Además, este libro desarrolla funciones y tipos abstractos de datos (TAD) para conformar una biblioteca (API) que podrá utilizar en la resolución de una gran cantidad de ejercicios y problemas. Asimismo, gracias a esta lectura: ' Aprenderá a programar ágilmente con los vídeos explicativos del autor que acompañan cada lección. ' Podrá validar los conocimientos adquiridos con las autoevaluaciones que se proponen y recibirá el feedback con el que determinará si debe releer la lección o parte de esta, antes de pasar a la siguiente. En esta nueva edición se profundiza especialmente en el análisis y la resolución de problemas. Se propone un caso testigo y diversas variantes de este, que le permitirán identificar distintos tipos de problemas que estudiar y discutir estrategias de solución. Sin duda, esta es una obra imprescindible si desea ser un futuro programador o busca afianzar y profundizar sus conocimientos en la materia.