tp_ejemplo/pila_c.pas

   1 unit pila_C;\r
   2 \r
   3 \r
   4 \r
   5 {\r
   6 \r
   7         IMPLEMENTACION : pilas\r
   8 \r
   9         ALMACENAMIENTO : CURSORES\r
  10 \r
  11         MODIFICADO PARA QUE COMPILE, y un par de errores que tenia (estan marcados)\r
  12 \r
  13 }\r
  14 \r
  15 \r
  16 \r
  17 { ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular }\r
  18 \r
  19 interface\r
  20 \r
  21 \r
  22 \r
  23 { usa las funciones generales de TDAs }\r
  24 \r
  25 uses tda_gral;\r
  26 \r
  27 \r
  28 \r
  29 { maximo tamano del cursor }\r
  30 \r
  31 const PILAC_MAX_CURSOR = 100;\r
  32 \r
  33 \r
  34 \r
  35 { tipos propios de la lista para definir el cursor }\r
  36 \r
  37 TYPE\r
  38 \r
  39         PILAC_puntero = integer;\r
  40 \r
  41 \r
  42 \r
  43 const\r
  44 \r
  45    PILAC_nulo : PILAC_puntero = 0;\r
  46 \r
  47 \r
  48 \r
  49 type\r
  50 \r
  51 \r
  52 \r
  53         PILAC_nodo = RECORD\r
  54 \r
  55                 Elem : Tipo_Elem;\r
  56 \r
  57                 Sig : PILAC_puntero;\r
  58 \r
  59         END;\r
  60 \r
  61 \r
  62 \r
  63 \r
  64 \r
  65    { ahora le toca definir el cursor }\r
  66 \r
  67    PILAC_Almac = record\r
  68 \r
  69       almacenamiento : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Nodo;\r
  70 \r
  71       siguientes     : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Puntero;\r
  72 \r
  73       primero_dispo  : PILAC_puntero;\r
  74 \r
  75    end;\r
  76 \r
  77 \r
  78 \r
  79 \r
  80 \r
  81    PILAC_Pila = RECORD\r
  82 \r
  83                 almac : PILAC_Almac;\r
  84 \r
  85                 primero: PILAC_puntero;\r
  86 \r
  87         END;\r
  88 \r
  89 \r
  90 \r
  91 \r
  92 \r
  93 { ========= }\r
  94 \r
  95 { INTERFASE }\r
  96 \r
  97 \r
  98 \r
  99 \r
 100 \r
 101 PROCEDURE PILAC_Inicializar ( VAR l: PILAC_Pila );\r
 102 \r
 103 FUNCTION  PILAC_vacio( l: PILAC_Pila): BOOLEAN;\r
 104 \r
 105 FUNCTION  PILAC_lleno( l: PILAC_Pila): BOOLEAN;\r
 106 \r
 107 \r
 108 \r
 109 PROCEDURE PILAC_poner ( VAR l: PILAC_Pila; VAR e: Tipo_Elem );\r
 110 \r
 111 PROCEDURE PILAC_sacar ( VAR l: PILAC_Pila; VAR e: Tipo_Elem);\r
 112 \r
 113 PROCEDURE PILAC_vaciar ( VAR l: PILAC_Pila );\r
 114 \r
 115 PROCEDURE PILAC_copiar ( a: PILAC_Pila; VAR b: PILAC_Pila );\r
 116 \r
 117 \r
 118 \r
 119 implementation\r
 120 \r
 121 \r
 122 \r
 123 { CURSORES DE ESTA IMPLEMENTACION }\r
 124 \r
 125 { ========================================================================== }\r
 126 \r
 127 {  inicializar el almacenamiento }\r
 128 \r
 129 { PRE : 'almac' no esta inicializado  }\r
 130 \r
 131 { POST: 'almac' esta inicializado y vacio }\r
 132 \r
 133 procedure PILAC_Almac_Inicializar( VAR almac : PILAC_Almac );\r
 134 \r
 135 var i : PILAC_Puntero;\r
 136 \r
 137 begin\r
 138 \r
 139    almac.primero_dispo := 1;\r
 140 \r
 141    for i := 1 to PILAC_MAX_CURSOR - 1 do\r
 142 \r
 143    begin\r
 144 \r
 145       almac.siguientes[i] := i + 1;\r
 146 \r
 147    end;\r
 148 \r
 149    almac.siguientes[PILAC_MAX_CURSOR] := PILAC_Nulo;\r
 150 \r
 151 end;\r
 152 \r
 153 \r
 154 \r
 155 { ========================================================================== }\r
 156 \r
 157 {  saber si hay lugar para reservar un nuevo elemento en el almacenamiento }\r
 158 \r
 159 { PRE : 'almac' esta inicializado  }\r
 160 \r
 161 { POST: si hay lugar en 'almac' para un nuevo elemento,\r
 162 \r
 163             entonces retorna TRUE y sino FALSE }\r
 164 {ANDABA AL REVES, CORREGIDO}\r
 165 \r
 166 \r
 167 function PILAC_Almac_HayLugar( almac : PILAC_Almac ): boolean;\r
 168 \r
 169 begin\r
 170 \r
 171    PILAC_Almac_HayLugar := NOT (almac.primero_dispo = PILAC_Nulo);\r
 172 \r
 173 end;\r
 174 \r
 175 \r
 176 \r
 177 { ========================================================================== }\r
 178 \r
 179 {  el pedido de un nuevo elemento al almacenamiento }\r
 180 \r
 181 { PRE : 'almac' esta inicializado  }\r
 182 \r
 183 { POST: si hay lugar en 'almac' para un nuevo elemento,\r
 184 \r
 185             entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento\r
 186 \r
 187             sino 'puntero' tiene el valor TTDA_Nulo }\r
 188 \r
 189 procedure PILAC_Almac_Reservar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero );\r
 190 \r
 191 begin\r
 192 \r
 193    if not PILAC_Almac_HayLugar( almac )\r
 194 \r
 195    then\r
 196 \r
 197       puntero := PILAC_Nulo\r
 198 \r
 199    else begin\r
 200 \r
 201       puntero := almac.primero_dispo;\r
 202 \r
 203       almac.primero_dispo := almac.siguientes[ puntero ];\r
 204 \r
 205    end;\r
 206 \r
 207 end;\r
 208 \r
 209 \r
 210 \r
 211 { ========================================================================== }\r
 212 \r
 213 {  liberar un elemento del almacenamiento }\r
 214 \r
 215 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r
 216 \r
 217 { POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo }\r
 218 \r
 219 procedure PILAC_Almac_Liberar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero );\r
 220 \r
 221 begin\r
 222 \r
 223    almac.siguientes[ puntero ] := almac.primero_dispo;\r
 224 \r
 225    almac.primero_dispo := puntero;\r
 226 \r
 227    puntero := PILAC_Nulo;\r
 228 \r
 229 end;\r
 230 \r
 231 \r
 232 \r
 233 { ========================================================================== }\r
 234 \r
 235 {  acceder al elemento del almacenamiento apuntado por un puntero }\r
 236 \r
 237 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r
 238 \r
 239 { POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' }\r
 240 \r
 241 procedure PILAC_Almac_Acceder( almac : PilaC_Almac; puntero : PILAC_Puntero; VAR elemento : PILAC_Nodo );\r
 242 \r
 243 begin\r
 244 \r
 245    elemento := almac.almacenamiento[ puntero ];\r
 246 \r
 247 end;\r
 248 \r
 249 \r
 250 \r
 251 { ========================================================================== }\r
 252 \r
 253 {  modificar el elemento del almacenamiento apuntado por un puntero }\r
 254 \r
 255 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento }\r
 256 \r
 257 { POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' }\r
 258 \r
 259 procedure PILAC_Almac_Modificar( VAR almac : PILAC_Almac; puntero : PILAC_Puntero; elemento : PILAC_Nodo );\r
 260 \r
 261 begin\r
 262 \r
 263    almac.almacenamiento[ puntero ] := elemento;\r
 264 \r
 265 end;\r
 266 \r
 267 \r
 268 \r
 269 \r
 270 \r
 271 \r
 272 \r
 273 { Estas son los dos procedimientos principales de la aplicación }\r
 274 \r
 275 \r
 276 \r
 277 PROCEDURE PILAC_Inicializar ( VAR l: PILAC_Pila );\r
 278 \r
 279 BEGIN\r
 280 \r
 281    PILAC_Almac_Inicializar( l.almac );\r
 282 \r
 283    l.primero := PILAC_Nulo;\r
 284 \r
 285 END;\r
 286 \r
 287 \r
 288 \r
 289 FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN;\r
 290 \r
 291 BEGIN\r
 292 \r
 293         PILAC_vacio := ( l.Primero = PILAC_Nulo);\r
 294 \r
 295 END;\r
 296 \r
 297 \r
 298 \r
 299 FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN;\r
 300 \r
 301 BEGIN\r
 302 \r
 303         PILAC_lleno := not PILAC_Almac_HayLugar( l.almac );\r
 304 \r
 305 END;\r
 306 \r
 307 \r
 308 \r
 309 PROCEDURE PILAC_poner ( VAR l: PILAC_Pila; var e: Tipo_Elem);\r
 310 \r
 311 VAR\r
 312 \r
 313    n : PILAC_Nodo;\r
 314 \r
 315    np: PILAC_Puntero;\r
 316 \r
 317 BEGIN\r
 318 \r
 319         n.Elem := e;\r
 320 \r
 321    n.sig := l.primero;\r
 322 \r
 323         PILAC_Almac_Reservar( l.almac, np );\r
 324 \r
 325    PILAC_Almac_Modificar( l.almac, np, n );\r
 326 \r
 327    l.primero := np;\r
 328 \r
 329 END;\r
 330 \r
 331 \r
 332 \r
 333 { pre: no esta vacia }\r
 334 \r
 335 PROCEDURE PILAC_sacar ( VAR l: PILAC_Pila; VAR e: Tipo_Elem);\r
 336 \r
 337 VAR n : PILAC_Nodo;\r
 338 \r
 339     tmp : PILAC_Nodo;\r
 340 \r
 341     tmpp: PILAC_Puntero;\r
 342 \r
 343 BEGIN\r
 344 \r
 345    PILAC_Almac_Acceder( l.almac, l.primero, n );\r
 346 \r
 347    PILAC_Almac_Liberar( l.almac, l.primero );\r
 348 \r
 349    l.primero := n.Sig;\r
 350 \r
 351 \r
 352 \r
 353    { y se lo asigno al parametro }\r
 354 \r
 355    e := n.Elem;\r
 356 \r
 357 END;\r
 358 \r
 359 \r
 360 \r
 361 PROCEDURE PILAC_vaciar ( VAR l: PILAC_Pila );\r
 362 \r
 363 VAR np : PILAC_Puntero;\r
 364 \r
 365     n : PILAC_Nodo;\r
 366 \r
 367 BEGIN\r
 368 \r
 369    np := l.primero;\r
 370 \r
 371    while( np <> PILAC_Nulo ) do begin\r
 372 \r
 373       PILAC_Almac_Acceder( l.almac, np, n );\r
 374 \r
 375       PILAC_Almac_Liberar( l.almac, np );\r
 376 \r
 377       np := n.sig;\r
 378 \r
 379       end;\r
 380 \r
 381    l.primero := PILAC_Nulo;\r
 382 \r
 383 END;\r
 384 \r
 385 \r
 386 \r
 387 { pre: 'a' y 'b' estan creadas y 'b' esta vacia }\r
 388 \r
 389 { POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero }\r
 390 \r
 391 PROCEDURE PILAC_copiar ( a : PILAC_Pila; VAR b : PILAC_Pila );\r
 392 \r
 393 VAR np, mp, tmpp : PILAC_Puntero;\r
 394 \r
 395     n,m : PILAC_Nodo;\r
 396 \r
 397 BEGIN\r
 398 \r
 399    if a.primero = PILAC_Nulo then exit;\r
 400 \r
 401    np := a.primero;\r
 402 \r
 403    PILAC_Almac_Acceder( a.almac, np, n );\r
 404 \r
 405 \r
 406 \r
 407    PILAC_Almac_Reservar( b.almac, mp );\r
 408 \r
 409    b.primero := mp;\r
 410 \r
 411    m.elem := n.elem;\r
 412 \r
 413 \r
 414 \r
 415    while( n.sig <> PILAC_Nulo ) do begin\r
 416 \r
 417 \r
 418 \r
 419       PILAC_Almac_Reservar( b.almac, tmpp );\r
 420 \r
 421       m.sig := tmpp;\r
 422 \r
 423       PILAC_Almac_Modificar( b.almac, mp, m );\r
 424 \r
 425 \r
 426 \r
 427       np := n.sig;\r
 428 \r
 429       PILAC_Almac_Acceder( a.almac, np, n );\r
 430 \r
 431 \r
 432 \r
 433       mp := tmpp;\r
 434 \r
 435       m.elem := n.elem;\r
 436 \r
 437 \r
 438 \r
 439       end;\r
 440 \r
 441    m.sig := PILAC_Nulo;\r
 442 \r
 443    PILAC_Almac_Modificar( b.almac, mp, m );\r
 444 \r
 445 END;\r
 446 \r
 447 \r
 448 \r
 449 end.\r
 450 \r