Directorio C de libros sobre principios de estructura de datos y resolución de problemas clásicos

Capítulo 1 Introducción 1

1.1 Datos y estructuras de datos 2

1.1.1 Datos y sus tipos 2

1.1.2 Introducción a la estructura de datos 4

1.2 Algoritmo 6

1.2.1 Concepto de algoritmo 6

1.2.2 Análisis del algoritmo 8

1.2 .3 Diseño del algoritmo 12

1.3 Introducción al lenguaje C 18

1.3.1 El surgimiento y desarrollo de C 18

1.3.2C y orientado a objetos pensando 20

p>

1.3.3 Clases y objetos en C 23

1.4 Resumen de este capítulo 28

Capítulo 2 Conceptos básicos de la programación en C 29

2.1 Iniciar programación en C 30

2.1.1 Entrada y salida 30

2.1.2 Preprocesamiento 38

2.1.3 Espacio de nombres 44

2.2 Programación de clases en profundidad 50

2.2.1 Control de acceso 50

2.2.2 Inicialización y autorización 53

2.2 .3 Creación dinámica de objetos 57

2.2.4 Funciones amigas 60

2.2.5 Copiar constructor 61

2.3 Funciones de Rich C 65

2.3.1 Constantes 65

2.3.2 Sobrecarga de funciones 68

2.3.3 Sobrecarga de operadores 71

2.3.4 Manejo de excepciones 77

2.4 Mecanismo de reutilización de código 79

2.4.1 Herencia 80

2.4.2 Polimorfismo 87

2.4.3 Plantilla 90

2.5 Biblioteca de plantillas estándar 93

2.5.1 Introducción a STL 94

2.5.2 Composición de STL 95

2.5.3 Diferentes versiones de STL 97

2.6 Resumen de este capítulo 98

Capítulo 3 Punteros, matrices y cadenas 99

3.1 Punteros 100

3.1.1 Concepto de punteros 100

3.1.2 Sintaxis de punteros 102

3.1.3 Transferencia de funciones y parámetros 103

3.2 Matriz 108

3.2.1 Definición de matriz e inicialización 109

3.2 .2 Matrices y punteros 113

3.2.3 Tipos de datos abstractos de matrices 116

3.2.4 Problema de multiplicación de enteros grandes 120

3.2.5 Problema de la bandera holandesa 121

3.3 Cadena 124

Cadena 124 en 3.3.1C

3.3.2 Tipo de datos abstractos de cadena 126

3.3.3 Algoritmo de coincidencia de cadenas 128

3.3.4 Problema de índice de cadenas 141

3.4 Gestión de memoria dinámica 142

3.4.1 Palabras clave nuevas y eliminar 143

3.4.2 Evitar errores de memoria 146

3.5 Resumen de este capítulo 152

Capítulo 4 Lista enlazada 153

4.1 Lista enlazada unidireccional 154

4.1.1 Estructura de lista enlazada unidireccional 154

4.1.2 Implementación de clase de lista enlazada unidireccional 155

4.1.3 Fusión de listas enlazadas ordenadas 162

4.1.4 Problema de suma polinomial 163

4.2 Lista enlazada circular unidireccional 164

4.2.1 La estructura de lista enlazada circular unidireccional 164

4.2.2 Implementación de la clase de lista enlazada circular unidireccional 166

4.2.3 Problema de Joseph 169

4.2 .4 Problema de reparto de cartas del mago 170

4.2.5 Problema del cuadrado latino 172

4.3

Lista enlazada circular bidireccional 173

4.3.1 Estructura de la lista enlazada circular bidireccional 173

4.3.2 Implementación de la clase de lista enlazada circular bidireccional 174

4.3.3 Problemas de cifrado de Vigenere 182

4.3.4 Problemas del concurso de belleza 184

4.4 Diseño e implementación de la clase de cursor 186

4.4.1 Estructura de la clase de cursor 186

