Estructuras de datos orientadas a objetos

Por Bruno López

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 o

• Idioma: Español
• Editorial: Alfaomega Grupo Editor
• Fecha de lanzamiento: 17 abr 2024
• ISBN: 9786077079293

Vista previa del libro

p_portada_image

Datos Catalográficos

López Takeyas, Bruno

Estructuras de datos orientadas a objetos Pseudocódigo y aplicaciones en C# .NET

Primera Edición

Alfaomega Grupo Editor, S.A. de C.V., México

ISBN: 978-607-707-529-5

eISBN: 978-607-707-929-3

Formato: 17 X 23 cm

Páginas: 512

Director Editorial

Marcelo Grillo Giannetto

[e-mail]

Editor

Francisco Javier Rodríguez Cruz

[e-mail]

Diagramación

LDG Ingrid García Camacho

Estructuras de datos orientadas a objetos. Pseudocódigos y aplicaciones en C# .NET

Bruno López Takeyas

Derechos reservados © Alfaomega Grupo Editor, S.A. de C.V., México

Primera edición: Alfaomega Grupo Editor, México, septiembre de 2012

© 2012 Alfaomega Grupo Editor, S.A. de C.V.

Pitágoras 1139, Col. Del Valle, 03100, México D.F.

Miembro de la Cámara Nacional de la Industria Editorial Mexicana

Registro No. 2317

Pág. Web: http://www.alfaomega.com.mx

E-mail: [e-mail]

ISBN: 978-607-707-529-5

eISBN: 978-607-707-929-3

La transformación a libro electrónico del presente título fue realizada por

Sextil Online, S.A. de C.V./ Editorial Ink ® 2016.

[phone]

[e-mail]

www.editorial-ink.com

Derechos reservados:

Esta obra es propiedad intelectual de su autor y los derechos de publicación en lengua española han sido legalmente transferidos al editor. Prohibida su reproducción parcial o total por cualquier medio sin permiso por escrito del propietario de los derechos del copyright.

Nota importante:

La información contenida en esta obra tiene un fin exclusivamente didáctico y, por lo tanto, no está previsto su aprovechamiento a nivel profesional o industrial. Las indicaciones técnicas y programas incluidos, han sido elaborados con gran cuidado por los autores y reproducidos bajo estrictas normas de control. ALFAOMEGA GRUPO EDITOR, S.A. de C.V. no será jurídicamente responsable por: errores u omisiones; daños y perjuicios que se pudieran atribuir al uso de la información comprendida en este libro, ni por la utilización indebida que pudiera dársele.

Edición autorizada para venta en todo el mundo.

Impreso en México. Printed in Mexico.

Empresas del grupo:

México: Alfaomega Grupo Editor, S.A. de C.V.

Pitágoras 1139, Col. Del Valle, México, D.F., México, C.P. 03100

Tel.: [phone] Fax: [phone] / 2490. Sin costo: 01-800-020-4396

E-mail: [e-mail]

Colombia: Alfaomega Colombiana S.A. Carrera 15 No. 64 A 29, Bogotá, Colombia

PBX (57-1) 2100122 Fax: [phone]

E-mail: [e-mail]

Chile: Alfaomega Grupo Editor, S.A.

Doctor La Sierra 1437 Providencia, Santiago, Chile

Tel.: [phone] Fax: [phone]

E-mail: [e-mail]

Argentina: Alfaomega Grupo Editor Argentino, S.A.

Paraguay 1307 P.B. 11, Buenos Aires, Argentina, C.P. 1057

Tel.: [phone] / 0887 E-mail: [e-mail]

ACERCA DEL AUTOR

pic-3.jpg

Bruno López Takeyas se tituló de Ingeniero en Sistemas Computacionales en el Instituto Tecnológico de Nuevo Laredo en 1993. Obtuvo el grado de Maestro en Ciencias de la Administración con especialidad en Sistemas en la Universidad Autónoma de Nuevo León en marzo del 2000. Desde 1994 es profesor del Depto. de Sistemas y Computación del Instituto Tecnológico de Nuevo Laredo. También es profesor invitado de varias universidades públicas y privadas en sus programas de nivel maestría.

Ha impartido varias conferencias relacionadas con sistemas computacionales, las más recientes en el Instituto Tecnológico de Cancún y para la Universidad Técnica de Machala, Ecuador.

Entre sus áreas de interés están la Docencia, Programación, Inteligencia Artificial, Algoritmos Genéticos y … el beisbol.

AGRADECIMIENTOS

Durante el tiempo de mi labor como docente, he percibido la dificultad que muestran los estudiantes para comprender las estructuras de datos, por ello, quiero agradecerles especialmente a ellos, quienes al manifestar sus dudas y cuestionamientos, me motivaron a escribir esta obra.

