Estructuras De Datos Lineales - RI UAEMex

2y ago
63 Views
2 Downloads
1.81 MB
46 Pages
Last View : 1d ago
Last Download : 2m ago
Upload by : Alexia Money
Transcription

Ingeniería en ComputaciónUnidad de Aprendizaje:Estructura de DatosUnidad de Competencia II:Estructuras de DatosLinealesM. en C. Edith Cristina Herrera LunaMarzo 2015

ESTRUCTURAS DE DATOSPropósito de la Unidad de Aprendizaje Conocer, analizar y aplicar estructuras de datosestáticas y dinámicas mediante programas parala solución de problemas informáticos.2UAEM / ED / ECHL

Estructuras de DatosINTRODUCCIÓN El estudio de las estructuras de datos, sin duda es uno de los más importantesdentro de las carreras relacionadas con la computación, ya que elconocimiento eficiente de las estructuras de datos suele ser imprescindible enla formación de los alumnos debido a la trascendencia que un aprendizajeteórico-práctico de las mismas supondrá́ para su carrera. En muchas ocasiones se necesitan estructuras que puedan cambiar detamaño durante la ejecución del programa. Por supuesto, se pueden usararreglos dinámicos, pero una vez creados, su tamaño también será́ fijo, y parahacer que crezcan o disminuyan de tamaño, deberán reconstruirse desde elprincipio. Las estructuras dinámicas permiten crear estructuras de datos que se adaptena las necesidades reales a las que suelen enfrentarse los programas. Pero nosolo eso, también permitirá́ crear estructuras de datos muy flexibles, ya sea encuanto al orden, la estructura interna o las relaciones entre los elementos quelas componen.3UAEM / ED / ECHL

Estructuras de Datos LinealesUnidad de Competencia IIOBJETIVO: Desarrollar programas que incorporen las principalesestructuras de datos lineales: Pila, Cola y Lista enlazada.4UAEM / ED / ECHL

Estructuras de Datos LinealesCONTENIDO1. Pila – Stack ¿Qué es una pila?Representación GráficaOperacionesAplicaciones2. Cola – Queue 5¿Qué es una cola?Tipos y representación GráficaOperacionesAplicacionesUAEM / ED / ECHL

Estructuras de Datos LinealesCONTENIDO3. Lista – List 6¿Qué es un nodo?¿Qué es una lista?Tipos y representación GráficaOperacionesAplicacionesUAEM / ED / ECHL

¿Qué es una Pila?C. U. UAEM ZUMPANGO / ICO / ED / ECHL

¿Qué es una PILA? Una pila o stack es una estructura de datos lineal en laque los datos son agregados y eliminados únicamentepor un extremo de la estructura.Son estructuras tipo LIFO:Last In, First Out. - “Ultimo en entrar, primero en salir”Consta de un tope y no permite el uso de índices como un arreglo,aunque las pilas pueden ser implementadas a partir de ellos y deestructuras tipo lista.8UAEM / ED / ECHL

Representación GráficaUna pila generalmente se representa gráficamente de forma vertical, sinembargo, el TOPE en la estructura es una señal para orientar naCBA9AgregaEl TOPE (TOP) en una pila puede indicar:-El ultimo dato agregado a la estructura-El limite o borde del contenedorUAEM / ED / ECHL

OperacionesLas operaciones permitidas sobre una pila son: agregar, eliminar,consultar el tope, pila vacía. PUSH - Apilar: Se agrega un dato al tope de la pila.Ejemplo: En una pila de números enteros:push( 8 ),push( 50 ) , push ( -14 ) ,push ( 39 )39-1450top108top8toptoptop-14505088UAEM / ED / ECHL

Operaciones POP - Des apilar: Se elimina el tope de la pila.Ejemplo:pop ( ) ,3911pop ( )toptop-14-14505050888topUAEM / ED / ECHL

Operaciones TOP : Indica cual es el tope de la pila.No se producen cambios. (Consulta)Ejemplo:top ( )El tope de la pila es 50 EMPTY - Pila Vacía: Indica si la pila estavaciaEjemplo:empty ( )50topLa pila esta vacia false812UAEM / ED / ECHL

AplicacionesLas pilas se usan en: Administración de llamadas a funciones.Equilibrio de paréntesis (corchetes y llaves) en expresiones.Pilas de recursividad.Equivalencias entre notaciones infijas, postfijas y prefijas. Historiales de cambios (deshacer). Torres de Hanoi, etc.Una estructura tipo pila es util cuando el orden de los datos senecesita invertir, porque es el orden natural de sufuncionamiento.13UAEM / ED / ECHL

