Estructuras dinámicas
PUNTEROS
Los punteros son variables simples cuyo contenido es precisamente una referencia a otra variable. Una manera de realizar estructuras de datos ilimitadas es mediante el empleo de variables dinámicas. Una variable dinámica no se declara como tal, sino que se crea en el momento necesario, y se destruye cuando ya no se necesita. Las variables dinámicas no tienen nombre, sino que se designan mediantes otras variables llamadas punteros o referencias. El
valor de un puntero no es representable como número o texto. El tipo de un puntero especifica en realidad el tipo de variable a la que debe apuntar.
Operaciones
· Recorrido: se consigue mediante un bucle de acceso a elementos y avance del cursor. Puesto que la secuencia tiene un número indefinido de elementos, no se usar un bucle con contador. En este caso usaremos un esquema MIENTRAS.
· Búsqueda: ha de hacerse en forma secuencial. Es parecida al recorrido, pero la condición de terminación cambiar . De hecho habrá una doble condición de terminación: que se localice el elemento buscado y/o que se agote la secuencia. A continuación se presenta la búsqueda de la posición en que ha de insertarse un nuevo número en la secuencia ordenada. La posición ser la que ocupe el primer valor igual o mayor que el que se quiere insertar.
· Inserción: se consigue creando una variable din mica para contenerlo y modificando los punteros para enlazar dicha variable en mitad de la secuencia.
LISTAS
Es un conjunto variable de objetos del mismo tipo llamados elementos de la lista. La lista está almacenada en un soporte direccionable y existe una operación que permite pasar de un elemento a otro, si éste existe. Los elementos característicos de esta estructura son los siguientes:
· El espacio asignado para ella, es decir, los límites izquierdo y derecho de la lista.
· El tipo de los elementos de la lista y por tanto el número de bytes ocupados por cada elemento.
· Un puntero principio que contiene la dirección de la posición del elemento inicial de la lista.
· Un puntero fin con la dirección del elemento siguiente al último de la lista.
Llamaremos lista vacía a la que no contiene ningún elemento, es decir, cuando se cumple que el límite izquierdo es igual al límite derecho. Los procesamientos posibles sobre un lista son:
· Acceder al primer elemento de la lista (cabeza).
· Acceder a otros elementos.
· Suprimir o añadir elementos.
Listas encadenadas
Es un conjunto variable de elementos, donde el orden de los mismos se establece mediante punteros. Cada elemento se divide en dos partes: una primera que contiene la información asociada al elemento, y una segunda,
llamada campo de enlace o campo de puntero, que contiene la dirección del siguiente elemento de la lista.
Listas dobles
Son aquellas en que cada elemento, además de su información correspondiente, contiene un puntero con la dirección del siguiente elemento, y un puntero con la posición del elemento anterior de la lista.
Listas circulares
Son aquellas en las que su último elemento contiene un puntero con la dirección del primer elemento de la lista.
COLAS
Una cola es una lista en la que las supresiones se realizan solamente al principio de la lista y las inserciones al final de la misma. Al igual que en el caso de la pilas, hay que prever un vector para almacenar el m ximo número de elementos que puedan presentarse en el programa. A diferencia de las pilas, no basta con añadir a la representación un simple contador, tal que indique el número de elementos válidos. Hay que prever además dos índices que indiquen la posición del comienzo y del final de la cola. Si la cola no está vacía, en CABEZA está el primer elemento, y si la cola no está llena, en FIN es el lugar donde hay que copiar el siguiente elemento que se incorpore a la misma.
Colas de prioridades
Es una lista lineal donde los elementos son pares de la forma (qi, pi), donde q es un elemento del tipo base y p es una prioridad. Se dispone de una política FIFO (First In First Out) entre elementos de la misma prioridad, es decir, se puede entrar por cualquier sitio.
PILAS
Es una lista de elementos en la cual un elemento sólo puede ser añadido o eliminado por un extremo llamado CIMA. Esto significa que los elementos se sacan de la pila en orden inverso al que se pusieron en ella. Las dos operaciones básicas asociadas a las pilas son:
· Poner: es añadir un elemento a la pila.
· Sacar: es extraer un elemento de la pila.
Los sistemas operativos usan este tipo de estructuras cuando ejecutan los subprogramas o subrutinas. Cuando se efectúa, los números de posición de la línea y la sentencia son colocados en la pila y se pasa el control a la línea especificada por la sentencia. Cuando se ejecuta el retorno, el proceso continúa desde la posición en que se encontraba gracias a los datos almacenados en la pila. La representación consiste en un vector con espacio para un máximo de elementos y un contador que indica el número de elementos válidos almacenados en el vector.
ARBOLES
Puede definirse como un grafo no orientado, conexo y acíclico en el que existe un vértice destacado llamado raíz.
Todo árbol está compuesto por una jerarquía de elementos llamados nudos. El nivel superior de la jerarquía tiene un sólo nudo, al que se llama raíz. Excepto la raíz, todo nudo está vinculado a otro nudo de nivel superior que llamaremos antecesor o padre. Ningún elemento puede tener más de un antecesor. En cambio, todo elemento puede tener uno o más elementos relacionados con él, en un nivel inferior, a los que llamaremos descendientes o hijos. Los elementos que no tienen descendientes se llaman hojas y las líneas que unen unos nudos con otros ramas. Se dice que un árbol es N-ario cuando el número máximo de descendientes de cada uno de los nudos es N. Todo árbol N-ario puede convertirse en un árbol binario equivalente y, frecuentemente, es ésta la forma de representar un árbol en la memoria central del computador, por ser más simples los procesamientos relacionados con ellos.
Arboles binarios
Un árbol binario es una estructura que puede estar formada por:
· Ningún elemento (árbol vacío).
· Una raíz y un número finito de nudos. Cada uno de ellos estará constituido por dos subárboles distintos (ocasionalmente vacíos) llamados subárbol izquierdo y subárbol derecho del árbol binario.
La altura y profundidad de un árbol binario es el número de nudos que constituye el camino más largo desde la raíz hasta un hoja. Un árbol vacío tiene una profundidad nula. Decimos que un árbol binario está equilibrado si la diferencia entre las alturas de los dos subárboles de cada uno de los nudos del árbol es como máximo igual a la unidad, es decir, si para todo nudo del árbol se cumple:
· Valor abs( altura( subárbol-izq ) - altura( subárbol-der ) ) = 1
Operaciones
Las operaciones usuales sobre un árbol binario son:
· Recorrido del rbol.
· Inserción de elementos.
· Eliminación de elementos.
Existen tres modos estándar de recorrer un árbol binario de raíz R. Estos tres algoritmos, denominados preorden, orden central y postorden, son los siguientes:
· Preorden: R - A - B.
· Orden central: A - R - B.
· Postorden: A - B - R.
Estructuras en RED o PLEX
Con las estructuras en árbol, con uno o varios enlaces en cada nudo, existen ciertas relaciones que no pueden resolverse. Ejemplo de ello puede ser el caso de las relaciones antecesor-sucesor, cuando un sucesor tiene más de un antecesor. Para estos casos, la descripción se realiza por medio de otra clase de estructuras llamadas PLEX o en RED. Una estructura plex no es más que una yuxtaposición de estructuras en árbol en la que puede descomponerse admitiendo ciertas redundancias.
