• Author / Uploaded
• Bryan Ochoa

Citation preview

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS FACULTAD DE INGENIERIA DE SISTEMAS E INFORMATICA

CURSO: ESTRUCTURA DE DATOS CLASE 06 LISTAS ENLAZADAS PARTICULARES

CONTENIDO DEFINICION DE LISTAS ENLAZADAS CON CABECERA CARACTERISTICAS LISTAS CIRCULARES OPERACIONES CON LISTAS CIRCULARES LISTAS ENLAZADAS DOBLES OPERACIONES CON LISTAS ENLAZADAS DOBLES

LISTAS ENLAZADAS CON CABECERA DEFINICION DE LISTAS ENLAZADAS CON CABECERA Una lista enlazada con cabecera es una lista enlazada que contiene un nodo especial llamado nodo cabecera que se ubica al principio de la lista.

Las listas enlazadas con cabecera se clasifican en: Lista con cabecera y tierra. Es una lista con cbecera y cuyo ultimo nodo contiene el puntero nulo, el termino “tierra” es mas utilizado en el campo electrico para indicar tierra en un circuito. Lista circular con cabecera es una lista enlazada en la que el último nodo apunta hacia el nodo cabecera.

REPRESENTACIÓN ESQUEMÁTICA DE LA ESTA ENLAZADA CON CABECERA Y TIERRA

COMIENZO o CAB

Puntero Nulo o tierra

0

X

Primer nodo Ultimo nodo

REPRESENTACIÓN ESQUEMÁTICA DE LA LISTA CIRCULAR CON CABECERA COMIENZO o CAB

Puntero Nulo o tierra

0

Primer nodo Ultimo nodo

Características En lo sucesivo las listas con cabecera serán siempre circulares por ello el nodo cabecera actuara como centinela o marca que indica el final de la lista. El puntero comienzo o Cab siempre apuntará al nodo cabecera, de acuerdo con esto se tiene que Enlace cab = NULL, indicará que una Lista con cabecera y tierra esta vacía, sin embargo Enlace (cab) nos indicará que la Lista esta vacía es una Lista circular. Las Listas con cabecera y las Listas disponibles se representan en memoria como si se tratara de una Lista enlazada normal. Las Listas con cabecera se utilizan en lugar de las Listas enlazadas normales debido a muchas operaciones, se pueden realizar e implementar más fácilmente en las listas enlazadas normales debido dos propiedades siguientes: 1.- No se requiere utilizar el puntero NULL y por tanto los punteros contiene direcciones validas. 2.- cada nodo normal tiene un predecesor, por lo que el primer nodo es un caso

especial. Operaciones con Listas Circularers: Adición: Consiste en adicionar un nodo al final de la Lista Recorrido: Consiste en recorrer cada elemento de la Lista por única vez Búsqueda: Consiste en localizare un elemento determinado valor - Búsqueda por valor - Búsqueda por posición Inserción: Consiste en añadir un elemento en alguna posición determinada Eliminación: Consiste en eliminar un elemento en alguna posición determinada Ordenación: Consiste en ordenar los elementos de acuerdo a un orden lógico determinado. Ejemplo de Lista Enlazada circular: Sea una Lista Circular que contiene el archivo de personal de una empresa organizado como una Lista Circular, donde LUG = 5, es la posición del registro cabecera Cab = 5 En el ejemplo, Ruiz es el ultimo empleado entonces ENLACE10  = 5, se puede tratar este archivo como una Lista enlazada con cabecera o circular. Por ejemplo el NSS 5  =999, este indica el SALARIO TOTAL a pagar es de 77,500 Nº LUG

AP NOMBRE

NSS

SEXO

SUELDO

CAB

1

DIAZ

521112213

M

8000

12

5

2

KENT

650304123

M

7500

7

3

GONZALES

66041612O M

12000

14

4

ENLACE

0

5

999

77500

6

6

BRAVO

670912904

F

9000

9

DISP

7

LOPEZ

651212543