Aplicaciones14UAEM / ED / ECHL

¿Qué es una Cola?C. U. UAEM ZUMPANGO / ICO / ED / ECHL

¿Qué es una COLA? Una cola o queue es una estructura de datos lineal en la quelos datos son agregados por un extremo y eliminados por elextremo contrario.Son estructuras tipo FIFO:First In, First Out. - “Primero en entrar, primero en salir”Se tiene un extremo frontal y uno final (front / back), no permite eluso de índices como un arreglo, aunque las pilas pueden serimplementadas a partir de ellos y de estructuras tipo lista.16UAEM / ED / ECHL

Representación GráficaUna cola generalmente se representa gráficamente de forma horizontal,sin embargo, el frente (front) de la estructura es una señal para orientarsu CBAEliminaCEFRONTBACKLos datos se agregan por el final(back) de laestructura y se eliminan por el frente(front)de la estructura.UAEM / ED / ECHL

Tipos de ColasExisten diferentes tipos de estructura cola:- Cola simpleQueue- Cola circular- Cola de prioridadPriority queue- BicolaDeque- Bicola de salida restringida- Bicola de entrada restringida18UAEM / ED / ECHL

Cola Circular El ultimo elemento de la estructura esta “ligado” o enlazado con elprimer elemento de la misma.InicioManzanaLimónMangoFinPiñaFresa Generalmente se tiene un numero especifico de datos que se puedenalmacenar en la estructura y apuntadores al inicio y final de la misma.19UAEM / ED / ECHL

Cola CircularCuando un elemento se agrega se coloca al final de la estructura si hay espacio yse recorre el puntero iñaLimónFresaUvaCuando un elemento se elimina el punterode inicio recorre la estructura por lo tantolibera un lugar.20FinMangoPiñaFresaUAEM / ED / ECHL

Cola de PrioridadLos elementos se agregan al final de la estructura pero el elemento quesale o el primero es el de mayor importancia o prioridad.Generalmente los elementos no están ordenados dentro de laestructura, sino que el primer elemento (y segundo en ocasiones) es elque tiene mayor prioridad.Si existen dos o mas elementos con la misma prioridad se tomanconforme se agregan a la estructura, como si fuera una cola TUAEM / ED / ECHL

Bicola Bicola de salida restringida Se agregan elementos por ambos extremos de la estructura, pero seeliminan solo por el inicio (front).PiñaManzanaLimónMangoPiñaBACKFresaFRONT Bicola de entrada restringida Se eliminan elementos por ambos extremos de la estructura, pero seagregan solo por el final TUAEM / ED / ECHL

