Estructura De Datos Lineales

Republica Bolivariana de Venezuela.

Departamento de Informática.

Asignatura. Estructura de Datos.

Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios subelementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:

 El desarrollo de compiladores de lenguajes de programación que están conformados por varios subprogramas con finalidades más específicas, como por ejemplo: el analizador de léxico que genera la tabla de símbolos.

 La simulación discreta de sistemas a través del computador, donde la mayoría de los paquetes de simulación digital ofrecen lenguajes de simulación que soportan las primitivas para el manejo de colas y sus diferentes versiones.

 La realización de sistemas operativos para los computadores, los cuales hacen un uso intensivo de las estructuras lineales, ya que internamente se soportan en los sistemas operativos, las colas de ejecución para los dispositivos, las pilas de llamadas a los subprogramas de cualquier programa, las listas de usuarios en los sistemas operativos multiusuario, etc.

Listas.

Una lista es una estructura de datos secuencial.

Una manera de clasificarlas es por la forma de acceder al siguiente elemento:

 Lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.

 Lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.

Una lista enlazada se puede definir recursivamente de la siguiente manera:

 Una lista enlazada es una estructura vacía o

 Un elemento de información y un enlace hacia una lista (un nodo).

Las propiedades de las listas son:

 Si n = 0 entonces la lista está vacía.

 Si n ³ 1 entonces e1 es el primer elemento de la lista y en el último.

 Si es el predecesor de e i+1 y el sucesor de e i-1 con 1 £ i £ n.

Ejemplo: Sea la lista l = (‘casa’, ‘perro’, ‘carro’, ‘árbol’) entonces ‘casa’ es el primer elemento de l y no tiene predecesor

 ‘árbol’ es el último elemento de l y no tiene sucesor.

 ‘casa’ es el predecesor de ‘perro’.

 ‘perro’ es el sucesor de ‘casa’.

Las listas se pueden clasificar por varios criterios:

 Por el orden de sus elementos sobre la base de un subelemento: ordenadas (ascendente o descendente), y desordenadas.

 Por el método de almacenamiento: secuencial y enlazada (simple, doble, simple circular y doble circular).

Operaciones con las listas.

Crear una lista.

En toda creación de una lista existen dos pasos:

 Creación del primer nodo.

 Creación del resto de nodos.

 Creación del primer nodo.

new(lista);

lista^_nodo:= 1;

lista^.siguiente=nil; .

 Creación de una lista con N nodos.

begin

new(lista);

lista^_info:= 1;

aux=lista;

for i=1 to N do

begin

new(aux^.sig);

aux=aux^.sig;

aux^.info=I;

end;

aux^.sig=nil;

end;

Recorrido de una lista

Aux:= lista;

While aux <> nil do

Write (aux^.info);

Aux:=(aux^.siguiente);

End.

Inserción en la Lista.

For i=n to downto 1 do

Begin

New(aux);

Aux^.info:=I;

Aux^.siguiente:0lista;

Lista:=aux;

End.

Búsqueda de un Elemento en la Lista.

Var

Aux:=puntero;

Inc:

Begin

Aux:=comienzo;

Inc:=false;

While (not inc) and (aux <> nil) do

Begin

If aux^.info:=elemento then

Inc:=true;

Else

Aux:=aux^.siguiente;

End

If inc=false then

Write(‘ Elemento no encontrado ‘);

Else

Write(‘ elemento Encontrado’);

End .

End.

Borrar un Elemento en la Lista.

Var

Igual, anterior:=lista;

Begin

{ se debe buscar la posición del elemento a borrar }

Actual:=l,

Anterior:=l;

While (actual <> nil) and (actual^.clave <> elem) do

Begin

Anterior:= actual;

Actual:0actual^.siguiente;

End;

If (actual <> nil) and (actual^. Clave<> elem) then

Begin

If (anterior=actual) then

L:=actual^. Sig { borrar el primero }

Else

Anterior^. Sig:= actual^.sig;

Dispose(actual);

End;

End;

Pila.

Una pila es un subtipo de las listas donde el acceso está restringido a un solo extremos de la lista, en este caso al tope de la misma. Un ejemplo de esta estructura es una pila de bandejas de un restaurante de comida rápida (self service) o una pila de platos, etc. Si se analiza el ejemplo en detalle, se tiene que cualquier cliente del restaurante, al llegar toma la primera bandeja que encuentra en la pila de bandejas, es decir la que está encima de todas las demás. Asimismo, cuando el empleado del restaurante coloca bandejas limpias en la pila, lo hace colocándolas encima de la que está arriba, puesto que es más trabajo, alzar algunas y colocar las limpias entre las que quedan y las que alzó. Las operaciones básicas sobre una pila son: crearla, destruirla, agregar un nuevo elemento, suprimir un elemento, consultar el elemento del tope y verificar si está vacía.

...