05/06/2018
1
Facultad de Informática Culiacán
Tema: LISTAS
Instructor: MC. Gerardo Gálvez Gámez
Junio de 2018
UNIVERSIDAD AUTÓNOMA DE SINALOA
Listas • FIUAS
Temas
• Descripción General
• Listas Enlazadas
• Representación Gráfica
• Representación del Elemento Nodo
• Operaciones Básicas
• Clasificación de Listas
• Diseño de Jerarquía de clases
• Actividades
05/06/2018
2
Listas • FIUAS
Descripción general
• Una lista es una estructura de datos homogéneay dinámica, que va a estar formada por unasecuencia de elementos llamados nodos, dondecada uno de ellos va seguido de otro o deninguno.
▫ Homogénea: Todos los elementos que la forman tienen elmismo tipo base.
▫ Dinámica: Puede crecer o decrecer en tiempo de ejecuciónsegún nuestras necesidades.
Listas • FIUAS
Listas enlazadas
Es una de las estructuras de datos fundamentales,y puede ser usada para implementar otrasestructuras de datos, tales como:
Pilas,
Colas y sus variaciones.
Consiste en una secuencia de nodos, en los que seguardan campos de datos arbitrarios y una o dosreferencias (punteros o direcciones) al nodoanterior y/o posterior.
05/06/2018
3
Listas • FIUAS
Estructura Básica del Nodo
Un nodo consta de dos partes:
• Campo Información.- Es del tipo de datos quese quiera almacenar en la lista.
• Campo Puntero Siguiente (Liga).- Se utiliza paraestablecer el enlace con otro nodo de la lista.
Listas • FIUAS
Representación Grafica
En esta representación, unalista está formada pornodos; cada nodo contieneun elemento de la lista y unapuntador al siguientenodo.
Raíz
05/06/2018
4
Listas • FIUAS
Actividad #1
Objetivo: Diseñar la clase TDA Nodo en ellenguaje de programación C#, el cualrepresente a un elemento de una lista.
Listas • FIUAS
Diagrama de clase para
Representación del TDA Nodo
05/06/2018
5
Listas • FIUAS
Clasificación de Listas Enlazadas
Lista Enlazadas Simples
Listas Doblemente Enlazadas
Listas Enlazadas Circulares
Listas Enlazadas Doblemente Circulares
Listas • FIUAS
Clasificación de Listas Enlazadas
• Listas simplemente enlazadas. Cada nodo contiene unúnico enlace que lo conecta al nodo siguiente o nodosucesor. La lista es eficiente en recorridos directos(“adelante”).
• Listas doblemente enlazadas. Cada nodo contiene dosenlaces, uno a su nodo predecesor y otro a su nodosucesor. La lista es eficiente tanto en recorrido directo(“adelante”) como en recorrido inverso (“atrás”).
05/06/2018
6
Listas • FIUAS
Clasificación de Listas Enlazadas
• Lista circular simplemente enlazada. Una lista enlazadasimplemente en la que el último elemento (cola) se enlaza alprimer elemento (cabeza) de tal modo que la lista puede serrecorrida de modo circular (“en anillo”).
• 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 modocircular (“en anillo”) tanto en dirección directa (“adelante”)como inversa (“atrás”).
Listas • FIUAS
Operaciones Básicas
Inicializacióno creación
Insertar Nodo
Al Inicio
Antes o Después de
nodo referencia
Al Final
Eliminar Nodo
Primero
Ultimo
Nodo referencia X
Nodo Antes o después de
Nodo Referencia
Buscar NodoRecorrido de
la lista
de Derecha a Izquierda
de Izquierda a Derecha
Otra Operación : Comprobar si la lista está vacía
05/06/2018
7
Listas • FIUAS
Actividad #2
Objetivo: Diseñar la clase Lista simple, en ellenguaje de programación C#, que permitarealizar las operaciones básicas de estaestructura citada.
Requerimientos funcionales Solicitados:
RF1 - Insertar datos en la nueva Lista Simple.RF2 - Eliminar datos en la Lista Simple.RF3 - Editar datos de la Lista Simple.RF4 – Consultar (Buscar) datos en la Lista Simple.RF5 - Conocer el tamaño de la Lista Simple.RF6 –Conocer (recorridos) los datos de la Lista Simple.
Listas • FIUAS
Clase Lista Simple
• Investigar los algoritmos propuestos por:
Cap. 5 Pág.. 141 Cap. 8 Pág.225
05/06/2018
8
Listas • FIUAS
Actividad #3
Desarrollar los algoritmos correspondientesa cada una de los requerimientosfuncionales para la clase Lista simple,codificándolos posteriormente al lenguajeC#.
Listas • FIUAS
Actividad #4
Objetivo: Diseñar la clase Lista DoblementeEnlazada , en el lenguaje de programaciónC#, que permita realizar las operacionesbásicas de la estructura citada.
05/06/2018
9
Listas • FIUAS
Lista Doblemente
Enlazadas
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
11 junio 2018 Diseño de la interfaz para listas doblemente ligadas programación de la clase Nodo y ListaDoblementeEnlazada (a nivel diseño)Algoritmo y Programación de la operación insertar al inicioAlgoritmo y Programación de la operación recorrido de izquierda a derechaPrueba de interfaz grafica de las operaciones anteriores.
11 junio 2018 Algoritmo y Programación de la operación insertar al finalAlgoritmo y Programación de la operación buscar Nodo (para obtener la dirección de un nodo referencia).Algoritmo y Programación de la operación insertar antes de nodo referenciaPrueba de interfaz grafica de las operaciones anteriores.
11 junio 2018 Algoritmo y Programación de la operación insertar después de nodo referenciaAlgoritmo y Programación de la operación eliminar Inicio(primer nodo)Algoritmo y Programación de la operación eliminar final(último nodo)Prueba de interfaz grafica de las operaciones anteriores.
05/06/2018
10
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
12 junio 2018 Algoritmo y Programación de la operación eliminar antes de nodo referenciaAlgoritmo y Programación de la operación eliminar después de nodo referenciaAlgoritmo y Programación de la operación recorrido de derecha a izquierdaPrueba de interfaz grafica de las operaciones anteriores.
18 junio 2018 Revisión del proyecto listas doblemente enlazadas por alumno , atención y resolución de dudas
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
13 junio 2018 Diseño de la interfaz para listas enlazadas simples circularesprogramación de la clase Nodo y ListaSimpleCircular (a nivel diseño)Algoritmo y Programación de la operación insertar al inicioAlgoritmo y Programación de la operación recorrido de izquierda a derechaPrueba de interfaz grafica de las operaciones anteriores.
13 junio 2018 Algoritmo y Programación de la operación insertar al finalAlgoritmo y Programación de la operación buscar Nodo (para obtener la dirección de un nodo referencia).Algoritmo y Programación de la operación insertar antes de nodo referenciaPrueba de interfaz grafica de las operaciones anteriores.
13 junio 2018 Algoritmo y Programación de la operación insertar después de nodo referenciaAlgoritmo y Programación de la operación eliminar Inicio(primer nodo)Algoritmo y Programación de la operación eliminar final(último nodo)Prueba de interfaz grafica de las operaciones anteriores.
05/06/2018
11
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
14 junio 2018 Algoritmo y Programación de la operación eliminar antes de nodo referenciaAlgoritmo y Programación de la operación eliminar después de nodo referenciaAlgoritmo y Programación de la operación recorrido de derecha a izquierdaPrueba de interfaz grafica de las operaciones anteriores.
18 abril 2014 Revisión del proyecto listas doblemente enlazadas por alumno , atención y resolución de dudas
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
15 abril 2014 Diseño de la interfaz para listas doblemente enlazadas circularesprogramación de la clase Nodo y ListaDoblementeEnlazadaCircular (a nivel diseño)Algoritmo y Programación de la operación insertar al inicioAlgoritmo y Programación de la operación recorrido de izquierda a derechaPrueba de interfaz grafica de las operaciones anteriores.
15 abril 2014 Algoritmo y Programación de la operación insertar al finalAlgoritmo y Programación de la operación buscar Nodo (para obtener la dirección de un nodo referencia).Algoritmo y Programación de la operación insertar antes de nodo referenciaPrueba de interfaz grafica de las operaciones anteriores.
15 abril 2014 Algoritmo y Programación de la operación insertar después de nodo referenciaAlgoritmo y Programación de la operación eliminar Inicio(primer nodo)Algoritmo y Programación de la operación eliminar final(último nodo)Prueba de interfaz grafica de las operaciones anteriores.
05/06/2018
12
Listas • FIUAS
Calendario de Actividades
Fecha Actividad
16 junio 2018 Algoritmo y Programación de la operación eliminar antes de nodo referenciaAlgoritmo y Programación de la operación eliminar después de nodo referenciaAlgoritmo y Programación de la operación recorrido de derecha a izquierdaPrueba de interfaz grafica de las operaciones anteriores.
18 junio 2018 Revisión del proyecto listas doblemente enlazadas por alumno , atención y resolución de dudas
Listas • FIUAS
Bibliografía
ESTRUCTURAS DE DATOS
De: OSVALDO CAIRO
Editorial: MCGRAW-HILL INTERAMERICANA
ISBN: 9701059085
Edición: 3ª
Año: 2006
No. de páginas: 467
Idioma: ESPAÑOL
País: MEXICO