Punteros

Es un dato que indica la posición de memoria ocupada por otro dato. Puede concebirse como una flecha, que "apunta" al dato en cuestión.

Estos proporcionan los enlaces de unión entre los elementos, permitiendo que durante la ejecución del programa, las structuras dinámicas puedan cambiar sus tamaños. En las estructuras dinámicas estos elementos, llamados nodos son normalmente registros, de al menos dos campos de donde uno de ellos es puntero, es decir contiene información que permite localizar el siguiente- siguiente- nodo d ela estructura.

La utilización de punteros permite que sea relativamente fácil añadir indeterminadamente nuevos datos, insertar nuevos nodos en otros ya existentes y en general modificar estas estructuras. Deperndiendo de las relaciones entre los nodos de la estructura se hablara de estructuras lineales y no lineales, si partiendo del nodo inicial es posible dirigirse sucesivamente a todos los nodosvisitando cada uno una única vezdiremos que es una estructura lineal, en caso de no ser posible el recorridoen estas condiciones se hablade estructura no lineal.

Anillos y Cadenas

Cadena

La cadena es quizás la estructua más simple y se define como una secuencia de caracteres que se interpretan como un dato único. su longitud puede ser fijo o variable, por lo que además de ser constituidas por caracteres alfanumericos, hemos de conocer su longitud. En una variable tipo cadena se puede almacenar una palabra, una frase, una matricula de coche, una temperatura, etc. La longitud de una cadena se puede determinar bien indicando al principio de la misma el número dde caracteres que contiene, bien situando una carácter especial denominado fin-de-cadena.

Direccionamiento

Listas circulares

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.

El nodo típico es el mismo que para construir listas abiertas

Listas doblemente enlazadas

Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.

Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos.

El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior.

Tablas Hash

Las tablas de dispersión, más conocidas como tablas hash , son unas de las estructuras de datos más frecuentemente usadas. Para tener una idea inicial, las tablas de dispersión posibilitan tener una estructura que relaciona una clave con un valor, como un diccionario. Internamente, las tablas de dispersión son un array. Cada una de las posiciones del array puede contener ninguna, una o varias entradas del diccionario. Normalmente contendrá una como máximo, lo que permite un acceso rápido a los elementos, evitando realizar una búsqueda en la mayoría de los casos. Para saber en qué posición del array se debe buscar o insertar una clave, se utiliza una función de dispersión. Una función de dispersión relaciona a cada clave con un valor entero. Dos claves iguales deben tener el mismo valor de dispersión, también llamado hash value , pero dos claves distintas pueden tener el mismo valor de dispersión, lo cual provocaría una colisión.

El valor de dispersión es un entero sin signo entre 0 y el máximo entero de la plataforma, por lo que la tabla de dispersión usa el resto de dividir el valor de dispersión entre el tamaño del array para encontrar la posición. Cuando dos claves tienen que ser almacenadas en la misma posición de la tabla se produce una colisión. Esto puede ser debido a que la función de dispersión no distribuye las claves lo suficiente, o a que hay más claves en la tabla hash que el tamaño del array. En el segundo caso, GLib ™ se encargará de redimensionar el array de forma automática.

Arbol

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

- Una estructura vacía o
- Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo: un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.

Formas de representación

- Mediante un grafo:

Figura 1

- Mediante un diagrama encolumnado:

a
   b
     d
   c
     e
     f

En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles tienen 0, 1 o 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

- Raíz: es aquel elemento que no tiene antecesor; ejemplo: a .
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
- Nodo interno: aquel que tiene al menos un descendiente.
- Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
- Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
- Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones : se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b . Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Pila

Una pila es una estructura de datos de acceso restrictivo a sus elementos. Se puede entender como una pila de libros que se amontonan de abajo hacia arriba. En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima de la pila de libros, es decir, desde el último que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.

En los programas estas estructuras suelen ser fundamentales. La recursividad se simula en un computador con la ayuda de una pila. Asimismo muchos algoritmos emplean las pilas como estructura de datos fundamental, por ejemplo para mantener una lista de tareas pendientes que se van acumulando.

Las pilas ofrecen dos operaciones fundamentales, que son apilar y desapilar sobre la cima. El uso que se les de a las pilas es independiente de su implementación interna. Es decir, se hace un encapsulamiento. Por eso se considera a la pila como un tipo abstracto de datos.

Es una estructra de tipo LIFO (Last In First Out), es decir, último en entrar, primero en salir.

