Estructuras de datos

| INSTITUTO POLITÉCNICO NACIONALUNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERIA Y CIENCIAS SOCIALES Y ADMINISTRATIVAS | |

Algoritmos de las Estructuras de Datos

Alumno: Pineda Corona Luis Adrian
Secuencia: 1CV50
Asignatura: Estructura y Representación de Datos
Profesor:Melo González José M.

México D.F. a 14 de abril de 2011
ÍNDICE

1.- PILA 3
1.1 ALGORITMO DE LA FUNCIÓN EMPTY (p) 3
1.2 ALGORITMO DE LA FUNCIÓN POP(p) 4
1.3 ALGORITMO DE LA FUNCIÓN PUSH(p, x) 4
1.4 EJEMPLO 4
2.- COLA 5
2.1 ALGORITMO DE LA FUNCIÓN EMPTY (q) 5
2.2 ALGORITMO DE LA FUNCIÓN REMOVE(q) 6
2.3 ALGORITMO DE LA FUNCIÓN INSERT(q, x) 6
2.4 EJEMPLO 6
3.- LISTA 73.1 ALGORITMO DE LA FUNCIÓN REMOVE(list) 7
3.2 ALGORITMO DE LA FUNCIÓN INSERT(list, x) 8
3.3 EJEMPLO 8
4.- BIBLIOGRAFÍA 8
4.1 Estructuras de Datos con C y C++ 8
4.2 Wikipedia 8

1.- PILA
Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primeroen salir) que permite almacenar y recuperar datos.
Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
Para las operaciones push y pop debemos tomar en cuenta la estructura de la pila:
-Entero que indique el tope
-Un arreglo del tamaño que se deseela pila
En C, podemos verlo de la siguiente manera:
#define STACKSIZE 100 /*Define el tamaño de la pila*/
struct stack{
int top; /*Indicará el límite de la pila*/
int items [STACKSIZE];
};
Para desarrollar los algoritmos de push y pop debemos desarrollar una función auxiliar que se llamará empty y verificara si la pila esta o no vacía. La pila vacía no contiene elementos y, por tanto, seindica mediante top igual a -1.
Pila = p.
X = valor a insertar.
1.1 ALGORITMO DE LA FUNCIÓN EMPTY (p)
Si el valor de tope es igual a -1
Regresa VERDADERO
En otro caso
Regresa FALSO
Fin EMPTY
1.2 ALGORITMO DE LA FUNCIÓN POP(p)
Si EMPTY(p) es igual a VERDADERO
UNDERFLOW (La pila no contiene ningún elemento)
En otro caso
Devuelve el valor de la p.items en la casilla número top
Restaen 1 el valor de top
Fin POP
1.3 ALGORITMO DE LA FUNCIÓN PUSH(p, x)
Si el valor de tope es igual al tamaño de la pila -1
OVERFLOW (La pila está llena y no se agrega el elemento)
En otro caso
p.items en la casilla número top = x
Incrementa en 1 el valor de top
Fin PUSH
1.4 EJEMPLO
STACKSIZE=3
push(p, 1) top=0
push(p, 2) top=1
push(p, 3) top=2
push(p, 4) top=STACKSIZE-1, OVERFLOWX=pop(p) x=3, top=1
X=pop(p) x=2 top=0
X=pop(p) x=1 top=-1
X=pop(p) top=-1, UNDERFLOW

2.- COLA
Una cola (queue en inglés) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debidoa que el primer elemento en entrar será también el primero en salir.
En esta sección veremos a la cola como un arreglo de manera similar a como utilizamos a la pila.
Para las operaciones insert y remove debemos tomar en cuenta la estructura de la cola:
-Enteros que indican el inicio y fin de la cola
-Un arreglo del tamaño que se desee la pila.
En C, podemos verlo de la siguiente manera:#define MAXQUEUE 100 /*Tamaño de la cola*/
struct queue{
int items[MAXQUEUE];
int front, rear;
};
struct queue q;
q.front = q.rear = MAXQUEUE -1;
2.1 ALGORITMO DE LA FUNCIÓN EMPTY (q)
Si el valor de front es igual a rear
Regresa VERDADERO
En otro caso
Regresa FALSO
Fin EMPTY

2.2 ALGORITMO DE LA FUNCIÓN REMOVE(q)
Si EMPTY(q) es igual VERDADERO
UNDERFLOW (La cola no contiene...