4.4.2 Implementación de la clase de cursor 187

4.5STL y lista enlazada 191

4.5.1 Interfaz de la clase de lista enlazada en STL 191

4.5.2 Recorrido 194

4.5.3 Inserción y eliminación de elementos 196

4.6 Resumen de este capítulo 196

Capítulo 5 Pila y cola 197

5.1 Pila 198

5.1.1 Estructura de la pila 198

5.1.2 Implementación de la pila 199

5.1.3 Problema de coincidencia de soportes 203

5.1 .4 Problema de simulación de estacionamiento 204

5.2 Cola 208

5.2.1 Estructura de cola 208

5.2.2 Implementación de cola 210

5.2.3 Problema de pareja de baile 214

5.2.4 Problema del triángulo Yang Hui 215

5.2.5 Problema de codificación de longitud de ejecución 216

5.3 Cola de prioridad 218

5.3.1 Estructura de la cola de prioridad 218

5.3.2 Implementación de la cola de prioridad 220

5.4 Pila y cola en STL 222

5.4.1 stack222 en STL

5.4.2 queue224 en STL

5.4.3 Priority_queue226 en STL

5.5 Resumen de esto capítulo 229

Capítulo 6 Recursividad 231

6.1 El concepto de recursividad 232

6.1.1 La definición de recursividad 232

6.1. 2 El principio de aplicación de la recursividad 235

6.1.3 Transformación recursiva y no recursiva 240

6.2 Método divide y vencerás 243

6.2.1 Breve descripción de método divide y vencerás 243

6.2.2 Problema de la Torre de Hanoi 244

6.2.3 Problema de enfermedades infecciosas 246

6.3 Método de retroceso 250

6.3.1 Breve descripción del método de retroceso 251

6.3.2 Problema del laberinto 251

6.3.3 Problema de las ocho reinas 255

6.3.4 Problema del viaje de Knight 258

6.4 Resumen de este capítulo 265

Capítulo 7 Árbol 267

7.1 Concepto de árbol 268

7.1.1 Definición de árbol 268

7.1.2 Terminología de árbol 271

7.1.3 Tipo de datos abstractos de árbol 272

7.2 Árbol binario 273

7.2.1 Definición de árbol binario 273

7.2 .2 Propiedades de los árboles binarios 275

7.2.3 Implementación de árboles binarios 276

7.2.4 Recorrido de árboles binarios 285

7.2.5 Pista de árboles binarios 289

7.3 Árboles y bosques 291

7.3.1 Representación de almacenamiento de árboles 291

7.3.2 Implementación de Árboles 294

7.3.3 Recorrido de árboles y bosques 298

7.3.4 Conversión de bosques y árboles binarios 300

7.4 Árboles de Huffman 304

7.4.1 Concepto de árboles de Huffman 304

7.4.2 Método de construcción del árbol de Huffman 305

7.4.3 Codificación de Huffman y su implementación 307

7.5 Montón 313

7.5.1 Concepto de montón 314

7.5.2 Establecimiento de montón 314

7.5.3 Operación de montón 316

7.6 Implementación de estructura de árbol basada en STL 317

7.6.1 vector317 en STL

7.6.2 map321 en STL

7.7 Problemas de modelado hospitalario 323

7.8 Resumen de este capítulo 328

Capítulo 8 Figura 329

8.1 Concepto básico de la Figura 330

8.1.1 Definición de la Figura 330

8.1.2 Definición de terminología de figuras 331

8.1.3 Operaciones de gráficos 334

8.1.4 Tipos de datos abstractos de gráficos 336

8.2 Almacenamiento y representación de gráficos 337

8.2.1 Representación matricial de adyacencia del gráfico 337

8.2.2 Representación de lista de adyacencia del gráfico 339

8.2.3 Comparación de dos representaciones 342

8.3 Recorrido de gráficas 342

8.3.1 Caminos de Euler y circuitos de Euler 343

