estructura de datos

Diseño y Análisis de Algoritmos

Realizado por:
Gabriela Márquez
C.I. 15.622.883
Mayo 2005

Estructuras de Datos

Estructuras de Datos
• Matrices
• Pilas y Colas
• Tablas Asociativas
• Estructuras de Conjuntos Disjuntos (Partición)

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

1

Estructuras de Datos

Matrices:
Una matríz es una estructura dedatos que costa de un número fijo de ítems
del mismo tipo.
• Matrices monodimensionales → Arrays
Para declarar una matriz:

vec : matriz [1..50] de enteros
Donde:

vec[1] = primer elemento
vec[50] = último elemento
Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

2

Estructuras de Datos

Propiedad esencial de una matriz:
La propiedad esencial de unamatriz es que podemos calcular la dirección
de cualquier elemento dado en un tiempo constante.
Ejemplo: Si la matriz vec comienza en la dirección 5000, y sus variables enteras
ocupan 4 bytes de almacenamiento cada una, entonces la dirección del elemento
cuyo índice es k está dada claramente por: 4996+4k
5000
5001
5002
5003

Acceder a un elemento:
4996+4k

5004
5005
.
.
.

Mayo 2005Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

3

Estructuras de Datos

PILAS.
• Son implemetadas eficientemente con matrices monodimensionales.
• Estructura con política LIFO (last in, first out), el último elemento
insertado es el primer elemento en ser extraído de la pila.
Operaciones principales:
• Pila vacía
• Sacar un elemento (POP).
• Meter un elemento(PUSH).
Implementación:
pila: arreglo [1..N] de tipo_elemento
tope = 0
Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

4

Estructuras de Datos

tope = 0 → La pila está vacía.

1
2
3
4
5
...
N
Array → PILA

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

5

Estructuras de Datos

1

X

tope

Meter(X)

2
3
4
5...
N
Array → PILA

Al insertar un elemento en la pila, se incrementa el contador tope, que
señalará el índice del vector donde se encuentra el último elemento insertado

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

6

Estructuras de Datos

1
2

X

Meter(X)

X
tope

3
4
5
...
N
Array → PILA

Mayo 2005

Gabriela Márquez. Cátedra de Diseñoy Análisis de Algoritmos

7

Estructuras de Datos

1

X

2

X

3

X

4

X

5
...

tope

A medida que se
introducen elementos en
la pila, se incrementa el
tope

N
Array → PILA

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

8

Estructuras de Datos

20/05/05
Pila.Vacia ( ) : Lógico
{pos: regresa verdadero si la cadena estavacía}
1

Si tope=0 entonces
retornar Verdadero
sino
retornar Falso

tope: indica el indice
correspondiente al tope de la
pila

1

tope = 0 => VERDADERO

2

tope 0 => FALSO

Regresa verdadero pues la pila
está vacía.
Regresa falso pues la pila no
está vacía.

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

9

Estructuras de Datos

20/05/05Meter ( Elemento: Tipo_Elemento)
{pre: Elemento < > Vacio}
{pos: pila=pila+elemento}
1
2

tope = tope + 1
pila [tope] = elemento

tope: indica el índice
correspondiente al tope de la
pila

1

Elemento = X => pila[tope]=X

Inserta X (del tipo
Tipo_Elemento) en pila[tope]

Mayo 2005

Gabriela Márquez. Cátedra de Diseño y Análisis de Algoritmos

10

Estructuras de Datos20/05/05
Sacar ( )
{pre: pila < > Pila.Vacia}

{pos: pila = pila - elemento}

1

Si Pila.Vacia() entonces
desplegar “Error underflow”
sino
tope = tope – 1
retornar pila[tope + 1]

tope: indica el índice
correspondiente al tope de la
pila

1

pila[tope]=X, sacar() => X, tope= tope-1

Devuelve el elemento en el
tope de la pila, y decrementa el
contador “tope”.

Mayo 2005...