Estructura de Datos : Lista Generalizada

Definiciones

Una lista lineal es definida como una secuencia finita de n elementos, n >= 0, e1, e2, ..., en, donde cada elemento es un átomo, tal que ei precede a ei+1, para 1 <= i < n.

Una lista generalizada es una lista donde cada elemento ei, puede ser un átomo o una lista, para 1 <= i <= n.

Un elemento átomo es un nodo con datos.

Un elemento lista es un nodo donde nace una lista.

Una lista generalizada, A, es una secuencia finita de n elementos, n >= 0, e1, e2, ..., en, donde ei puede ser o un átomo o una lista. Los elementos ei, para 1 <= i <= n, que no son átomos, se dicen ser sublistas de A.

La definición de lista generalizada es recursiva, puesto que en la definición de la lista usamos el concepto de lista.

Usaremos las letras mayúsculas para las listas y las minúsculas para los átomos.

Las listas tienen indice de origen 1.

Nodos

Las listas generalizadas se pueden representar con la siguiente arquitectura de nodo :

     +-------------------------------------------+
     |     TAG     |     DATA     |     LINK     |
     +-------------------------------------------+

donde TAG = 0 si es un elemento atomo y TAG = 1 si es un elemento lista.

Ejemplos

Ejemplo 1

A = ( ( a, b ), ( ( c, d ), e ) )

Ancho = 2 - Lista llena - 1er Elemento Sublista - 2do Elemento Sublista

   +---+     +-----------+                                     +-----------+
 A | *-----> | 1 | * | --------------------------------------> | 1 | * | 0 |
   +---+     +-----|-----+                                     +-----|-----+
                   |                                                 |
                   |                                                 |
                   |        +-----------+      +-----------+         |        +-----------+      +-----------+
                   +------> | 0 | a | *------> | 0 | b | 0 |         +------> | 1 | * | *------> | 0 | e | 0 |
                            +-----------+      +-----------+                  +-----|-----+      +-----------+
                                                                                    |
                                                                                    |
                                                                                    |        +-----------+      +-----------+
                                                                                    +------> | 0 | c | *------> | 0 | d | 0 |
                                                                                             +-----------+      +-----------+

Ejemplo 2

A = ( a, ( b, c ) )

Ancho = 2 - Lista llena - 1er Elemento Atomo - 2do Elemento Sublista

B = ( A, A, ( ) )

Ancho = 3 - Lista llena - 1er Elemento Sublista - 2do Elemento Sublista - 3er Elemento Sublista

C = ( a, C )

Ancho = 2 - Lista llena - 1er Elemento Atomo - 2do Elemento Sublista

D = ( )

Ancho = 0 - Lista vacia

 +----->    +---+     +-----------+      +-----------+
 |        A | *-----> | 0 | a | -------> | 1 | * | 0 |
 | +--->    +---+     +-----------+      +-----|-----+
 | |                                           |
 | |                                           |
 | |                                           |            +-----------+      +-----------+
 | |                                           +----------> | 0 | b | *------> | 0 | c | 0 |
 | |                                                        +-----------+      +-----------+
 | +-------------------------------------------+
 |                                             |
 +--------------------------+                  |
                            |                  |
            +---+     +-----|-----+      +-----|-----+      +-----------+
          B | *-----> | 1 | * | --|----> | 1 | * | -------> | 1 | 0 | 0 |
            +---+     +-----------+      +-----------+      +-----------+



    +------------------------------------------+
    |                                          |
    |                                          |
    |       +---+     +-----------+      +-----|-----+
    +---> C | *-----> | 0 | a | --|----> | 1 | * | 0 |
            +---+     +-----------+      +-----------+




            +---+
          D | 0 |
            +---+

Tipos

Listas Normales

El ejemplo 1 muestra una lista generalizada normal.

Listas Compartidas

El ejemplo 2 muestra una lista generalizada compartida, la A.

Listas Recursivas

El ejemplo 2 muestra una lista generalizada recursiva, la C.

Polinomios

El diseno de los nodos de esta aplicacion puede ser :

Nodo con 5 campos :

     +---------------------------------------------------------------------+
     |    COEF    |    EXPOX    |    EXPOY    |    EXPOZ    |     LINK     |
     +---------------------------------------------------------------------+

Nodo con 4 campos :

     +----------------------------------------------------------+
     |     TAG     |     COEF     |     EXPO     |     LINK     |
     +----------------------------------------------------------+

La segunda alternativa se obtiene factoreando por la primer variable, luego por la segunda variable, luego por la tercer variable y asi siguiendo, hasta agotar todas las variables.

P(x,y,z) = x**10 y**3 z**2 + 2 x**8 y**3 z**2 + 3 x**8 y**2 z**2 + x**4 y**4 z + 6 x**3 y**4 z + 2 y z
P(x,y,z) = ( x**10 y**3 + 2 x**8 y**3 + 3 x**8 y**2 ) z**2 + ( x**4 y**4 + 6 x**3 y**4 + 2 y ) z
P(x,y,z) = ( ( x**10 + 2 x**8 ) y**3 + ( 3 x**8 ) y**2 ) z**2 + ( ( x**4 + 6 x**3 ) y**4 + 2 y ) z

En el dibujo que sigue omitiremos el campo TAG por simplicidad. Utilizaremos, ademas, un nodo cabeza por cada polinomio basico, y el campo COEF almacenaremos la variable factoreada, siendo, en este caso, el campo EXPO irrelevante.

             +-----------+     +-----------+                                                              +-----------+
P(x,y,z) --> | z | - | ------->| * | 2 | *--------------------------------------------------------------> | * | 1 | 0 |
             +-----------+     +-----------+                                                              +-|---------+
                                 |                                                                          |
                                 V                                                                          V
                               +-----------+      +-----------+      +-----------+                        +-----------+      +-----------+      +-----------+
                               | y | - | *------> | * | 3 | *------> | * | 2 | 0 |                        | y | - | *------> | * | 4 | *------> | * | 4 | 0 |
                               +-----------+      +-|---------+      +-|---------+                        +-----------+      +-|---------+      +-----------+
                                                    |                  |                                                       |                         |
                                                    |                  V                                                       |                         V
                                                    |                +-----------+      +-----------+                          |                +-----------+      +-----------+
                                                    |                | x | - | *------> | 3 | 8 | 0 |                          |                | x | - | *------> | 2 | 0 | 0 |
                                                    |                +-----------+      +-----------+                          |                +-----------+      +-----------+
                                                    |                                                                          |
                                                    V                                                                          V
                                                  +-----------+      +-----------+      +-----------+                        +-----------+      +-----------+      +-----------+
                                                  | x | - | *------> | 1 |10 | *------> | 2 | 8 | 0 |                        | x | - | *------> | 1 | 4 | *------> | 6 | 3 | 0 |
                                                  +-----------+      +-----------+      +-----------+                        +-----------+      +-----------+      +-----------+