Estructura de datos (versión en lenguaje C) publicada por China Railway Press

Título del libro: Estructura de datos (versión en lenguaje C)

Nombre de la serie: Serie de tutoriales prácticos informáticos, libros de texto de planificación para universidades vocacionales superiores

ISBN: 978-7 - 113-12943-9 Edición: 1-1 Formato: 16 Páginas: 236 páginas

Autor: Wang Guizhi

Fecha de publicación: 2011-08-01

Precio: 24 yuanes

Editor: China Railway Press

Especialidades aplicables: especialidades en informática Este libro se centra en las descripciones de tipos de varias estructuras de datos básicas, la implementación de algoritmos comunes y su aplicación. El libro está dividido en 9 capítulos: el Capítulo 1 presenta principalmente los conceptos básicos y la terminología de las estructuras de datos; los Capítulos 2 al Capítulo 7 analizan respectivamente tablas lineales, pilas y colas, cadenas, matrices y tablas generalizadas, árboles y gráficos y otros tipos básicos. de las estructuras de datos; los Capítulos 8 y 9 analizan principalmente varios métodos de implementación de búsqueda y clasificación y su análisis y comparación integrales. Excepto el Capítulo 1, la última sección de cada capítulo proporciona ejemplos de aplicación de los algoritmos clave de este capítulo en forma de capacitación práctica para facilitar la verificación por computadora.

Las teorías básicas de este libro se explican de lo más superficial a lo más profundo, la descripción del algoritmo es clara, el contenido está razonablemente organizado, el lenguaje es conciso y el razonamiento lógico es riguroso. un libro de texto para carreras relacionadas con la informática o la información en escuelas vocacionales superiores. También puede proporcionar referencia para que los profesionales de la informática estudien por su cuenta o tomen exámenes de informática.

Capítulo 1 Descripción general de las estructuras de datos 1

1.1 La naturaleza y el estado de los cursos de estructura de datos 1

1.1.1 Contenidos tratados en los cursos de estructura de datos 1

1.1. 2 El estado de la estructura de datos en informática 4

1.1 La naturaleza y el estado de los cursos de estructura de datos 1

1.1.1 El contenido discutido en los cursos de estructura de datos 1

1.1.2 El estado de la estructura de datos en informática 4

1.2 Conceptos y terminología básicos 5

1.2.1 Términos relacionados con la estructura de datos 5

1.2 .2 Estructura lógica de los datos 5

1.2.3 Estructura de almacenamiento de los datos 6

1.2.4 Tipos de datos y tipos de datos abstractos 7

1.3 Algoritmos y Análisis de algoritmos 8

1.3.1 Concepto de algoritmo 8

1.3.2 Requisitos de diseño del algoritmo 8

1.3.3 Complejidad temporal del algoritmo 9

1.3.4 Complejidad espacial del algoritmo 11

Resumen de este capítulo 11

Ejercicio 12

Capítulo 2 Tabla lineal 15

2.1 Estructura lógica de la tabla lineal 15

2.1.1 Definición de tabla lineal 15

2.1.2 Operaciones comunes de la tabla lineal 16

2.2 Tabla lineal Estructura de almacenamiento secuencial 16

2.2.1 Definición de tipo de tabla de secuencia 17

2.2.2 Operaciones básicas de la tabla de secuencia 18

2.3 Forma vinculada de almacenamiento de lista lineal estructura 21

2.3.1 Lista enlazada simple 21

2.3.2 Lista enlazada circular 25

2.3.3 Lista enlazada doblemente 26

2.3 .4 Lista enlazada estática 28

2.4 Comparación de dos estructuras de almacenamiento 28

2.5 Formación práctica 29

Resumen de este capítulo 31

Ejercicio 32

Capítulo 3 Pila y cola 35

3.1 Pila 35

3.1.1 Definición de pila y operaciones comunes 35

3.1.2 Estructura de almacenamiento secuencial de la pila 36

3.1.3 Estructura de almacenamiento encadenada de la pila 40

3.1.4 Aplicación de la pila 41

3.2 Cola 47

3.2.1 Definición y operaciones comunes de la cola 47

3.2.2 Estructura de almacenamiento secuencial de la cola 47

3.2.3 Estructura de almacenamiento encadenado de cola 49

3.2.4 Aplicación de cola 51

