دانلود کتاب estructuras de datos usando C++

فهرست مطالب :

Cover
CONTENIDO BREVE
CONTENIDO
PREFACIO
Enfoque
Cómo utilizar este libro
CAPÍTULO 1 PRINCIPIOS DE INGENIERÍA DE SOFTWARE Y CLASES DE C++
Ciclo de vida del software
Etapa de desarrollo del software
Análisis
Diseño
DISEÑO ESTRUCTURADO
DISEÑO ORIENTADO A OBJETOS
Implementación
Pruebas y depuración
Análisis de algoritmos: la notación O grande
Clases
Constructores
Diagramas del lenguaje unificado de modelado
Declaración de variables (objetos)
Acceso a los miembros de clase
Implementación de funciones miembro
Parámetros de referencia y objetos de clase (variables)
OPERACIONES INTEGRADAS EN LAS CLASES
Operador de asignación y clases
Ámbito de clase
Funciones y clases
Constructores y parámetros predeterminados
Destructores
Estructuras
Abstracción de datos, clases y tipos de datos abstractos
EJEMPLO DE PROGRAMACIÓN: Máquina dispensadora de jugos
Identificar clases, objetos y operaciones
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 2 DISEÑO ORIENTADO A OBJETOS (DOO) Y C++
Herencia
Redefinición (anulación) de las funciones miembro de la clase base
Constructores de las clases base y derivadas
Archivo de encabezado de una clase derivada
Inclusiones múltiples de un archivo de encabezado
Miembros protegidos de una clase
La herencia como public, protected o private
Composición
Polimorfismo: sobrecarga de funciones y operadores
Sobrecarga de operadores
Por qué se requiere la sobrecarga de operadores
Sobrecarga de operadores
Sintaxis para las funciones de operador
Sobrecarga de un operador: algunas restricciones
El apuntador this
Funciones friend de las clases
DEFINICIÓN DE UNA FUNCIÓN friend
Funciones de operador como funciones miembro y funciones no miembro
Sobrecarga de operadores binarios
SOBRECARGA DE LOS OPERADORES BINARIOS COMO FUNCIONES MIEMBRO
SINTAXIS GENERAL PARA LA SOBRECARGA DE OPERADORES BINARIOS (ARITMÉTICOS O RELACIONALES) COMO FUNCIONES MIEMBRO
SOBRECARGA DE OPERADORES BINARIOS (ARITMÉTICOS O RELACIONALES) COMO FUNCIONES NO MIEMBRO
SINTAXIS GENERAL PARA SOBRECARGAR LOS OPERADORES BINARIOS (ARITMÉTICOS O RELACIONALES) COMO FUNCIONES NO MIEMBRO
Sobrecarga de los operadores de inserción (<<) y extracción (>>) de flujo
SOBRECARGA DEL OPERADOR DE INSERCIÓN DE FLUJO (<<)
SOBRECARGA DEL OPERADOR DE EXTRACCIÓN DE FLUJO (“>>”)
SOBRECARGA DE OPERADORES UNARIOS
Sobrecarga de operadores: miembro versus no miembro
EJEMPLO DE PROGRAMACIÓN: Números complejos 2
Sobrecarga de funciones
Plantillas
Plantillas de funciones
Plantillas de clases
Archivo de encabezado y archivo de implementación de una plantilla de clase
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 3 APUNTADORES Y LISTAS BASADAS EN ARREGLOS (ARRAYS)
El tipo de datos apuntador y las variables apuntador
Declaración de variables apuntador
Dirección del operador (&)
Operador de desreferenciación (*)
Apuntadores y clases
Inicialización de variables apuntador
Variables dinámicas
Operador new
Operador delete
Operaciones con variables apuntador
Arreglos dinámicos
Nombre del arreglo: Un apuntador constante
Funciones y apuntadores
Apuntadores y valores a devolver de una función
Arreglos dinámicos bidimensionales
Copia superficial versus copia profunda y apuntadores
Clases y apuntadores: algunas peculiaridades
Destructor
Operador de asignación
SOBRECARGA DEL OPERADOR DE ASIGNACIÓN
Constructor de copia
Herencia, apuntadores y funciones virtuales
Clases y destructores virtuales
Clases abstractas y funciones virtuales puras
Listas basadas en arreglos
Constructor de copia
Sobrecarga del operador de asignación
Búsqueda
Función insert
Función remove
Complejidad temporal de las operaciones de lista
EJEMPLO DE PROGRAMACIÓN: Operaciones con polinomios
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 4 BIBLIOTECA DE PLANTILLAS ESTÁNDAR (STL) I
Componentes de la STL
Tipos de contenedores
Contenedores secuenciales
Contenedor secuencial: vector
DECLARACIÓN DE OBJETOS VECTOR
Declaración de un iterador a un contenedor vector
Contenedores y las funciones begin y end
Funciones miembro comunes a todos los contenedores
Funciones miembro comunes a los contenedores secuenciales
El algoritmo copy
El iterador ostream y la función copy
Contenedor secuencial: deque
Iteradores
Tipos de iteradores
Iteradores de entrada
Iteradores de salida
Iteradores de avance
Iteradores bidireccionales
Iteradores de acceso aleatorio
Iteradores de flujo
EJEMPLO DE PROGRAMACIÓN: Informe de califi caciones
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 5 LISTAS LIGADAS
Listas ligadas
Listas ligadas: algunas propiedades
CÓMO RECORRER UNA LISTA LIGADA
Inserción y eliminación de elementos
INSERCIÓN
ELIMINACIÓN
Creación de una lista ligada
CREACIÓN DE UNA LISTA LIGADA HACIA ADELANTE
CÓMO CREAR UNA LISTA LIGADA HACIA ATRÁS
Lista ligada como ADT
Estructura de los nodos de las listas ligadas
Variables miembro de la clase linkedListType
Iteradores de las listas ligadas
Constructor predeterminado
Destruir la lista
Inicializar la lista
Imprimir la lista
Longitud de una lista
Recuperar los datos del primer nodo
Recuperar los datos del último nodo
Begin y end
Copiar la lista
Destructor
Constructor de copia
Sobrecarga del operador de asignación
Listas ligadas sin ordenar
Buscar en la lista
Insertar el primer nodo
Insertar el último nodo
ELIMINAR UN NODO
Archivo de encabezado de la lista ligada sin ordenar
Listas ligadas ordenadas
Buscar en la lista
Insertar un nodo
Insertar al principio e insertar al final
Eliminar un nodo
Archivo de encabezado de la lista ligada ordenada
Listas doblemente ligadas
Constructor predeterminado
isEmptyList
Destruir la lista
Inicializar la lista
Longitud de la lista
Imprimir la lista
Imprimir la lista en orden inverso
Buscar en la lista
Primer y último elementos
INSERTAR UN NODO
ELIMINAR UN NODO
Contenedor de secuencias STL: list
Listas ligadas con nodos iniciales y fi nales
Listas ligadas circulares
EJEMPLO DE PROGRAMACIÓN: Tienda de video
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 6 RECURSIÓN
Definiciones recursivas
Recursión directa e indirecta
Recursión infinita
Solución de problemas mediante recursión
El elemento más grande en un arreglo
Imprimir una lista ligada en orden inverso
LA FUNCIÓN printListReverse
El número de Fibonacci
La “Torre de Hanoi”
“TORRE DE HANOI”: ANÁLISIS
Conversión de un número de decimal a binario
¿Recursión o iteración?
Recursión y búsqueda en retroceso:el problema de las 8 reinas
Búsqueda en retroceso
Problema de las n reinas
Búsqueda en retroceso y el problema de las 4 reinas
Problema de las 8 reinas
Recursión, búsqueda en retroceso y sudoku
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 7 PILAS
Pilas
Implementación de pilas como arreglos
Inicializar la pila
Pila vacía
Pila llena
Push (añadir)
Devolver el elemento superior
Pop (eliminar)
Copiar la pila
Constructor y destructor
Constructor de copia
Sobrecarga del operador de asignación (=)
Archivo del encabezado de pila
EJEMPLO DE PROGRAMACIÓN: El promedio más alto
Implementación ligada de pilas
Constructor predeterminado
Pila vacía y pila llena
Inicializar la pila
Push (añadir)
Devolver el elemento superior
Pop (eliminar)
Copiar una pila
Constructores y destructores
Sobrecarga del operador de asignación (=)
Pila derivada de la clase unorderedLinkedList
Aplicación de las pilas: cálculo de expresiones posfijas
ALGORITMO PRINCIPAL
FUNCIÓN evaluateExpression
FUNCIÓN evaluateOpr
FUNCIÓN discardExp
FUNCIÓN printResult
LISTADO DEL PROGRAMA
Eliminar la recursión: algoritmo no recursivo para imprimir una lista ligada hacia atrás (en retroceso)
Pila de la clase STL
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 8 COLAS
Operaciones con colas
Implementación de colas como arreglos
Cola vacía y cola llena
Inicializar una cola
Frente
Parte posterior
Añadir a la cola
Eliminar de la cola
Constructores y destructores
Implementación ligada de colas
Cola vacía y llena
Inicializar una cola
Operaciones AddQueue, front, back y deleteQueue
Cola derivada de la clase unorderedLinkedList
Cola de la clase STL (adaptador del contenedor de la cola)
Colas con prioridad
Clase STL priority_queue
Aplicación de las colas: simulación
Diseño de un sistema de colas
Cliente
Servidor
Lista de servidores
Cola de clientes en espera
Programa principal
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 9 ALGORITMOS DE BÚSQUEDA Y HASHING
Algoritmos de búsqueda
Búsqueda secuencial
ANÁLISIS DE LA BÚSQUEDA SECUENCIAL
Listas ordenadas
Búsqueda binaria
FUNCIONAMIENTO DE BÚSQUEDA BINARIA
Inserción en una lista ordenada
Límite inferior de los algoritmos de búsqueda por comparación
Hashing
Funciones hash: algunos ejemplos
Solución de la colisión
Direccionamiento abierto
EXPLORACIÓN LINEAL
EXPLORACIÓN ALEATORIA
REHASHING
EXPLORACIÓN CUADRÁTICA
Eliminación: direccionamiento abierto
Hashing: implementación utilizando la exploración cuadrática
Encadenamiento
INSERCIÓN DE UN ELEMENTO Y COLISIÓN
BÚSQUEDA
BORRAR
DESBORDAMIENTO
VENTAJAS DEL ENCADENAMIENTO
DESVENTAJAS DEL ENCADENAMIENTO
Análisis del hashing
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 10 ALGORITMOS DE ORDENAMIENTO
Algoritmos de ordenamiento
Ordenamiento por selección: listas basadas en arreglos
Análisis: Ordenamiento por selección
Ordenamiento por inserción: listas basadas en arreglos
Ordenamiento por inserción: listas ligadas basadas en listas
Análisis: Ordenamiento por inserción
Ordenamiento Shell
Límite inferior de algoritmos de ordenamiento basados en la comparación
Ordenamiento rápido: listas basadas en arreglos
Análisis: Ordenamiento rápido
Ordenamiento por mezcla: listas ligadas basadas en listas
Dividir
Mezclar
Análisis: Ordenamiento por mezcla
Ordenamiento por montículos: listas basadas en arreglos
Construir el montículo
Análisis: Ordenamiento por montículos
Colas con prioridad (revisión)
INSERTAR UN ELEMENTO EN LA COLA CON PRIORIDAD
ELIMINAR UN ELEMENTO DE LA COLA CON PRIORIDAD
EJEMPLO DE PROGRAMACIÓN: Resultados electorales
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 11 ÁRBOLES BINARIOS Y ÁRBOLES B
Árboles binarios
Función copyTree
Recorrido de un árbol binario
Recorrido inorden
Recorrido preorden
Recorrido posorden
Implementación de árboles binarios
Árboles binarios de búsqueda
Búsqueda
Inserción
Eliminar
Árbol binario de búsqueda: Análisis
Algoritmos de recorrido no recursivo de árboles binarios
Recorrido inorden no recursivo
Recorrido preorden no recursivo
Recorrido posorden no recursivo
Recorrido de un árbol binario y funciones como parámetros
Árboles AVL (de altura balanceada)
Inserción
Rotaciones de árboles AVL
Eliminación de elementos de árboles AVL
Análisis: Árboles AVL
Árboles B
Búsqueda
Recorrido de un árbol B
Inserción en un árbol B
Eliminación de un árbol B
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 12 GRAFOS
Introducción
Definiciones y notaciones de grafos
Representación de grafos
Matrices de adyacencia
Listas de adyacencia
Operaciones con grafos
Grafos como ADT
Recorridos de grafos
Recorrido primero en profundidad
Recorrido primero en anchura
Algoritmo de la trayectoria más corta
La trayectoria más corta
Árbol de expansión mínima
Orden topológico
Orden topológico primero en anchura
Circuitos de Euler
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
CAPÍTULO 13 BIBLIOTECA DE PLANTILLAS ESTÁNDAR (STL) II
Clase pair
Comparación de objetos del tipo pair
Tipo pair y función make_pair
Contenedores asociativos
Contenedores asociativos: set y multiset
DECLARACIÓN DE LOS CONTENEDORES ASOCIATIVOS set O multiset
INSERCIÓN Y ELIMINACIÓN DE ELEMENTOS DE set/multiset
Contenedores asociativos: map y multimap
DECLARACIÓN DE LOS CONTENEDORES ASOCIATIVOS map O multimap
INSERCIÓN Y ELIMINACIÓN DE ELEMENTOS DE map/multimap
Contenedores, archivos de encabezado asociados y soporte del iterador
Algoritmos
Clasificación de algoritmos de la biblioteca de plantillas estándar (STL)
Algoritmos no modificadores
Algoritmos modificadores
Los algoritmos numéricos
Algoritmos de montículo
Objetos de función
Predicados
ITERADOR DE INSERCIÓN
Algoritmos STL
Funciones fill y fill_n
Funciones generate y generate_n
Funciones find, find—if, find—end y find—first—of
Funciones remove, remove—if, remove—copy y remove—copy—if
Funciones replace, replace—if, replace—copy y replace—copy—if
Funciones swap, iter—swap y swap—ranges
Funciones search, search—n, sort y binary—search
Funciones adjacent—find, merge e inplace—merge
Funciones reverse, reverse—copy, rotate y rotate—copy
Funciones count, count—if, max—element, min—element y random—shuffle
Funciones for—each y transform
Funciones includes, set—intersection, set—union, set—difference y set—symmetric—difference
Funciones accumulate, adjacent—difference, inner—product y partial—sum
REPASO RÁPIDO
EJERCICIOS
EJERCICIOS DE PROGRAMACIÓN
APÉNDICE A PALABRAS RESERVADAS
APÉNDICE B PRIORIDAD DE LOS OPERADORES
APÉNDICE C CONJUNTOS DE CARACTERES
ASCII (American Standard Code for Information Interchange)
Código EBCDIC (Extended Binary Coded Decimal Interchange Code)
APÉNDICE D OPERADOR DE SOBRECARGA
APÉNDICE E ARCHIVOS DE ENCABEZADO
Encabezado del archivo cassert
Encabezado del archivo cctype
Encabezado del archivo cfloat
Encabezado del archivo climits
Encabezado del archivo cmath
Encabezado del archivo cstddef
Encabezado del archivo cstring
ENCABEZADO DEL ARCHIVO string
APÉNDICE F TEMAS ADICIONALES DE C++
Análisis: Insertion Sort
Análisis: Quicksort
Análisis del peor de los casos
Análisis del caso promedio
APÉNDICE G C++ PARA PROGRAMADORES DE JAVA
Tipos de datos
Operadores y expresiones aritméticas
Constantes con nombre, variables y declaraciones de asignación
Biblioteca de C++: directivas del preprocesador
Programa C++
Entrada y salida
Entrada
Falla de entrada
Salida
setprecision
fixed
showpoint
setw
Manipuladores left y right
Archivo de entrada/salida
Estructuras de control
Namespaces
Funciones y parámetros
Funciones que retornan un valor
SINTAXIS: LISTA DE PARÁMETROS FORMALES
FUNCIÓN DE LLAMADA
SINTAXIS: LISTA REAL DE PARÁMETROS
Funciones void
LISTA FORMAL DE PARÁMETROS
FUNCIÓN DE LLAMADA
LISTA ACTUAL DE PARÁMETROS
Parámetros de referencia y funciones que devuelven un valor
Funciones con parámetros predeterminados
Arreglos
Acceso a componentes del arreglo
El índice del arreglo fuera de límites
Arreglos como parámetros para las funciones
APÉNDICE H REFERENCIAS
APÉNDICE I RESPUESTAS DE LOS EJERCICIOS IMPARES
Capítulo 1
Capítulo 2
Capítulo 3
Capítulo 4
Capítulo 5
Capítulo 6
Capítulo 7
Capítulo 8
Capítulo 9
Capítulo 10
Capítulo 11
Capítulo 12
Capítulo 13
ÍNDICE