ESTRUCTURAS DE DATOS ORIENTADAS A OBJETOS – Pseudocódigo y Aplicaciones en C#.NET

Este es un libro de texto para los cursos de Estructuras de Datos, y es la base para aplicar los conceptos de estas estructuras y de la programación orientada a objetos a situaciones particulares de la vida cotidiana que requieren una solución práctica implementada en un lenguaje de programación poderosos y actual como C#.

Muchos problemas de las organizaciones actuales se resuelven a través de sistemas informáticos, de los cuales un componente importante son los datos. De su correcta manipulación depende el éxito y el impacto causado. Es por ello que se debe poner especial atención al tratamiento que se le da a esas pequeñas unidades elementales de las entidades involucradas. Sin embargo, existen diversas formas de organizar estos datos, provocando con esto variantes en su utilización, de tal forma que determinadas formas de organización sean recomendables para algunas aplicaciones pero no para otras; además, no es posible la concepción de un sistema informático sin pensar en la forma de administrar los datos. Por esta razón, las carreras profesionales de sistemas computacionales, informática y en general de computación, tienen en su plan de estudios cursos del objeto de estudio de esta obra: Estructura de Datos.

Ventajas Competitivas 

El enfoque práctico, el contenido y el material web complementario hacen de este libro un auxiliar extraordinario en el aprendizaje de la aplicación de la programación orientada objetos al caso de las estructuras de datos. En particular se tiene que:

Como parte fundamental de lo expuesto, en la página Web del libro se incluyen la exposición de temas adicionales.

En la página Web del libro se encuentra disponible el código fuente completo de todos los programas expuestos en el libro.

En la página web del libro se incluyen el cuestionario y los ejercicios de cada capítulo del libro.

Conozca

• Los conceptos básicos de la POO aplicada a las estructuras de datos.

Aprenda

• A usar el compilador Microsoft Visual C# 2010.
• Cómo escribir programas utilizando POO cuyo propósito general sea resolver problemas de la vida cotidiana.

Contenido

CAPÍTULO 1

INTRODUCCIÓN A LA PROGRAMACIÓN ORIENTADA A OBJETOS

1.1 Introducción 2

1.2 Resolución de problemas mediante la computadora 3

1.3 Conceptos de programación orientada a objetos 5

1.3.1 Clase 5

1.3.2 Objeto 5

1.3.3 Atributo 5

1.3.4 Método 5

1.3.5 Propiedad 6

1.3.6 Constructor 6

1.3.7 Destructor 6

1.3.8 Mensaje 6

1.3.9 Instancia 6

1.3.10 Sobrecarga 6

1.3.11 Clase abstracta 6

1.3.12 Interface 7

1.3.13 Clase parametrizada 7

1.4 Características de la POO 7

1.4.1 Abstracción 7

1.4.2 Encapsulamiento 8

1.4.3 Modularidad 8

1.4.4 Herencia 8

1.4.5 Polimorfismo 8

1.5 Ventajas de la POO 9

1.6 Análisis y diseño orientado a objetos 9

1.7 Introducción a UML 10

1.7.1 Diagramas de clases en UML 11

1.7.2 Restricciones de acceso de los componentes de una clase 12

1.7.3 Relaciones entre clases 13

1.7.4 Clases abstractas e interfaces 17

1.7.5 Clases parametrizadas 19

CUESTIONARIO LECTURA COMPLEMENTARIA

CAPÍTULO 2

EL LENGUAJE DE PROGRAMACIÓN MICROSOFT C#.NET

2.1 Introducción 22

2.2 La plataforma.NET 22

2.3 El compilador Microsoft Visual C# 2010 Express 23

2.3.1 Descarga de Microsoft Visual C# 2010 Express 24

2.3.2 Creación de proyectos con Microsoft Visual

C# 2010 Express 24

2.4 ¿Cómo agregar clases al proyecto? 26

2.5 Controles de formas de Windows 27

2.5.1 Propiedades de los controles de formas de Windows 28

2.5.2 Controles más comunes 28

CUESTIONARIO LECTURA COMPLEMENTARIA

CAPÍTULO 3

ARREGLOS

3.1 Introducción 42

3.2 Definición de arreglo y sus características 42

3.3 Arreglos unidimensionales 43

3.3.1 Representación de arreglos unidimensionales 43

3.3.2 Operaciones con arreglos unidimensionales 44

3.3.3 Ejemplos de arreglos unidimensionales 46

3.3.4 Situaciones críticas al trabajar con

arreglos unidimensionales 46

3.4 Arreglos unidimensionales desordenados 47

3.4.1 Definición de una clase para el arreglo

desordenado que almacena números enteros 47

3.4.2 Programa 3.1. Proyecto de consola en C#

con un arreglo unidimensional desordenado:

