ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Estructura De Datos Lineal Y No Lineal


Enviado por   •  2 de Octubre de 2011  •  2.051 Palabras (9 Páginas)  •  1.232 Visitas

Página 1 de 9

Pilas

Una pila es un concepto aplicable sobre estructuras de datos lineales, en la que la insercion y eliminacion de datos se realiza solo por un extremo denominado cima o tope.

Se define el tope o cima de la pila al unico dato visible de la estructura que seria el ultimo que se coloco (el que esta encima).

Operaciones básicas o permitidas

Entre las operaciones permitidas estan:

• Verificar si es vacia (empty)

• Insertar un dato sobre la pila (push)

• Eliminar un dato de la pila (pop)

• Inspeccionar la cima (top)

a) Pusheando (apilando) elementos sobre la pila

b) Popeando (desapilando) elementos de la pila

Aplicaciones de las Pilas

Las pilas son utilizadas ampliamente para solucionar una amplia variedad de

problemas. Se utilizan en compiladores, sistemas operativos y en programas de

aplicacion. Veamos algunas de las aplicaciones mas interesantes.

✔ Llamadas a métodos.- Cuando se realizan llamadas a metodos, el programa

principal debe recordar el lugar donde se hizo la llamada, de modo que pueda

retornar alli cuando el metodo se haya terminado de ejecutar.

✔ Almacenamiento temporal de páginas Web.- Los navegadores de Internet

almacenan las direcciones de las paginas recientemente visitadas en una pila.

Cada vez que un usuario visita un nuevo sitio, las direcciones son introducidas

en la pila de direcciones. El navegador despues permite al usuario volver a las

paginas visitadas previamente usando un boton.

✔ El mecanismo de “deshacer-rehacer” en los editores de texto.- Los

editores de texto utilizan usualmente un mecanismo de “deshacer” (undo) que

cancela las operaciones editadas actualmente para volver a las operaciones

previas. Para ello se utiliza una pila.

En general, las aplicaciones de esta estructura de datos seran aquellas en las

que los datos se manejen de modo dinamico siguiendo una politica LIFO.

Colas

Las colas son otro tipo de concepto tambien aplicables sobre estructuras de datos lineales. En una cola las eliminaciones se realizan por el principio (inicio) y las inserciones se realizan en el otro extremo (fin).

Se usan para almacenar datos que necesitan ser procesados segun el orden de llegada.

Existen varias formas de implementar a una cola , de forma estatica

utilizando arreglos o bien, de manera dinamica utilizando el concepto de listas. De cualquier manera las operaciones sobre colas tambien deberian tardar una cantidad de tiempo constante en ejecutarse, independientemente del numero de elementos que existan sobre ella.

Operaciones

Entre las operaciones basicas permitidas estan:

• Verificar si es vacia

• Insertar un dato sobre la cola (encolar)

• Eliminar un dato de la cola (decolar)

• Inspeccionar el primero (primero)

Aplicaciones de las Colas

En informatica existen numerosas aplicaciones de las colas. Por ejemplo, en un sistema de tiempo compartido suele haber un procesado central y una serie de perifericos compartidos: discos, impresoras, lectores de CD, etc. Los recursos se comparten por diferentes usuarios y se utiliza una cola para almacenar los programas o las peticiones de los diferentes usuarios que esperan su turno de ejecucion. El procesador central atiende, normalmente, por riguroso orden de llamada del usuario; por tanto, todas las llamadas se almacenan en una cola.

Listas

Una lista en su sentido amplio, es un conjunto de elementos del mismo tipo donde cada elemento tiene un unico predecesor (excepto el primero) y un único sucesor (excepto el ultimo) y cuyo numero de elementos es variable.

S = {a, b, c, d,. . . z}

Ejemplo: Una lista de letras

Operaciones

Entre las operaciones permitidas estan:

• Verificar si es vacia.

• Insertar, eliminar o localizar un elemento.

• Determinar el tamano de la lista.

• Etc.

En fin, una lista podria tener todo tipo de operaciones que le permitan ser manipulada como un arreglo por ejemplo.

Otra forma de ver a una lista es como un conjunto de celdas o nodos que se encuentran enlazados entre si.

Y dependiendo de los enlaces y como se los tenga, podemos tener una lista de simple enlace, lista de doble enlace, lista de simple enlace circular o lista de doble enlace circular.

Lista de Simple Enlace

Cada nodo de la lista tiene 2 campos: un campo que tiene el dato y otro que tiene la referencia del siguiente nodo.

Los nodos de la lista son enlazados por medio de los campos enlaces. El ultimo nodo de una lista de simple enlace, por definicion no tiene siguiente o no existe o en terminos de programacion es NULL.

Para tener una lista enlazada con estos nodos, basta con tener la referencia solamente del primero, al igual que para sostener un conjunto de pelotitas enlazadas solo tenemos que agarrarnos de la primera pelotita.

Lista de Doble Enlace

En las listas lineales estudiadas anteriormente el recorrido de ellas solo podía hacerse en un unico sentido: de izquierda a derecha. Sin embargo en muchas ocasiones es necesario recorrer la lista en ambas direcciones. Este tipo de listas se denomina Listas de Doble Enlace o Listas Doblementa Enlazadas. En este tipo de listas cada nodo ha de tener 3 campos: un campo que tiene el dato, otro que tiene la referencia del siguiente nodo y otro que tiene la referencia del nodo anterior

.

Los nodos de la lista son enlazados por medio de los campos enlaces. El ultimo nodo de una lista de doble enlace, no tiene siguiente y el primer nodo de la lista no tiene anterior.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista,

...

Descargar como (para miembros actualizados) txt (13 Kb)
Leer 8 páginas más »
Disponible sólo en Clubensayos.com