Análisis y Diseño de Algoritmos
Prof: Ing. Victor Garro
Asistente: Marco Elizondo Vargas
Listas
Lineales
CONCEPTO
Listas LINEALES
En esta sección se mostrarán algunos algoritmos sobre listas lineales sin nodo de cabecera y con nodo de cabecera.
Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista contendrá en su campo dato algún valor que lo diferencíe de los demás nodos (como : *, -, +, etc). Un ejemplo de lista con nodo de cabecera es el siguiente:
En el caso de utilizar listas con nodo de cabecera, usaremos el apuntador CAB para hacer referencia a la cabeza de la lista.
Para el caso de las listas sin nodo de cabecera, se usará la expresión TOP para referenciar al primer nodo de la lista, y TOP(dato), TOP(liga) para hacer referencia al dato almacenado y a la liga al siguiente nodo respectivamente.
top<--NIL
repite
new(p)
leer(p(dato))
si top=NIL entonces
top<--p
en caso contrario
q(liga)<--p
p(liga)<--NIL
q<--p
mensaje('otro nodo?')
leer(respuesta)
hasta respuesta=no
p<--top
mientras p<>NIL haz
escribe(p(dato))
p<--p(liga:)
p<--top
mientras p(liga)<>NIL haz
p<--p(liga)
new(q)
p(liga)<--q
q(liga)<--NIL
p<--top
mensaje(antes/despues)
lee(respuesta)
si antes entonces
mientras p<>NIL haz
si p(dato)='x' entonces
new(q)
leer(q(dato))
q(liga)<--p
si p=top entonces
top<--q
en caso contrario
r(liga)<--q
p<--nil
en caso contrario
r<--p
p<--p(link)
si despues entonces
p<--top
mientras p<>NIL haz
si p(dato)='x' entonces
new(q)
leer(q(dato))
q(liga)<--p(liga)
p(liga)<--q
p<--NIL
en caso contrario
p<--p(liga)
p<--top
mientras p(liga)<>NIL haz
p<--p(liga)
new(q)
p(liga)<--q
q(liga)<--NIL
p<--top
leer(valor_a_borrar)
mientras p<>NIL haz
si p(dato)=valor_a_borrar entonces
si p=top entonces
si p(liga)=NIL entonces
top<--NIL
en caso contrario
top(liga)<--top(liga)
en caso contrario
q(liga)<--p(liga)
dispose(p)
p<--NIL
en caso contrario
q<--p
p<--p(liga)
new(cab)
cab(dato)<--'*'
cab(liga)<--NIL
q<--cab
repite
new(p)
leer(p(dato))
p(liga)<--NIL
q<--p
mensaje(otro nodo?)
leer(respuesta)
hasta respuesta=no
leer(valor_a_borrar)
p<--cab
q<--cab(liga)
mientras q<>NIL haz
si q(dato)=valor_a_borrar entonces
p<--q(liga)
dispose(q)
q<--NIL
en caso contrario
p<--q
q<--q(liga)