Reconozco el esfuerzo de mis compañeros maestros, quienes al compartir sus conocimientos, experiencia, inquietudes y anhelos académicos, enriquecieron el material del libro; especialmente al M.C. Ramón V. Roque Hernández y a la M.C. Thelma Guadalupe Cantú Treviño, quienes me apoyaron durante la revisión de los capítulos.

Manifiesto especial gratitud al estudiante Pablo Fernando González Moreno por plasmar su habilidad creativa en el diseño de la portada de este proyecto.

También quiero mostrar mi agradecimiento a la Dirección General de Educación Superior Tecnológica y al equipo administrativo de mi alma máter, el Instituto Tecnológico de Nuevo Laredo, por apoyar el desarrollo de actividades académicas, especialmente al M.C. Sergio Efraín Beltrán Beltrán, Director y al Ing. Humberto Peña Valle, Jefe del Departamento de Sistemas y Computación.

Bruno López Takeyas

Agosto 2011

Dedicado especialmente para

Josefa, Bruno, Fely, Irma, Pepe y Luisa Fernanda.

A mi familia. A mis maestros.

No es vergüenza no saber, sino saber que no sabes y no querer saber

- Bruno López Takeyas -

MENSAJE DEL EDITOR

Una de las convicciones fundamentales de Alfaomega es que los conocimientos son esenciales en el desempeño profesional, ya que sin ellos es imposible adquirir las habilidades para competir laboralmente. El avance de la ciencia y de la técnica hace necesario actualizar continuamente esos conocimientos, y de acuerdo con esto Alfaomega publica obras actualizadas, con alto rigor científico y técnico, y escritas por los especialistas del área respectiva más destacados.

Consciente del alto nivel competitivo que debe de adquirir el estudiante durante su formación profesional, Alfaomega aporta un fondo editorial que se destaca por sus lineamientos pedagógicos que coadyuvan a desarrollar las competencias requeridas en cada profesión específica.

De acuerdo con esta misión, con el fin de facilitar la comprensión y apropiación del contenido de esta obra, cada capítulo inicia con el planteamiento de los objetivos del mismo y con una introducción en la que se plantean los antecedentes y una descripción de la estructura lógica de los temas expuestos, asimismo a lo largo de la exposición se presentan ejemplos desarrollados con todo detalle y cada capítulo concluye con un resumen y una serie de ejercicios propuestos.

Además de la estructura pedagógica con que están diseñados nuestros libros, Alfaomega hace uso de los medios impresos tradicionales en combinación con las Tecnologías de la Información y las Comunicaciones (TIC) para facilitar el aprendizaje. Correspondiente a este concepto de edición, todas nuestras obras tienen su complemento en una página Web en donde el alumno y el profesor encontrarán lecturas complementarias así como programas desarrollados en relación con temas específicos de la obra.

Los libros de Alfaomega están diseñados para ser utilizados en los procesos de enseñanza-aprendizaje, y pueden ser usados como textos en diversos cursos o como apoyo para reforzar el desarrollo profesional, de esta forma Alfaomega espera contribuir así a la formación y al desarrollo de profesionales exitosos para beneficio de la sociedad, y espera ser su compañera profesional en este viaje de por vida por el mundo del conocimiento.

CONTENIDO

PRÓLOGO

CAPÍTULO 1. INTRODUCCIÓN A LA PROGRAMACIÓN ORIENTADA A OBJETOS

1.1 Introducción

1.2 Resolución de problemas mediante la computadora

1.3 Conceptos de programación orientada a objetos

1.3.1 Clase

1.3.2 Objeto

1.3.3 Atributo

1.3.4 Método

1.3.5 Propiedad

1.3.6 Constructor

1.3.7 Destructor

1.3.8 Mensaje

1.3.9 Instancia

1.3.10 Sobrecarga

1.3.11 Clase abstracta

1.3.12 Interface

1.3.13 Clase parametrizada

1.4 Características de la POO

1.4.1 Abstracción

1.4.2 Encapsulamiento

1.4.3 Modularidad

1.4.4 Herencia

1.4.5 Polimorfismo

1.5 Ventajas de la POO

1.6 Análisis y diseño orientado a objetos

1.7 Introducción a UML

1.7.1 Diagramas de clases en UML

1.7.2 Restricciones de acceso de los componentes de una clase

1.7.3 Relaciones entre clases

1.7.4 Clases abstractas e interfaces

1.7.5 Clases parametrizadas

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

CAPÍTULO 2. EL LENGUAJE DE PROGRAMACIÓN MICROSOFT C#.NET

2.1 Introducción

2.2 La plataforma.NET

2.3 El compilador Microsoft Visual C# 2010 Express

2.3.1 Descarga de Microsoft Visual C# 2010 Express

2.3.2 Creación de proyectos con Microsoft Visual C# 2010 Express

2.4 ¿Cómo agregar clases al proyecto?

