Estructura y organización de datos

[pic 1][pic 2][pic 3][pic 4]

1. Estructuras lineales

1. Listas

Una lista es una colección o secuencia de elementos ordenados uno tras otro, en la que cada elemento se conecta por medio de un apuntador.

A cada elemento de la lista se le llama nodo. Cada nodo está constituido por dos partes las cuales son:

1a. Parte Información

[pic 5]

2a. Parte Apuntador que señala

al siguiente nodo

Representación gráfica

•••[pic 6][pic 7][pic 8][pic 9][pic 10]

Debido a que el último elemento de la lista no está señalando a ningún elemento, existen diferentes formas de representarlo gráficamente:

[pic 11][pic 12][pic 13]

Listas enlazadas

Listas Simples

Cada nodo contiene un único enlace que conecta al siguiente nodo. La lista se recorre solamente hacia adelante.

•••[pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20]

Apuntadores al inicio y al final de la lista

Para poder manipular una lista de una manera eficiente, se deben utilizar apuntadores al inicio y al final de la lista. El apuntador al frente de la lista se llamará “inicio” y el que apunte al final se llamará “fin”.

inicio[pic 21][pic 22]

•••[pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29]

fin

Listas Dobles.

Cada nodo contiene dos enlaces o apuntadores, el enlace izquierdo apunta al nodo predecesor y el enlace derecho apunta al nodo sucesor.

…[pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36]

Circulares.

En las listas simples, el último nodo apunta al primer elemento de la lista.

[pic 37]

En las listas dobles, cada nodo esta enlazado a su predecesor y sucesor; y el último nodo apunta al primero y el primer nodo apunta al último.

[pic 38][pic 39][pic 40]

Multilistas.[pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48]

En las multilistas existen enlaces verticales y horizontales.

inicio[pic 49][pic 50]

[pic 51]        [pic 52]        [pic 53]

[pic 54][pic 55]

1. Pilas estáticas y dinámicas[pic 56]

Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar elementos por un extremo y retirarlo por el mismo extremo; ese extremo se llama parte superior de la pila o cima de la pila.

Cuando se dice que una pila esta ordenada, lo que se quiere decir es que hay un elemento al que se puede accesar primero (el que está en la cima de la pila), ver la siguiente figura el elemento F, el segundo elemento al cual se puede accesar es el que está después de la cima de la pila, ver el elemento E de la siguiente figura.

[pic 57]

Si deseamos insertar un nuevo elemento a la pila (elemento G), la pila quedara como se muestra en la siguiente figura.

[pic 58]

Ahora deseamos retirar un elemento de la pila, por lo que se retirará el elemento F, que es el que está en la cima.[pic 59]

[pic 60]

La pila sigue la filosofía LIFO (last-in, first-out) o UEPS (último en entrar, primero en salir).

Las operaciones más frecuentes en una pila son Insertar y Quitar. La operación Insertar (push) añade un elemento a la pila, colocándolo en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la cima de la pila.

La pila se puede implementar mediante arreglos, en cuyo caso su dimensión o longitud es fija; otra forma de implementarla es mediante listas ligadas, en cuyo caso se utiliza memoria dinámica y el límite es la memoria RAM de la computadora.

Una pila puede estar vacía (no tener elementos) o estar llena (en caso de ser de tamaño fijo y esté en el límite el tamaño de la pila). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error, debido a que esta operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila llena se producirá un error llamado desbordamiento (overflow). Para evitar estas situaciones se diseña métodos, que comprueben si la pila está llena o está vacía.

Operaciones.

Antes de poder utilizar una pila debemos estipular que tipo de datos va almacenar (int, float, char, etc.).

Operaciones básicas

Las operaciones básicas de una pila son:

• Tamaño de la pila        Número de elementos máximos que puede contener

la pila.

• Crear Pila        Crear una pila vacía.
• Inicializar la Pila        Inicializar la pila en vacía.
• Insertar (push)        Poner un elemento en la pila.
• Quitar (pop)        Retirar un elemento en la pila.
• Pila vacía (stackempty)        Comprobar si la pila no está vacía.
• Pila llena (stackfull)        Comprobar si la pila está llena.
• Limpiar pila (stackclear)        Eliminar todo lo elementos de la pila.
• Cima (stacktop)        Obtener el elemento que está en la cima de la pila.

Al utilizar un arreglo para almacenar los elementos de una pila, hay que tener en cuenta que el tamaño de la pila no debe de exceder el número de elementos del arreglo, por lo que el método pilaLlena() es importante en el diseño.

El método más común para introducir elementos en una pila nueva es definir el fondo de la pila en la posición -1, es decir, crear una pila vacía. Posteriormente se van introduciendo elementos en el arreglo, de modo que el primero se agregara en la posición 1, el siguiente en la posición 2 y así sucesivamente. Por tal motivo los algoritmos de Insertar (push) y Quitar (pop) se definen como sigue:

...