• Author / Uploaded
• Acastro2608

• Categories
• Java (lenguaje de programación)
• Ingeniería de software
• Software
• Áreas de informática
• Programación de computadoras

Citation preview

Estructura de datos Unidad 1. Estructura de datos

Ingeniería en Desarrollo de Software 4º semestre

Programa de la asignatura: Estructura de datos

Unidad 1. Estructuras de datos Clave: Ingeniería: 15142419

TSU: 16142419

Universidad Abierta y a Distancia de México

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

1

Estructura de datos Unidad 1. Estructura de datos

Índice Unidad 1. Estructuras de datos .............................................................................................. 3 Presentación de la unidad ..................................................................................................... 3 Propósitos ............................................................................................................................. 3 Competencia específica......................................................................................................... 3 Temario de la unidad ............................................................................................................. 3 1. Estructura de datos ............................................................................................................ 4 1.1. Pilas ................................................................................................................................ 4 1.2. Listas .............................................................................................................................. 6 1.3. Colas .............................................................................................................................. 8 Cierre de la unidad .............................................................................................................. 10 Para saber más… ................................................................................................................ 11 Fuentes de consulta ............................................................................................................ 11

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

2

Estructura de datos Unidad 1. Estructura de datos

Unidad 1. Estructuras de datos Presentación de la unidad En esta primera unidad conocerás las tres principales estructuras de datos: pilas, colas y listas. Para cada una de estas estructuras, conocerás, comprenderás y utilizarás adecuadamente las operaciones aplicables. De esta manera, serás capaz de realizar ejercicios de programación en los que apliques las operaciones que se ejecutan sobre las estructuras mencionadas, éstos estarán relacionados con aplicaciones reales.

Propósitos Al término de esta unidad lograrás: 

Emplear pilas, colas y listas, así como sus diferentes operaciones en programas con aplicaciones reales haciendo uso de este tipo de estructuras.

Competencia específica 

Aplicar algoritmos para almacenar, eliminar y mostrar datos de forma segura, mediante la utilización de las estructuras básicas de la programación.

Temario de la unidad 1. Estructuras de datos 1.1. Pilas 1.1.1. Generalidades 1.1.2. Creación de una pila 1.1.3. Operaciones básicas 1.2. Listas 1.2.1. Generalidades 1.2.2. Creación de una lista 1.2.3. Operaciones básicas 1.3. Colas 1.3.1. Generalidades 1.3.2. Creación de una cola 1.3.3. Operaciones básicas

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

3

Estructura de datos Unidad 1. Estructura de datos

1. Estructura de datos Los datos simples, como ya lo has revisado en asignaturas previas como Fundamentos de programación, representan valores de tipo simple: Como un número entero o real. En muchas situaciones se necesita, sin embargo, procesar una colección de valores que están relacionados entre sí por algún método, por ejemplo, una lista de calificaciones, una serie de temperaturas medidas a lo largo de un mes, etcétera. El procesamiento de tales conjuntos de datos, utilizando datos simples, puede ser extremadamente difícil y por ello la mayoría de los lenguajes de programación incluyen características de estructuras de datos (Joyanes, 2010, p. 247). Una estructura de datos se define como “una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen en ella” (Joyanes, 2010, p. 248).

1.1. Pilas El primer tema que se revisará es el de pila. Una pila se puede definir como un contenedor de objetos que se introducen y se sacan según el principio conocido como LIFO (last – in, first - out) que significa, último en entrar, primero en salir. Siempre es posible insertar objetos en una pila; sin embargo, sólo es posible sacar el objeto que se introdujo más recientemente. Las pilas son estructuras de datos fundamentales que se usan en muchas aplicaciones, como puede ser cuando los navegadores de internet van guardando en una pila las direcciones de los sitios recién revisados. Cuando un usuario visita un sitio nuevo, su dirección es introducida para meterla en la pila de direcciones, luego el navegador permite que el usuario quite el sitio recién visitado dando clic al botón “atrás”. Como se puede notar, son muchas las aplicaciones de las pilas que se realizan de forma cotidiana en actividades informáticas. El nombre de pila se le da a esta estructura como una analogía con las máquinas servidoras de platos de resorte en una cafetería o también por la forma como salen los dulces con el despachador PEZ. También se puede relacionar con una pila de libros o de monedas.