2.5 Controles de formas de Windows

2.5.1 Propiedades de los controles de formas de Windows

2.5.2 Controles más comunes

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

CAPÍTULO 3. ARREGLOS

3.1 Introducción

3.2 Definición de arreglo y sus características

3.3 Arreglos unidimensionales

3.3.1 Representación de arreglos unidimensionales

3.3.2 Operaciones con arreglos unidimensionales

3.3.3 Ejemplos de arreglos unidimensionales

3.3.4 Situaciones críticas al trabajar con arreglos unidimensionales

3.4 Arreglos unidimensionales desordenados

3.4.1 Definición de una clase para el arreglo desordenado que almacena números enteros

3.4.2 Programa 3.1. Proyecto de consola en C# con un arreglo unidimensional desordenado: Datos enteros

pin_web_white.jpg 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

pin_web_white.jpg PROGRAMA 3.2 CÓDIGO FUENTE

3.5 Arreglos unidimensionales ordenados

3.5.1 Definición de una clase para el arreglo unidimensional ordenado

3.5.2 Programa 3.3. Proyecto de consola en C# con un arreglo unidimensional ordenado: Datos enteros

pin_web_white.jpg 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

pin_web_white.jpg PROGRAMA 3.4 CÓDIGO FUENTE

3.6 Arreglos bidimensionales

3.6.1 Representación de arreglos bidimensionales

3.6.2 Operaciones con arreglos bidimensionales

3.6.3 Ejemplos de arreglos bidimensionales

3.6.4 Definición de una clase para un arreglo bidimensional que almacene números reales

3.6.5 Programa 3.5. Proyecto de consola en C# con un arreglo bidimensional: suma y multiplicación matriciales

pin_web_white.jpg PROGRAMA 3.5 CÓDIGO FUENTE

3.6.6 Proyecto de formas de Windows con un arreglo bidimensional: Ventas

pin_web_white.jpg PROGRAMA 3.6 CÓDIGO FUENTE

3.7 Arreglos tridimensionales

3.7.1 Representación de arreglos tridimensionales

3.7.2 Operaciones con arreglos tridimensionales

3.7.3 Ejemplos de arreglos tridimensionales

3.7.4 Definición de una clase para un arreglo tridimensional que almacene calificaciones

3.7.5 Programa 3.7. Proyecto de consola en C# con un arreglo tridimensional: Calificaciones

pin_web_white.jpg PROGRAMA 3.7 CÓDIGO FUENTE

3.7.6 Programa 3.8. Proyecto de formas de Windows con un arreglo tridimensional: Ventas

pin_web_white.jpg PROGRAMA 3.8 CÓDIGO FUENTE

3.8 Aplicación de arreglos unidimensionales usando la clase genérica ArrayList

3.8.1 Principales métodos y propiedades de la clase genérica ArrayList

3.8.2 Programa 3.9. Proyecto en C# de una aplicación de consola utilizando la clase genérica ArrayList

pin_web_white.jpg PROGRAMA 3.9 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS CON ARREGLOS UNIIDIMENSIONALES LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS CON ARREGLOS BIDIMENSIONALES LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS CON ARREGLOS TRIDIMENSIONALES LECTURA COMPLEMENTARIA

CAPÍTULO 4. PILAS

4.1 Introducción

4.2 Representación de pilas

4.3 Operaciones con pilas

4.4 Ejemplos de pilas

4.5 Situaciones críticas al trabajar con pilas

4.6 Definición de la clase para una pila

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

pin_web_white.jpg PROGRAMA 4.1 CÓDIGO FUENTE

4.8 Programa 4.2 Proyecto de formas de Windows en C# con una pila: estacionamiento de autos

4.8.1 Entrada de auto (Push)

4.8.2 Salida de auto (Pop)

4.8.3 Definición de las clases para la pila

pin_web_white.jpg PROGRAMA 4.2 CÓDIGO FUENTE

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

4.9.1 Principales métodos y propiedades de la clase genérica Stack

4.9.2 Programa 4.3. Proyecto de consola en C# con una aplicación utilizando la clase genérica Stack

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 5. COLAS

5.1 Introducción

5.2 Representación de colas

5.3 Operaciones con colas

5.4 Ejemplos de colas

5.5 Situaciones críticas al trabajar con colas

5.6 Definición de la clase para una cola

5.7 Programa 5.1 Proyecto de consola en C# con una cola: datos enteros

pin_web_white.jpg PROGRAMA 5.1 CÓDIGO FUENTE

5.8 Programa 5.2 Proyecto de formas de Windows en C# con una cola: banco

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

5.8.2 Atender en ventanilla (Eliminación)

5.8.3 Definición de las clases para una cola

pin_web_white.jpg PROGRAMA 5.2 CÓDIGO FUENTE

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

5.9.1 Principales métodos y propiedades de la clase genérica Queue

