Aplicaciones De Las Relaciones

6.7 Aplicaciones de las
relaciones
Alexis Herrera Munguía
Kevin Osmar Tena Chávez
Gilberto Nambo Aspera

6.7.1 Una lista enlazada es una relación
Sea A un vector de dimensión N que, contienenombres de personas, los cuales fueron colocados de
acuerdo con el orden en que llegan, y sea P otro
vector de las mismas dimensiones para guardar la
dirección del siguiente nombre. Además se considera
unavariable X que guarda la posición en donde inicia
la tabla de nombres.
a) Si el orden en que llegan los nombres es "María",
"Juan", "Ana", "Pedro", "Jaime", ¿cuál es el valor de la
variable X y cómoquedarían los vectores A y P?
b) ¿Cuál es el grafo dirigido de la relación formada por
los arreglos A, P y la variable X?

c) Supóngase que se dan de alta los nombres

"Benito" y "Luis" y se da debaja a "Juan".
¿Cómo quedaría la información en los arreglos
y cuál es el grafo dirigido?
Solución de (a)
Considérese que la variable que indica el
inicio de la lista es X = * y que los arreglos A yP están vacíos, como se muestra en la
siguiente tabla:

X = * (* significa fin de lista)
A

1
2
3
4
5
.
.
N

P

1
2
3
4
5
.
.
N

Al llegar el primer nombre los arreglos quedan
de la siguientemanera:
X=1

A
1
2
3
4
5
.
.
N

María

P
1
2
3
4
5
.
.
N

*

ariable X = 1 indica que el primer nombre de la lista está en la posición
glo A. El * en P indica que ya no hay más nombres y ahí termina lalista.

Cuando llega el segundo nombre los arreglos
tienen la siguiente información:
A

1
2
3
4
5
.
.
N

María
Juan

X=2

P

1
2
3
4
5
.
.
N

1
*

omo el nombre de Juan se coloca alfabéticamente antesque María, ahora
variable que indica el inicio de la lista apunta a la posición de ese nombre X = 2
n esa misma posición pero para el arreglo P, se coloca el número 1 que indica qu
osición del siguientenombre a recorrer está en la posición número 1 del arreglo
el * en P significa que ahí termina la lista.

Al agregar los nombres de Ana, Pedro y Jaime, los

arreglos quedan como se muestra a...