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:
- Dise�e un programa que lea e imprima una la fecha del sistema.
-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:
- Se desea controlar los registros de personas que tienen seguros de auto,
-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.
- Supondremos que ya se cre� un nodo nuevo (hablaremos de eso despu�s),
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 est� vac�a, meterlo en la pila. Repetir desde
- 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:
- Un vector en f�sica, puede representarse mediante sus componentes
-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:
- los n�meros radicalesse componen de una base y un signo radical,
-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:
- se desea transformar un n�mero base10, a binario; utilizando una
-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.
- una palabra es polindromo si se lee igual por la derecha que por la izquierda,
 P�gina anterior | Volver al principio del trabajo | P�gina siguiente  |