Pila de libros. Tomada de http://pixabay.com/es/libroseducaci%C3%B3n-escuela-literatura-441866/

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

4

Estructura de datos Unidad 1. Estructura de datos

Pila de monedas. Tomada de http://pixabay.com/es/logrobar-negocio-gr%C3%A1fico-moneda18134/

Una pila es un tipo de dato abstracto (TDA) que soporta dos métodos fundamentales: push y pop. Por su importancia, la estructura de datos pila se incluye como clase “constructora” en el paquete java.util de Java. Apóyate en la bibliografía sugerida de la unidad para revisar los métodos que se emplean en las pilas, por ejemplo: push (o): permite insertar, introducir o empujar un objeto en la parte superior de la pila. Entrada: objeto Salida: ninguna pop (): sacar el objeto superior de la pila y regresarlo; se produce un error si la pila está vacía. Entrada: ninguna Salida: objeto

Tomada de http://es.wikipedia.org/wiki/Pila_(inform%C3 %A1tica)#mediaviewer/File:Pila.svg

Para una pila también se definen métodos de soporte: size(): regresa la cantidad de objetos en la pila. Entrada: ninguna Salida: entero isEmpty(): regresa un valor booleano que indica si la pila está vacía.

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

5

Estructura de datos Unidad 1. Estructura de datos

Entrada: ninguna Salida: booleana top(): regresa el objeto superior de la pila sin sacarlo de ella, se produce un error si la pila está vacía. Entrada: ninguna Salida: objeto La implementación de un tipo de dato abstracto en Java se hace en dos pasos. El primero es la definición de una interfaz de programación de aplicación Java o interfaz, solamente que describe los nombres de los métodos que soporta el TDA (tipo de dato abstracto) y cómo se deben declarar y usar. Revisa Goodrich, Tamassia, (2010, pp. 136-137), porque en este texto, podrás ver a través de ejemplos cómo se crea la interfaz en Java, el proceso de declaración y uso de variables. También hace referencia a la forma de utilizar los métodos que emplea la estructura de datos pila. Las pilas son aplicaciones importantes en el ambiente de ejecución de los programas Java. Un programa Java en ejecución tiene una pila privada, llamada pila de métodos Java, que se usa para rastrear las variables locales y otra información importante sobre los métodos, a medida que se invocan durante la ejecución. En Joyanes y Zahonero (2012, pp. 490-498) encontrarás cómo emplear este tipo de estructura para realizar aplicaciones cotidianas. También, podrás darte cuenta cómo este tipo de estructura queda inherente a la forma de ejecución de los programas en el lenguaje Java. Revisa las páginas que se te señalan. Como has constatado, el tema de pilas es amplio y a la vez muy interesante, ya que con la implementación de las pilas en diferentes programas podrás mejorar la eficiencia de los mismos, también podrás identificar la funcionalidad y en qué áreas se han hecho aplicaciones de las pilas. No olvides el ejemplo del caso de los sitios web visitados por los usuarios; otro ejemplo lo puedes verificar en los editores de texto, estos suelen tener una función llamada “deshacer” (undo) que cancela las operaciones recientes de edición, y hace regresar al documento a sus estados anteriores. Esta operación de deshacer se logra guardando los cambios de texto en una pila.

1.2. Listas El siguiente tipo de estructura que conocerás es la lista. Una lista es una colección de nodos que en conjunto forman un ordenamiento de forma lineal. El orden se determina como en el juego infantil “sigan al líder”, porque cada nodo es un objeto compuesto que guarda una referencia a un elemento y, una referencia llamada next (siguiente), a otro nodo.

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

6

Estructura de datos Unidad 1. Estructura de datos

