Estructura De Datos Lineales
Enviado por Darwin7826 • 26 de Julio de 2012 • 1.381 Palabras (6 Páginas) • 963 Visitas
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
...