Listas multienlazadas

LISTAS MULTIENLAZADAS Y MATRICES ESPARCIDAS

Listas Multienlazadas

Una lista multienlazada o N-enlazada tiene como característica que sus nodos contienen enlaces que los asocian con más de una lista. Esto quiere decir que con una misma lista física, los diferentes apuntadores hacen que en realidad se enlacen N listas “lógicas”.

Ejemplo: Supongamos que tenemos una lista de personas quese enlazan entre sí de dos maneras:
1. Ordenada alfabéticamente por el Primer Apellido.
2. Ordenada ascendentemente por Cédula de Identidad.

Si representamos esta información como dos listas tenemos el problema de la duplicación de nodos, tanto en su representación como al desarrollar sus operaciones. Si se pide insertar o eliminar se debe hacer en ambas listas.

Podemosrepresentar mediante el uso de apuntadores estas dos listas lógicas en una sola lista física, definiendo sus nodos de la siguiente manera:

El apuntador N y las flechas continuas representan la lista ordenada por nombre y el apuntador C y las flechas punteadas la lista ordenada por cédula.

Esta lista se puede representar también con el uso de un nodo cabeza, que contenga un apuntador al comienzode cada lista lógica.

La definición de esta lista es la siguiente:

Clase Persona #representa a una persona
Atributos
Público
String Nombre; #nombre
Entero Cédula; #cédula
Operaciones
#Operaciones aquí
fClase Persona

Clase Nodo #Nodo de la lista de personas
Atributos
Público
Persona Info; #datos de la persona
(Nodo proxN;#apuntador al próximo por nombre
(Nodo proxC; #apuntador al próximo por cédula
Operaciones
#Operaciones aquí
FClase Nodo

Clase NodoCab #Nodo Cabeza de la lista de personas
Atributos
Público
(Nodo primN; #apuntador al primero por nombre
(Nodo primC; #apuntador al primero por cédula
Operaciones
#Operaciones aquí
FClase NodoCab

Clase Lista_PersonasAtributos
Privado #solo usa uno de los dos
(NodoCab L; #referencia al nodo cabeza (rep. 2)
(Nodo N, C; #si no usa nodo cabeza (rep. 1)
Operaciones
#Operaciones aquí
FClase Lista_Personas

Las operaciones cambian para adaptarse a los nuevos características de lista, básicamente mantener el orden entre sus elementos. Se muestra como ejemplo el algoritmo de inserción,que va en las operaciones de la clase Lista_Personas.

Acción Insertar (Persona P)
#inserta una persona en la lista manteniendo el orden
(Nodo X,Q,Q1;
X ( Reservar(Nodo);
X(.Info ( P; #o X(.Info.Nombre ( P.Nombre;
# X(.Info.Cedula ( P.Cedula;
Si (L(.primN =null) entonces #o N=null lista vacía
L(.primN ( X; #o N ( X;
L(.primC ( X;#o C ( X;
Sino
#buscar donde va en la lista por nombre
Q ( L(.primN; #o Q ( N;
Q1(null;
Mientras (Q(null) y (Q(.Info.Nombre ( P.Nombre) hacer
Q1 ( Q; Q ( Q(.proxN;
fMientras
#Q1 queda en el nodo previo y Q en el próximo del que se va a insertar.
X(.proxN ( Q; #enlazar el nodo con la lista por nombre
Si (Q1 = null) entonces #va de primero
L(.primN (X; #o N ( X;
Sino
Q1(.proxN ( X; #enlazar la lista con el nodo
FSi
#buscar donde va el nodo en la lista por cédula
Q ( L(.primC; #o Q ( C;
Q1(null;
Mientras (Q(null) y (Q(.Info.Cedula ( P.Cedula) hacer
Q1 ( Q; Q ( Q(.proxC;
fMientras
#Q1 queda en el nodo previo y Q en el próximo del que se va a insertar.
X(.proxC ( Q; #enlazar el nodo con la lista porcédula
Si (Q1 = null) entonces #va de primero
L(.primC ( X; #o C ( X;
Sino
Q1(.proxC ( X; #enlazar la lista con el nodo
FSi
FSi
fAcción Insertar

Matriz Esparcida

Una matriz esparcida (Sparse Matriz o Matriz Dispersa) es una combinación de estructuras que se utiliza para representar solamente los elementos que son significativos en una matriz estática “grande”,...