5.9.2 Programa 5.3. Proyecto de consola en C# con una aplicación utilizando la clase genérica Queue

pin_web_white.jpg PROGRAMA 5.3 CÓDIGO FUENTE

5.10 Colas circulares

5.10.1 Definición de una clase para la cola circular

5.10.2 Programa 5.4. Proyecto de consola en C# con una aplicación de una cola circular: Datos enteros

pin_web_white.jpg 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

pin_web_white.jpg PROGRAMA 5.5 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 6. LISTAS ENLAZADAS

6.1 Introducción

6.2 Representación de listas simples

6.3 Operaciones y situaciones críticas que se pueden presentar al trabajar con listas simples

6.4 Ejemplos de listas simples

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

6.6 Programa 6.1 Proyecto de consola en C# con una lista enlazada simple ordenada: datos enteros

pin_web_white.jpg 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

6.7.1 Insertar objetos

6.7.2 Borrar un objeto

6.7.3 Definición de las clases para una lista simple

pin_web_white.jpg PROGRAMA 6.2 CÓDIGO FUENTE

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

6.8.1 Principales métodos y propiedades de la clase genérica List

6.8.2 Programa 6.3 Proyecto de consola en C# con una aplicación de la clase genérica List

pin_web_white.jpg PROGRAMA 6.3 CÓDIGO FUENTE

6.9 Implementación de pilas mediante listas simples

6.9.1 Representación de una pila con datos desordenados mediante una lista simple (Pila-Desordenada-Lista)

pin_web_white.jpg PROGRAMA 6.4 CÓDIGO FUENTE

6.9.2 Representación de una pila con datos ordenados mediante una lista simple (pila-ordena-lista)

pin_web_white.jpg PROGRAMA 6.5 CÓDIGO FUENTE

6.10 Implementación de una cola mediante una lista simple

6.10.1 Representación de una cola mediante una lista simple (Cola-Lista)

6.10.2 Operaciones básicas con una Cola-Lista

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

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

6.10.5 Programa 6.6. Proyecto de consola en C# con una Cola-Lista: Datos enteros

pin_web_white.jpg PROGRAMA 6.6 CÓDIGO FUENTE

6.11 Listas enlazadas dobles

6.11.1 Representación de listas dobles

6.11.2 Operaciones y situaciones críticas que se pueden presentar al trabajar con listas dobles

6.11.3 Ejemplo de listas dobles

6.11.4 Definición de las clases para una lista Doble con nodos ordenados

6.12 Programa 6.7 Proyecto de consola en C# con una lista doble ordenada: Datos enteros

pin_web_white.jpg PROGRAMA 6.7 CÓDIGO FUENTE

6.13 Programa 6.8 Proyecto de formas de Windows con una lista doble desordenada: Ferrocarril

6.13.1 Agregar un vagón a la lista doble

pin_web_white.jpg PROGRAMA 6.7 CÓDIGO FUENTE

6.13.2 Eliminar un vagón de la lista doble

6.13.3 Mostrar desde el principio y desde el final

6.13.4 Buscar vagón

6.13.5 Definición de las clases de la lista doble para almacenar los datos del ferrocarril

pin_web_white.jpg PROGRAMA 6.8 CÓDIGO FUENTE

6.14 Aplicación de listas dobles usando las clases genéricas LinkedList y LinkedListNode

6.14.1 Principales métodos y propiedades de las clases genéricas LinkedList y LinkedListNode

6.14.2 Programa 6.9. Proyecto de consola en C# con una aplicación utilizando las clases genéricas LinkedList y LinkedListNode

pin_web_white.jpg PROGRAMA 6.9 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 7. RECURSIVIDAD

7.1 Introducción

7.2 Ejemplos de recursividad en la vida cotidiana

7.3 Algoritmos recursivos

7.4 Ventajas y desventajas del uso de algoritmos recursivos

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

7.6 Envío de parámetros a un método: por valor y por referencia

pin_web_white.jpg PARÁMETROS POR VALOR Y POR REFERENCIA LECTURA COMPLEMENTARIA

pin_web_white.jpg PROGRAMA 7.1 CÓDIGO FUENTE

pin_web_white.jpg PROGRAMA 7.2 CÓDIGO FUENTE

pin_web_white.jpg PROGRAMA 7.3 CÓDIGO FUENTE

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

7.7.1 Programa 7.4. Proyecto de consola en C# con un algoritmo recursivo: Cálculo del factorial

pin_web_white.jpg PROGRAMA 7.4 CÓDIGO FUENTE

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

7.9 Programa 7.5 Proyecto de formas de Windows en C# con un algoritmo recursivo: Las torres de Hanoi

pin_web_white.jpg PROGRAMA 7.5 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 8. ÁRBOLES BINARIOS

8.1 Introducción

8.2 Árboles binarios

8.3 Representación de árboles binarios

