Estructura y tipos de datos

Universidad Nacional Experimental de Guayana
Vicerrectorado Académico
Ingeniería Informática
Cátedra: Estructura de Datos
Profesor: A. Caniumilla

Bachilleres:

Moreno, Luis C.I: 20.035.771
Malaver, Roberto C.I:23.502.393

Ciudad Guayana, Marzo de 2010

Índice.

CONTENIDO | Pág. |
| |
Pilas………………………………….…..………………..…………..... | 03 |
Aplicaciones de Pilas…………………….…..………………………… | 03 |
Arboles….…………………………………….…..……………………. | 06 |
Tipos de Arboles……………………….…..…………………………… | 06 |
Aplicaciones de Arboles………...….……….…..……………………. | 09 |Grafos………………………… ….…….…..………………………… | 12 |
Aplicaciones de Grafos.…….…..…………………………………..… | 14 |
| |
Bibliografía…………………………………………………………….. | 19 |

Pilas.

Aplicaciones de Pilas.

Dentro del mundo de la programación existe una gran variedad de aplicaciones o algoritmos, donde la estructura de Pilas permite dar una solución confiable y eficiente a un determinadoproblema. Entre las aplicaciones que utilizan pilas están:

* Evaluación de Expresiones Aritméticas.

Una expresión aritmética está formada por operandos y operadores. Los operandos pueden ser valores constantes, variables o, incluso otra expresión, y los operadores son los símbolos conocidos de las operaciones matemáticas. La evaluación de una expresión aritmética escrita de manerahabitual, en notación infija, se realiza en dos pasos principales:

1- Transformar la expresión de notación infija a postfija.
2- Evaluar la expresión en notación postfija.

Algoritmo de Conversión de Notación Infija a Postfija o Notación Polaca Inversa.
**********************************************************************
Pila y Postfijo; //Dos pilas vacias.
PilaVacia(Postfijo);PilaVacia(Pila);

Mientras Not Fin_Expresion Hacer
Inicio

Caracter = Siguiente_Caracter; // Caracter almacena cada uno de los caracteres
de la expresion

Si (Es_Operando(Caracter) AND IsPilaVacia(Postfijo)) entonces
Inicio
Apilar(Postfija, Caracter);
Fin

Si (Es_Operador(Caracter)) entonces
Inicio

Si(IsPilaVacia(Pila)) entonces
Inicio
Apilar(Pila, Caracter);
Fin
Sino
Inicio
Si (Prioridad(Caracter) > Prioridad(Cima(Pila))) entonces
Inicio
Apilar(Pila, Caracter);
Fin
Sino
Inicio
car = Desempilar(Pila);
Apilar(Postfija,car);
Apilar(Pila, Caracter);
Fin

Si (Caracter == '(') entonces
Inicio
Apilar(Pila, Caracter);
Fin

Si (Caracter == ')') entonces
Inicio
Mientras (Cima(Pila) != '(') Hacer
Inicio
car = Desempilar(Pila);
Apilar(Postfija, car);
Fin
car = Desempilar(Pila);
Fin
Fin
FinMientras (Not IsPilaVacia(Pila)) Hacer
Inicio
car = Desempilar(Pila);
Apilar(Postfija, car);
Fin
Fin
**********************************************************************
Evaluación de la Notación Polaca Inversa (Notación Postfijo).
**********************************************************************
Pila //Pila vacia
PilaVacia(Pila);

Mientras (NotFin_Expresion) Hacer
Inicio

Caracter = Siguiente Caracter;
Si (EsOperando(Caracter) And not EsPilaVacia(Pila)) Entonces
Inicio
Apilar(Pila, Caracter);
Fin
Sino
Inicio
Si (Not EsPilaVacia(Pila)) Entonces
Inicio
Operando1 = Desempilar(Pila);
Operando2 = Desempilar(Pila);
Valor = Calcular(Caracter, Operando1, Operando2);
Apilar(Pila, Valor);...