rimeras paginas 13/6/05 10:17 Página I C Algoritmos, programación y estructuras de datos rimeras paginas 13/6/05 10:17 Página II rimeras paginas 13/6/05 10:17 Página III C Algoritmos, programación y estructuras de datos LUIS JOYANES AGUILAR ANDRÉS CASTILLO SANZ LUCAS SÁNCHEZ GARCÍA IGNACIO ZAHONERO MARTÍNEZ Departamento de Lenguajes y Sistemas Informáticos e Ingeniería del Software Facultad de Informática/Escuela Universitaria de Informática Universidad Pontificia de Salamanca campus Madrid MADRID• BOGOTÁ •BUENOS AIRES• CARACAS •GUATEMALA •LISBOA •MÉXICO NUEVA YORK •PANAMÁ •SAN JUAN •SANTIAGO •SÃO PAULO AUCKLAND • HAMBURGO • LONDRES • MILÁN • MONTREAL • NUEVA DELHI • PARÍS SAN FRANCISCO • SIDNEY • SINGAPUR • ST. LOUIS • TOKIO • TORONTO rimeras paginas 13/6/05 10:17 Página IV La información contenida en este libro procede de una obra original entregada por los autores. No obstante, McGraw- Hill/Interamericana de España no garantiza la exactitud o perfección de la información publicada. Tampoco asume ningún tipo de garantía sobre los contenidos y las opiniones vertidas en dichos textos. Este trabajo se publica con el reconocimiento expreso de que se está proporcionando una información, pero no tratando de prestar ningún tipo de servicio profesional o técnico. Los procedimientos y la información que se presentan en este libro tienen sólo la inten- ción de servir como guía general. McGraw-Hill ha solicitado los permisos oportunos para la realización y el desarrollo de esta obra. C. Algoritmos, programación y estructuras de datos. Serie Schaum No está permitida la reproducción total o parcial de este libro, ni su tratamiento informático, ni la transmisión de ninguna forma o por cualquier medio, ya sea electrónico, mecánico, por fotocopia, por registro u otros métodos, sin el permiso previo y por escrito de los titulares del Copyright. McGraw-Hill/Interamericana de de España, S. A. U. DERECHOS RESERVADOS ©2005, respecto a la primera edición en español, por McGRAW-HILL/INTERAMERICANADE ESPAÑA, S. A. U. Edificio Valrealty, 1ª planta Basauri, 17 28023 Aravaca (Madrid) www.mcgraw-hill.es [email protected] ISBN: 84-481-4514-3 Depósito legal: M. Editor: Carmelo Sánchez González Compuesto en CD-FORM, S.L. Impreso en IMPRESO EN ESPAÑA - PRINTED IN SPAIN rimeras paginas 13/6/05 10:17 Página V Contenido Prólogo............................................................................................................................................................................. XI Capítulo 1 Introducción a las computadoras y a los lenguajes de programación.......................................................... 1 1.1 Organizacion física de una computadora......................................................................................................... 1 1.2 Redes................................................................................................................................................................ 5 1.3 El software (los programas)............................................................................................................................. 6 1.4 Lenguajes de programación............................................................................................................................. 7 1.5 El lenguaje C: historia y características........................................................................................................... 10 Referencias bibliográficas y lecturas suplementarias............................................................................................. 11 Ejercicios de repaso................................................................................................................................................ 12 Capítulo 2 Fundamentos de programación..................................................................................................................... 13 2.1 Fases en la resolución de problemas................................................................................................................ 13 2.1.1 Análisis del problema............................................................................................................................ 14 2.1.2 Diseño del algoritmo.............................................................................................................................. 14 2.1.3 Codificación de un programa................................................................................................................. 14 2.1.4 Compilación y ejecución de un programa............................................................................................. 14 2.1.5 Verificación y depuración...................................................................................................................... 15 2.1.6 Documentación y mantenimiento.......................................................................................................... 15 2.2 Programación estructurada............................................................................................................................... 16 2.2.1 Recursos abstractos................................................................................................................................ 16 2.2.2 Diseño descendente (Top Down)........................................................................................................... 16 2.2.3 Estructuras de control............................................................................................................................ 16 2.2.4 Teorema de la programación estructurada............................................................................................. 16 2.3 Métodos formales de verificación de programas............................................................................................. 16 2.4 Factores de calidad del software...................................................................................................................... 17 Problemas resueltos................................................................................................................................................. 18 Problemas propuestos.............................................................................................................................................. 24 Capítulo 3 El lenguaje C: elementos básicos................................................................................................................. 25 3.1 Estructura general de un programa en C.......................................................................................................... 25 3.1.1 Directivas del preprocesador.................................................................................................................. 25 3.1.2 Declaraciones globales........................................................................................................................... 25 3.1.3 Función main()..................................................................................................................................... 26 3.1.4 Funciones definidas por el usuario........................................................................................................ 26 3.2 Los elementos de un programa C ................................................................................................................... 27 3.3 Tipos de datos en C.......................................................................................................................................... 27 3.3.1 Enteros (int)....................................................................................................................................... 27 3.3.2 Tipos de coma flotante(float/double)............................................................................................. 28 3.3.3 Caracteres (char).................................................................................................................................. 29 3.4 El tipo de dato lógico....................................................................................................................................... 29 3.5 Constantes........................................................................................................................................................ 29 3.6 Variables........................................................................................................................................................... 30 3.7 Entradas y salidas............................................................................................................................................. 30 rimeras paginas 13/6/05 10:17 Página VI VI CONTENIDO Problemas resueltos................................................................................................................................................. 31 Problemas propuestos.............................................................................................................................................. 35 Capítulo 4 Operadores y expresiones............................................................................................................................. 37 4.1 Operadores y expresiones................................................................................................................................ 37 4.2 El operador de asignació.................................................................................................................................. 37 4.3 Operadores aritméticos..................................................................................................................................... 38 4.4 Operadores de incrementación y decrementación........................................................................................... 39 4.5 Operadores relacionales................................................................................................................................... 39 4.6 Operadores lógicos........................................................................................................................................... 40 4.7 Operadores de manipulación de bits................................................................................................................ 40 4.7.1 Operadores de asignación adicionales................................................................................................... 41 4.7.2 Operadores de desplazamiento de bits (>>, <<).................................................................................... 41 4.8 Operador condicional....................................................................................................................................... 41 4.9 Operador coma ,............................................................................................................................................. 42 4.10 Operadores especiales (), [] ............................................................................................................ 42 4.11 El operador sizeof................................................................................................................................. 42 4.12 Conversiones de tipos............................................................................................................................. 42 4.13 Prioridad y asociatividad......................................................................................................................... 43 Problemas resueltos................................................................................................................................................. 44 Problemas propuestos.............................................................................................................................................. 53 Capítulo 5 Estructuras de selección: sentencias ify switch........................................................................................ 55 5.1 Estructuras de control....................................................................................................................................... 55 5.2 La sentencia ifcon una alternativa................................................................................................................. 55 5.3 Sentencia ifde dos alternativas: if-else...................................................................................................... 56 5.4 Sentencia de control switch............................................................................................................................ 57 5.5 Expresiones condicionales: el operador ?:..................................................................................................... 57 5.6 Evaluación en cortocircuito de expresiones lógicas ....................................................................................... 58 Problemas resueltos................................................................................................................................................. 58 Problemas propuestos.............................................................................................................................................. 69 Capítulo 6 Estructuras de control: bucles....................................................................................................................... 71 6.1 La sentencia while.......................................................................................................................................... 71 6.1.1 Miscelánea de control de bucleswhile................................................................................................. 72 6.2 Repetición: el bucle for................................................................................................................................. 73 6.3 Repetición: el bucle do...while.................................................................................................................... 74 6.4 Comparación de bucles while, for y do-while......................................................................................... 74 Problemas resueltos................................................................................................................................................. 75 Problemas propuestos.............................................................................................................................................. 92 Capítulo 7 Funciones...................................................................................................................................................... 95 7.1 Concepto de función........................................................................................................................................ 95 7.2 Estructura de una función................................................................................................................................ 95 7.3 Prototipos de las funciones.............................................................................................................................. 96 7.4 Parámetros de una función............................................................................................................................... 97 7.5 Funciones en línea, macros con argumentos................................................................................................... 98 7.6 Ámbito (alcance).............................................................................................................................................. 98 7.7 Clases de almacenamiento............................................................................................................................... 99 7.8 Concepto y uso de funciones de biblioteca...................................................................................................... 100 7.9 Miscelánea de funciones.................................................................................................................................. 100 Problemas resueltos................................................................................................................................................. 101 Problemas propuestos.............................................................................................................................................. 121 rimeras paginas 13/6/05 10:17 Página VII CONTENIDO VII Capítulo 8 Recursividad................................................................................................................................................. 123 8.1 La naturaleza de la recursividad...................................................................................................................... 123 8.2 Funciones recursivas........................................................................................................................................ 123 8.3 Recursión versus iteración .............................................................................................................................. 124 8.4 Recursión infinita............................................................................................................................................. 125 8.5 Algoritmos divide y vencerás.......................................................................................................................... 125 Problemas resueltos................................................................................................................................................. 125 Problemas propuestos.............................................................................................................................................. 135 Capítulo 9 Arrays (listas y tablas).................................................................................................................................. 137 9.1 Arrays............................................................................................................................................................... 137 9.2 Inicialización de un array................................................................................................................................. 138 9.3 Arrays de caracteres y cadenas de texto.......................................................................................................... 138 9.4 Arrays multidimensionales............................................................................................................................... 139 9.5 Utilización de arrays como parámetros............................................................................................................ 140 Problemas resueltos................................................................................................................................................. 140 Problemas propuestos.............................................................................................................................................. 159 Capítulo 10 Algoritmos de ordenación y búsqueda....................................................................................................... 161 10.1 Ordenación..................................................................................................................................................... 161 10.2 Ordenación por burbuja................................................................................................................................. 161 10.3 Ordenación por selección............................................................................................................................... 162 10.4 Ordenación por inserción............................................................................................................................... 162 10.5 Ordenación Shell............................................................................................................................................ 163 10.6 Ordenación rapida (QuickSort)...................................................................................................................... 163 10.7 Búsqueda en listas: búsqueda secuencial y binaria........................................................................................ 163 Problemas resueltos................................................................................................................................................. 165 Problemas propuestos.............................................................................................................................................. 170 Capítulo 11 Estructuras y uniones.................................................................................................................................. 173 11.1 Estructuras...................................................................................................................................................... 173 11.2 Uniones........................................................................................................................................................... 175 11.3 Enumeraciones............................................................................................................................................... 176 11.4 Sinonimo de un tipo de datos: Typedef........................................................................................................ 177 11.5 Campos de bit................................................................................................................................................. 179 Problemas resueltos................................................................................................................................................. 180 Problemas propuestos.............................................................................................................................................. 190 Problemas de programación de gestión.................................................................................................................. 190 Capítulo 12 Punteros (apuntadores)............................................................................................................................... 191 12.1 Concepto de puntero (apuntador)................................................................................................................... 191 12.2 Punteros NULLy VOID................................................................................................................................... 192 12.3 Punteros y arrays............................................................................................................................................ 192 12.4 Aritmética de punteros................................................................................................................................... 194 12.5 Punteros como argumentos de funciones....................................................................................................... 195 12.6 Punteros a funciones...................................................................................................................................... 196 Problemas resueltos................................................................................................................................................. 197 Problemas propuestos.............................................................................................................................................. 209 Capítulo 13 Asignación dinámica de memoria.............................................................................................................. 211 13.1 Gestión dinámica de la memoria.................................................................................................................... 211 13.2 Función malloc( )....................................................................................................................................... 212 13.3 Liberación de memoria, función free( )..................................................................................................... 213 13.4 Funciones calloc( )y realloc( )........................................................................................................... 213 Problemas resueltos................................................................................................................................................. 214 rimeras paginas 13/6/05 10:17 Página VIII VIII CONTENIDO Problemas propuestos.............................................................................................................................................. 223 Capítulo 14 Cadenas....................................................................................................................................................... 225 14.1 Concepto de cadena....................................................................................................................................... 225 14.2 Inicialización de variables de cadena............................................................................................................. 226 14.3 Lectura de cadenas......................................................................................................................................... 226 14.4 Las funciones de STRING.H........................................................................................................................... 227 14.5 Conversión de cadenas a números................................................................................................................. 229 Problemas resueltos................................................................................................................................................. 231 Problemas propuestos.............................................................................................................................................. 240 Capítulo 15 Entrada y salida por archivos..................................................................................................................... 243 15.1 Flujos.............................................................................................................................................................. 243 15.2 Apertura de un archivo................................................................................................................................... 244 15.3 Funciones de lectura y escritura..................................................................................................................... 244 15.4 Archivos binarios de C................................................................................................................................... 246 15.5 Datos externos al programa con argumentos de main()............................................................................... 248 Problemas resueltos................................................................................................................................................. 249 Problemas propuestos.............................................................................................................................................. 265 Capítulo 16 Organización de datos en un archivo.......................................................................................................... 267 16.1 Registros......................................................................................................................................................... 267 16.2 Organización de archivos............................................................................................................................... 268 16.2.1Organización secuencial..................................................................................................................... 268 16.2.2Organización directa........................................................................................................................... 270 16.3 Archivos con direccionamiento hash ............................................................................................................ 271 16.4 Archivos secuenciales indexados .................................................................................................................. 272 16.5Ordenación de archivos: ordenación externa ................................................................................................. 274 Problemas resueltos................................................................................................................................................. 277 Problemas propuestos.............................................................................................................................................. 293 Capítulo 17 Tipos abstractos de datos TAD/objetos...................................................................................................... 295 17.1 Tipos de datos................................................................................................................................................. 295 17.2 Tipos abstractos de datos............................................................................................................................... 296 17.3 Especificación de los TAD............................................................................................................................ 298 Problemas resueltos................................................................................................................................................. 298 Problemas propuestos.............................................................................................................................................. 309 Capítulo 18 Listas enlazadas.......................................................................................................................................... 311 18.1 Fundamentos teóricos..................................................................................................................................... 311 18.2 Clasificación de las listas enlazadas.............................................................................................................. 311 18.3 Operaciones en listas enlazadas..................................................................................................................... 312 18.3.1 Inserción de un elemento en una lista............................................................................................... 313 18.3.2 Eliminación de un nodo en una lista................................................................................................. 313 18.4 Lista doblemente enlazada............................................................................................................................. 314 18.4.1 Inserción de un elemento en una lista doblemente enlazada............................................................ 314 18.4.2 Eliminación de un elemento en una lista doblemente enlazada........................................................ 315 18.5 Listas circulares.............................................................................................................................................. 316 Problemas resueltos................................................................................................................................................. 317 Problemas propuestos.............................................................................................................................................. 344 Capítulo 19 Pilas y colas................................................................................................................................................ 347 19.1 Concepto de pila............................................................................................................................................. 347 19.2 Concepto de cola............................................................................................................................................ 348 rimeras paginas 13/6/05 10:17 Página IX CONTENIDO IX Problemas resueltos................................................................................................................................................. 350 Problemas propuestos.............................................................................................................................................. 366 Capítulo 20 Árboles........................................................................................................................................................ 369 20.1 Árboles generales........................................................................................................................................... 369 20.2 Árboles binarios............................................................................................................................................. 370 20.3 Estructura y representación de un árbol binario............................................................................................ 371 20.4 Árboles de expresión...................................................................................................................................... 371 20.5 Recorridos de un árbol................................................................................................................................... 372 20.6 Árbol binario de busqueda............................................................................................................................. 372 20.7 Operaciones en árboles binarios de búsqueda............................................................................................... 373 Problemas resueltos................................................................................................................................................. 374 Problemas propuestos.............................................................................................................................................. 389 Apéndice A. Compilación de programas C en UNIX y LINUX..................................................................................... 391 Apéndice B. Compilación de programas C en Windows................................................................................................ 395 Apéndice C.Recursos Web de programación................................................................................................................. 399 Índice................................................................................................................................................................................ 405