Se puede traer a la mente una lista de alumnos inscritos en un curso, una lista de productos para hacer el mandado, etc. La lista es el tipo más general de estructura lineal donde las inserciones y eliminaciones se realizan en cualquier punto de la lista, por esta razón se debe especificar dónde se requiere que se haga la operación. Sus operaciones básicas son: creación, destrucción, inserción, eliminación, consulta y verificación de lista vacía. Pudiera considerarse como una redundancia el hecho de tener un nodo que refiera a otro nodo; sin embargo, la referencia next dentro de un nodo se puede considerar como un enlace o apuntador hacia otro nodo. Pasar de un nodo a otro con una referencia next se llama salto de apuntador. Al primer nodo de la lista se le llama cabeza (top) y al último se le conoce como fin de la lista. Para que puedas conocer a detalle la forma como se conceptualiza la lista, cómo se agregan elementos, se retiran, etc. es conveniente que revises el libro de Joyanes (2010). Fundamentos de programación, algoritmos, estructuras de datos y objetos, las páginas son de la 440 a la 443. También deberás revisar Joyanes y Zahonero (2012, pp. 500-512), en dicho texto encontrarás: cómo emplear este tipo de estructura para realizar aplicaciones cotidianas. Podrás también darte cuenta de cómo este tipo de estructura queda inherente a la forma de ejecución de los programas en el lenguaje Java. Es de vital importancia que consultes la fuente arriba citada para que puedas conocer a detalle esta estructura de datos y, de esta manera, puedas establecer la diferencia en uso respecto con otras estructuras como la pila, que fue el tema revisado anteriormente, así como la estructura cola que es otra de las estructuras más utilizadas. Después de haber revisado la bibliografía deberás tener una idea clara del tema, así como poder emplear las diferentes estructuras que conoces y conocerás dependiendo del tipo de problemas de desarrollo que se te presente.

Componentes de una lista Tomada de yatarihuana2.blogspot.es

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

7

Estructura de datos Unidad 1. Estructura de datos

Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes: una referencia al siguiente elemento de la lista y un valor que puede ser de cualquier tipo. Una lista enlazada requiere de las siguientes funciones:  Definir la clase nodo y referencia a nodo.  Inicializar o crear.  Insertar elementos en una lista.  Eliminar elementos de una lista.  Buscar elementos de una lista.  Recorrer una lista.  Comprobar si la lista está vacía. Este tipo de estructura puede resultar un poco más compleja de utilizar, lo recomendable es que conozcas y sepas utilizar las diferentes estructuras de datos, así como la forma de emplear adecuadamente los temas de las siguientes unidades como son los árboles y, con base en tu experiencia, decidas qué conceptos utilizar para la resolución de determinado problema. Las listas resuelven las situaciones mencionadas arriba; son, probablemente, la segunda estructura de almacenamiento de propósito general más comúnmente utilizada, después de los arreglos. Una lista es un tipo de estructura conveniente para usarse en muchos tipos de bases de datos de propósito general. También, puede remplazar a los arreglos como base para otras estructuras de almacenamiento como pilas y colas. La ventaja más evidente de utilizar estructuras ligadas, es que permite optimizar el uso de la memoria, porque no se desperdicie el espacio de localidades vacías. Las listas son una estructura de datos bastante interesante; sin embargo, presentan algunas desventajas, la más grande es que deben ser recorridas desde su inicio para localizar un dato particular. Es decir, no hay forma de acceder a algún dato de la lista en particular, como se haría en un arreglo.

1.3. Colas Para concluir con esta unidad a continuación se tratará el tema de colas, que es una estructura que consta solamente de dos operaciones: inserción (push) y eliminación (pop). La función push sólo se puede realizar a través de un extremo (frente) y la función pop sólo se realiza por el otro extremo (final).

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

8

Estructura de datos Unidad 1. Estructura de datos

Este tipo de estructura se conoce como FIFO (first in – firstout), el recorrido se realiza sacando el primer dato que se insertó hasta llegar al extremo final. Para entender este concepto se debe pensar en la cola (fila) que se hace para comprar las tortillas, la fila en el banco o para comprar un boleto en el cine.

Fila para las tortillas, también conocida como cola de las tortillas. Tomada de fotolog.com

