Estructuras Linales

Indice

Listas 3

Pilas 5

Colas 7

Bibliografía 7

Listas

Una lista lineal es un conjunto de elementos de u tipo dado que pueden variar en número y donde cada elemento tiene un único predecesor y un único sucesor o siguiente, excepto el primero y último de la lista. Esta es una definición muy general que incluye los ficheros y vectores.

Los elementos d una lista lineal se almacena normalmente contigua – un elemento tras de otro – en posiciones consecutivas de la memoria. Las sucesivas entradas en una guía o dirección telefónico, por ejemplo, están en líneas sucesivas, excepto en las partes superior e inferior de cada columna. Una lista lineal se almacena en la memoria principal de una computadora en posiciones sucesivas de memoria; cuando de almacenan en cinta magnética, los elementos sucesivos se presentan en sucesión en la cinta. Esta asignación de memoria se denomina almacenamiento secuencial. Posteriormente se verá que existen otros tipos de almacenamiento denominado en cadenado o enlazado.

Las líneas así definidas se denominan contiguas. Las operaciones que se pueden realizar con listas lineales contiguas son:

1.- Insertar, eliminar o localizar un elemento.

2.- Determinar el tamaño – número de elementos – de la lista.

3.- Recorrer la lista para localizar un determinado elemento.

4.- Clasificar los elementos de la lista en orden ascendente o descendente.

5.- Unir dos o más listas e una sola.

6.- Dividir una lista en varias sublistas.

7,- Copiar la lista.

8.- Borrar la lista.

Una lista lineal contigua se almacenan en la me memoria de la computadora en posiciones sucesivas o adyacentes y se procesa como un array unidimensional. En este caso, el acceso a cualquier elemento de la lista y la adición de nuevos elementos es fácil; sin embargo, la inserción o borrado requiere un desplazamiento del lugar de los elementos que los siguen y, en consecuencia, el diseño de un algoritmo especifico.

Listas enlazadas

Una lista enlazada la constituye una colección lineal de elementos, llamados nodos, donde el orden de los mismos se establece mediante punteros. Cada nodo se divide en dos partes: una primera que contiene la información asociada al elemento, y una segunda parte, llamada campo de enlace o campo al siguiente puntero, que contiene la dirección del siguiente nodo de la lista. Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista.

Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales.

Las listas enlazadas tienen la ventaja de que permiten ingresar elementos en cualquier lugar de la lista sin necesidad de tener que hacer un espacio como

En los vectores. En una lista enlazada existen varias posiciones en las que se

Puede introducir un elemento, supongamos la lista que tiene los elementos

abc existen cuatro lugares donde se pueden insertar los nuevos valores, estos

son: kabc, akbc, abkc y abck.

Lista circulares

Las listas simples enlazadas no permiten a partir de un elemento acceder directamente a cualquiera de los elementos que le proceden. En lugar de almacenar un puntero NULO en el campo SIG del último elemento de la lista. Este tipo de estructura se llama lista enlazada circular o simplemente lista circular.

Las listas circulares presentan las siguientes ventajas:

• Cada nodo de la lista circular es accesible desde cualquier otro nodo de ella. Es decir, dado un nodo se puede recorrer toda la lista completa.

• Las operaciones de concatenación y división de las listas son más eficaces con listas circulares.

Los inconvenientes, por el contrario son:

• Se pueden producir lazos o bucles infinitos. Una forma de evitar estos bucles infinitos es disponer de un nodo especial que se encuentra permanentemente asociado a la existencia de la lista circular.

El nodo cabecera pude diferenciarse de los otros nodos en unas de las formas siguientes:

• Puede tener un valor especial en su campo INFO que no es válido como datos de otros elementos.

• Puede tener un indicador o bandera que señale cuando es nodo cabecera.

El campo de información del nodo cabecera no se utiliza, en el sombreado

...