A continuación se expone la implementación de pilas mediante arrays y mediante listas enlazadas. En ambos casos se cubren cuatro operaciones básicas: Inicializar, Apilar, Desapilar, y Vacía (nos indica si la pila está vacía). Las claves que contendrán serán simplemente números enteros, aunque esto puede cambiarse a voluntad y no supone ningún inconveniente.

Cola

Una cola es una estructura de datos de acceso restrictivo a sus elementos. Un ejemplo sencillo es la cola del cine o del autobús, el primero que llegue será el primero en entrar, y afortunadamente en un sistema informático no se cuela nadie salvo que el programador lo diga.

Las colas serán de ayuda fundamental para ciertos recorridos de árboles y grafos.

Las colas ofrecen dos operaciones fundamentales, que son encolar (al final de la cola) y desencolar (del comienzo de la cola). Al igual que con las pilas, la implementación de las colas suele encapsularse, es decir, basta con conocer las operaciones de manipulación de la cola para poder usarla, olvidando su implementación interna.

Es una estructra de tipo FIFO (First In First Out), es decir: primero en entrar, primero en salir.

A continuación se expone la implementación de colas, con arrays y con listas enlazadas circulares. En ambos casos se cubren cuatro operaciones básicas: Inicializar, Encolar, Desencolar, y Vacía. Asimismo las claves que contendrán serán simplemente números enteros.

Estructuras de Red

Grafos

   Un grafo, G, es un par, compuesto por dos conjuntos V y A. Al conjunto V se le llama conjunto de vértices o nodos del grafo. A es un conjunto de pares de vértices, estos pares se conocen habitualmente con el nombre de arcos o ejes del grafo. Se suele utilizar la notacion G = (V, A) para identificar un grafo.

   Los grafos representan un conjunto de objetos donde no hay restricción a la relación entre ellos. Son estructuras más generales y menos restrictivas. Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices , de forma que y representan dos arcos diferentes.

   Los grafos permiten representar conjuntos de objetos arbitrariamente relacionados. Se puede asociar el conjunto de vértices con el conjunto de objetos y el conjunto de arcos con las relaciones que se establecen entre ellos.

   Los grafos son modelos matemáticos de numerosas situaciones reales: un mapa de carreteras, la red de ferrocarriles, el plano de un circuito eléctrico, el esquema de la red telefónica de una compañia, etc.

   El número de distintos pares de vértices (v(i), v(j)), con v(i) <> v(j), en un grafo con n vértices es n*(n-1)/2. Este es el número máximo de arcos en un grafo no dirigido de n vértices. Un grafo no dirigido que tenga exactamente n*(n-1)/2 arcos se dice que es un grafo completo. En el caso de un grafo dirigido de n vértices el número máximo de arcos es n*(n-1).

• Orden de un grafo: es el número de nodos (vértices) del grafo.
• Grado de un nodo: es el número de ejes (arcos) que inciden sobre el nodo
• Grafo simétrico: es un grafo dirigido tal que si existe la relación entonces existe , con u, v pertenecientes a V.
• Grafo no simétrico: es un grafo que no cumple la propiedad anterior.
• Grafo reflexivo: es el grafo que cumple que para todo nodo u de V existe la relación (u, u) de A.
• Grafo transitivo: es aquél que cumple que si existen las relaciones (u, v) y (v, z) de A entonces existe (u, z) de A.
• Grafo completo: es el grafo que contiene todos los posibles pares de relaciones, es decir, para cualquier par de nodos u, v de V, (u <> v), existe (u, v) de A.
• Camino: un camino en el grafo G es una sucesión de vértices y arcos: v(0), a(1), v(1), a(2), v(2), ... , a(k), v(k); tal que los extremos del arco a(i) son los vértices v(i-1) y v(i).
• Longitud de un camino: es el número de arcos que componen el camino.
• Camino cerrado (circuito): camino en el que coinciden los vértices extremos (v(0) = v(k)).
• Camino simple: camino donde sus vértices son distintos dos a dos, salvo a lo sumo los extremos.
• Camino elemental: camino donde sus arcos son distintos dos a dos.
• Camino euleriano: camino simple que contiene todos los arcos del grafo.
• Grafo euleriano: es un grafo que tiene un camino euleriano cerrado.
• Grafo conexo: es un grafo no dirigido tal que para cualquier par de nodos existe al menos un camino que los une.
• Grafo fuertemente conexo: es un grafo dirigido tal que para cualquier par de nodos existe un camino que los une.
• Punto de articulación: es un nodo que si desaparece provoca que se cree un grafo no conexo.
• Componente conexa: subgrafo conexo maximal de un grafo no dirigido (parte más grande de un grafo que sea conexa).