8.4 Árboles binarios de búsqueda

8.5 Operaciones y situaciones críticas que se pueden presentar al trabajar con árboles binarios de búsqueda

8.6 Ejemplos de árboles binarios

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

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

pin_web_white.jpg 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

8.9.1 ¿Cómo dibujar una estructura de datos utilizando Graphviz?

pin_web_white.jpg GRAPHVIZ Y EL LENGUAJE DOT LECTURA COMPLEMENTARIA

pin_web_white.jpg PROGRAMA 8.2 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 9. GRAFOS

9.1 Introducción

9.2 Representación de grafos

9.2.1 Representación secuencial de grafos: matriz de adyacencia

9.2.2 Representación enlazada de grafos: listas enlazadas

pin_web_white.jpg PROGRAMA 9.1 CÓDIGO FUENTE

pin_web_white.jpg PROGRAMA 9.2 CÓDIGO FUENTE

9.3 Operaciones con grafos representados mediante listas

9.4 Ejemplos de grafos

9.5 Definición de las clases para un grafo dirigido no ponderado representado mediante listas

9.5.1 Búsqueda de un camino entre dos nodos: recorridos en profundidad y en anchura

9.5.2 Representación de los recorridos en profundidad y anchura

9.6 Programa 9.3. Proyecto de consola en C# con un grafo dirigido no ponderado: Datos enteros

pin_web_white.jpg PROGRAMA 9.3 CÓDIGO FUENTE

9.7 Definición de las clases para un grafo no dirigido y ponderado representado mediante listas

9.7.1 Búsqueda de un camino más corto entre dos nodos: recorrido del camino mínimo

9.7.2 Representación del recorrido del camino mínimo

9.7.3 Representación de las clases necesarias para dibujar el grafo

9.8 Programa 9.4. Proyecto de formas de Windows en C# con un grafo no dirigido y ponderado: Mapa carretero entre ciudades

9.8.1 Insertar ciudad

9.8.2 Eliminar ciudad

9.8.3 Cargar un ejemplo prediseñado

9.8.4 Dibujar el mapa

9.8.5 Insertar una carretera

9.8.6 Eliminar una carretera

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

9.8.8 Representación de las clases

pin_web_white.jpg PROGRAMA 9.4 CÓDIGO FUENTE

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

CAPÍTULO 10. MÉTODOS DE ORDENAMIENTO

10.1 Introducción

10.2 Criterios de ordenamiento

10.3 Tipos de ordenamiento

10.4 Consideraciones importantes para el pseudocódigo de los métodos

10.5 Métodos de ordenamiento interno

10.5.1 Métodos de ordenamiento interno por intercambio

10.5.2 Métodos de ordenamiento interno por selección

10.5.3 Métodos de ordenamiento interno por inserción

10.5.4 Métodos de ordenamiento interno de árbol

10.5.5 Definición de las clases para los métodos de ordenamiento interno

10.5.6 Consideraciones importantes para la implementación de las clases

10.5.7 Programa 10.1 Proyecto de consola en C# con métodos de ordenamiento interno: datos enteros

pin_web_white.jpg 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

pin_web_white.jpg PROGRAMA 10.2 CÓDIGO FUENTE

10.5.9 Análisis de eficiencia de los métodos de ordenamiento interno

pin_web_white.jpg CUESTIONARIO LECTURA COMPLEMENTARIA

pin_web_white.jpg EJERCICIOS LECTURA COMPLEMENTARIA

Bibliografía

Índice analítico

PRÓLOGO

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.

Durante los años que he tenido la oportunidad de desempeñar trabajo docente, he podido observar la dificultad que ofrece el curso de Estructura de Datos a los estudiantes de computación, ya que, por una parte, el curso demanda del estudiante la organización de su razonamiento para plantear soluciones a diversos problemas, analizando conceptos, teorías, procedimientos y estructuras lógicas de manera teórica y por otra la comprobación de dichos planteamientos mediante implementaciones prácticas a través de programas computacionales. Esta combinación teórico-práctica, en muchas ocasiones provoca presión y estrés en los estudiantes debido a que por una parte deben definir un modelo lógico a la solución de un problema (el cual exige un ejercicio mental) y por otra parte deben aterrizarlo en una aplicación práctica que demuestre que el planteamiento es adecuado, donde la exigencia es tener habilidades en el desarrollo de sistemas de cómputo.

A QUIÉNES ESTÁ DIRIGIDA ESTA OBRA

Las vivencias en el aula me motivaron a desarrollar este material, que sirve de base para el curso de Estructura de Datos y está dirigido a las siguientes personas:

