unidad 2: estructuras de datos - unneexa.unne.edu.ar/informatica/programacion1/public...unidad 2:...

Unidad 2: Estructuras de Datos

Tema III. Estructuras de datos Compuestas.

Pilas, Colas y Listas implementadas con punteros

Programación I (Plan 1999)

Algoritmos y Estructuras de Datos II (Plan 2009)

Mgter. Oscar Adolfo VallejosFaCENA - UNNE

Punteros

• Las estructuras de datos estudiadas hasta ahora se almacenan estáticamente en la memoria física del computador.

• Esta rigidez en las estructuras de datos estáticas hace que no pueden crecer o menguar durante la ejecución de un programa.

• Por otra parte, la representación de ciertas construcciones (como las listas) usando las estructuras conocidas (concretamente los arrays) tiene que hacerse situando elementos consecutivos en componentes contiguas, de manera que las operaciones de inserción de un elemento nuevo o desaparición de uno ya existente requieren el desplazamiento de todos los posteriores para cubrir el vacío producido, o para abrir espacio para el nuevo.

Introducción al uso de punteros

• Un puntero es una variable que sirve para señalar la posición de la memoria en que se encuentra otro dato almacenando como valor la dirección de ese dato.

Al usar punteros conviene tener muy claro que la variable puntero y la variable a la que apunta son dos variables distintas y, por lo tanto, sus valores son también distintos.

Definición y declaración de punteros

• Antes de poder usar punteros es necesario declararlos: en primer lugar habrá que definir el tipo del dato apuntado y, posteriormente, declarar la(s) variable(s) de tipo puntero que se usará(n).

• Por consiguiente, una variable puntero sólo puede señalar a objetos de un mismo tipo, establecido en la declaración.

Generación y destrucción de variables dinámicas

• La creación y destrucción de variables dinámicas se realiza por medio de los procedimientos predefinidos New y Dispose.

tiene un efecto doble:1. Reserva la memoria para un dato del tipo apropiado (en este caso del tipochar).2. Coloca la dirección de esta nueva variable en el puntero..

Obsérvese que la operación de generación New ha generado el dato apuntadopor apCar, pero ¶este contiene por el momento una información desconocida.

• Para destruir una variable dinámica se usa el procedimiento estándar Dispose.

realiza las dos siguientes acciones1. Libera la memoria asociada a la variable referida apCar^ (defiandola disponiblepara otros ¯nes).2. Deja indefinido el valor del puntero..

Operaciones básicas con datos apuntados

• Recuérdese que el dato referido por el puntero apCarse denota apCar^, que es de tipo char. Por consiguiente, son válidas las instrucciones de asignación, lectura y escritura y demás operaciones legales para los caracteres:

Igualmente, suponiendo que se ha declarado

el siguiente fragmento de programa es válido:

• Por su parte, las operaciones siguientes, por ejemplo, no serán legales:

Operaciones básicas con punteros

• Sólo las operaciones de comparación (con la igualdad) y asignación están permitidas entre punteros.

• Observese que las instrucciones

apNum1:= apNum2 y apNum1^:= apNum2^

tienen distinto efecto.

El valor nil

• Un modo alternativo para dar valor a un puntero es, simplemente, diciendo que no apunta a ningún dato. Esto se puede conseguir utilizando la constante predefinida nil.

Estructuras lineales: las listasenlazadas

• Las representaciones para listas (con punteros) nos permitirán insertar y borrar elementos más fácil y eficientemente que en una implementación estática (para listas acotadas) usando el tipo de datos array.

• Una lista es una colección lineal de elementos que se llaman nodos. El término colección lineal debe entenderse de la siguiente manera: tenemos un primer y un último nodo, de tal manera que a cada nodo, salvo el último, le corresponde un único sucesor, y a cada nodo, salvo el primero, le corresponde un único predecesor.

• Esencialmente, una lista será representada como un puntero que señala al principio (o cabeza) de la lista.

Inserción de elementos

• Supóngase que nuestra lista está iniciada con el valor nil. Para introducir

• un elemento nuevoDato en ella, habrá que completar la siguiente secuencia de pasos, que se muestra gráficamente en la ¯gura 17.2:

• 1. En primer lugar, habrá que generar una variable del tipo tNodo, que ha de contener el nuevo eslabón: esto se hace mediante la sentencia New(lista).

• 2. Posteriormente, se asigna nuevoDato al campo contenido del nodo recién generado. La forma de esta asignación dependerá del tipo de datos de la variable nuevoDato.

• 3. Y por ¶ultimo, hay que anular (con el valor nil) el campo siguiente del nodo para indicar que es el ¶ultimo de la lista.

• Para insertar un nuevoDato al principio de una lista no vacía, lista, se ha de proceder como se indica :

• 1. Una variable auxiliar listaAux se usa para apuntar al principio de la lista con el ¯n de no perderla.

listaAux:= lista

• 2. Después se asigna memoria a una variable del tipo tNodo (que ha de contener el nuevo elemento): esto se hace mediante la sentencia New(lista).

• 3. Posteriormente, se asigna nuevoDato al campo contenido del nuevo nodo:

• lista^.contenido:= nuevoDato

• 4. Y, por ¶ultimo, se asigna la listaAux al campo siguiente del nuevo nodo para indicar los demás elementos de la lista, es decir:

• lista^.siguiente:= listaAux

Eliminación de elementos

El procedimiento EliminarK

El procedimiento InsertarK

Pilas

• Una pila es un tipo de lista en el que todas las inserciones y eliminaciones de elementos se realizan por el mismo extremo de la lista.

• El nombre de pila procede de la similitud en el manejo de esta estructura de datos y la de una “pila de objetos". Estas estructura también son llamadas listas LIFO,1 acrónimo que refleja la característica más importante de las pilas.

Definición de una pila como lista enlazada

Operaciones básicas sobre las pilas

• Creación de una pila vacía

Averiguar si una pila está vacía

Consulta de la cima de una pila

Añadir un nuevo elemento en la cima de la pila

Eliminar la cima de la pila

Colas

• Una cola es una lista en la que todas las inserciones se realizan por un extremo y todas las eliminaciones se realizan por el otro extremo de la lista.

• El ejemplo más importante de esta estructura de datos, del cual recibe el nombre, es el de una cola de personas ante una ventanilla. En esta situación, el primero en llegar es el primero en ser servido; por esto, las colas también se llaman listas FIFO.

Definición del tipo cola

Creación de una cola vacía

Añadir un elemento

Suprimir el primer elementoPara definir SacarDeCola tenemos que considerar dos casos distintos:

1. Que la cola sea unitaria, pues al sacar su ¶unico elemento se queda vac¶³a,con lo que hay que actualizar tanto su principio como su final.

2. Que la cola tenga longitud mayor o igual a dos, en cuyo caso s¶olo hay queactualizar el campo principio.