Estructura de DatosRepaso

Tipos de Datos Simples o

Primitivos

Dato Longitud Rango

Arreglos Estáticas

• Una estructura de datos estática esaquella en la que el tamaño ocupado enmemoria se define antes de que elprograma se ejecute y no puedemodificarse dicho tamaño durante laejecución del programa.

• Entre las estructuras de datos estáticas seencuentran los arreglos (vectores ymatrices), registros, archivos y cadenas decaracteres.

Estructuras de Información

• Una estructura de datos o de información es unacolección de datos que pueden ser caracterizados porsu organización y las operaciones que se definen sobreellos.

• Las estructuras de datos se utilizan generalmente paraprocesar una colección de valores que estánrelacionados entre sí por algún método.

– Por ejemplo: una lista de notas, una serie de puntajes deun concurso o una lista de temperaturas medidas a lolargo de un período de tiempo.

• Las estructuras de datos básicas que soportan lamayoría de los lenguajes de programación son lasestructuras estáticas.

Registro

• Un registro o estructura es un conjuntode n elementos heterogéneos que estánagrupados bajo un único nombre (enuna sola variable).

– Heterogéneo: los elementos son por logeneral de distinto tipo de dato.

– Es un nuevo tipo de dato definido por elprogramador.

– A cada uno de los elementos de unaestructura se le conoce con el nombre decampo o miembro.

– Los miembros de una estructura pueden sera la vez otras estructuras.

Uniones

• Las uniones son un tipo especial de estructuras quepermiten almacenar elementos de diferentes tipos en lasmismas posiciones de memoria, aunque evidentementeno simultáneamente. Así, las uniones son similares a lasestructuras, pero con la diferencia de que en las unionessus campos se almacenan solapándose unos con otrosen la misma ubicación de memoria; al contrario que enlas estructuras, donde los campos se almacenan unosseguidos de otros en posiciones contiguas de memoria.

• En esencia, las uniones sirven para ahorrar espacio enmemoria. Para almacenar los miembros de una unión, serequiere una zona de memoria igual a la que ocupa elmiembro de mayor tamaño en la unión.

• Todos los miembros son almacenados en el

mismo espacio de memoria y comienzan en la

misma dirección. El valor almacenado es

sobree escrito cada vez que se asigna un valor

al mismo miembro o a un miembro diferente,

aquí radica la diferencia con las estructuras.

• Las uniones pueden albergar diferentes tipos

de datos, pero sólo uno, de entre todos los

posibles, al mismo tiempo. Lo cual indica que

sólo uno de ellos puede estar activo en cada

momento.

ESTRUCTURA DE DATOS

ColasPilas

8Ing. Laura Lopez Lopez

Colas

Una cola es un caso particular de lista en el cual loselementos se insertan en un extremo (el posterior o final)y se suprimen en el otro (el anterior o frente).

Las colas se conocen también como listas FIFO (first-in first-out) o listas ``primero en entrar, primero ensalir''.

Algunas de las operaciones vistas para listaspierden sentido en el TDA Cola y se definen nuevasoperaciones

9Ing. Laura Lopez Lopez

Operaciones Básicas

Podemos definir las siguientes operaciones:

CREA. Crea una cola vacía.

VACIA. Devuelve un valor cierto si la cola estávacía, y falso en caso contrario.

PRIMERO. Devuelve el primer elemento de unacola.

INSERTA. Añade un elemento por el extremo finalde una cola.

SUPRIME. Suprime el primer elemento de una cola.

10Ing. Laura Lopez Lopez

Funciones Asociadas con las Colas

11Ing. Laura Lopez Lopez

12Ing. Laura Lopez Lopez

Colas de Prioridad

Una cola de prioridad es una cola a cuyos elementos seles ha asignado una prioridad, de forma que elorden en que los elementos son procesados sigue lassiguientes reglas:

El elemento con mayor prioridad es procesadoprimero.

Dos elementos con la mismaprioridad son procesados según el orden en quefueron introducidos en la cola.

13Ing. Laura Lopez Lopez

14Ing. Laura Lopez Lopez

Pilas

Una pila es un caso especial de lista en la cual todas lasinserciones y supresiones tienen lugar en un extremodeterminado llamado tope.

A las pilas se les llama también listas LIFO (last-in first-out) o listas “primero en entrar, primero en salir”.

Al igual que ocurría con el TDA Cola, en el TDA Pilatampoco se definen operaciones de posicionamiento en lapila. Esto es debido a que todas las operaciones de accesose realizan en la misma posición, el tope de la pila.

15Ing. Laura Lopez Lopez

Operaciones Básicas

Un TDA de la familia pila incluye a menudo las cinco

operaciones siguientes:

CREA. Crea una pila vacía.

VACIA. Devuelve un valor cierto si la pila está vacía, y falso encaso contrario.

TOPE. Devuelve el elemento situado el tope de la pila, sinextraerlo.

PUSH. Añade un elemento a la pila, quedando éste situado enel tope.

POP. Suprime el elemento situado en el tope de la pila.16Ing. Laura Lopez Lopez

Funciones Asociadas con las Pilas

17Ing. Laura Lopez Lopez

18Ing. Laura Lopez Lopez

0

1

a3max-3

tope = max-3

a2max-2

a1max-1

19Ing. Laura Lopez Lopez