Datos enteros 53

PROGRAMA 3.1 CÓDIGO FUENTE

3.4.3 Programa 3.2. Proyecto de formas de Windows en

C# con un arreglo unidimensional desordenado:

Equipo de béisbol 56

PROGRAMA 3.2 CÓDIGO FUENTE

3.5 Arreglos unidimensionales ordenados 65

3.5.1 Definición de una clase para el arreglo

unidimensional ordenado 65

3.5.2 Programa 3.3. Proyecto de consola en C# con

un arreglo unidimensional ordenado: Datos enteros 69

PROGRAMA 3.3 CÓDIGO FUENTE

3.5.3 Programa 3.4. Proyecto de formas de Windows

en C# con un arreglo unidimensional ordenado:

Calificaciones 73

PROGRAMA 3.4 CÓDIGO FUENTE

3.6 Arreglos bidimensionales 82

3.6.1 Representación de arreglos bidimensionales 82

3.6.2 Operaciones con arreglos bidimensionales 83

3.6.3 Ejemplos de arreglos bidimensionales 83

3.6.4 Definición de una clase para un arreglo

bidimensional que almacene números reales 84

3.6.5 Programa 3.5. Proyecto de consola en C# con

un arreglo bidimensional:

suma y multiplicación matriciales 86

PROGRAMA 3.5 CÓDIGO FUENTE

3.6.6 Proyecto de formas de Windows con

un arreglo bidimensional: Ventas 91

PROGRAMA 3.6 CÓDIGO FUENTE

3.7 Arreglos tridimensionales 99

3.7.1 Representación de arreglos tridimensionales 99

3.7.2 Operaciones con arreglos tridimensionales 101

3.7.3 Ejemplos de arreglos tridimensionales 101

3.7.4 Definición de una clase para un arreglo

tridimensional que almacene calificaciones 101

3.7.5 Programa 3.7. Proyecto de consola en C#

con un arreglo tridimensional: Calificaciones 107

PROGRAMA 3.7 CÓDIGO FUENTE

3.7.6 Programa 3.8. Proyecto de formas de

Windows con un arreglo tridimensional: Ventas 113

PROGRAMA 3.8 CÓDIGO FUENTE

3.8 Aplicación de arreglos unidimensionales usando

la clase genérica ArrayList 123

3.8.1 Principales métodos y propiedades de la

clase genérica ArrayList 123

3.8.2 Programa 3.9. Proyecto en C# de una

aplicación de consola utilizando la

clase genérica ArrayList 123

PROGRAMA 3.9 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS CON ARREGLOS

UNIIDIMENSIONALES LECTURA COMPLEMENTARIA

EJERCICIOS CON ARREGLOS

BIDIMENSIONALES LECTURA COMPLEMENTARIA

EJERCICIOS CON ARREGLOS TRIDIMENSIONALES

LECTURA COMPLEMENTARIA

CAPÍTULO 4

PILAS

4.1 Introducción 126

4.2 Representación de pilas 126

4.3 Operaciones con pilas 127

4.4 Ejemplos de pilas 128

4.5 Situaciones críticas al trabajar con pilas 129

4.6 Definición de la clase para una pila 129

4.7 Programa 4.1 Proyecto de consola en C# con una pila: datos enteros 132

PROGRAMA 4.1 CÓDIGO FUENTE

4.8 Programa 4.2 Proyecto de formas de Windows en

C# con una pila: estacionamiento de autos 135

4.8.1 Entrada de auto (Push) 136

4.8.2 Salida de auto (Pop) 136

4.8.3 Definición de las clases para la pila 137

PROGRAMA 4.2 CÓDIGO FUENTE

4.9 Aplicación de pilas usando la clase genérica Stack 142

4.9.1 Principales métodos y propiedades de la

clase genérica Stack 143

4.9.2 Programa 4.3. Proyecto de consola en C# con

una aplicación utilizando la clase genérica Stack 143

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 5

COLAS

5.1 Introducción 146

5.2 Representación de colas 146

5.3 Operaciones con colas 147

5.4 Ejemplos de colas 148

5.5 Situaciones críticas al trabajar con colas 149

5.6 Definición de la clase para una cola 149

5.7 Programa 5.1 Proyecto de consola en C#

con una cola: datos enteros 153

PROGRAMA 5.1 CÓDIGO FUENTE

5.8 Programa 5.2 Proyecto de formas de Windows

en C# con una cola: banco 156

5.8.1 Entrada de un cliente en la ventanilla (Agregar a la cola) 157

5.8.2 Atender en ventanilla (Eliminación) 157

5.8.3 Definición de las clases para una cola 158

PROGRAMA 5.2 CÓDIGO FUENTE

5.9 Aplicación de colas usando la clase genérica Queue 164