Estudiantes que por primera ocasión cursan la materia. Para ellos resulta un texto que los lleva de la mano en el avance programático del curso, donde el estudiante puede sentir confianza de contar con el material necesario y suficiente para cumplir con las exigencias de la materia. Para ellos, resulta un eslabón más en su cadena de aprendizaje, porque es continuación de los cursos tomados con anterioridad, donde seguramente aprendieron a desarrollar técnicas para la solución de problemas a través de la computadora y habilidades de programación con un enfoque orientado a objetos y que, aunado a los conocimientos, habilidades y competencias adquiridas en este curso, servirán de base para cursos posteriores.

Profesores. Es una guía teórico-práctica aplicada directamente a las necesidades del curso, la cual le ayudará en el aula al momento de impartir los aspectos teóricos, en el laboratorio durante el desarrollo de los programas y como parte del instrumento de evaluación, ya que cada capítulo presenta al final un cuestionario y una serie de ejercicios prácticos.

Estudiantes o egresados que cursaron la materia con un enfoque no orientado a objetos. El contenido de esta obra es una buena oportunidad de actualización en el ambiente de los objetos con un enfoque directo a las estructuras de datos, donde la finalidad es aplicarlos en situaciones particulares orientadas a la solución de problemas. Además le brinda la oportunidad de conocer una nueva plataforma de desarrollo de aplicaciones de software como es .NET en un lenguaje de programación poderoso y de fácil acceso como C#.

Interesados en conocer, dominar, profundizar y aplicar estructuras de datos orientadas a objetos en la solución de problemas en C#. Sirve de base para aplicar los conceptos de las estructuras de datos y 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#. Además le brinda la oportunidad de emigrar sus aplicaciones desarrollas en antiguos lenguajes de programación a una plataforma de desarrollo muy poderosa como .NET en un lenguaje actual y de gran versatilidad como C#.

CARACTERÍSTICAS DE CADA CAPÍTULO

La lectura de cada capítulo pretende ser independiente del resto (en la medida de lo posible) y presenta el siguiente esquema:

Contiene una introducción a la estructura de datos analizada donde se explican los términos utilizados y sus características principales.

Se muestra la representación gráfica de la estructura en cuestión.

Explica a detalle las operaciones y las situaciones críticas que se pueden presentar al trabajar con la estructura de datos.

Muestra ejemplos de la vida cotidiana donde se aplica la estructura de datos estudiada.

Se explica paso a paso el análisis, diseño orientado a objetos y pseudocódigo de cada programa que ilustra el uso de la estructura.

Incluye una aplicación práctica, sencilla y completa en modo consola utilizando el lenguaje de programación C# .NET.

Contiene una aplicación práctica de la vida cotidiana mediante un programa en modo gráfico que utiliza formas (formularios) en C# .NET.

Agrega una aplicación en C# .NET que utiliza las clases genéricas incluidas en el espacio de nombres System.Collections.Generic de la biblioteca de .NET.

Al final, se muestra un cuestionario y un conjunto de ejercicios que sirven para reforzar el aprendizaje y pueden utilizarse como estrategia de evaluación.

COMPETENCIAS PREVIAS

Para aprovechar al máximo el material expuesto en esta obra, es importante que el lector muestre habilidad en las siguientes competencias:

Conocimiento y aplicación de técnicas de solución de problemas a través de la computadora.

Fundamentos de programación.

Representación de modelos orientados a objetos.

Aplicación de técnicas de análisis y diseño orientado a objetos.

Programación orientada a objetos en el lenguaje C# .NET.

ORGANIZACIÓN DEL LIBRO

Este libro se compone de los siguientes capítulos:

Capítulo 1. Introducción a la Programación Orientada a Objetos.- Este capítulo contiene un repaso general de la metodología para resolver problemas a través de la computadora y explica los conceptos básicos relacionados con la Programación Orientada a Objetos (POO) así como sus características y ventajas. También se hace una breve introducción al Lenguaje Unificado de Modelado (UML) haciendo énfasis en la representación de clases, ya que se utilizará en el resto de los capítulos.

Capítulo 2. El lenguaje de Programación Microsoft C# .NET.- En este capítulo se hace una breve introducción a la plataforma .NET, posteriormente se describe la descarga, instalación y utilización del compilador Microsoft Visual C# 2010 Express, el cual se utiliza para la realización de todos los programas contenidos en esta obra. En este capítulo se hace especial énfasis en el uso y propiedades de los controles a utilizar en los proyectos con formas de Windows de los capítulos posteriores.

