Listas

Definición

Una lista es un conjunto ordenado de elementos homogéneos, en la que no hay restricciones de acceso, la introducción y borrado de elementos puede realizarse en cualquier posición de la misma. Esta es una estructura dinámica, por lo que no podemos saber con certeza los elementos (nodos) que puede contener, ya que su tamaño cambia a medida que se añaden y eliminan elementos de la misma.

Características

- Se accesa a toda la lista a partir de un apuntador externo llamado Lista contiene la dirección del primer nodo en la lista.

- Cada nodo tiene dos secciones: el contenido de datos (Info) y el campo del apuntador (sig).

- El campo Info (de información) contiene el elemento real en la lista.

 -El campo sig (dirección siguiente) contiene la dirección del siguiente nodo en la lista. Tal dirección se conoce como apuntador.

-El último nodo tiene un apuntador nulo.

-Cada nodo es una estructura de datos de tipo registro.

-Una lista vacía es aquella que no contiene nodos. Lista=NULL.

Operaciones básicas de una lista:

·         Recorrido de la lista: Visita todos los elementos de la lista.

Function largo (l: lista): integer;

Var

      Contador: integer;

      P: lista;

Begin

      Contador:=0;

      P:=l;

      While p <> vnil do

      Begin

           Contador:= contador + 1;

            P:=p .siguiente;         (Avanzar a la siguiente celda)

     End;

     Largo:=contador;

End;

·         Inserción de un elemento: Agrega un elemento a la lista.

Procedure agregar_al_principio (var l: Lista; elem: t);

Var p: Lista;

Begin

       New (p);                        (crear nueva celda)

       p. elemento:= elem;      (cargar el elemento)

       (Ajuste de punteros)

       p. siguiente:=L;

       L:=p;

End;

Procedure agregar_al_final (var L: Lista; elem: T);

Var p.q: Lista;

Begin

       New (p);                     (crear nueva celda)

       p.elemento:=elem;     (cargar el elemento)

       p. siguiente:= nil;       (es el ultimo)

       If l= nil then

           L:=p

       Else

       Begin

              (Buco el último de l)

              Q:=l;

              While q. siguiente <> nil do

                    Q:=q. siguiente;

             (Engancho p a continucion del último)

             q. siguiente:=p;

      End;

End;

·         Borrado de un elemento: Retira un elemento de la lista.

Procedure borrar_primero (var l: lista);

Var

       P: lista;

Begin

       P:=l;

       L:=l. siguiente;

       Dispose (p)

End;

Procedure borrar_lista (l: lista);

Var

      P: lista;

Begin

     While l <>nil do

     Begin

            P:= l;

            L:= l. siguiente;

            Dispose (p);

     End;

End;

·         Búsqueda de un elemento: Busca el elemento en la lista.

Function pertenece (elem: T; L Lista): boolean;

Var

      P: Lista;

Begin

      P:=L;

(Notar: evolución por circuito corto)

       Write (p <> nil) and (p. elemento <> elem) do

             P:= p. siguiente;

Pertenece:= (p <> nil);

End;

           

·         Vacía: Indica si la lista contiene o no elementos.

·         Tamaño: Indica el número de elementos de la lista. 

Estructura básica

Type

      Lista = celda;

      Celda = record

                 Elemento: T;

                 Siguiente: lista;

End;

Tipos de listas

·         Listas Simples: Se define como un conjunto de nodos uno detrás de otro, del cual siempre se puede conocer al nodo inicial y al final, de cada nodo de la lista, se conoce un contenido, que es la información que almacena dentro puede ser de cualquier tipo de dato un sucesor único excepto el ultimo nodo de la lista.

·         Listas Ordenadas: Son las que la posición de cada nodo viene determinada por el valor de uno o más campos obligatorios de información del nodo denominado clave. No se permite tener dos nodos con la misma clave.