Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Listas Lineales

 

CONCEPTO 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