Tabla de Contenidos

!

" #

#

$ %

&

ndice de Listados $'!&

$('!!(

$'!) (

$' !*

$"' !!*

$&'!+

$*'!(

1. Introduccin

! "#$

%#

& % ! $ " '$

(

# & )*

!"#

# &%+!

,--. "#

-%

! " % -

#

&$-$

#

2. Pilas *)

+%#&/0!/-0"#1

2

2#

, 3!*

" %!/0"#& 3

%#

2.1 Funciones asociadas a las pilas %,

#&%(

push(/%+#

pop( 4 * %+ #

*

- - -

$#5

,#& % %push$pop-$#

1%push62*!',"#1*%pop 62 ! * *"# 7

%,(

push(A) A push(B) AB pop() A B push(C) AC push(D) ACD pop() AC D pop() A C pop() A

2.2 Soporte para la implementacin de una pila 1$ ' - %-

$%#

3$3#

2.2.1 Uso de listas

1 3 3 -

%!push",3(

1#

/#

%*!pop",3(

8

&*#

9#

2.2.2 Uso de tablas

1 3 , -

' ,(3

+#

&+3(

- base- 3 3 # & +% #

7+, cima ,#&+%#

:+,#

%+,3%pop$push%(

&

/ push(A) push(B) pop()

9

, ; ; ;

;,+%-$

%, 3 , *- dimension#,

(base + dimension) == cima &-,=3

LIFO!/0"--'$

2.4 Ejercicio con tablas 53!4:"

% #,--

$!+---*$/"$ #&4:-?*%

(7 - 3) * (2 + 1)

4:(

7 3 2 1 + *

' 3=#

,#

&-$3%(

,$'

@fA ,-$ 3 #

1#

1-*!

,"-$#

, MAXELE ! 10" , pila# 5 3 !0,"#,int$+, *#&+

;3%coge_op-=+(

7

% push , %# &%0'3-$1#>,#

%pop*#&%%-0 ' 3- $1 # > *,

C

Listado 2: Fichero pila.h #ifndef PILA_H #define PILA_H

int push(int i); int pop(int *f);

#endif

Listado 3: Fichero makefile # # Macros #

COMPILADOR = gcc OBJETO = pila.o cogeOp.o calc.o CABECERA = pila.h cogeOp.h OPCIONES = -Wall -c EJECUTABLE = calculadora

# # Construccion del ejecutable #

$(EJECUTABLE): $(OBJETO) $(CABECERA) $(COMPILADOR) -o $(EJECUTABLE) $(OBJETO) pila.o: pila.c $(CABECERA) $(COMPILADOR) $(OPCIONES) pila.c cogeOp.o: cogeOp.c $(CABECERA) $(COMPILADOR) $(OPCIONES) cogeOp.c calc.o: calc.c $(CABECERA) $(COMPILADOR) $(OPCIONES) calc.c

D

Listado 4: fichero cogeOp.c #include #include /*para usar isspace e isdigit*/ #include cogeOp.h

int coge_op(int *pnum) { /*Funcion que lee un elemento de la entrada*/ int c; int num;

do { c = getchar(); }while (isspace(c) && c!= '\n');

if (isdigit(c)) { num = 0;

do{ num = num *10 + c - '0'; c = getchar(); } while(isdigit(c));

*pnum = num;

if (c!=f) ungetc(c,stdin); c = '0'; }

return c; }

Listado 5: fichero cogeOp.h #ifndef COGEOP_H #define COGEOP_H

int coge_op(int *pnum);

#endif

E

Listado 6: Fichero calc.c #include #include "pila.h" /*para usar push y pop */ #include "cogeOp.h"

int main() { int op1; int op2; int tipo; /*Clase de operador u operando*/ int numero; /*Valor del operando */

while (f != (tipo = coge_op(&numero))) { switch(tipo) { case '0': if (push(numero)) printf("pila llena\n"); break; case '+': if (pop(&op1) || pop(&op2)) printf("No hay suficientes operandos\n"); else push(op2 + op1); break; case '-': if (pop(&op1) || pop(&op2)) printf("No hay suficientes operandos\n"); else push(op2 - op1); break; case '*':

if (pop(&op1) || pop(&op2)) printf("No hay suficientes operandos\n"); else push(op2 * op1); break; case '/': if (pop(&op1) || pop(&op2)) printf("No hay suficientes operandos\n"); else if (op1 == 0) printf("Error: division por cero\n"); else push(op2 / op1); break; case '\n': if (pop(&op1)) printf("Pila vacia\n"); else { printf("Resultado: %d\n", op1); push(op1); } break; default: printf("Error: token %c no reconocido\n", tipo); break; } } return 0; }

2.5 Ejercicio con listas 4 3 3 ,#

,p06/pilaConListas$=%'calc.c-pila.h-cogeOp.c$cogeOp.h #1 ,= %'!listas.h-listas.c-###"#

F%%'%'pila.c3#

F%,=%'makefile ,#

3. Colas /0!/-0"#1

-6

2#

+% - -(

-$*#&1-

3%#

3.1 Funciones asociadas a las colas

% ,

#&%(

alm(#

rec(*#&-%

-=#

&%%alm$rec(

1%alm62*#1*%rec

!GG"#, %alm$rec(

alm(A) A alm(B) AB rec() B A alm(C) BC alm(D) BCD rec() CD B rec() D C rec() D

3.2 Soporte para la implementacin de las colas ; -

%- $ %

#H-,$

3#

3.2.1 Listas enlazadas.

1 3 3 -

%!alm",3(

1#

/

8

1,-+(

apos == rpos

& % % - , apos %,#;-,+-

$'$,#&-apos'

,=(

apos == rpos

$+#&,

%-3

( '$( '$

aposrpos?-apos$' ,-rpos+#/#1apos,-?rpos,-(

apos(

apos = (apos + 1) % dimension; if (0 == apos) // Hemos dado la vuelta indicador = 1;

rpos(

rpos = (rpos + 1) % dimension; if (0 == rpos) // Hemos dado la vuelta indicador = 0;

&-,+rpos3apos(

(rpos == apos) && (indicador == 0) $apos3rpos(

alm(E)(

alm(G)(

apos

rpos apos

rpos

rpos

apos

rpos

apos

Sit. inicial:

alm(F)(

apos

rpos rpos

apos

rpos apos

apos

rpos

(rpos == apos) && (indicador == 1)

3.3 Ejercicio 1p06/colas#1' %' gcolas.c- , p06/colas #

1%'colas.c-colas.h$makefile ,'#7,#

C

Listado 7: Fichero gcolas.c /* fichero: gcolas.c utiliza: colas.h colas.c

comentarios: demo de trabajo con colas

*/

#include #include

#include "colas.h"

int main() { int i; /* auxiliar: seleccion menu*/ int dato;

do { printf("\nGESTION DE COLAS BASICA"); printf("\n========================"); printf("\nElija opcion:\n"); printf("\t 0: Salir\n"); printf("\t 1: Insertar un elemento\n"); printf("\t 2: Recuperar un elemento\n"); printf("\n \t\t Opcion: ");

scanf("%d", &i);

switch (i) { case 0: break; case 1: printf(Valor a insertar: ); scanf(%d, &valor); if (0 != alm(valor)) printf(La cola est llena\n); break; case 2: if (0 == rec(&valor)) printf(El valor recuperado es %d\n, valor); else printf(La cola est vaca\n); break; } } while (0 != i);

return 0; }