8.3.2 Caminos hamiltonianos y circuitos hamiltonianos 345

8.3 Amplitud. -primer recorrido 346

8.3.4 Primero recorrido en profundidad 349

8.4 Problema de ruta más corta 353

8.4.1 Problema de ruta más corta del punto de partida fijo 353

8.4.2 Problema del camino más corto con punto de partida no fijo 355

8.4.3 Solución de programación dinámica del camino más corto 358

8.4.4 Problema de ruta de transporte turístico 364

8.5 Árbol de expansión mínimo 372

8.5.1 Definición de árbol de expansión mínimo 372

8.5.2 Algoritmo de Kruskal 373

8.5. 3 Algoritmo de Prim 375

8.6 Ejemplos de problemas clásicos 379

8.6.1 Problema de juego de palabras 380

8.6.2 Problema de construcción de carreteras 382

8.6.3 Problema de ruta de inicio 385

8.6.4 Problema de cálculo de estanque 387

8.6.5 Problema de restauración de palos 389

8.7 Resumen de este capítulo 392

Capítulo 9 Estructura de árbol de búsqueda 393

9.1 Árbol de búsqueda binaria 394

9.1.1 Concepto de árbol de búsqueda binaria 394

9.1. 2 Operación del árbol de búsqueda binaria 395

9.1.3 Implementación del árbol de búsqueda binaria 397

9.1.4 Análisis del árbol de búsqueda binaria 400

9.2 Árbol AVL 403

9.2.1 Concepto de árbol AVL 404

9.2.2 Rotación de árbol AVL 405

9.2.3 Implementación de árbol AVL 410

9.3 Árbol rojo-negro 418

9.3.1 Concepto de árbol rojo-negro 418

9.3.2 Funcionamiento del árbol rojo-negro 421

9.3 .3 Implementación del árbol rojo-negro 428

9.4 Árbol Trie 433

9.4.1 Concepto de árbol Trie 433

9.4.2 Representación del árbol Trie 434

9.4.3 Implementación del árbol Trie 435

9.5 Resumen de este capítulo 439

Capítulo 10 Conjuntos y diccionarios 441

10.1 Conceptos básicos de la teoría de conjuntos 442

10.1.1 Concepto del Conjunto 442

10.1.2 Operación del Conjunto 444

10.2 Implementación del Conjunto 445

10.2.1 Conjunto de vectores de bits 445

10.2.2 Conjunto de listas enlazadas 451

10.3 Diccionario 460

10.3.1 El concepto de diccionario 461

10.3.2 Operación de búsqueda

463

10.4 Hash 467

10.4.1 El concepto de hash 467

10.4.2 Función hash 469

10.4. con conflictos de hash 471

10.4.4 Aplicación de hash 475

10.5 Ejemplos de problemas clásicos 476

10.5.1 Problemas de revisión ortográfica 476

10.5.2 Problema de red inalámbrica 485

10.5.3 Problema de número Kth 488

10.6 set490 en STL

10.7 Resumen de este capítulo 493

Capítulo 11 Clasificación 495

11.1 Descripción general de los problemas de clasificación 496

11.1.1 Conceptos y definiciones básicos 496

11.1.2 Clasificación Clasificación de algoritmos 497

11.1.3 Análisis y selección de algoritmos de clasificación 497

11.2 Ordenación por inserción 498

11.2.1 Ordenación por inserción directa 498

11.2.2 Clasificación por inserción de dicotomía 501

11.2.3 Clasificación por colina 503

11.3 Clasificación por selección 506

11.3.1 Clasificación por selección directa 506

11.3.2 Clasificación de montón 508

11.4 Clasificación de intercambio 512

11.4.1 Clasificación de burbuja 512

11.4.2 Clasificación de agitador 514

11.4.3 Clasificación rápida 517

11.5 Clasificación por combinación 522

11.6 Clasificación por conteo 526

11.7 Resumen de este capítulo 531

Referencia 533

……