Ejemplo 9.2
Se desea dise�ar una estructura que contenga la informaci�n de operaciones financieras. Esta estructura debe contar con un n�mero de cuenta, una cantidad de dinero, el tipo de operaci�n (deposito=0, retiro de fondos=1, puesta al dia=2 o estado de cuenta=3) y la fecha y hora en que la operaci�pn se ha realizado.
#include <stdio.h>
#include <conio.h>
#include <dos.h>
/*declaracion de las estructuras*/
struct fecha
{
unsigned int mes, dia, anyo;
};
struct tiempo
{
unsigned int horas, minutos;
};
struct registro_operacion
{
long numero_cuenta;
float cantidad;
int tipo_operacion;
struct fecha f;
struct tiempo t;
};
struct registro_operacion entrada();
main()
{
struct registro_operacion w;
w=entrada();
printf(«nn operacion realizadan»);
printf(«t%ldn», w.numero_cuenta);
/*ATENCION: note, la forma en la que llamamos a los miembros
de una estructura anidada*/
printf(«t%d-%d-%dn», w.f.dia, w.f.mes, w.f.anyo);
printf(«t%d:%dn», w.t.horas, w.t.minutos);
getch();
return 0;
}
struct registro_operacion entrada()
{
struct time t;
struct date d;
struct registro_operacion una;
printf(«nNumero de cuenta:n»);
scanf(«%ld», &una.numero_cuenta);
puts(«nTipo de Operacion:n»);
puts(«Deposito (0)»);
puts(«Retirada de Fondos (1)»);
puts(«Puesta al Dia (2)»);
puts(«Estado de Cuenta (3)»);
scanf(«%d», &una.tipo_operacion);
/*fecha y tiempo del sistema*/
gettime(&t);
una.t.horas=t.ti_hour;
una.t.minutos=t.ti_min;
getdate(&d);
una.f.anyo=d.da_year;
una.f.mes=d.da_mon;
una.f.dia=d.da_day;
return una;
}
Explicaci�n
A fin de realizar el acceso correcto a los campos d�a, mes y a�o, as� como el tiempo (la hora y los minutos) en que se efectu� la operaci�n, se define una estructura fecha y una estructura tiempo. La estructura registro_operaci�n tiene como miembro una variable (un campo) de tipo fecha, otra variable de tipo tiempo y otras variables para representar los otros campos. La estructura de tipo operaci�n se hace con una variable entera. A continuaci�n se declara tipos, se escribe una funci�n que lee una operaci�n financiera y devuelve la operaci�n le�da. La fecha y hora es capturada del sistema. (ejemplo tomado de «Algoritmos y Estructuras de datos, una perspectiva en C», Luis Joyanes Aguilar)
Arrays de Estructuras
Los ejemplos de estructuras que hemos visto hasta el momento, s�lo podemos manejar un conjunto de datos a la vez, o podemos declarar varias variables para manejar, por ejemplo, los datos de 5 alumnos de una instituci�n.
Sin embargo, al igual que los tipos int, float… en c, podemos crear arrays con estructuras.
Por ejemplo, supongamos que ya tenemos declarada una estructura llamada datos, que contiene los datos personasles de alumnos de cierta instituci�n, y queremos guardar los datos de 100 alumnos, no necesitamos de crear 100 variables de tipo estructura, sino que hacemos esta declaratoria:
strcut datos alumnos[100];
Ejemplo 9.3
Una biblioteca, desea tener un registro de los libros que en ella se encuentran, se sabe que existe un n�mero no mayor a 100 libros, y que los datos que se necesitan registrar son: el nombre del autor, el t�tulo del libro y las existencias del mismo. Dise�e una estructura que sea capaz de guardar esa informaci�n y luego mandarla a impresi�n.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 100
struct info_libro
{
char autor[20];
char titulo[30];
int num_ejemplares;
};
main()
{
struct info_libro libro[N];
int i=0;
clrscr();
printf(«ttPROGRAMA QUE CONTROLA UN INVENTARIO DE LIBROSnnn»);
for(i=1; i<=N; i++)
{
printf(«Ingrese los datos del libro %dn»,i);
printf(«Nombre del autor: «);
scanf(«%s», &libro[i].autor);
printf(«El titulo del libro es: «);
scanf(«%s», &libro[i].titulo);
printf(«Las existencias de este libro son:n»);
scanf(«%d», &libro[i].num_ejemplares);
}
clrscr();
printf(«tttLOS DATOS SON LOS SIGUIENTES:nnn»);
for(i=1; i<=N; i++)
{
printf(«********************************************n»);
printf(«Autor: %sn», libro[i].autor);
printf(«Titulo: %sn», libro[i].titulo);
printf(«Existencias: %dn», libro[i].num_ejemplares);
}
getch();
return 0;
}
Lo m�s resaltante que, debo rescatar es que, a diferencia de los vectores y las matrices, las estructuras no identifican su primer elemento con cero, sino con el n�mero uno, es por ello que nuestro contador, inicia con ese n�mero, adem�s que, para diferenciar un registro por otro, debemos incluir siempre el sub�ndice, [i].
Estructuras y Funciones
Cuando hacemos uso de funciones y de estructuras, debemos tener en cuenta la forma correcta, de c�mo enviarle a la funci�n el par�metro deseado, y con las estructuras, no es la excepci�n, por ejemplo:
/*declaraci�n de la estructura*/
struct info_libro
{
char autor[20];
char titulo[30];
int num_ejemplares;
};
/*declaraci�n de las funciones */
void impresi�n (struct info_libro *ptr);
void impresi�n1 (struct info_libro p);
/*definici�n de la estructura*/
struct info_libro libros;
/*llamado de la funcion: env�o por referencia*/
impresi�n(&libros);
/*�llamado de la funci�n: env�o por valor*/
impresi�n (libros);
Uso del typedef
Un operador typedef permite al programador crear un sin�nimo de tipo definido por el usuario o de un tipo ya exitente. La sintaxis es la siguiente:
typedef tipo_de_dato nuevotipodedato;
a partir de la declaraci� hecha por el typedef se puede hacer uso del nuevo sin�nimo del tipo de dato para definir variables, en general donde se utilizan los tipos de datos.
Veamos un ejemplo donde matemos dos p�jaros de un solo tiro, es decir donde se muestren el uso de funciones y el typedef.
Ejemplo 9.4
Un m�dico almacena la siguiente informaci�n de sus paciente en un array de registros (como mucho habr� 100 pacientes): Nombre, tel�fono, direcci�n, y si tiene alergias. Escribir un programa con las siguientes opciones (todas ellas diben realizarse con funciones):
a) Introducir los datos interactivamente. Para saber que ya no se van a introducir m�s pacientes, el usuario introducir� un 0 al solicitarle el n�mero de tel�fono del paciente. b) Imprimir por pantalla toda la informaci�n. c) Listar todos los pacientes con alergias. d) Crear una lista con el �ndice de todos los pacientes que sean de la Comunidad de Madrid (su tel�fono comienza por el prefijo 91). e) Salir.
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <string.h>
#define TAM_NOM 31
#define TAM_DIR 41
#define TAM_ALE 71
#define TAM_PAC 100
typedef struct {
char nombre[TAM_NOM];
double telefono;
char direccion[TAM_DIR];
char alergias[TAM_ALE];
} reg_paciente;
void tecla();
char menu();
void leerdatos(reg_paciente *pacientes, int *tamano);
void hayalergias(reg_paciente *pacientes, int tamano);
void imprimirtodos(reg_paciente *pacientes, int tamano);
void telefono91(reg_paciente *pacientes, int tamano);
void main()
{
char opcion;
int tamano;
reg_paciente pacientes[TAM_PAC];
system(«color f0″);
printf(«nnnnnnnnntttINICIO DEL PROGRAMAnnnnnnnn»);
tecla();
leerdatos(pacientes,&tamano);
do {
opcion=menu();
switch(opcion) {
case ‘1’:
imprimirtodos(pacientes,tamano);
break;
case ‘2’:
hayalergias(pacientes,tamano);
break;
case ‘3’:
telefono91(pacientes,tamano);
break;
case ‘4’:
leerdatos(pacientes,&tamano);
break;
case ‘0’:
printf(«nSaliendo…»);
break;
}
tecla();
} while (opcion!=’0′);
printf(«nnnnnnntttFIN DEL PROGRAMAnnnnnnn»);
tecla();
}
void tecla()
{
printf(«nPresiona cualquier tecla para continuar «);
getch();
clrscr();
return;
}
void leerdatos(reg_paciente *pacientes, int *tamano)
{
char buffer[15];
int i;
for (i=0;i<TAM_PAC;i++) {
printf(«nnn****PACIENTE NUMERO %2d****»,i+1);
printf(«nIntroduzca el nombre (no m�s de %d caracteres)nt»,TAM_NOM-1);
do {
gets(pacientes[i].nombre);
} while (strlen(pacientes[i].nombre)==0);
printf(«nIntroduzca su tel�fono (o 0 o cualquier letra para no introducir m�s datos)nt»);
do {
gets(buffer);
} while (strlen(buffer)==0);
pacientes[i].telefono=atof(buffer);
if (pacientes[i].telefono==0) {
*tamano=i;
break;
}
printf(«nIntroduzca la direccion (no m�s de %d caracteres)nt»,TAM_DIR-1);
do {
gets(pacientes[i].direccion);
} while (strlen(pacientes[i].direccion)==0);
printf(«nIntroduzca la descripcion de la alergias (no m�s de %d caracteres)n»,TAM_ALE-1);
printf(«n****Escriba «NO» si el paciente no tiene ninguna alergia****nt»);
do {
gets(pacientes[i].alergias);
} while (strlen(pacientes[i].alergias)==0);
}
return;
}
char menu()
{
char respuesta;
printf(«nnnntMENU DEL PROGRAMA»);
printf(«n1.- Imprimir en la pantalla toda la informacion»);
printf(«n2.- Listar los pacientes con alergias»);
printf(«n3.- Crear una lista de los pacientes con el telefono 91-XXXXXXX»);
printf(«n4.- Crear una lista nueva de pacientes»);
printf(«n0.- Salir del programa.n»);
do {
respuesta=getch();
} while (respuesta<‘0′ || respuesta>’9’);
return respuesta;
}
void imprimirtodos(reg_paciente *pacientes, int tamano)
{
int i,contimpresos=0;
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
if (tamano>0) {
for (i=0;i<tamano;i++) {
printf(«ntÛÛ%5dt%20stt%9.0ftÛÛ»,i+1,pacientes[i].nombre,pacientes[i].telefono);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].direccion);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].alergias);
contimpresos++;/*CUENTA EL NUMERO DE LOS QUE SE VAN IMPRIMENDO*/
if ((contimpresos)%10==0) {
printf(«ntÛÛ *** Presione cualquier tecla para continuar. *** ÛÛ»);
getch();
}
}
}
if (contimpresos==0) printf(«nÛÛt No hay ningun dato que mostrar en la pantalla.t ÛÛ»);
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
return;
}
void telefono91(reg_paciente *pacientes, int tamano)
{
int i,contimpresos=0;
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
if (tamano>0) {
for (i=0;i<tamano;i++) {
if (pacientes[i].telefono>=910000000 && pacientes[i].telefono<920000000) {
printf(«ntÛÛ%5dt%20stt%9.0ftÛÛ»,i+1,pacientes[i].nombre,pacientes[i].telefono);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].direccion);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].alergias);
contimpresos++;/*CUENTA EL NUMERO DE LOS QUE SE VAN IMPRIMENDO*/
if ((contimpresos)%10==0) {
printf(«ntÛÛ *** Presione cualquier tecla para continuar. *** ÛÛ»);
getch();
}
}
}
}
if (contimpresos==0) printf(«nÛÛt No hay ningun dato que mostrar en la pantalla.t ÛÛ»);
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
return;
}
void hayalergias(reg_paciente *pacientes, int tamano)
{
int i,contimpresos=0;
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
if (tamano>0) {
for (i=0;i<tamano;i++) {
if (strcmp(pacientes[i].alergias,»NO»)!=0 && strcmp(pacientes[i].alergias,»no»)!=0 && strcmp(pacientes[i].alergias,»No»)!=0) {
printf(«ntÛÛ%5dt%20stt%9.0ftÛÛ»,i+1,pacientes[i].nombre,pacientes[i].telefono);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].direccion);
printf(«ntÛÛt%40stÛÛ»,pacientes[i].alergias);
contimpresos++;/*CUENTA EL NUMERO DE LOS QUE SE VAN IMPRIMENDO*/
if ((contimpresos)%10==0) {
printf(«ntÛÛ *** Presione cualquier tecla para continuar. *** ÛÛ»);
getch();
}
}
}
}
if (contimpresos==0) printf(«nÛÛt No hay ningun dato que mostrar en la pantalla.t ÛÛ»);
printf(«ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ»);
return;
}
(tomado de «Practicas de C» /*Fernando Mu�oz Ledesma .Practica 10.Ejercicio 3*/
Le recuerdo al lector que, el uso del do…while, en programaci�n estructurada, est� prohibido, sin embargo, he decidido, no modificar este ejemplo, pues por respeto al escritor y si decid� colocarlo como ejemoplo es por que considero que es un buen c�digo, muy bien desarrollado, adem�s que, para el lector podr�a ser un reto, el pasarlo a estructurado.
Uniones
Hemos visto que las estructuras toman una parte de la memoria y se la reparten entre sus miembros. Cada miembro tiene reservado un espacio para �l solo. El tama�o total que ocupa una estructura en memoria es la suma del tama�o que ocupa cada uno de sus miembros.
Las uniones tienen un aspecto similar en cuanto a c�mo se definen, pero tienen una diferencia fundamental con respecto a las estructuras: los miembros comparten el mismo trozo de memoria. El espacio que ocupa en memoria una uni�n es el espacio que ocupa el campo m�s grande. Para entenderlo mejor vamos a ver un ejemplo:
Primero vamos a ver c�mo se define una uni�n:
union nombre_de_la_union
{
miembros de la union;
};
El tama�o de la uni�n corresponde, a la variable de mayor tama�o, por ejemplo, si en una uni�n tenemos una variable tipo int (2 bytes), uno de tipo float (4 bytes) y un arreglo de 10 elementos (10 bytes), entonces el tama�o de la uni�n ser� de 10 bytes.
Ejemplo 9.5
Dise�e un programa que lea el nombre y la inicial de una persona y luego lo imprima:
#include <stdio.h>
#include <conio.h>
union _persona
{
char nombre[10];
char inicial;
} pers;
main()
{
printf(«Escribe tu nombre: «);
gets(pers.nombre);
printf(«nTu nombre es: %sn», pers.nombre);
printf(«Tu inicial es: %cn», pers.inicial);
getch();
return 0;
}
(Tomado de «Curso C», por Gorka Urrutia. www.elrincondelc.com)
Cuestionario
- �C�mo se define una esructura?________________________________________________________________________________________________________________________________________
- �Cu�l es la diferencia entre una declaraci�n y una definici�n de la estructura?__________________________________________________________________________________________________________________________________________________________
- �C�mo se determina el tama�o de una estructura? �y el de una uni�n?_______________________________________________________________________________________________________________________________________________________________
- �En que se diferencia una estructura de una uni�n?_______________________________________________________________________________________________________________________________________________________________
- �Para que sirve el typedef?_____________________________________________________________________________________________________________________________________________________________
Las siguientes l�neas de c�digo presentan errores, puedes identificarlas y corregirlos:
1. Struct nombre
{
char nom[10];
apellido[10];
int edad[2];
}
2. struct nombre[10];
3. struct nombre *ptr;
ptr=&b;
printf(«El nombre es %sn», ptr.nom);
Ejercicios
- Dise�e un programa que lea e imprima una la fecha del sistema. Declare la fecha como una estructura.
- Defina una estructura que contenga los elementos de un n�mero racional (numerador y denominador), y permira sumar, restar, multiplicar y dividir, dos n�meros racionales.
- En una tienda de perfumes, se desea crear un programa que controle las facturas de las ventas, dichas facturas deben contener los siguientes datos: n�mero correlativo, nombre del cliente, unidades solicitadas, monto total, estado (morosos, atrasados, pagado). El sistema debe generar el listado de los morosos as� como tambi�n el total de clientes atrasados y en monto por los pagos de los clientes.
- un punto en el plano cartesiano, necesita �nicamente una coordenada «x» y otra «Y», definir un programa que muestre:
-la distancia entre los dos puntos (D=sqrt((x2-x1)^2+(y2-y1)^2))
-La ecuaci�n general del plano
-el punto medio entre los dos puntos (Xm=(x1+x2)/2; Ym=(y1+y2)/2).
- Se desea controlar los registros de personas que tienen seguros de auto, casa y de vida, escriba un programa en C, que permita leer los datos indicados y luego los muestre en pantalla, indicando, lo siguiente:
-cantidad de personas que poseen m�s de un seguro
-cantidad de personas que poseen seguro de vida
-la n�mina de las personas que tienen un seguro mayor a una cantidad ingresada por el usuario
Cap�tulo X: Tipos Abstractos de Datos (TAD�s) y Pilas
Dentro de las tantas ventajas que ofrece C, encontramos la potente herramienta de crear nuestros propios tipos de datos, es decir que C, no nos restringe al uso de los tipos de datos que ta trae definidos, sino que el programador, puede ir creando sus propios tipos para hacer las solucines m�s f�ciles, al proceso anterior es al que se le denomina implementaci�n de TAD�s (Tipo Abstracto de Datos)
Abstracci�n
Es la capacidad de manejar un objeto, (tema o idea) como un concepto general sin considerar la enorme cantidad de detallesque pueden estar asociados con dicho objetoel proceso de abstracci�n presenta dos aspectos importantes:
- Destacar los aspectos relevantes
- Ignorar aspectos irrelevantes.
La abtracci�n de datos es la t�cnica que permite inventar o definir nuevos tipos de datos (tipos de datos definidos por el usuario), adecuados a la aplicaci�n que se desea realizar.
Tipos Abstractos de Datos (TAD):
Es un conjunto de valores y un grupo de operadores que trabajan sobre tales valores.
Ejemplo:
Si tenemos los n�meros d�gitos (1, 2, 3,…,9) y los operadores (+, -, *,/), podremos sumar, restar, multiplicar, dividir esos valores.
Un programa, se compone almenos un TAD m�s un algoritmo de control
(PROGRAMA= TAD + ALGORITMO DE CONTROL)
Ventajas de los TAD�s
- Mejora la comprensi�n y la presentaci�n de los programas
- Permite gran riqueza conceptual en nuetros programas
- Para los sistemas tipificados, optimiza el tiempo de compilaci�n
- Permite la modificaci�n de los mismos sin afectar la interfaz al usuario
- Un TAD, lo podemos volver a usar, siempre y cuando lo hayamos creado en archivo de tipo cabecera (*.h), el cual podemos invocar desde cualquier otro programa.
- Se mantienen casi intactas, las peculiaridades del tipo definido.
TAD en C
Las caracter�sticas del lenguaje C que va a permitir la implementaci�n de un TAD son principalmente, las estructuras o registros para representaci�n de los datos , y las funciones para representar las operaciones especificadas. Adem�s en un archivo de inclusi�n o cabecera se guarda la representaci�n de los datos y el interfaz, prototipos de funciones, etc.
Ejemplo:
Se desea especificar el un TAD que manipule n�meros complejos (los n�meros cmplejos est�n compuestos por una parte real y otra imaginaria a+bi)
.tupedef struct
{
float a;
int b;
}complejo;
La anterior declaraci�n puede hacerse en un archvo .h, y en programa principal, debe esp�cificarse esa inclusi�n de la siguiente manera:
#include «nuevotad.h»
y con ello, ya podemos hacer uso de nuestro TAD, haciendo declaraciones como la siguiente:
complejo p1;
C�digo
/*archivo camplejo.h*/
typedef struct
{
float a;
int b;
}complejo;
/*archivo complejo.c*/
#include <stdio.h>
#include <conio.h>
#include «complejo.h»
main()
{
complejo p, q,r;
clrscr();
p.a=5.6;
q.a=6.5;
p.b=3;
q.b=8;
r.a=p.a+q.a;
r.b=p.b+q.b;
printf(«El n�emero complejo es %.1f + %din», r.a, r.b);
getch();
return 0;
}
Explicaci�n
El lector debe comprender la importanci, de lo que acabamos de hacer, y es que con la declaraci�n anterior, en cualquier otro de nuestros programas deseamos usar el tipo de dato, complejo, lo �nico que debemos hacer es incluir la cabecera complejo. H�que definimos en un archivo .h, algunos escritores, indican que en este tipo de archivos (.h), podemos declarar las funciones que vamos a usar en nuetro programa, lo cual, no est� errado, sino que; personalmente considero que, para mantener de una manera fidedigna, el concepto de TAD, debemos �nicamente declararlo en el archivo *.h.
Tambi�n hay que apuntar que la cabecvera complejo.h, se distingue de las dem�s por que va entre comillas («») y no entre signos (<>), y es que, si una cabecera va entre signos mayor y menor que, le estamos indicando al compilador que lo busque en la carpeta de los includes (por lo menos para turbo C), pero si va entre comillas(«»), es como decirle al compilador que busque el archivo *.h en la misma carpeta en la que est� guardado el archivo *.c que estamos compilando.
Lo siguiente de lo que hablaremos es, en sencia, la m�dula central de �sta segunda parte del curso, por tanto, si para el lector, no han quedado claros algunos conceptos de punteros, estructuras, etc; le recomiendo que vuelva a leer los cap�tulos correspondientes, ya que de lo contrario, le ser� un poco dif�cil la comprensi�n de lo que sigue, puesto que, continuamos con: La Gesti�n de Memoria Din�mica.
Para ello, iniciremos hablando de una estrictura muy importante como lo son las:
Pilas y sus Aplicaciones
Una pila es un tipo especial de estructura de datos en la que s�lo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como «push» y «pop», respectivamente «empujar» y «tirar». Adem�s, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo le�do.
Estas caracter�sticas implican un comportamiento de lista LIFO (Last In First Out), el �ltimo en entrar es el primero en salir.
El s�mil del que deriva el nombre de la estructura es una pila de platos. S�lo es posible a�adir platos en la parte superior de la pila, y s�lo pueden tomarse del mismo extremo. Tambi�n una rimera de libros, en la que no se puede acceder a un determinado libro, sino se mueven primero los libros que est�n encima de �l.
Las pilas se pueden implementar de dos formas:
->Como Arreglos
->Usando Memoria Din�mica.
Operaciones con Pilas
push-> Se utiliza para introducir elementos, �sta funci�n necesita como argumento a la pila y el elemento a introducir.
pop-> se utiliza para sacar elementos de la pila, Como argumentos, necesita, unicamente a la pila.
Hemos llenado nuestra pila, llamada «s», con los valores que le insicamos en la funci�n push.
Ahora si queremos sacar el elemento del tope, basta indicar con la siguiente sentencia:
Pop(s);
Pop(s);
Y la pila quedar�a:
Se debe tener en cuenta que, dentro de las funciones pop y push, puden estar otras funciones inmersas, por ejemplo, si queremos introducir m�s datos, debemos tener otra funci�n que verifique si la pila, no est� llena. Por el contrario si queremos sacar datos, debemos sersiorarnos que la pila no est� vac�a, es ah� donde nacen estas otras funciones que deben estar presentes en nuestros programas:
->empty, que verifica si la pila est� vac�a
->stacktop->retorna el elemento superior de la pila.
Representaci�n de Pilas usando arreglos
Para �sta abstracci�n consideraremos que nuestra pila, est� compuesta por un arreglo de n elementos y una variable que controla el sub�ndice de la cima de la pila.
De declaraci�n puede ser la siguiente:
Typedef struct {
char elementos[100];
int top;
}Pila;
donde Pila, es el nombre de nuestra estructura.
Elementos, es el arreglo que contendr� 100 caracteres
Y top, es la variable, que ser� inicializada a �1, y que aumentar� (o disminuir�) a medida que se agreguen (o eliminen) datos.
Por ejemplo:
s.top=-1; /*inicializamos la pila*/
push(&s, x);
s.top++; /*ahora top vale 0*/
push (&s, y);
s.top++; /*top vale 1*/
push(&s, k);
s.top++; /*ahora top vale 2*/
pop(&s);
s.top– /*s.top=1*/
claro que �ste aumento (o decremento) debe hacerse dentro de la funci�n push (o pop), seg�n corresponda.
Muchas veces un programa puede llevar otras funciones, pero digamos que eso ya es valor agregado por parte del programador, las funciones m�s importantes son pop y push, y son esas las que vamos a describir a continuaci�n:
Algoritmo de la funci�n push (para arreglos)
- Verificar si la pila no est� llena
- incrementar en 1 el puntero �ndice de la pila
- almacenar el elemento en la posici�n del puntero de la pila
Algoritomo de la funci�n pop (para arreglos)
- si la pila est� vac�a imprimir un mensaje
- sino est� vac�a, leer el elemento de la posici�n del puntero de la pila
- decrementar en uno el puntero de la pila.
Ejemplo 10.2
Se desea guardar un aproximado de 100 n�meros enteros en una estructura tipo pila, la cual permita a�adir elementos, sacar los elemtos e imprimir los datos contenidos en la pila.
/*pila en forma de arreglo*/
#include <stdio.h>
#include <conio.h>
/*declaracion de la pila*/
typedef struct{
int datos[100];
int top;
}Pila;
/*declaracion de las funciones*/
void push(Pila *ps, int x); /*Introduce un elemento a la pila*/
int top (Pila *ps); /*elimina y muestra un elemento de la pila*/
int empty (Pila *ps);
/*Programa Pincipal*/
main()
{
Pila pila; /*definicion de la variable pila*/
int x, opc=5, i, k=0;
pila.top=-1;
clrscr();
while(opc!=4)
{
printf(«ttt MENU PRINCIPALnnn»);
printf(«t1. Introducir datosn»);
printf(«t2. Sacar datosn»);
printf(«t3.Imprimir la pilan»);
printf(«t4.Salirn»);
scanf(«%d», &opc);
switch(opc)
{
case 1: if(pila.top==99)
printf(«ERROR, pila llenaan»);
else
{
printf(«Ingrese el daton»);
scanf(«%d», &x);
push(&pila, x);
k++;
}
break;
case 2: printf(«El elemento sacado es %dnn», pop(&pila));
k–;
getch();
break;
case 3: if(pila.top>=0)
{
printf(«Los elementos de la pila son:n»);
for(i=0; i<k; i++)
printf(«%d->», pila.datos[i]);
getch();
}
else
printf(«No hay datos en la pilaan»);
break;
}
clrscr();
}
printf(«Fin del programann»);
getch();
return 0;
}
/*funcin que agregaun dato a la pila*/
void push (Pila *ps, int x)
{
ps->datos[++(ps->top)]=x;
}
/*funcin que elimina y devuelve un elemento de la pila*/
int pop(Pila *ps)
{
int r=NULL;
if(empty(ps)==1)
printf(«No hay elementos para sacaran»);
else
r=ps->datos[(ps->top)–];
return r;
}
/*funcion que verifica si la pila esta vac�a*/
int empty (Pila *ps)
{
int r;
if(ps->top==-1)
r=1;
else
r=0;
return r;
}
Explicaci�n
El programa enterio, muestra, en forma sencilla, el uso de las pilas, en forma est�tica, (usando arreglos), con funciones muy sencillas como pop, push y empty, pero el lector debe recordar que �l puede modificar, crear otras funciones (o estas mismas) seg�n sea el problema que se est� resolviendo. Para el caso, en este ejemplo, he usado sintaxis como la siguiente:
r=ps->datos[(ps->top)–];
lo cual, podr�a haberse hecho en m�s pasos, de la siguiente forma:
i=ps->top–;
r=ps->datos[i];
y as� sucesivamente, por tanto se debe encasillar a que la sintaxis anterior es la �nica soluci�n viable a �ste problema. Las instrucciones pueden cambiar, pero lo que debe permanecer siempre invariable, es el algoritmo correspondiente a las funciones anteriores (pop y push).
Tambi�n el lector se preguntar�, el por que hemos usado una variable auxiliar, identificada como k. Pues bien la respuesta es muy simple, esta variable sirve para controlar el n�mero de impresiones que se har�n en la funci�n pertinente es por ello que esa variable crece (en la funci�n push) y decrece (en la funci�n pop).
Pilas Implementadas con Memoria Din�mica
Las pilas, que hasta ahora hemos tratado, han sido usando �nicamente memoria est�tica, es decir definimos ciertos espacios, dentro de los cuales guardamos nuestros datos. Pero, que pasar�a, si los datos superan el espacio reservado en memoria para ellos?.
Es aqu� donde surge, la importancia que la pila crezca y decrezca din�micamente, donde el �nico l�mite existente es la memoria misma de la pc.
La forma de declararlo es la siguiente:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Pila es el tipo para declarar pilas.
As� que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas.
Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el �ltimo elemento de la pila.
Las operaciones b�sicas siguen siendo las mismas, aunque claro con sus respectivas variantes:
-push, para igresar nuevos valores en la pila
-pop, para eliminar lementos de la pila
Funci�n push (para memoria din�mica)
- Supondremos que ya se cre� un nodo nuevo (hablaremos de eso despu�s), si la pila est� vac�a, es decir el puntero que apunta a la pila, est� apuntando a NULL.
- lo que debemos hacer es que, nodo en su parte de siguiente, apunte a NULL
- Y el puntero que apunta a la pila, apunte ahora al nuevo nodo.
Un nodo, est� compuesto del dato (que puede ser entero, real, car�cter u otra estructura) y un puntero, que enlazar� �ste nodo con el siguiente.
El puntero Pila, apunta a la cima de la pila, cuando no hay datos est� inicializada a NULL.
Si la pila, no est� vac�a (es decir hay elementos):
creamos un nuevo nodopara el valor que colocaremos en la pila
- hacemos que nodo, en su parte de siguiente, apunte a pila
- hacemos que pila, apunte a nodo.
Funci�n Pop
Partiremos del supuesto que exiten m�s de un nodo en la pila, el algoritmo, ser�a el siguiente:
- Hacemos que nodo, apunte al primer elemento de la pila
- asignamos a pilala direcci�n del segundo elemento de la pila
- guardamos el contenido del nodo para devolverlo posteriormente
- liberamos la memoria del nodo que queremos eliminar.
(NOTA: las im�genes anteriores han sido tomadas de http://www.conclase.net/c/edd/index.php?cap=002b).
Si por ejemplo, tenemos s�lo un nodo, el proceso ser� parecido, s�lo que pila, apuntar�a ahora a nodo->siguiente, que ser�a NULL.
Funci�n push
void push(Pila *pila, int v)
{
pNodo *nuevo;
nuevo=(pNodo)malloc(sizeof(tiponodo));
nuevo->valor=v;
nuevo->siguiente=*pila;
*pila=nuevo;
}
en la funci�n anterior, observamos que, no devuelve ning�n valor, que recibe como argumentos, la direcci�n de la pila y el valor (entero, en �ste caso) que vamos a guardar en la pila.
Posteriomente, declara un nuevo puntero que tendr� la direcci�n del nodo que vamos a crear.
nuevo=(pNodo)malloc(sizeof(tiponodo))
quiz�, la l�nea anterior es una de las m�s potentes e interesantes que podemos encontrar y es que con esa l�nea le estamos diciendo al compilador que vamos a crear un nuevo nodo, del tama�o de tiponodo, para ello usamos la instrucci�n malloc, que sive para pedirle al sistema memoria, sizeof, lo que hace es determinar el tama�o (en bytes), de la variable que le pasamos como argumento y ese valor, es lo que malloc le pide al sistema, y como �ste devuelve un puntero del tipo void, por eso es necesario hacer el casting: (pNodo)malloc.
Funci�n Pop:
int pop (Pila *pila)
{
pNodo nuevo;
int v;
nodo=*pila;
if(!nodo)
*pila=nodo->siguiente;
v=nodo->valor;
free(nodo);
return (v);
}
Note que �sta funci�n lo �nico que recibe es el puntero a la pila. La funci�n free(), sirve para liberar ese espacio de memoria.
Ejemplo 10.3
C�digo completo para el uso de las pilas
#include <stdio.h>
#include <conio.h>
typedef struct nodo{
int valor;
struct nodo *siguiente;
}tiponodo;
typedef tiponodo *pNodo;
typedef tiponodo *Pila;
void push(Pila *pila, int v);
int pop(Pila *pila);
main()
{
Pila pila=NULL;
push(&pila, 20);
push(&pila, 30);
push(&pila, 40);
printf(«%d», pop(&pila));
printf»%d», pop(&pila));
getch();
return 0;
}
void push(Pila *pila, int v)
{
pNodo *nuevo;
nuevo=(pNodo)malloc(sizeof(tiponodo));
nuevo->valor=v;
nuevo->siguiente=*pila;
*pila=nuevo;
}
int pop (Pila *pila)
{
pNodo nuevo;
int v;
nodo=*pila;
if(!nodo)
*pila=nodo->siguiente;
v=nodo->valor;
free(nodo);
return (v);
}
Explicaci�n.
La salida, de �ste programa no es muy atractiva, pero hagamos un esfuerzo por comprenser que es lo que hemos hecho.
Y aunque lo que veamos en pantalla, son s�lo unos n�meros, que a lo mejor al principio, no tengamos ni idea de donde aparecieron, (igual que yo, la primera vez), debemos estar seguros que �ste programita cumple con todas las especificaciones de una pila.
Por ejemplo, las invocaciones de push, mandamos a la pila, los valores de 20, 30, 40. de los cuales el n�mero 40, es el que se encuentra en la cima de la pila, por eso, al llamar a pop, manda a impresi�n el n�mero 40. ahora quien est� en la cima es 30, y al volver a invocar a pop, es ese valor el que se imprime. El lector puede modificar este programa colocando otros valores en push, agregando m�s llamadas a pop, etc.
A pesar que el programa anterior es muy apropiado para exponer el funcionamiento de las pilas, hasta cierto punto, est� incompleto, ya que no interact�a mucho que digamos con el usuario.
Por ello mostramos a continucaci�n otro c�digo que es un poco m�s completo.
En el cual no pasamos par�metros a las funciones, por que las variables son de tipo global, �ste es un m�todo, para hacer las cosas un poco m�s f�ciles.
Ejemplo 10.4
Se desean guadar en una pila, cierta cantidad de nombres, a la vez que el usuario puede eliminar e imprimir el estado de la pila, seg�n lo desee. Dise�e un programa en C, que de soporte a dicho problema, usando pilas implementadas con memoria din�mica.
/* Ejemplo de una pila. */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>
void push(void);
void pop(void);
void visualizar(void);
struct pila
{
char nombre[20];
struct pila *ant;
}*CAB=NULL,*AUX=NULL;
main( )/* Rellenar, extraer y visualizar */
{
char opc=8;
while(opc!=4)
{
clrscr( ); /* borramos la pantalla */
printf(«tt1.- Insertarn»);
printf(«tt2.- Extraern»);
printf(«tt3.- Visualizar la pilan»);
printf(«tt4.- Salirnn»);
opc=getch( );
switch(opc)
{
case ‘1’:
push( );
break;
case ‘2’:
pop( );
break;
case ‘3’:
visualizar( );
}
}
getch();
}
void push(void)
{
AUX=(struct pila *)malloc(sizeof(struct pila));
clrscr( );
printf(«Nombre: «);
gets(AUX->nombre);
if (CAB==NULL)
{
CAB=AUX;
AUX->ant=NULL;
}
else
{
AUX->ant=CAB;
CAB=AUX;
}
}
void pop(void)
{
if (CAB==NULL) return;
AUX=CAB;
CAB=CAB->ant;
free(AUX);
}
void visualizar(void)
{
if (CAB==NULL) return;
clrscr( );
AUX=CAB;
while (AUX!=NULL)
{
printf(«Nombre: %sn»,AUX->nombre);
AUX=AUX->ant;
}
getch( );
}
Explicaci�n
�ste ejemplo es un poco m�s completo, ya que le permite al usuario, interactuar, al poder ingresar los datos c�mo �l los desee, adem�s que, note, que en las funciones (push, pop e insertar) no mandamos par�metros. Ya que �stos son declarados fuera del main(), por tanto se pueden acceder a ellas, por cualquier funci�n dentro del programa. Lo cual puede ser muy �til, cuando estamos trabajando, por ejemplo, con cadenas de caracteres, como en �ste caso.
Evaluciones de Expresiones
Las expresiones aritm�ticas que hasta ahora hemos usado, las encontramos en forma infija, es decir usando (), *,/,-,+…
Ejemplo:
X=z+(b+c)^(q-m)-(b*c)
A la expresi�n anterior tambi�n algunos autores la llaman, interfija. Sin embargo las expresiones tienen otras formas de poderlas representar, por ejemplo: la notaci�n posfija o tambi�n conocida como polaca inversa (en honor al matem�tico de origen polaco, que la propuso), y �sta consiste en colocar el operador a continuaci�n de los operandos. Por ejemplo:
A*b/(c-d) /*infija*/
A*b/c-d /*quitamos par�ntesis*/
Ab*/cd-/*signo delante de operador*/
Ab*cd-/ /*posfija*/
Otro ejemplo:
A+(B*C)
A+B*C
A+BC*
ABC*+
Ahora bien, lo anterior podr�a parecer bastante complejo, y ciertamente lo es, por lo cuala continuaci�n mostramos el algoritmo para pasar una expresi�n de infija a posfija:
- leer la cadena de caracteres, y repetir el paso 2 al 4 por cada car�cter
- si es un operando, pasarlo a expresi�n posfija
- si es un operador:
- si la pila est� vac�a, meterlo en la pila. Repetir desde 1
- si la pila no est� vac�a:
-si la prioridad del operador le�do es mayor que la prioridad del operador cima de la pila, meterlo en la pila y repetir dede 1
-si la prioridad del operador es menor o igual que la prioridad del operador de la cima de la pila, sacar operador cima de la pila y pasarlo a la expresi�n posfija, volver a 3
- si es par�ntesis derecho:
- sacar operador cima de la pila y pasarlo a la expresi�n posfija
- si nueva cima es par�ntesis izquierdo suprimir elemento cima
- si cima no es par�ntesis izquierdo, volver a 4.1
- volver a partir de 1
- si quedan elementos en la pila pasarlos a la expresi�n posfija
- fin del algoritmo
(Algoritmo tomado de: «Algoritmos y estructuras de datos, una perspectiva en C». Joyanes Aguilar, Luis. Madris 2004. P�g. 329)
el c�digo ser�a el siguiente:
Ejemplo 10.5
#include<stdio.h>
#include<string.h>
#define n 60
/* *********** Prototipo de funciones de pila **************** */
void push(struct pila *p, struct operador num);//meter datos a la pila
int full(struct pila *p); //devuelve 1 si la pila esta llena
void clear(struct pila *p); //limpia la pila
struct operador pop(struct pila *p); //elimina el dato de la cima y lo devuelve
struct operador ver(struct pila *p); //devuelve el dato de la cima sin eliminarlo
int empty(struct pila *p); //devuelve 1 si la pila esta vacia
void tranformacion( char expin[n], char *expos,struct pila *p); //transforma de infija a posfija
int infija(char expin[n]); //devuelve 1 si la expresion infija es valida
struct operador asignacion(char i); //devuelve la prioridad de los operadores
void marco(); //funcion adicional para el marco
void error(); /*describe las posibles causas de error en la introduccion
de la expresion infija*/
/* ***************** Declaracion de la pila ***************** */
struct operador{
int prioridad;
char caracter;
} ;
struct pila{
int tope;
struct operador vect[n];
} ;
/* ********************** Programa Principal************************* */
void main(void)
{
char expin[n],expos[n];/* expin contiene la expresion infija
expos contiene la expresion posfija */
int s;
struct pila pila1; //creacion de la pila
clrscr();
clear(&pila1); //inicializacion de la pila
marco();
printf(«Introduzca una expresion en notacion infija n»);
scanf(«%s»,expin); //introduccion de la expresion infija
clrscr();
tranformacion( expin,expos,&pila1);
getch();
clrscr();
marco();
printf(«-.Si desea introducir otra expresion presione 1n»);
printf(«-.Otro numero para salir.n»);
scanf(«%i»,&s);
if(s==1)
main();
}
/* *****funciones de ordenamiento de expresion infija a postfija ******** */
void tranformacion( char expin[n], char expos[n], struct pila *p)
{
struct operador auxiliar; /* auxiliar se utiliza para introducir operadores
a la pila*/
struct operador comparador;/* comparador se utiliza para contener el valor
de la cima de la pila */
int i,j,bandera; /* i y j son variables de cambio , bandera permite
sacar los operadores de apertura de la pila y
operadores de menor prioridad al que se introducira*/
if( infija(expin)== 1) //1.si expresion infija es valida
{
for(i=0,j=-1 ;i<=(strlen(expin)-1);i++)//1.evaluacion caracter por caracter
{
// 2. si es caracter lo copiara en la expresion posfija
if (((expin[i]>=65 )&&(expin[i]<=90)) || ((expin[i]>=97 )&&
(expin[i]<=122)))
{
j+=1;
expos[j]=expin[i];
}//cierra 2
else
{ //3 . si es operador de cierre derecho
if( (expin[i]==’}’ )||(expin[i]==’]’ )||(expin[i]==’)’ ))
{
bandera=1;
do{
auxiliar=pop(p); //quite la cima de la pila
j+=1;
expos[j]=auxiliar.caracter;/* agregar el operador quitado
a la expresion posfija */
comparador=ver(p); //comparador contiene lo que hay en la cima
if(comparador.prioridad==0)//si la cima de la pila es operador de apertura
{
auxiliar=pop(p); //quitar operador de apertura
bandera=1;
}
else
bandera=0; //si cima de la pila es operador regrese a 3
}while(bandera==0);
} //cierra 3
else // 4 si es operador de apertura o +,/,*,-,^
{
bandera=1;
do{
auxiliar=asignacion(expin[i]); //asignacion prioridad a operadores
if (empty(p)==1) // si la pila esta vacia operador entra a la pila
{
if(auxiliar.prioridad==6)// si es operador de apretura
auxiliar.prioridad=0; // en la pila su prioridad es 0
push(p,auxiliar);
bandera=1;
}
else{ // comparando prioridad de operadores del tope y el entrante
comparador=ver(p);
//comparador tiene el valor de la cima
if(auxiliar.prioridad > comparador.prioridad)
{ if(auxiliar.prioridad==6) //si es operador de apertura
auxiliar.prioridad=0; //en la pila su prioridad es 0
push(p,auxiliar);
bandera=1;
}
else
{ //si operado entrante es menor o igula que el de la pila
auxiliar=pop(p);//sacar operandor de la cima de la pila 4
j+=1;
expos[j]=auxiliar.caracter; //agregarlo a expresion posfija
bandera=0; //volver a evaluar evaluar operador entrante regreso a
}
}
}while(bandera==0);
}//cierra 4
}
}//cierra 1
while(empty(p)!=1)//sacar todos los operadores sobrantes en pila
{
auxiliar=pop(p);
j+=1;
expos[j]=auxiliar.caracter;
}
//impresion de resultado
marco();
printf(«nnLA EXPRESION EN NOTACION INFIJA ES :n «);
printf(«%s»,expin);
printf(«nnLA EXPRESION EN NOTACION POSFIJA ES :n»);
for(i=0;i<=j;i++) {
printf(«%c»,expos[i]);}
} //cierre de expresion infija valida
else{ //expresion infija no valida
marco();
printf(«nnaLA EXPRESION INFIJA ES ERRONEA:»);
error();
}
}//cierra funcion transformacion
//funcion que asigna la prioridad de los operadores
struct operador asignacion(char i)
{
struct operador auxiliar;
switch(i){ //asignacion de prioridades
case ‘^’: auxiliar.prioridad=5;
auxiliar.caracter=’^’;
break;
case ‘*’: auxiliar.prioridad=4;
auxiliar.caracter=’*’;
break;
case ‘/’: auxiliar.prioridad=3 ;
auxiliar.caracter=’/’;
break;
case ‘+’: auxiliar.prioridad=2 ;
auxiliar.caracter=’+’;
break;
case ‘-‘: auxiliar.prioridad=1 ;
auxiliar.caracter=’-‘;
break;
case ‘(‘: auxiliar.prioridad=6;
auxiliar.caracter=''(‘;
break;
case ‘[‘: auxiliar.prioridad=6 ;
auxiliar.caracter=''[‘;
break;
case ‘{‘: auxiliar.prioridad=6 ;
auxiliar.caracter=''{‘;
break; }
return auxiliar;
}
/* ************ funcion de validacion de la expresion *********************/
int infija (char expin[n])
{
int i,numero[3],parentesis,bandera=1;
//evaluacion: operando operador operando
for(i=1;i<=(strlen(expin)-2);i++)
{
if((expin[i]==’+’)||(expin[i]==’-‘)||(expin[i]==’*’)||
(expin[i]==’/’)||(expin[i]==’^’))
{
if(!(((expin[i+1]>=65 )&&(expin[i+1]<=91)) || ((expin[i+1]>=97 )&&
(expin[i+1]<=123)) ||(expin[i+1]==40) || (expin[i+1]==41 )||
(expin[i+1]==93) || (expin[i+1]==125 ) ))
bandera=0;
if(!(((expin[i-1]>=65 )&&(expin[i-1]<=91)) || ((expin[i-1]>=97 )&&
(expin[i-1]<=123)) ||(expin[i-1]==40) || (expin[i-1]==41 )||
(expin[i-1]==93) || (expin[i-1]==125 ) ))
bandera=0;
};
}
//evaluacion:no deben haberdos operandos juntos
for(i=0;i<=(strlen(expin)-2);i++)
{
if (((expin[i]>=65 )&&(expin[i]<=90)) || ((expin[i]>=97 )&&
(expin[i]<=122)))
{
if (((expin[i+1]>=65 )&&(expin[i+1]<=91)) || ((expin[i+1]>=97 )&&
(expin[i+1]<=123)) || (expin[i+1]==40 ))
bandera=0;
if (((expin[i-1]>=65 )&&(expin[i-1]<=90)) || ((expin[i-1]>=97 )&&
(expin[i-1]<=122)) || (expin[i-1]==41 )||
(expin[i-1]==93) || (expin[i-1]==125 ))
bandera=0;
}
}
// evaluacion: la expresion no comience con operador
if((expin[0]==’+’)||(expin[0]==’-‘)||(expin[0]==’*’)||(expin[0]==’/’)||
(expin[0]==’^’))
bandera=0;
// evaluacion: la expresion no termine con operador
if((expin[strlen(expin)-1]==’+’)||(expin[strlen(expin)-1]==’-‘)||
(expin[strlen(expin)-1]==’*’)||(expin[strlen(expin)-1]==’/’)||
(expin[strlen(expin)-1]==’^’))
bandera=0;
//evaluacion: despues de un simbolo de apertura no debe haber operador
for(i=0;i<=(strlen(expin)-2);i++)
{
if((expin[i]==''(‘)||(expin[i]==''{‘)||(expin[i]==''[‘))
if ((expin[i+1]==’+’)||(expin[i+1]==’-‘)||(expin[i+1]==’*’)||
(expin[i+1]==’/’)||(expin[i]==’^’))
bandera=0;
};
//evaluacion: antes de un simbolo de cierre no debe haber operador
for(i=1;i<=(strlen(expin)-1);i++)
{
if((expin[i]==’)’)||(expin[i]==’}’)||(expin[i]==’]’))
if ((expin[i-1]==’+’)||(expin[i-1]==’-‘)||(expin[i-1]==’*’)||
(expin[i-1]==’/’)||(expin[i-1]==’^’))
bandera=0;
}
//evaluacion de los parentesis
parentesis=0; //suma final=0, evita (}, (],[}
for(i=0;i<=2;i++)
numero[i]=0; // evita {) ,{],[)
for(i=0;i<=(strlen(expin)-1);i++)
{
switch(expin[i])
{
case ‘(‘:parentesis+=1;
numero[0]+=1;
break;
case ‘[‘:parentesis+=2;
numero[1]+= 2;
break;
case ‘{‘:parentesis+=3;
numero[2]+=3;
break;
case ‘)’:parentesis-=1;
numero[0]-=1;
if(parentesis<0) bandera=0;
break;
case ‘]’:parentesis-=2;
numero[1]-=2;
if(parentesis<0) bandera=0;
break;
case ‘}’:parentesis-=3;
numero[2]-=3;
if(parentesis<0) bandera=0;
break;
}
}
if(parentesis!=0) // si la suma de los parentesis es <> 0 existe error
bandera=0;
for(i=0;i<=2;i++) // debe haber un numero igual operadores
{if(numero[i]!=0) // de cierre y apetura por cada tipo
bandera=0;}
return bandera;
}//terminacion de funci�n validaci�n expresi�n
/* ************************* funciones de la pila ******************* */
int full (struct pila *p) //funcion full devuelve 1 si la pila esta llena
{
if (p->tope==4)
return 1;
else
return 0;
}
void push(struct pila *p,struct operador num)//funcion push encargada de
{ //introducir datos a la pila
if(full(p)==1)
printf(«pila llena»);
else
{
p->tope++,
p->vect[(p->tope)]=num;
}
}
void clear(struct pila *p)//funcion clear encargada de limpia la pila
{
p->tope=-1;
}
int empty(struct pila *p)// funcion empty devulve 1 si la pila esta vacia
{
if (p->tope==-1)
return 1;
else
return 0;
}
struct operador pop(struct pila *p) //funcion pop quita el dato que
{ //se encuntre en la cima de la pila
struct operador auxiliar;
if (empty(p)==1)
{
auxiliar.caracter=’0′;
}
else
{
auxiliar= p->vect[p->tope];
p->tope–;
};
return auxiliar;
};
struct operador ver(struct pila *p) // funcion ver devuelve el dato
{ // que esta en la cima de la pila
struct operador auxiliar; // sin removerlo
auxiliar= p->vect[p->tope];
return auxiliar;
};
/* ***************** funcione adicional ******************** */
void marco()
{
int i;
for (i=1;i<=79;i++)
{
printf(«*»);
printf(«*»);
}
printf(«nPROGRAMA QUE CALCULA UNA EXPRESION EN NOTACION POSFIJAnnn»);
}
void error()
{
printf(«Posibles razones:n»);
printf(«1-hay dos operadores juntosn»);
printf(«2-hay dos operandos juntosn»);
printf(«3-la expresion comienza con operadorn»);
printf(«4-la expresion termina con operadorn»);
printf(«5-hay un operador luego de ( ,[ o{ n»);
printf(«6-hay un operador antes de ),] o }n»);
printf(«7-Existe un error en los parentesisn»);
}
NOTA: el c�digo anterior fue elaborado por : Nelson Eduardo Najarro Alvarez, para la Asignatura de Programaci�n II, de la Carrera de Ingenier�a de Sistemas Inform�ticos de la Universidad de El Salvador.
El ejemplo anterior es baste complejo y muy largo, pero decid� colocarlo, por que en muchos libros s�lo colocan las funciones o trozos del c�digo, pero como aqu� queremos hacer las cosas bien, hemos decidido colocar el c�digo completo.
Adem�s que en muchas universidades o colegios, dejan como tarea �ste c�digo, as� creo que te servir� mucho.
Cuestionario
- �Qu� es un TAD?_____________________________________________________________________________________________________________________________________________
- �Cu�l es la importancia del TAD?___________________________________________________________________________________________
- �Para que se usan las pilas?__________________________________________________________________________________________________________________________________________
- �C�mo funcionan las pilas?__________________________________________________________________________________________________________________________________________
- Mencione y explique las implementaciones de Pilas en C:______________________________________________________________________________________________
En las siguientes funciones, descubre donde hay errores, identif�calos y corr�gelos.
1. void push ( ptrNodoPila *ptrCima, int info )
{
ptrNodoPila ptrNuevo; /* apuntador al nuevo nodo */
ptrNuevo = malloc( sizeof( NodoPila ) );
/* inserta el nodo en la cima de la pila */
if ( ptrNuevo != NULL ) {
ptrNuevo->dato = dato;
ptrNuevo->ptrSiguiente = *ptrCima;
*ptrCima = ptrNodoPila;
} /* fin de if */
else { /* no queda espacio disponible */
printf( «%d no se inserto. Memoria insuficiente.n», info );
} /* fin de else */
} /* fin de la funci�n empujar */
2. /* Elimina un nodo de la cima de la pila */
int pop( ptrNodoPila *ptrCima )
{
ptrNodoPila ptrTemp; /* apuntador a un nodo temporal */
ptrTemp = *ptrCima;
valorElim = ( *ptrCima )->dato;
*ptrCima = ( *ptrCima )->ptrSiguiente;
free( ptrCima);
return valorElim;
} /* fin de la funci�n sacar */
Ejercicios
- Un vector en f�sica, puede representarse mediante sus componentes x, y, z; de la siguiente forma: V=2i + 4j �6k. Cuando una de las componente est� ausente, simplemente no se escribe (o la podemos representar con un cero: V= 0i + 4j + 6k.) Cree un TAD que lea un vector y luego calcule:
-Su magnitud (||V||=sqrt(a^2+b^2+c^2)). Donde a,b y son los coeficientes
-Su vector unitario: U=a/||V|| + b/||V|| + c/||V||
- los n�meros radicalesse componen de una base y un signo radical, dise�e un programa que sea capaz de implementar un TAD llamado radical y permita:
-sumarlos, restarlos o dividirlos; seg�n lo desee el usuario.
- Dis�e un TAD que represente un tipo cadena (string), y que permita las siguientes operaciones: leer la cadena, imprimirla, copiarla, determinar el tama�o de la cadena y buscar un car�cter espec�fico en la cadena.
- se desea transformar un n�mero base10, a binario; utilizando una pila, en la cual se guarden los residuos de las divisiones. A partir de las impresiones generadas por la pila, muestre el n�mero binario equivalente.
- A partir de un p�rrafo ingresado por el usuario, dise�e un programa que, determine el n�mero de consonantes y vocales que est�n presentes en dicho p�rrafo.
- Dise�e un programa que lea una cadena de caracteres y luego la imprima en forma inversa
- Se desea crear una pila en c, que lea cierta cantidad de n�meros enteros y luego muestre:
-La suma de todos los n�meros y el producto de ellos, cu�ntos son mayores que cero.
- una palabra es polindromo si se lee igual por la derecha que por la izquierda, dise�e un programa que lea una palabra, luego imprim esa misma palabra al rev�s y con un mensaje indique si es o no pal�ndromo.
- En una tienda de repuestos llevan su control de inventarios, mediante el sistema UEPS (�ltimos en entrar, primeros en salir), el cual puede ser controlado mediante una estructura del tipo Pila; en �sta tiendo necesitan que se registren sus productos, los cuales tendr�n los siguientes datos: c�digo, descripci�n, precio unitario, fecha de ingreso (del sistema). Adem�s de registrar las �rdenes de salida y mostrar los siguientes reportes: ventas por fecha, ventas por producto (ingresando el c�digo), cantidad de productos que exceden un precio determinado. El cual ser� ingresado por el usuario.
| P�gina siguiente |