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 que se 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 …ver más…

Calculemos la complejidad en memoria de una matriz de enteros estática 100X100.

Arreglo M de Entero [1..100][1..100];

Cm(M) = Cm(descriptor) + (100-1+1)*(100-1+1)*Cm(Entero) = 6+100*100*1 Cm(M) = 6 + 10000 = 10006 palabras

En cambio si se usa una representación de tipo matriz esparcida, se define de la siguiente manera:

Supongamos que cada elemento de la lista (Nodo) está formado por dos apuntadores y dos enteros, que indican la fila y columna asociada. Y que el arreglo solo contiene un apuntador a Nodo.
Cm(ME) = Cm(F) + Cm(C) + 250 * Cm(Nodo)
= 2*(Cm(descriptor) + (100-1+1)*Cm((Nodo)( + 250* (3*Cm(Entero)+2*Cm((Nodo)(
= 2*(3 + 100*1( + 250* (3*1+2*1( = 2*(103( + 250*5 = 206 + 1250

Cm(ME) = 1456 palabras

Quiere decir que se tiene un ahorro en memoria (respecto a la representación completa de una matriz 100 x 100) de:
Cm(M) – Cm(ME) = (10006 – 1456) palabras = 8550 palabras

Representación de la Matriz Esparcida con Encabezados de Tipo Arreglo

Clase Nodo Atributos Elem Info; #información guardada en el nodo (si existe) Entero IdF, IdC; #id de Fila y Columna (Nodo ProxF, ProxC; #apuntador al próximo por fila y columna Operaciones #Operaciones aquí
FClase Nodo

Clase Matriz_Esparcida Atributos Arreglo F