M

6500

10

8

8

11

9

CONTRERAS

710903234

M

11500

1

10

RUIZ

490103230

F

10000

5

11 12

13 ELCANO

740212090

M

6500

13 14

3 4

HERRERA

801209235

F

6500

2

En este caso de listas circulares para referirse al nodo cabecera y su posición se indicará

Enlace cab  y no solo cab como en las listas enlazadas normales. Se utilizará variables punteros Ptr para recorrer la Lista circular Ptr = enlace 5  = 9 (cab) y no Ptr = cab Y termina el recorrido cuando Ptr = cab Y no cuando Ptr = NULL Pseudocodigo de Recorrido en una Lista Enlazada Circular Acción Recorrido_Lista_Circular(cab, Enlace, Val, Ptr) Inicio Ptr = Enlace (cab). ……… Se inicializa el puntero Ptr Mientras (Ptr < > cab) Escribir Val Ptr  Ptr = Enlace Ptr  …….. Ptr apunta al siguiente nodo Fin Mientras Fin Supongamos que se tiene en Memoria una Lista enlazada con cabecera almacenada y nos dan Pseudocodigo de Búsqueda de un elemento en una posición determinada Accion Búsqueda_Lista_Circular( inf, Enlace, cab, elemento, LUG) Inicio //La lista es circular con cabecera //Se trata de Encontrar la posición LUG que ocupa el primer nodo en el que //elemento aparece por primera vez //O devuelve en caso contrario LUG = NULL Ptr = Enlace (cab). …………// Se inicializa el puntero Ptr Mientras (inf Ptr  < > elemento y Ptr < > elemento) Ptr = Enlace Ptr  ……….// Ptr apunta al siguiente nodo Si (inf Ptr  = elemento) LUG = Ptr Sino LUG = NULL FinSi FinMientras Fin

Pseudocodigo de Eliminación de un nodo en una lista circular Dado una lista circular, eliminar un nodo de la lista que se encuentra ubicado en una posición determinada

Accion Eliminar_Lista_Circular( inf, Enlace, cab, elemento, disp) Inicio // La lista es circular con cabecera // Llama a ENCLISTC para encontrar la posición determinada ENCLISTC (inf, enlace, cab, elemento, LUG, LUGP) SI(LUG =NULL) Escribir “El elemento no se encuentra en la lista” Sino Enlace LUGP  = Enlace LUG  //Elimina el l nodo Enlace LUG  = disp // nodo eliminado pasa a Disp disp = LUG Finsi Fin Pseudocodigo para encontrar la posicion determinada Accion ENCLISTC(inf, Enlace, cab, elemento, LUG, LUGP) Inicio aux =cab Ptr = Enlace cab  …………//Se inicializa el puntero Ptr Mientras (inf (Ptr) < > elemento y Ptr < > cab) aux =Ptr Ptr = Enlace Ptr  . ……….// Actualiza los punteros FinMientras Si (inf Ptr  = elemento) LUG = Ptr LUGP=aux Sino LUG = NULL LUGP=aux FinSi Fin

LISTAS DOBLES O DOBLEMENTE ENLAZADAS Una lista simple presenta un problema, el de accder a un nodo antecesor. La única forma será empezando desde la cabecera y explorar la listas hasta llegar al nodo.Una solución a este problema es añadir un apuntadfor adicional a cada nodo que contenga la dirección del nodo anterior. El inconveniente en esta representación es el puntero adicional en cada nodo.

Es decir que cada nodo esta divido en tres partes: 1. Campo de información INF que contiene el dato de N 2. Un campo puntero SGTE que contiene la direccion del siguiente nodp de la lista. 3. Un campo puntero anterior ANT que contiene la posición del nodo anterior en la lista

INF

PUNTERO ANT

PUNTERO SGTE

Sea un conjunto de nodos de una lista enlazada doble: PRIMERO O

ULTIMO O