3.3 Entrenamiento práctico 52

Resumen de este capítulo 55

Ejercicio 56

Capítulo Capítulo 4 Cadena 58

4.1 Definición de cadena y operaciones comunes 58

4.1.1 Definición de cadena y términos relacionados 58

4.1 .2 Operaciones comunes de cadenas 59

4.2 Estructura de almacenamiento de cadenas 59

4.2.1 Estructura de almacenamiento secuencial de longitud fija de cadenas 60

4.2.2 Secuencial dinámico estructura de almacenamiento de cadena 62

4.2.3 Estructura de almacenamiento encadenada de cadena 63

4.3 Coincidencia de patrones de cadena 63

4.4 Aplicación de cadena 65

4.5 Capacitación en implementación 66

Resumen de este capítulo 68

Ejercicio 68

Capítulo 5 Matrices y tablas generalizadas 71

5.1 Array 71

5.1.1 Definición y operaciones comunes de los arrays 71

5.1.2 Estructura de almacenamiento secuencial y operaciones básicas de los arrays 72

5.2 Almacenamiento comprimido de matrices

Almacenamiento 73

5.2.1 Matriz especial 73

5.2.2 Matriz dispersa 76

5.3 Tabla generalizada 77

5.3.1 Generalizada Definición de tablas y operaciones comunes 78

5.3.2 Estructura de almacenamiento de tablas generalizadas 79

* 5.3.3 Implementación de operaciones básicas de tablas generalizadas 82

5.4 Lección práctica 83

Resumen de este capítulo 86

Ejercicio 87

Capítulo 6 Árbol 89

6.1 Estructura lógica del árbol 89

6.1.1 Definición y características lógicas del árbol 89

6.1.2 Forma de representación del árbol 90

6.1.3 Terminología básica del árbol 91

6.1.4 Operaciones comunes de árboles 92

6.2 Árboles binarios 92

6.2.1 Definición y operaciones comunes de árboles binarios 92

6.2.2 Propiedades de árboles binarios 93

6.2.3 Estructura de almacenamiento del árbol binario 96

6.3 Recorrido del árbol binario 97

6.3.1 Concepto de recorrido del árbol binario 97

6.3.2 Algoritmo para recorrido de árbol binario 98

6.4 Construyendo un árbol binario 101

6.4.1 Construyendo un árbol binario a partir de una secuencia transversal 101

6.4.2 Algoritmo para construir un árbol binario 103

6.4.3 Otros algoritmos recursivos para árboles binarios 104

6.5 Árbol binario de pistas 105

6.5.1 El concepto de árbol binario de pistas 105

6.5.2 Enhebrado de árboles binarios 106

6.5.3 Principales algoritmos de árboles binarios enhebrados 107

6.6 Árboles y bosques 109

6.6.1 Estructura de almacenamiento de árboles 109

6.6.2 Conversión de árboles, bosques y árboles binarios 112

6.6 .3 Recorrido de árboles y bosques 115

6.7 Árboles de Huffman 116

6.7.1 Definición del árbol de Huffman 116

6.7.2 Algoritmo de construcción del árbol de Huffman 118

6.7.3 Codificación de Huffman 119

6.8 Formación práctica 120

Resumen de este capítulo 123

Ejercicio 123

Capítulo 7 Figura 127

7.1 Definición y terminología de gráficas 127

7.1.1 Conceptos básicos de gráficas 128

7.1.2 Operaciones básicas de gráficas 130

7.2 Estructura de almacenamiento de gráficos 130

7.2.1 Representación de matriz de adyacencia 130

7.2.2 Representación de lista de adyacencia 131

7.3 Gráfico recorrido 132

7.3.1 Búsqueda en profundidad 133

7.3.2 Búsqueda en amplitud 134

7.4 Árbol de expansión y árbol de expansión mínimo 136

7.4.1 Conceptos básicos 136

7.4 .2 Algoritmo de Prim 137

7.4.3 Algoritmo de Kruskal 138

7.5 Gráfico acíclico dirigido y sus aplicaciones 139

7.5.1 Clasificación topológica 139

7.5.2 Ruta crítica 142

7.6 Ruta más corta 145

7.6.1 El concepto del camino más corto 145

7.6.2 Camino más corto de fuente única 145

7.6.3 Camino más corto entre todos los vértices 148

7.7 Formación práctica 151