estructura de datos - unidad 3 estructuras lineales (poo)
TRANSCRIPT
Instituto Tecnológico Superior de GuasaveIngeniería en Sistemas Computacionales
Estructura de DatosUnidad III: Estructuras Lineales
Mtro. José Antonio Sandoval AcostaRetícula ISIC-2010-224: Programa: AED-1026/2016
Itsguasave.edu.mx
Competencia de la Unidad
• Comprende y aplica estructuras de datos lineales para solución de problemas.
ESTRUCTURA DE DATOS
Estructuras Lineales• En esta unidad se comienza el estudio de las estructuras de datos dinámicas.
Al contrario que las estructuras de datos estáticas (arrays) en las que sutamaño en memoria se establece durante la compilación y permaneceinalterable durante la ejecución del programa, las estructuras de datosdinámicas crecen y se contraen a medida que se ejecuta el programa, por loque la cantidad de memoria que requieren para funcionar es muy variable.
• Las estructuras lineales de elementos homogéneos implementadas con arraysnecesitan fijar por adelantado el espacio a ocupar en memoria, de modo quecuando se desea añadir un nuevo elemento, que rebase el tamaño prefijado,no será posible sin que se produzca un error en tiempo de ejecución. Esto haceineficiente el uso de los arrays en algunas aplicaciones.
ESTRUCTURA DE DATOS
PILAS
ESTRUCTURA DE DATOS
PILAS
PILA: Es un conjunto de elementos que solo pueden insertarse yeliminarse por un extremo. Se trata de una estructura de datos deacceso restrictivo a sus elementos.
Un ejemplo de pila es una torre de discos compactos, en la cual losdiscos se insertan y se extraen por el mismo extremo.
ESTRUCTURA DE DATOS
• En la computación estas estructuras suelen ser fundamentales. La recursividadse simula en un computador con la ayuda de una pila. Asimismo muchosalgoritmos emplean las pilas como estructura de datos fundamental, porejemplo para mantener una lista de tareas pendientes que se van acumulando.
• Las pilas ofrecen dos operaciones fundamentales, que son apilar y desapilarsobre la cima. El uso que se les de a las pilas es independiente de suimplementación interna. Es decir, se hace un encapsulamiento. Por eso seconsidera a la pila como un tipo abstracto de datos.
• Es una estructura de tipo LIFO (Last In First Out), es decir, último en entrar,primero en salir.
ESTRUCTURA DE DATOS
ELEMENTOS DE UNA PILA
• Tope o cima: Indica el último elemento insertado en la pila.
• Máximo: Se refiere al número de elementos que puede contener la pila.
ESTRUCTURA DE DATOS
• Pilas con Arreglos: Representar pilas usando arreglos es relativamente mássencillo que usando listas enlazadas, el único problema que existe es lalimitante de espacio en memoria, ya que al definir un tamaño máximo ya no esposible insertar más elementos.
ESTRUCTURA DE DATOS
• Pilas con Listas enlazadas: Son llamadas también estructuras dinámicas, yaque el espacio en memoria se crea hasta que se inserta el elemento.
ESTRUCTURA DE DATOS
OPERACIONES CON PILAS
Operaciones Auxiliares con PILAS
• Pila llena (si el tope == Máximo-1)
• Pila vacía (si tope == -1)
• Recorrer pila (desde elemento 0 hasta tope)
Eliminar un elementoInsertar un elemento
ESTRUCTURA DE DATOS
Estatus de las PILAS
ESTRUCTURA DE DATOS
TRABAJANDO CON PILAS POR MEDIO DE ARRAYS (ESTÁTICAS)
Crear las variables necesarias
int pila[5];
int maximo=5;
Int tope=-1;
Int dato=0;
Int opc=0;
Pila
Máximo de
elementos
Iniciar tope con
valor negativo
Variable para
captura de datos
Variable para menú
de opciones
ESTRUCTURA DE DATOS
VERIFICAR SI LA PILA ESTA LLENA
AlgoritmoFUNCION boolena llena()
SI (tope == maximo – 1)regresar verdadero
SINOregresar falso
FINSIFINFUNCION
ESTRUCTURA DE DATOS
VERIFICAR SI LA PILA ESTA VACIA
AlgoritmoFUNCION boolena vacia()
SI (tope == – 1)regresar verdadero
SINOregresar falso
FINSIFINFUNCION
ESTRUCTURA DE DATOS
INSERTAR ELEMENTO EN LA PILA
AlgoritmoMODULO insertar() {
SI LA PILA ESTA LLENA MOSTRAR “Pila llena”
SINOCAPTURAR ELEMENTOINCREMENTAR tope EN 1pila[tope]=ELEMENTO;
FINSIFINMODULO
ESTRUCTURA DE DATOS
ELIMINAR ELEMENTO EN LA PILA
AlgoritmoMODULO eliminar() {
SI LA PILA ESTA VACIA MOSTRAR “Pila Vacia”
SINOMOSTRAR CONTENIDOELIMINAR ELEMENTODECREMENTAR TOPE EN 1
FINSIFINMODULO
ESTRUCTURA DE DATOS
RECORRIDO DE UNA PILA
AlgoritmoMODULO recorrer() {
DECLARAR var de trabajoSI LA PILA ESTA VACIA
MOSTRAR “Pila Vacia”SINO
MIENTRAS var<=topeMOSTRAR CONTENIDOINCREMENTAR var en 1
FINMIENTRASFINSI
FINMODULO
ESTRUCTURA DE DATOS
• Ejercicio: Desarrolle el programa correspondiente a la PILA que se ha visto enclase creando un menú que contemple las siguientes opciones:
1. Pila llena
2. Pila vacía
3. Insertar
4. Eliminar
5. Recorrido
6. Terminar
• Entregar el programa en código para revisión
ESTRUCTURA DE DATOS
COLAS
ESTRUCTURA DE DATOS
Definición de COLAS
Una COLA es un conjunto homogéneo de elementos, del cualpueden suprimirse elementos sólo desde un extremo llamadoparte delantera, asimismo, sólo pueden agregarse elementos enel extremo contrario llamado parte posterior.
• El primer elemento en ser agregado a una COLA esel primer elemento en ser eliminado.
• Por esta razón una COLA se denomina FIFO (FirstIn-First Out), que es justo el concepto contrario auna PILA o LIFO (Last In-First Out).
ESTRUCTURA DE DATOS
COLAS DINÁMICAS CON NODOS
Parte Delantera o
Salida
Parte Posterior o
Entrada
ESTRUCTURA DE DATOS
COLAS ESTÁTICAS CON ARRAYS
Parte Posterior o
Entrada
Parte Delantera o Salida
Operaciones Auxiliares con COLAS
• COLA llena (si el final == Máximo-1)
• COLA vacía (si final == -1)
• Recorrer COLA (desde elemento 0 hasta final)
ESTRUCTURA DE DATOS
TRABAJANDO CON COLAS ESTÁTICAS
• Una cola estática utiliza un arreglo con un número limitado de elementos en elmismo, dicho arreglo requiere de una constante que controle el máximo deelementos que pueden ser cargados a la cola, y de una variable que controle elelemento final de la cola (último en ser insertado).
• Declaración de las variables de la COLA estática
int cola[5];
int final = -1;
int maximo = 5;
COLA
Último elemento
Máximo de elementos
ESTRUCTURA DE DATOS
ALGORITMO PARA DETERMINAR SI LA COLA ESTÁ LLENA
FUNCION BOLEANA llena () SI (final >= maximo - 1 ) ENTONCES
REGRESAR verdaderoSINO
REGRESAR falsoFINSI
FINFUNCION
ALGORITMO
ESTRUCTURA DE DATOS
ALGORITMO PARA DETERMINAR SI LA COLA ESTÁ VACIA
FUNCION BOLEANA vacia () SI (final < 0) ENTONCES
REGRESAR verdaderoSINO
REGRESAR falsoFINSI
FINFUNCION
ALGORITMO
ESTRUCTURA DE DATOS
ALGORITMO PARA INSERTAR ELEMENTO EN LA COLA
MODULO insertar(DATO) SI (llena) ENTONCES
IMPRIME “cola llena”SINO
incrementar finalcola[final]=DATO
FINSIFINMODULO
ALGORITMO
ESTRUCTURA DE DATOS
ALGORITMO PARA ELIMINAR ELEMENTO EN LA COLA
MODULO eliminar () SI (vacia) ENTONCES
IMPRIME “cola vacia”SINO
FOR (J=0, J<máximo, j++)cola[j]=cola[j+1]
FINFORFINSIDECREMENTAR final
FINMODULO
ALGORITMO
ESTRUCTURA DE DATOS
ALGORITMO PARA HACER RECORRIDO DE COLA
MODULO recorrer () SI (vacia) ENTONCES
IMPRIME “cola vacia”SINO
FOR (J=0, J<=final, j++)imprime cola[j]
FINFORFINSI
FINMODULO
ALGORITMO
ESTRUCTURA DE DATOS
• Ejercicio: Desarrolle el programa correspondiente a la COLA que se ha visto enclase creando un menú que contemple las siguientes opciones:
1. Cola llena
2. Cola vacía
3. Insertar
4. Eliminar
5. Recorrido
6. Salir
• Nota: Cada vez que se desee eliminar un elemento debe verificarse la cantidadque se desea eliminar: si es menor al valor del elemento en la parte delanterade la cola deberá restarse pero sin eliminar el elemento; si es mayor debeeliminarse y el faltante restarlo del siguiente elemento en la cola a manera deun inventario de almacén.
ESTRUCTURA DE DATOS
LISTAS ENLAZADAS
ESTRUCTURA DE DATOS
• Una lista enlazada es una colección o secuencia de elementos dispuestos unodetrás de otro, en la que cada elemento se conecta al siguiente elemento porun “enlace”.
• La idea básica consiste en construir una lista cuyos elementos, llamadosnodos, se componen de dos partes o campos:
La primera parte contiene la información y es, por consiguiente, un valorde un tipo genérico (denominado Dato, TipoElemento, Info, etc.);
La segunda parte es un enlace que apunta al siguiente nodo de la lista.
ESTRUCTURA DE DATOS
• La representación gráfica más extendida es aquella que utiliza una caja con dossecciones en su interior. En la primera sección se encuentra el elemento ovalor a almacenar y en la segunda sección el enlace o puntero, representadomediante una flecha que sale de la caja y apunta al siguiente nodo.
ESTRUCTURA DE DATOS
Clasificación de las listas enlazadas
LISTAS SIMPLEMENTE ENLAZADAS: Cada nodo (elemento)contiene un único enlace que conecta ese nodo al nodo siguienteo nodo sucesor. La lista es eficiente en recorridos directos(“adelante”).
ESTRUCTURA DE DATOS
Clasificación de las listas enlazadas
LISTAS DOBLEMENTE ENLAZADAS: Cada nodo contiene dosenlaces, uno a su nodo predecesor y el otro a su nodo sucesor. Lalista es eficiente tanto en recorrido directo (“adelante”) como enrecorrido inverso (“atrás”).
ESTRUCTURA DE DATOS
Clasificación de las listas enlazadas
LISTA CIRCULAR SIMPLEMENTE ENLAZADA: Una lista simplementeenlazada en la que el último elemento (cola) se enlaza al primerelemento (cabeza) de tal modo que la lista puede ser recorrida demodo circular (“en anillo”).
ESTRUCTURA DE DATOS
Clasificación de las listas enlazadas
LISTA CIRCULAR DOBLEMENTE ENLAZADA: Una lista doblementeenlazada en la que el último elemento se enlaza al primerelemento y viceversa. Esta lista se puede recorrer de modo circular(en anillo) tanto en dirección directa (“hacia adelante”) comoinversa (“hacia atrás”).
ESTRUCTURA DE DATOS
TRABAJANDO CON LISTAS SIMPLES POR MEDIO DE CLASES
• Para trabajar con una lista enlazada debemos crear una clase que refleje lainformación contenida en cada nodo de la misma y que contenga una variablede tipo apuntador que conecte cada nodo con el nodo siguiente.
La variable tipo apuntador
se define con un asterisco
y debe ser del mismo tipo
de la clase declarada.
ESTRUCTURA DE DATOS
• Después debemos definir una segunda clase que contendrá todos los métodospara insertar, eliminar y recorrer la lista.
ESTRUCTURA DE DATOS
Las variables con un asterisco
indican que son apuntadores,
después en los métodos serán
creados los objetos de
memoria.
INSERTAR PRIMER NODO DE LA LISTA VACIA
Cando declaramos la variable NI utilizando un asterisco (*NI) lo que hicimos fue indicar que se trata de un apuntador, ahora corresponde crear el nodo en memoria por medio de la instrucción new, por lo que ya no es necesario declarar de nuevo o utilizar el asterisco. Cabe mencionar que cuando creas el nodo nuevo el campo sig es igualado a NULL en el constructor:
Algoritmo de inserción
Crear el nuevo nodo
Asignar la información al campo correspondiente
Asignar nodo cola
ESTRUCTURA DE DATOS
• Reservar memoria y crear nuevo nodo
• Asignar información al nuevo nodo• Encadenar nuevo nodo con el nodo
inicio actual• Convertir nuevo nodo en nodo
inicio
ESTRUCTURA DE DATOSINSERTAR NODO AL INICIO CUANDO LA LISTA YA TIENE ELEMENTOS
ALGORITMO DE INSERCIÓN DE NODOS SUBSECUENTES EN LA LISTA (INCLUYENDO NODO COLA O “TAIL”).• Reservar memoria y crear nuevo
nodo• Asignar datos al nuevo nodo• Convertir el nodo nuevo en nodo
cola
ESTRUCTURA DE DATOS
RECORRER LA LISTA DESDE EL INICIO
Igualar nodo de trabajo a nodo cabezaMIENTRAS sea VERDADERO
Imprimir datos del nodoNodo de trabajo = siguiente nodoSI nodo de trabajo es NULL salir
FIN-MIENTRAS
ESTRUCTURA DE DATOS
ALGORITMO DE INSERCIÓN DE NODOS AL INICIO DE LA LISTA O NODO CABEZA.
SI cabeza==NULLcrear nuevo nodo inicialasignar datos al campo correspondienteasignar NULL a la variable apuntador
SINOreservar memoria y crear nuevo nodoasignar datos al campo correspondienteenlazar el nodo actual con el nodo cabezaigualar nodo cabeza al nodo actual
FINSI
ESTRUCTURA DE DATOS
ELIMINAR UN NODO DE LA LISTA
• Para eliminar un nodo de la lista debemos verificar primero si se trata del nodo cabeza o de un nodo subsecuente, o del nodo cola.
• Para realizar esta eliminación son necesarios 3 variables auxiliares tipo nodo: auxiliar, actual, anterior
• A continuación se presenta el algoritmo para hacer dicha verificación y la posterior eliminación;
ESTRUCTURA DE DATOS
ESTR
UC
TUR
A D
E D
ATO
S
• Ejercicio: Realizar el programa completo con listas enlazadas simples.
Debe incluir menú de opciones;
Debe incluir módulo de captura de Nodo de Inicio o Nodo Cabeza;
Debe poder capturar Nodo Cola;
Debe poder insertar un nuevo Nodo Cabeza;
Debe poder eliminar un nodo seleccionado;
Debe incluir un recorrido desde el Nodo Cabeza hasta el Nodo Colamostrando el promedio los elementos contenidos y el número de nodosde la lista;
• Entregar el programa
ESTRUCTURA DE DATOS
TRABAJANDO CON LISTAS DE DOBLE ENLACE-CIRCULARES CON CLASES
• Al utilizar clases para crear los nodos se elimina el uso “struct” y se hace usode la POO en todos sus aspectos.
Se crea una clase que
contiene únicamente las
variables del NODO,
también debemos crear el
respectivo constructor.
ESTRUCTURA DE DATOS
Creamos una clase LISTA con
sus métodos y constructor,
también agregamos la
declaración de los nodos NI
(inicio) y NT (cola)
ESTRUCTURA DE DATOS
INSERTAR NODO INICIAL O CABECERA DE LA LISTA
• Cuando declaramos la variable NI utilizando un asterisco (*NI) lo que hicimosfue indicar que se trata de un apuntador, por lo que ahora solo tenemos quereservar el espacio de memoria por medio de la instrucción new;
Algoritmo de inserción • Crear el nuevo nodo
• Asignar la información al campo correspondiente
• Crear circularidad en campo siguiente
• Crear circularidad en campo anterior
• Asignar nodo cola
ESTRUCTURA DE DATOS
ALGORITMO DE INSERCIÓN DE NODOS AL INICIO DE LA LISTA
• Reservar memoria y crear nuevonodo.
• Asignar datos al campocorrespondiente.
• Crear circularidad del odo nuevocon nodo inicio.
• Crear circularidad del nodoinicio con nodo nuevo.
• Encadenar nodo cola con nodonuevo.
• Encadenar nodo nuevo connodo cola.
• Convertir nodo nuevo en nodoinicio.ESTR
UC
TUR
A D
E D
ATO
S
• Reservar memoria y crearnuevo nodo• Asignar al nodo actual datos• Encadenar nodo nuevo con
nodo cola actual• Encadenar nodo cola actual
con nodo nuevo• Crear circularidad del nodo
nuevo con el inicio• Crear circularidad del inicio
con nodo nuevo• Convertir nodo nuevo en
nodo cola
ALGORITMO DE INSERCIÓN DE NODOS AL FINAL O NODO COLA.ES
TRU
CTU
RA
DE
DAT
OS
ALGORITMO PARA RECORRER LA LISTA DESDE EL INICIO
Igualar nodo de trabajo a nodo cabezaMIENTRAS SEA VERDADERO
Imprimir datos del nodoNodo de trabajo = siguiente nodoSi nodo de trabajo es igual a nodo inicio salir
FIN-MIENTRAS
ESTRUCTURA DE DATOS
ELIMINAR UN NODO DE LA LISTAEl algoritmo debe tomar en cuenta todos losmomentos en que puede eliminarse unnodo, ya se a al inicio, al final, o un nodointermedio de la lista.
ESTR
UC
TUR
A D
E D
ATO
S
• Ejercicio: Realizar el programa completo con listas enlazadas doble-circularincluyendo los campos numero de vendedor y total de ventas del mes.
Debe incluir menú de opciones;
Debe incluir módulo de captura de Nodo de Inicio o Nodo Cabeza;
Debe poder capturar Nodo Subsecuente o Nodo Cola;
Debe poder insertar un nuevo Nodo Cabeza;
Debe poder eliminar un nodo seleccionado;
Debe incluir un recorrido desde el Nodo Cabeza hasta el Nodo Colamostrando el promedio de ventas de todos los vendedores en la lista.
• Entregar el programa
ESTRUCTURA DE DATOS
Bibliografía
• Joyanes, Zahonero. Estructura de Datos en C++. McGraw Hill. Madrid, España.2007. ISBN: 978-84-481-5645-9.
ESTRUCTURA DE DATOS