5.9.1 Principales métodos y propiedades de la

clase genérica Queue 164

5.9.2 Programa 5.3. Proyecto de consola en C#

con una aplicación utilizando la clase genérica Queue 165

PROGRAMA 5.3 CÓDIGO FUENTE

5.10 Colas circulares 166

5.10.1 Definición de una clase para la cola circular 167

5.10.2 Programa 5.4. Proyecto de consola en C# con

una aplicación de una cola circular: Datos enteros 170

PROGRAMA 5.4 CÓDIGO FUENTE

5.10.3 Programa 5.5. Proyecto de formas de Windows

en C# con una cola circular: marco fotográfico digital 174

PROGRAMA 5.5 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 6

LISTAS ENLAZADAS

6.1 Introducción 184

6.2 Representación de listas simples 185

6.3 Operaciones y situaciones críticas que se pueden

presentar al trabajar con listas simples 185

6.4 Ejemplos de listas simples 190

6.5 Definición de las clases para una lista simple ordenada 190

6.6 Programa 6.1 Proyecto de consola en C# con una lista enlazada

simple ordenada: datos enteros 198

PROGRAMA 6.1 CÓDIGO FUENTE

6.7 Programa 6.2 Proyecto de formas de Windows

en C# con listas enlazadas simples ordenadas:

estudiantes y sus libros 207

6.7.1 Insertar objetos 208

6.7.2 Borrar un objeto 208

6.7.3 Definición de las clases para una lista simple 209

PROGRAMA 6.2 CÓDIGO FUENTE

6.8 Aplicación de listas simples usando la clase genérica List 223

6.8.1 Principales métodos y propiedades

de la clase genérica List 224

6.8.2 Programa 6.3 Proyecto de consola en C# con una

aplicación de la clase genérica List 224

PROGRAMA 6.3 CÓDIGO FUENTE

6.9 Implementación de pilas mediante listas simples 227

6.9.1 Representación de una pila con datos desordenados

mediante una lista simple (Pila-Desordenada-Lista) 227

PROGRAMA 6.4 CÓDIGO FUENTE

6.9.2 Representación de una pila con datos ordenados

mediante una lista simple (pila-ordena-lista) 239

PROGRAMA 6.5 CÓDIGO FUENTE

6.10 Implementación de una cola mediante una lista simple 250

6.10.1 Representación de una cola mediante

una lista simple (Cola-Lista) 250

6.10.2 Operaciones básicas con una Cola-Lista 251

6.10.3 Situaciones críticas al trabajar con una Cola-Lista 251

6.10.4 Definición de la clase para una Cola-Lista 252

6.10.5 Programa 6.6. Proyecto de consola en

C# con una Cola-Lista: Datos enteros 256

PROGRAMA 6.6 CÓDIGO FUENTE

6.11 Listas enlazadas dobles 263

6.11.1 Representación de listas dobles 263

6.11.2 Operaciones y situaciones críticas que

se pueden presentar al trabajar con listas dobles 264

6.11.3 Ejemplo de listas dobles 269

6.11.4 Definición de las clases para una lista

Doble con nodos ordenados 270

6.12 Programa 6.7 Proyecto de consola en C# con una lista

doble ordenada: Datos enteros 280

PROGRAMA 6.7 CÓDIGO FUENTE

6.13 Programa 6.8 Proyecto de formas de Windows con una

lista doble desordenada: Ferrocarril 290

6.13.1 Agregar un vagón a la lista doble 291

6.13.2 Eliminar un vagón de la lista doble 292

6.13.3 Mostrar desde el principio y desde el final 293

6.13.4 Buscar vagón 293

6.13.5 Definición de las clases de la lista doble para

almacenar los datos del ferrocarril 293

PROGRAMA 6.8 CÓDIGO FUENTE

6.14 Aplicación de listas dobles usando las clases

genéricas LinkedList y LinkedListNode 307

6.14.1 Principales métodos y propiedades de las clases

genéricas LinkedList y LinkedListNode 307

6.14.2 Programa 6.9. Proyecto de consola en C# con

una aplicación utilizando las clases genéricas

LinkedList y LinkedListNode 308

PROGRAMA 6.9 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 7

RECURSIVIDAD

7.1 Introducción 314

7.2 Ejemplos de recursividad en la vida cotidiana 314

7.3 Algoritmos recursivos 315

7.4 Ventajas y desventajas del uso de algoritmos recursivos 316

7.5 Ámbito de las variables: variables globales y variables locales 316

7. 6 Envío de parámetros a un método: por valor y por referencia 317

PARÁMETROS POR VALOR Y POR REFERENCIA

LECTURA COMPLEMENTARIA

PROGRAMA 7.1 CÓDIGO FUENTE

PROGRAMA 7.2 CÓDIGO FUENTE