Cada nodo de una Lista enlazada doble puede implementarse como un registro. Registro Nodo Inicio T valor // valor del nodo de tipo T Nodo *PS // Puntero al sucesor Nodo *PA // Puntero al anterior Fin

OPERACIONES CON LISTAS ENLAZADAS DOBLES INSERCION EN LISTAS ENLAZADAS DOBLES

Acción Inserción (v, d) inicio n = nuevo_nodo nvalor =v nps =dps (dps)pa =n npa =d dps =n Fin

Esquema de una lista enlazada doble en proceso de inserción de un nodo

LUG A

NODO A

Nuevo_nodo A insertar de Disp

LUG B

NODO B

NODO INSERTADO

ELIMINACION EN LISTAS ENLAZADAS DOBLES LUG

NODO ELIMINADO

Acción Eliminacion(v d) inicio v = dvalor (dpa)ps =dps (d —ps)pa=dpa fin

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS FACULTAD DE INGENIERIA DE SISTEMAS E INFORMATICA CURSO: ESTRUCTURA DE DATOS PRACTICA Nº 03 LISTAS ENLAZADAS

1. Realizar un algoritmo para realizar la adición de un nodo al final de la lista enlazada. 2. Realizar un algoritmo para realizar la busqueda dado un valor determinado de la lista enlazada 3. Realizar un algoritmo para realizar la inserción de un nodo en la lista enlazada. 4. Realizar un algoritmo para realizar la inserción de un nodo con un valor determinado en la lista enlazada 5. Realizar un algoritmo para realizar la eliminación de un nodo dado su posición en la lista enlazada. 6. Realizar un algoritmo para realizar la eliminación de un nodo dado su valor en la lista enlazada. 7. Realizar un algoritmo para realizar el ordenamiento de una lista enlazada en orden creciente y decreciente. 8. Realizar un algoritmo para realizar la creación de una lista enlazada qu contenga numeros pares. 9. Realizar un algoritmo para realizar la intercalación de 2 listas enlazdas en una tercera lista enlazada. 10. Realizar un algoritmo para realizar lel proceso de salvar los elementos de una lista en una fila secuencial 11. Realizar un algoritmo para realizar el proceso de recuperación de la lista enlazada a partir de una fila secuencial. 12. Realizar un algoritmo para realizar la intercalación de un arreglo unidimensional y una lista enlazada en una nueva lista enlazada. 13. Realizar un algoritmo para realizar la intercalación de dos listas enlazdas en una tercera lista. 14. Realizar un algoritmo para realizar la inserción de un nodo en lista doblemente enlazada 15. Realizar un algoritmo para realizar la eliminación de un nodo en una lista doblemente en lazada 16. Realizar un algoritmo para realizar la inserción de un nodo en una lista enlazada circular. 17. Realizar un algoritmo para realizar la eliminación de un nodo en una lista circular.

18. Supongamos que se tiene el pabellon A de un Hospital X que tiene 12 camas de las cuales 9 estan ocupadas ppor pacientes, como se muestra en la figura siguiente. Realizar un apoyo informatico en la gestión de este pabellon utilizando listas enlazadas, para los cuales es necesario realizar las siguientes operaciones: a) Adicionar o crear los 9 pacientes que inicialmente tiene este pabellon ordenado por apellidos y nombres b) Listar o Mostrar los pacientes que se encuentran ocupando las camas de este pabellon mostrar la lista de pacientes en este momento. c) Insertar un paciente al pabellon dado su apellido y nombres y mostrar la lista de pacientes en este momento. d) Dar de alta a un paciente de una determinada cama de este pabellon mostrar la lista de pacientes en este momento. La Figura de laLista enlazada con los 9 pacientes ubicados en un Pabellon A del Hospital. Ejemplo Del Pabellon A del Hospital X con 12 camas y se tiene 9 camas ocupadas:

Nº cama

1

AP y Nombres del paciente

Puntero

Gomez Karla

7

SGTE

CAB

2

5

3

Cox David

11

4

Lucas Max

12

5

Alva Abel