OperacionesLas operaciones permitidas sobre una cola son: agregar, eliminar,consultar el primer y ultimo elemento, cola vacía. PUSH - Agregar: Se agrega un dato al final de la cola.Ejemplo: En una cola de números enteros:push( 8 ),push( 50 ) , push ( -14 ) ,push ( 39 08FRONTUAEM / ED / ECHL

Operaciones POP - Quitar: Se elimina o quita el primer elemento de laestructura, el primero que se agrego.Ejemplo:pop ( ) ,39-145039-1450FRONTBACK39248FRONTBACKBACKpop ( )-14FRONTUAEM / ED / ECHL

Operaciones FRONT : Indica cual es el primer elemento en la estructura. BACK : Indica cual es el ultimo elemento en la estructura.No se producen cambios (Consulta).Ejemplo:front ( ) EMPTY - Cola Vacía: Indica si la estructurano contiene elementosEl inicio de la cola es -14back ( )Ejemplo:El final de la cola es 39empty ( )39BACK25-14La cola esta vacia falseFRONTUAEM / ED / ECHL

AplicacionesLas estructuras tipo cola se usan en: Organización de archivos de impresión (colas de impresión). Orden de datos. Aplicaciones sobre filas de elementos. Visores de datos, imágenes, archivos. Atención de elementos por prioridades, etc.26UAEM / ED / ECHL

¿Qué es una Lista?C. U. UAEM ZUMPANGO / ICO / ED / ECHL

¿Qué es un Nodo? Un nodo es una estructura que agrupa un conjunto de datos ocampos arbitrarios, donde por lo menos un campo es de referencia oenlace a un nodo del mismo tipo (autorreferenciado).Campo de Datos28Campo de EnlaceUAEM / ED / ECHL

¿Qué es una Lista? Es una secuencia de nodos autorreferenciados con una o dosreferencias al nodo anterior y/o siguiente. Una lista enlazada (ligada o abierta) es una de las estructurasde datos fundamentales y puede se usada para implementarotras estructuras de datos, como pilas y colas.29UAEM / ED / ECHL

Representación GráficaUna lista generalmente se representa gráficamentede forma horizontal, cada nodo cuenta con unadivisión marcada de los datos y los enlaces.Generalmente tiene un puntero especial al inicio dela lista, y en algunas ocasiones se tiene un punteroque indica el final de la estructuraInicioA30BCDNULLUAEM / ED / ECHL

Tipos de ListasExisten diferentes tipos de estructura lista:- Lista simplemente enlazada- Lista doblemente enlazada- Lista circular simple- Lista circular doble31UAEM / ED / ECHL

Lista simplemente enlazada Cada nodo de la estructura tiene un único campo de enlace queapunta al siguiente nodo en la lista. El ultimo nodo en la lista apunta NULL (vacio).InicioFresa2032Uva15Limón30Piña5NULLUAEM / ED / ECHL

Lista doblemente enlazada Cada nodo de la estructura tiene un campo de enlace que apunta alsiguiente nodo en la lista y un campo de enlace que apunta al nodoanterior de la lista. El ultimo y primer nodo en la lista apunta UAEM / ED / ECHL

Lista circular simple Es una lista simple en la que el ultimo nodo apunta al primero enlugar de a NULL.InicioFresa2034Uva15Limón30Piña5NULLUAEM / ED / ECHL

Lista circular doble Es una lista enlazada doble en la que el ultimo nodo apunta alprimero y el primer nodo apunta al ultimo.InicioFinFresa2035Uva15Limón30Piña5UAEM / ED / ECHL

OperacionesLas operaciones básicas en una lista son:InserciónBorradoBusquedaPrimer nodo (No existe lista)Primer nodoAl inicio de la listaEntre dos nodosAl final de la listaBusqueda de un nodoespecificoCualquier nodo excepto elprimeroLas listas enlazadas permiten inserciones y eliminación de nodos encualquier punto de la lista en tiempo constante (suponiendo que dichopunto está previamente identificado o localizado), pero no permitenun acceso aleatorio.36UAEM / ED / ECHL

OperacionesInsertar nodos: No existe lista Final de la lista Inicio de la lista37UAEM / ED / ECHL

Operaciones Insertar entre dos nodos38UAEM / ED / ECHL

OperacionesBorrar nodos: Primer nodo Cualquier nodo excepto primero39UAEM / ED / ECHL

Operaciones Buscar un nodo40UAEM / ED / ECHL

Listas y arreglos Las listas no requieren memoria entra para soportar la expansión, portanto el rendimiento no se afecta. La inserción y borrado de elementos es más rápida que en losarreglos. Los elementos de los arreglos ocupan menos memoria que los nodosporque no requieren campos de enlace. Los arreglos ofrecen un acceso más rápido a los datos, medianteíndices basados en enteros. Las listas enlazadas son más apropiadas cuando se trabaja condatos dinámicos. En otras palabras, inserciones y borrados confrecuencia. Por el contrario, los arreglos son más apropiados cuandolos datos son estáticos (las inserciones y borrados son pocas).41UAEM / ED / ECHL

AplicacionesLas estructuras tipo lista se usan: Para implementar otras estructuras. Organizar de datos. Visores de datos, imágenes, archivos, reproductores. Indexar u ordenar datos. Listar tareas, canciones, recordatorios, archivos, etc.42UAEM / ED / ECHL

Referencias Koffman, Elliot y Wolfgang, Paul. (2008). Estructura de datos con C .Objetos, abstracciones y diseño. McGraw-Hill. Cairó, Osvaldo y Guardati, Silvia. (2006). Estructuras de datos (3a. Edición).McGraw-Hill. Criado, Ma. Asunción. (2006). Programación en lenguajes estructurados.AlfaOmega Ra-Ma. Joyanes, Luis. (2008). Fundamentos de programación (4a Edición). McGrawHill. López, Leobardo. (2004). Programación estructurada. Un enfoque algorítmico(2a. Edición). AlfaOmega. Joyanes, Luis. M. Fernández, L: Sánchez, I. Zahonero. (2005). Estructuras dedatos en C. McGraw-Hill. Schaum. 43Web:C Plus Plus: Biblioteca STL www.cplusplus.com/reference/stl .UAEM / ED / ECHL

GRACIASContinua Unidad de Competencia III:ÁrbolesC. U. UAEM ZUMPANGO / ICO / ED / ECHL

Guía para el Profesor Las primeras diapositivas muestran el propósito, justificación y objetivos de launidad de aprendizaje. Se presentan para que el alumno identifique dichoselementos. El contenido, conforme a la unidad de aprendizaje, maneja los temas de unmenor a mayor grado de dificultad. Se recomienda que para cada tipo de estructura el alumno indique ejemplosrelacionados a computación y de vida cotidiana donde se implemente laestructura. Realizar ejercicios en los que se pida dibujar la estructura y agregar o quitarelementos, mostrando cada paso en un dibujo para identificar que el alumnoaprendió el funcionamiento de la estructura, Para el tema de pilas, pedir que resuelva el ejercicio de torres de Hanoi, con 5discos y 3 torres. Se puede dibujar por pasos o usar monedas paravisualizarlo.45UAEM / ED / ECHL

Guía para el Profesor En ocasiones en conveniente iniciar con la estructura tipo lista, programarla yde ahí pasar a estructura tipo pila y cola, ya que para su implementación sepueden suprimir algunas operaciones ya programadas desde listas. El modelo de programación debe iniciar con la plantilla STL de C StandardTemplate Library para conocer el funcionamiento de las estructuras,posteriormente pedir que se programen usando arreglos y al final pedir que enbase a estructuras (struct) el alumno defina sus propias pilas, colas y listas. Aunque puede ser eficiente un modelo orientado a objetos no esrecomendable en este momento debido a que dicho paradigma se cubre enotra asignatura, y a menos que ya se haya cursado, implementar por medio declases las estructuras implica que el alumno debe aprender el paradigma y eluso de las estructuras de datos, situación que podría complicarle suaprendizaje.46UAEM / ED / ECHL

que los datos son agregados y eliminados únicamente por un extremo de la estructura. Son estructuras tipo LIFO: Last In, First Out. - “Ultimo en entrar, primero en salir” Consta de un tope y no permite el uso de índices como un arreglo, aunque las pilas pueden ser implementadas a partir de ellos y de estructuras tipo lista.

Related Documents:

capítulos 2 y 3 presentan las estructuras lineales de datos, tales como listas, pilas y colas. Los capítulos 4 y 5 estudian las estructuras recursivas de datos como los árboles binarios y los árboles n-arios. El capítulo 6 hace un estudio de estructuras de datos no lineales, como grafos dirigidos. Por último, el capítulo 7 trata el tema de

Procedimientos y funciones encapsulan las operaciones, las aíslan del . Escuela Superior de Ingeniería y Arquitectura, 2012 12 tipo puntero. Compara si dos punteros apuntan a la misma dirección de memoria. . Estructuras de datos lineales y no lineales

3. Conocer estructuras que permiten la persistencia del dato mas alla de la aplicacion. 4. Comenzar con las combinaciones de estructuras. Introduccion Hasta ahora trabajamos con datos simples, cuyas características son: tienen un único nombre para un único dato, y son indivisibles en datos más elementales. Por otro lado las estructuras de datos

Estructuras El uso de las estructuras o tipos de datos estructurados, permiten al usuario crear nuevos tipos de datos más versátiles y específicos, para crear aplicaciones más potentes y resolver problemas aun más complejos. E.g., diseñar elementos que contengan registros para una base de datos, creación de datos como: pilas, colas .

Construir las estructuras de datos eficientes para la correcta solución del problema. RA4. Elegir los algoritmos y estructuras de datos más adecuadas para la solución del problema 8. TEMAS 1. Técnicas Básicas de Implementación de Estructuras de Datos 1.1. Programación estructurada 1.2. Programación Orientada a Objetos 1.3.

relacional para capturar mejor el significado de los datos, para disponer de los conceptos de la orientación a objetos y para disponer de capacidad deductiva. El modelo relacional, como todo modelo de datos, tiene que ver con tres aspectos de los datos: o Estructura de datos. o Integridad de datos. o Manejo de datos.

SGBD. Modelo E-R 2 Durante el desarrollo de un sistema de información, se han de modelar tanto los datos empleados por el sistema como los procesos que realizan tareas sobre esos datos: Modelado de datos Representación gráfica del modelo de datos Diccionario de datos Modelado de procesos Diagramas de flujo de datos Diagramas de estados (automatas finitos)

Target Publications Pvt. Ltd. Std. XI Sci.: Perfect Maths - I 4 In figure XOP, XOQ and XOR lie in first, second and third quadrants respectively. Quadrantal Angles: If the terminal arm of an angle in standard position