Capítulo 3. Arreglos.- Este capítulo se explica a detalle la definición, características, representación, operaciones, ejemplos y situaciones críticas de arreglos unidimensionales (vectores), bidimensionales (matrices) y tridimensionales (cubos). Los vectores se analizan con dos enfoques: arreglos con datos desordenados y con datos ordenados. Los proyectos de consola con vectores (tanto ordenados como desordenados) administran datos simples de tipo entero. La aplicación de un vector desordenado con formas de Windows utiliza un arreglo de objetos con datos de los jugadores de un equipo de beisbol para identificar al mejor bateador, mientras que la aplicación de un vector ordenado con formas de Windows aplica un arreglo de objetos para mantener ordenados los datos de estudiantes y sus calificaciones. El proyecto de consola con matrices resuelve el problema matemático de la suma y multiplicación matricial, mientras que su proyecto con formas de Windows administra las ventas mensuales durante un año de una empresa con tres departamentos. El proyecto de consola con un cubo almacena las calificaciones de 4 materias de un grupo de 20 estudiantes durante 6 períodos escolares y se ejecutan en él varias operaciones; mientras que su aplicación de Windows almacena las ventas trimestrales de una empresa con 3 productos durante 2 años. Al final del capítulo se muestra una aplicación sencilla en modo consola con una aplicación de un arreglo unidimensional utilizando la clase genérica ArrayList.

Capítulo 4.- Pilas.Una pila es una estructura de datos con un comportamiento particular en la que el primer dato en entrar es el último en salir ó bien el último en entrar es el primero en salir y este capítulo explica a detalle su representación, operaciones, ejemplos de la vida cotidiana y situaciones críticas durante su manipulación. En este capítulo se analizan las pilas con una representación por medio de arreglos, es decir, con un enfoque estático. El proyecto de consola almacena datos de tipo entero en una pila, mientras que el proyecto con formas de Windows utiliza una pila que almacena objetos con datos de autos estacionados. Al final del capítulo se muestra una aplicación en modo consola que utiliza una pila para almacenar datos de tipo entero mediante la implementación de la clase genérica Stack.

Capítulo 5. Colas.- Una cola es una estructura que se comporta de la siguiente forma: el primer dato en entrar es el primero en salir, ó bien, el último dato en entrar es el último en salir y en este capítulo se explica detalladamente su representación, operaciones, ejemplos cotidianos y situaciones críticas al trabajar con ellas. Aquí se analiza la implementación de colas y colas circulares mediante arreglos, o sea, con un enfoque estático. Igual que en otros capítulos, el proyecto de consola de colas y de colas circulares, almacena datos de tipo entero. El proyecto de colas con formas de Windows simula el funcionamiento de una ventanilla de un banco, almacenando objetos con datos de los clientes; mientras que el proyecto de colas circulares con formas de Windows simula el funcionamiento de un marco fotográfico digital que almacena los nombres de los archivos de fotografías para exhibirlas de manera progresiva posteriormente.

También se explica un proyecto en modo consola con una cola que almacena datos de tipo entero mediante una implementación de la clase genérica Queue.

Capítulo 6.- Listas enlazadas. Aquí se muestra la primera estructura de datos dinámica del libro: la lista enlazada. Una estructura dinámica no requiere definir su tamaño inicial, ya que crece ó disminuye de acuerdo a la cantidad de datos que se insertan ó eliminan en ella. Este capítulo muestra la introducción, representación, operaciones, ejemplos y situaciones críticas al trabajar con listas enlazadas simples y dobles. Los proyectos de consola con listas simples y con listas dobles, almacenan datos ordenados de tipo entero. La aplicación de listas simples con formas de Windows, administra objetos con datos de estudiantes y sus libros. Para las listas simples también se incluye una aplicación en modo consola que almacena datos enteros mediante una implementación con la clase genérica List. El proyecto de listas dobles con formas de Windows administra objetos con los datos de los vagones de un ferrocarril. También se incluye un proyecto de consola con una lista doble de datos enteros utilizando las clases genéricas LinkedList y LinkedListNode. En este capítulo también se explica la implementación de pilas y colas mediante listas simples, las cuales conservan su comportamiento, pero con un enfoque dinámico. Este capítulo se utiliza como antecedente para las aplicaciones de grafos desarrolladas y explicadas en el capítulo 9.

Capítulo 7.- Recursividad. Aunque la recursividad no es una estructura de datos, es importante analizarla como una estrategia de implementación de ciertos procesos con la finalidad de facilitar su comprensión. Es por eso, que aquí se muestran algunos ejemplos recursivos de la vida cotidiana, se explican los algoritmos recursivos, sus características, ventajas y desventajas y para entenderlos mejor, se hace referencia al ámbito de las variables, definiendo variables globales y locales. También se explica el envío de parámetros por valor y por referencia y parámetros de salida (incluyendo varios proyectos en modo consola). El proyecto de consola contiene una aplicación típica de la aplicación de un algoritmo recursivo: el cálculo del factorial de un número; mientras que el proyecto con formas de Windows resuelve el problema de las torres de Hanoi mediante un algoritmo recursivo. Este capítulo se utiliza como antecedente para los recorridos de árboles explicados en el capítulo 8.