Para el caso particular del trabajo con la estructura FIFO en primera instancia se compara para saber si existe algún elemento en la cola, de no ser así, entonces se muestra un mensaje que indica que la cola está vacía. De otra forma compara si Frente es mayor o igual a Final, así simplemente hace un Recorrido lineal como los anteriores. De otra forma usar Max como bandera para saber cuándo empezar a contar de 0 a Final. Para profundizar en el tema, revisa la obra de Goodrich, Tamassia (2010, pp. 140-142). En dicho texto, encontrarás de forma detallada cada uno de los conceptos que se han mencionado: la forma de introducir elementos a cada estructura, sacar elementos de ella, entre otros. La finalidad de que consultes estos temas es que te adentres en ellos y que ubiques las similitudes y diferencia entre cada estructura, así como la forma adecuada de utilizar cada una de las estructuras de datos que has revisado en la unidad. Revisa el documento de Joyanes y Zahonero (2012, pp. 520-522) donde encontrarás cómo emplear este tipo de estructura para realizar aplicaciones cotidianas. Podrás también darte cuenta cómo este tipo de estructura queda inherente a la forma de ejecución de los programas en el lenguaje Java. Revisa las páginas que se te indican.

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

9

Estructura de datos Unidad 1. Estructura de datos

Estructura de datos cola Tomada de programacionfacil.com

Como puedes observar, la estructura de datos conocida como cola puede utilizarse para ayudar a resolver situaciones de nuestra vida cotidiana, por ejemplo, cuando se envía a imprimir un documento desde una red de computadoras, o cuando hay una conversación en un chat, etcétera.

Cierre de la unidad En esta unidad se abordaron las diferentes estructuras de datos: pilas, listas y colas. Como ya se mencionó es primordial que te adentres en cada uno de los temas de la unidad a través de la consulta de las diferentes fuentes indicadas, así como también es necesario que leas detalladamente las actividades que se te han asignado por unidad y las resuelvas a cabalidad para poder tener conocimiento profundo de las estructuras de datos, pues éstas son fundamentales en el área de la programación, además de que te permitirán asimilar de mejor manera los temas de las unidades posteriores. Por lo anterior, es necesario que conozcas bien en qué consiste cada una de las estructuras, cómo se utilizan, qué métodos se realizan en cada una, así como en qué casos puedo emplearlas. Además, comprender bien cada estructura te permitirá abordar de una manera más sencilla los temas de las siguientes unidades. Resultado del conocimiento y comprensión de los temas pilas, colas y listas, podrás realizar programas en los que apliques estos conceptos avanzados de programación, es decir, podrás

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

10

Estructura de datos Unidad 1. Estructura de datos

realizar programas de aplicación para el día a día, como lo son: una cola de impresión, una lista de correo electrónico, entre otras aplicaciones.

Para saber más Existen diversas fuentes que puedes consultar para ampliar tus conocimientos. Por ejemplo: 

http://www.utim.edu.mx/~svalero/docs/ED_Java.pdf En el documento PDF al que podrás acceder en la liga arriba anotada, encontrarás de forma breve, pero concisa, los conceptos básicos de las estructuras de datos, sobre todo, a través de imágenes que ilustran los componentes y comportamiento de los mismos; asimismo, podrás conocer cómo se utilizan dichas estructuras.



http://www.grycap.upv.es/gmolto/docs/eda/EDA_Tema_1_gmolto.pdf En esta fuente encontrarás conceptos de Java para utilizar en las estructuras de datos.

Es importante que para complementar tu conocimiento de ésta, y cualquiera otra de tus materias, consultes diferentes fuentes; las arriba mencionadas son sólo algunas, es recomendable, si buscas otras fuentes en internet, que te cerciores de que éstas son fidedignas.

Fuentes de consulta 

Goodrich, T. (2010). Estructura de datos y algoritmos en Java. México: CECSA.



Joyanes. (2010). Fundamentos de programación, algoritmos, estructuras de datos y objetos. España: McGraw-Hill.



Joyanes y Zahonero. (2012). Programación en Java 2, algoritmos, estructuras de datos y programación orientada a objetos. España: McGraw-Hill.

Ciencias Exactas, Ingeniería y Tecnología | Desarrollo de Software

11