3

7

Lopez Laura

4

8

García Gloria

1

9

Perez Samuel

0

11

Diaz Francisco

8

12

Nuñez Nelson

9

6

10

20. La Biblioteca de la FISI a fin de encontrar informacion enforma rapida Se pide crear las palabras o frases de interes. La Figura Ejemplo de Listas enlazada de caracteres formando palabras o frases. Ejemplo para obtener las cadena de caracteres

Nº caracter

INF

Puntero

(carácter)

SGTE

1

7

CAB

2

9

3

O

6

4

T

0

5 6

--

7

X

10

9

N

3

10

I

4

11

E

7

8

12 13

21 Supongamos que dos docentes reciben la ayuda de la Oficina de Matricula para tratra su información refernte a sus notas. Los profesores son de los cursos de Estructura de datos e Ingles La oFicina de matricula trata la información y debe realizar las siguientes operaciones a)crea las Listas enlazadas para estos curso de estructura de datos y el curso de Ingles. b) cada docente tiene el problema de insertar 2 alumnos para ED y uno para Ingles. c) tambien tien cada uno la eliminación de 2 alumnos

d) Deben ordenar por orden de merito y mostrar estas notas de los alumnos e) Debe tener el listado de alumnos con notas menores e iguales que 10, mostrar estos alumnos con bajas notas. La figura de las Listas en lazadas referentes a las notas de los Cursos de ED y de INGLES Ejemplo de lista de Notas de 2 cursos

Nº

INF

Puntero

(Alumno Nota)

SGTE

1 ED

2

DIAZ 15

14

11

3

MAS 09

13

5

DAN 08

10

6

LUNA 11

9

7

LAN 15

16

INGLES

8

ZELA 09

0

5

9

PINO 08

8

10

HONG 12

7

11

ALVA 13

2

13

SULCA 12

0

14

GIL 16

6

4

12

15 16 17

2 LAY 13

3

21. Una empresa Comercial X tiene un conjunto de vendedores y clientes, Cada vendedor tiene su lista de clientes. Sea el caso de 4 vendedores y cada vandedor con lista propia de clientes. Se pide: a) Adicionar a cada vendedor uno o mas clientes. b) Mostrar la lista de clientes de cada vendedor despues de adicionar o insertar c) Eliminar uno o mas clientes por apellidos y nombres. d) Mostrar la lista de clientes cada vendedor despues de eliminar. e) Mostrar al cliente con mayor cantidad de clientes Ejemplo: Sea na empresa con 4 vendedores y cada vendedor con su lista de cliente

Nº

VENDEDOR

APUNTA A

Nº

CLIENTE

SGTE

1

BRAVO

12

1

MARIO

6

2

PEREZ

3

2

3

RAMIREZ

0

3

MARIA

14

4

SALAS

9

4

RAUL

0

VICTOR

0

8

JUAN

1

9

CARMEN

20

10

LUIS

4

ALONSO

17

14

DAVID

10

15

RONALD

0

CARLOS

8

5 6 7

11 12 13

16 17 18 19

20

JULIO

16

22. Sea el archivo de personal de una empresa organizado como se pide organizar y gestionar esta informacion mediante listas enlazadas Se pide a) inserter un nuevo empleado. b) eliminar un nodo de la Lista c) Mostrar la lista enlazada despues de cada operación d) convertir la enlazada simple a Lista circular Nº LUG

AP NOMBRE

NSS

SEXO

SUELDO

ENLACE

CAB

1

DIAZ

521112213

M

8000

12

6

2

KENT

650304123

M

7500

12

3

GONZALES

66041612O M

12000

14

4

5

5

0

6

BRAVO

670912904

F

9000

9

DISP

7

LOPEZ

651212543

M

6500

10

8

8

11

9

CONTRERAS

710903234

M

11500

1

10

RUIZ

490103230

F

10000

0

11 12

13 ELCANO

740212090

M

6500

13 14

3 4

HERRERA

801209235

F

6500

7