Capítulo 8. Árboles binarios.- En este capítulo se introduce la primera estructura de datos no lineal del libro: el árbol binario. En los capítulos previos se habían analizado estructuras de datos lineales, es decir, aquellas en las que cada dato tiene uno y sólo un antecesor y sucesor (con excepción del primero ó el último, explicados en su momento); sin embargo, una estructura no lineal tiene como característica que un dato puede tener varios sucesores, la cual, complica considerablemente el recorrido de la estructura. En este capítulo se explica el detalle de la representación, ejemplos, operaciones y situaciones críticas de árboles binarios, haciendo especial énfasis en los árboles binarios de búsqueda (ABB). Tanto el proyecto en modo consola como el proyecto con formas de Windows contienen un ABB con datos de tipo entero; sin embargo, el proyecto con formas de Windows, contiene una sección muy atractiva que dibuja el ABB en pantalla utilizando el software de libre distribución: Graphviz y el lenguaje dot. En esta aplicación se explica a detalle la manera de utilizar este software para dibujar en pantalla diversas estructuras de datos.

Capítulo 9. Grafos.- El grafo es quizá la estructura de datos más complicada para muchos estudiantes de informática, ya que se trata de una estructura de datos no lineal que se compone de nodos y arcos, en la que existe la posibilidad de que se presenten ciclos, es decir, que durante el recorrido de la estructura se pueda regresar a un nodo previamente visitado. En este capítulo se explican los conceptos relacionados con grafos, sus esquemas de representación, ejemplos cotidianos y sus operaciones. Se muestran grafos con arcos con un sentido de dirección (grafo dirigido) ó con arcos bidireccionales (no dirigido), además, grafos con arcos etiquetados (grafos ponderados) ó sin etiqueta (grafos no ponderados). Una representación de grafos se basa en la utilización de arreglos bidimensionales ó matrices, para ello se explica detalladamente el diseño de dos proyectos en modo consola con esta representación y sus aplicaciones prácticas: el algoritmo de Warshall para saber si hay camino entre dos nodos y el algoritmo de Floyd para conocer la distancia más corta del camino que une dos nodos. Para explicar la representación de grafos mediante listas enlazadas se diseña una aplicación de consola con un grafo dirigido no ponderado que almacena datos enteros, mientras que el proyecto con formas de Windows contiene una aplicación típica de un grafo no dirigido ponderado: un mapa carretero entre ciudades. En esta aplicación se administra un grafo que contiene ciudades (nodos) y sus carreteras (arcos) con sus distancias, la cual también utiliza el software Graphviz y el lenguaje dot para dibujar el grafo en pantalla. Este proyecto encuentra el camino más corto para desplazarse de una ciudad a otra.

Capítulo 10. Métodos de ordenamiento.- En muchas ocasiones es necesario tener ordenado un conjunto de datos para localizar rápidamente algún dato en particular. Para ello, se somete dicho conjunto de datos a un método de ordenamiento. Estos métodos de ordenamiento se clasifican en internos y externos. Los métodos de ordenamiento internos funcionan con un conjunto de datos almacenados en la memoria principal, mientras que los externos se aplican a un conjunto de datos almacenados en algún dispositivo de almacenamiento secundario. En este capítulo se explica a detalle el funcionamiento de varios métodos de ordenamiento tanto internos como externos y se hace un análisis de eficiencia y comparaciones entre ellos.

MATERIAL WEB COMPLEMENTARIO

Como parte de la exposición del libro, en la página Web del mismo se incluyen la exposición de temas adicionales, el código fuente completo de todos los programas expuestos así como el cuestionario y los ejercicios de cada capítulo. En la tabla de contenido se encuentran listados por capítulo todos los recursos incluidos, además de que se señala el tipo de recurso y se destaca la sección del capítulo con la que está asociado.

PLATAFORMA DE CONTENIDOS INTERACTIVOS

Para tener acceso al material Web complementario del libro, siga los siguientes pasos:

Ir a la página http://virtual.alfaomega.com.mx

Registrarse como usuario del sitio.

En el catálogo identificar este libro y descargar el material adicional.

Bruno López Takeyas

Nuevo Laredo, Tam., México

Agosto 2011

Email: [e-mail]

Web: http://www.itnuevolaredo.edu.mx/takeyas

CAPÍTULO 1

pic-cap.png

INTRODUCCIÓN A LA PROGRAMACIÓN ORIENTADA A OBJETOS

1.1 INTRODUCCIÓN

1.2 RESOLUCIÓN DE PROBLEMAS MEDIANTE LA COMPUTADORA

1.3 CONCEPTOS DE PROGRAMACIÓN ORIENTADA A OBJETOS

1.4 CARACTERÍSTICAS DE LA POO

1.5 VENTAJAS DE LA POO

1.6 ANÁLISIS Y DISEÑO ORIENTADO A OBJETOS

1.7 INTRODUCCIÓN A UML

COMPETENCIAS GENERALES

Dominar la metodología