Listas ortogonales

En este tipo de lista se utiliza para representar matrices. Los nodos contienen cuatro apuntadores. Uno para apuntar al nodo izquierdo (li),otro para apuntar al derecho(ld), otro al nodo inferior(lb) y por último un apuntador al nodo superior(la).

Creación de una lista ortogonal

top<--nil
mensaje(número de renglones)
lee(númreo_renglones)
mensaje(número de columnas)
lee(número_columnas)
desde y=1 hasta número_renglones haz
	new(p)
	lee(p(dato))
	p(li)<--p
	p(ld)<--p
	si top=NIL entonces
		top<--p
		top(lb)<--p
	en caso contrario
		p(la)<--top(la)
		p(lb(la))<--p
		p(lb)<--top
	top(la)<--p
q<--top
desde y=1 hasta número_columnas-1 haz
	s<--NIL
	desde j=1 hasta número_renglones haz
		new(q)
		p(ld)<--q
		p(li)<--q(li)
		p(ld(li))<--p
		q(li)<--p
		si s=NIL entonces
			s<--p
			p(la)<--p
			p(lb)<--p
		en caso contrario
			p(la)<--s(la)
			p(lb(la))<--p
			p(lb)<--s
			s(la)<--p
		q<--q(lb)

Algoritmo para recorrer una lista ortogonal

q<--top
repite
      p<--q
      repite
            escribe(p(dato))
             p<--p(ld)
       hasta p=q
       q<--q(lb)
hasta q=top

Borrado en listas ortogonales

q<--top
mensaje(valor a borrar)
lee(valor_a_borrar)
repite
       p<--q
       repite
             si p(dato)=valor_a_borrar entonces
		si p=top entonces
			p(dato)<-- -999
		en caso contrario
			aux<--p
			p(ld(li))<--p(ld)
			p(li(ld))<--p(li)
			p(la(lb))<--p(la)
			p(lb(la))<--p(lb)
			dispose(aux)
			p<--q
              en caso contrario
		p<--p(ld)
       hasta p=q
       q<--q(lb)
hasta q=top

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz

Publicado en Estructura de datos

Suscríbete:

who's online