PROGRAMA 7.3 CÓDIGO FUENTE

7.7 Algoritmo recursivo para calcular el factorial de un número 318

7.7.1 Programa 7.4. Proyecto de consola en C# con

un algoritmo recursivo: Cálculo del factorial 320

PROGRAMA 7.4 CÓDIGO FUENTE

7.8 Algoritmo recursivo para resolver el juego de las torres de Hanoi 320

7.9 Programa 7.5 Proyecto de formas de Windows

en C# con un algoritmo recursivo: Las torres de Hanoi 324

PROGRAMA 7.5 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 8

ÁRBOLES BINARIOS

8.1 Introducción 328

8.2 Árboles binarios 329

8.3 Representación de árboles binarios 330

8.4 Árboles binarios de búsqueda 330

8.5 Operaciones y situaciones críticas que se pueden presentar

al trabajar con árboles binarios de búsqueda 331

8.6 Ejemplos de árboles binarios 338

8.7 Definición de las clases para un árbol binario de búsqueda 339

8.8 Progama 8.1. Proyecto de consola en C# con un ABB: Datos enteros 350

PROGRAMA 8.1 CÓDIGO FUENTE

8.9 Programa 8.2. Proyecto de formas de Windows

en C# con un ABB: Dibujo de un ABB 360

8.9.1 ¿Cómo dibujar una estructura de

datos utilizando Graphviz? 360

GRAPHVIZ Y EL LENGUAJE DOT LECTURA COMPLEMENTARIA

PROGRAMA 8.2 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 9

GRAFOS

9.1 Introducción 362

9.2 Representación de grafos 364

9.2.1 Representación secuencial de grafos:

matriz de adyacencia 365

PROGRAMA 9.1 CÓDIGO FUENTE

PROGRAMA 9.2 CÓDIGO FUENTE

9.2.2 Representación enlazada de grafos: listas enlazadas 376

9.3 Operaciones con grafos representados mediante listas 377

9.4 Ejemplos de grafos 379

9.5 Definición de las clases para un grafo

dirigido no ponderado representado mediante listas 380

9.5.1 Búsqueda de un camino entre dos nodos:

recorridos en profundidad y en anchura 389

9.5.2 Representación de los recorridos en

profundidad y anchura 392

9.6 Programa 9.3. Proyecto de consola en C# con un grafo

dirigido no ponderado: Datos enteros 396

PROGRAMA 9.3 CÓDIGO FUENTE

9.7 Definición de las clases para un grafo no dirigido

y ponderado representado mediante listas 398

9.7.1 Búsqueda de un camino más corto

entre dos nodos: recorrido del camino mínimo 405

9.7.2 Representación del recorrido del camino mínimo 410

9.7.3 Representación de las clases

necesarias para dibujar el grafo 413

9.8 Programa 9.4. Proyecto de formas de Windows

en C# con un grafo no dirigido y ponderado:

Mapa carretero entre ciudades 415

9.8.1 Insertar ciudad 416

9.8.2 Eliminar ciudad 416

9.8.3 Cargar un ejemplo prediseñado 417

9.8.4 Dibujar el mapa 417

9.8.5 Insertar una carretera 418

9.8.6 Eliminar una carretera 418

9.8.7 Buscar camino más corto (camino mínimo) 419

9.8.8 Representación de las clases 419

PROGRAMA 9.4 CÓDIGO FUENTE

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 10

MÉTODOS DE ORDENAMIENTO

10.1 Introducción 424

10.2 Criterios de ordenamiento 424

10.3 Tipos de ordenamiento 425

10.4 Consideraciones importantes para el

pseudocódigo de los métodos 425

10.5 Métodos de ordenamiento interno 426

10.5.1 Métodos de ordenamiento interno por intercambio 427

10.5.2 Métodos de ordenamiento interno por selección 447

10.5.3 Métodos de ordenamiento interno por inserción 450

10.5.4 Métodos de ordenamiento interno de árbol 457

10.5.5 Definición de las clases para

los métodos de ordenamiento interno 462

10.5.6 Consideraciones importantes

para la implementación de las clases 463

10.5.7 Programa 10.1 Proyecto de consola en C# con

métodos de ordenamiento interno: datos enteros 464

PROGRAMA 10.1 CÓDIGO FUENTE

10.5.8 Programa 10.2 Proyecto de formas

de Windows en C# con métodos de ordenamiento

interno: datos de estudiantes 469

PROGRAMA 10.2 CÓDIGO FUENTE

10.5.9 Análisis de eficiencia de los

métodos de ordenamiento interno 474

CUESTIONARIO LECTURA COMPLEMENTARIA

EJERCICIOS LECTURA COMPLEMENTARIA

Bibliografía 483

Índice analítico 485