MULTILISTAS

1. TDA FRENTE A ESTRUCTURA DE DATOS.

• Tipo de Dato Abstracto (TDA): Modelo formal de un ente junto con un conjunto de operaciones definidas sobre el modelo que nos permite procesarlo.
  
  
• Estructuras de Datos: Organización lógica de la información con que representamos los Datos.

2. ENTIDADES Y RELACIONES.

Tipos de Relación:

• Uno a uno (Ejemplo: Nombre <--> D.N.I.).
• Uno a muchos (Ejemplo: Equipo <-->> Jugador).
• Muchos a muchos (Ejemplo: Alumno <<-->> Asignatura).

Representación de relaciones muchos a muchos.

• Matriz.
• Listas.
• Multilistas.

3. ESTRUCTURA DE DATOS MULTILISTA

• Conjunto de nodos en que algunos tienen más de un puntero y pueden estar en más de una lista simultáneamente.
• Para cada tipo de nodo es importante distinguir los distintos campos puntero para realizar los recorridos adecuados y evitar confusiones.
• Estructura básica para Sistemas de Bases de Datos en Red.

4. IMPLEMENTACIÓN DE MULTILISTAS

Dados dos tipos de entidades, TipoA y TipoB, se necesitan:

• Dos nuevos tipos correspondientes a los nodos para cada clase de entidad, que junto con la información propia de la entidad incluye los punteros necesarios para mantener la estructura.
  
  

  typedef struct NodoTipoA {
  	TipoA Info;
     	NodoRelacion *PrimerB;
  } NodoTipoA;
  
  typedef struct NodoTipoB{
  	TipoB Info;
  	NodoRelacion *PrimerA;
  } NodoTipoB;
  

  
  
  
• Una estructura para agrupar los objetos de cada tipo de entidad (Array, Lista,Árbol, Tabla Hash, ...).
• Un TDA Nodo Relacion que incluye un puntero por cada lista así como información propia de la relación.
  
  

   typedef struct NodoRelacion {
  	NodoTipoA *SiguienteA;
     	NodoTipoB *SiguienteB;
     	<tipo1> campo1;
     	........
     	<tipon> campo_n;
  } NodoRelacion;
  

  
  
  
• Un nodo Multilista que engloba los distintos tipos de nodos (entidad A, entidad B y relación). El tipo de dato para construir esto es el registro variante:
  
  

  typedef enum {NODO_A, NODO_B, NODO_ML} TipoNodo;
  
  typedef struct NodoMultilista {
  	TipoNodo tipo;
     	union {
     		NodoTipoA a;
     		NodoTipoB b;
     		NodoRelacion nr;
   	} cont;
  } NodoMultilista;
  

  
  
  

5. CONSULTA SOBRE UNA ESTRUCTURA MULTILISTA.

Localizar todas las entidades de TipoA relacionadas con la entidad B de TipoB.

void BuscarEntidadesA (EntidadB B){

   NodoMultilista a, b, r;

   b = Direccion(B);
   /* Depende de como se agrupen los NodoTipoB. */
   r = b.cont.b.PrimerA;
   /* Mediante r se recorre el conjunto de entidades TipoA para B. */
   while (r.tipo == NODO_ML) {
	a = r;
   	do
   		a = a.cont.nr.SiguienteB;
   	while (a.tipo == NODO_ML)
   	Escribe(a.cont.a.Info);
   	r = r.cont.nr.SiguienteA;
   };
};

6. TDA RELACIÓN.

TDA Relacion: crear, añadeAlum, añadeAsig, borrarAlum, borrarAsig, añadir, borrar, existe, escribeAsig, escribeAlum, destruir.

Definición: Dados los TDAs Alumno y Asignatura, los objetos Relacion representan las relaciones (matrícula, calificación) entre un conjunto de Alumnos y un conjunto de Asignaturas.

• Son objetos mutables.
• Residen en memoria dinámica.

OPERACIONES:

• Relacion crear(int NumAlum, int NumAsig)
  Argumentos:

  NumAlum: Número máximo de alumnos.
  NumAsig: Número máximo de asignaturas.

  Efecto: (Constructor Primitivo): Crea un objeto del tipo Relacion, que representa las matrículas de hasta un máximo de NumAlum alumnos en un máximo de NumAsig asignaturas.Devuelve un objeto vacío, sin alumnos, asignaturas, ni vínculos entre éstos.
  
  
• void añadeAlum(Alumno al, Relacion r)
  Argumentos:

  al: Un alumno.
  r: El número de alumnos debe ser menor del máximo. Es modificada.

  Efecto: Añade el alumno al a la relación r, sin establecer ningún vínculo con las asignaturas.
  
  
• void añadeAsig(Asignatura as, Relacion r)
  Argumentos:

  as: Una asignatura.
  r: El número de asignaturas debe ser menor del máximo.Es modificada.

  Efecto: Añade la asignatura as a la relación r, sin establecer ningún vínculo con los alumnos.
  
  
• void borrarAlum(Alumno al, Relacion r)
  Argumentos:

  al: Alumno que debe existir en r.
  r: Es modificada.

  Efecto: Elimina todos los vínculos del alumno al con asignaturas en r. Después elimina el alumno de r.
  
  
• void borrarAsig(Asignatura as, Relacion r)
  Argumentos:

  as: Asignatura que debe existir en r.
  r: Es modificada.

  Efecto: Elimina todos los vínculos de la asignatura as con alumnos en r. Después elimina la asignatura de r.
  
  
• void añadir(Alumno al, Asignatura as, Relacion r)
  Argumentos:

  al: Alumno que debe existir en r.
  as: Asignatura que debe existir en r.
  r: Es modificada.

  Efecto: Establece un vínculo entre el alumno al y la asignatura as.
  
  
• logico existe(Alumno al, Asignatura as, Relacion r)
  Argumentos:

  al: Alumno que debe existir en r.
  as: Asignatura que debe existir en r.
  r: Una relación.

  Efecto: Si en r existe un vínculo entre el alumno al y la asignatura as, devuelve VERDAD.En otro caso, devuelve FALSO.
  
  
• void borrar(Alumno al, Asignatura as, Relacion r)
  Argumentos:

  al: Alumno que debe existir en r.
  as: Asignatura que debe existir en r.
  r: Es modificada.

  Efecto: Si existe un vínculo entre el alumno al y la asignatura as, es eliminado.
  
  
• void escribeAsignaturas(Alumno al, relacion r)
  Argumentos:

  al: Alumno que debe existir en r.
  r: Una relación.

  Efecto:Escribe en la salida estándar una lista de las asignaturas relacionadas con el alumno al en r.
  
  
• void destruir(Relacion r)
  Argumentos: r: Es modificada.
  Efecto Destruye el objeto r liberando los recursos que empleaba.Para volver a usarlo habrá que crearlo de nuevo.
  
  

typedef void *pnodo;
   
typedef struct NodoTipoA {
	TipoA info;
   	pnodo *PrimerB;
} NodoTipoA;

typedef struct NodoTipoB {
 	TipoB info;
   	pnodo *PrimerA;
} NodoTipoB;

typedef struct NodoRel {
	pnodo SiguienteB;
   	pnodo SiguienteA;
} NodoRel;

typedef enum {NODO_A, NODO_B, NODO_REL} TipoNodo;

typedef struct nodo {
	TipoNodo tipo;
  	union {
   		NodoRel nr;
   		NodoTipoA na;
   		NodoTipoB nb;
   	} cont;
} nodo;