lunes, 5 de diciembre de 2016

Programación del Sinclair QL (XVII): Estructuras de Datos. Listas enlazadas



Las listas enlazadas son las estructuras mas útiles, ya que sirven para casi todo. La estructura en sencilla, un registro se divide en dos partes, una con los datos que se necesitan guardar, y otro con un enlace al siguiente registro de datos. De esta manera no es necesario que los registros estén en posiciones consecutivas.

No voy a explicar mucho mas de las listas, hay suficiente información en la Web sobre ellas, presento un pequeño esquema de lo que es una lista enlazada, y las operaciones básicas de inserción de elementos en ellas:


Las listas pueden estar ordenadas por el criterio que se desee, en este caso yo voy a usar el mantener la lista en orden creciente de sus datos, así me sirve como rutina de ordenación, pero esto no es imprescindible y se pueden usar listas ordenadas con el criterio que se desee, por ejemplo para construir una cola se emplea una lista en la que se introducen elementos por el principio de la misma y se extraen por el final (o al contrario)

Para hacerlo sencillo en nuestro SuperBASIC usaré en esta ocasión arreglos para implementar nuestra lista, ya mas adelante hablaremos del manejo de la memoria. Voy a usar dos arreglos para almacenar los datos, en uno me guardo los datos del registro (en este caso será una lista de números, pero puede ser cambiado de manera sencilla a una lista de cadenas por ejemplo), y otro arreglo numérico con los enlaces, que inicio con un valor que indica que el nodo está vacío, así es muy sencillo encontrar elementos libres conforme crece el tamaño de la lista y se han ido añadiendo y retirando elementos. Esta técnica no es la mas eficiente, pero si sencilla. Además, hay unas variables auxiliares para guardar la cabecera entre otras cosas.

1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Lista encadenada ordenada                  --
1030 REMark --   Objetivo..: Lista encadenada usando un arreglo de dos  --
1040 REMark --               dimensiones: 0 elementos, 1 punteros       --
1050 REMark --   Autor.....: javu61, 11/2016                            --
1060 REMark --   Procesos..:                                            --
1070 REMark --     LISTA_CREAR      -- Crear la lista                   --
1080 REMark --     LISTA_NUEVA(tam) -- Crea la lista con un tama‰o      --
1090 REMark --     b=LISTA_LEN      -- Nro de elementos de la lista     --
1100 REMark --     LISTA_ADD(dato)  -- Introduce un dato en la lista    --
1110 REMark --     LISTA_DELETE(n)  -- Borra el elemento n de la lista  --
1120 REMark --     v=LISTA_VER(n)   -- Muestra elemento n de la lista   --
1130 REMark --     b=LISTA_BUSCAR(n)-- Busca un elemento en la lista    --
1140 REMark --     LISTA_CAMBIA(tam)-- Cambia el tama‰o de la lista     --
1150 REMark --   Procesos de uso interno:                               --
1160 REMark --     LISTA_INIT       -- Inicializa una lista             --
1170 REMark --     b=LISTA_EL_LIBRE -- Retorna elemento libre           --
1180 REMark --   Elementos.: Se usan los siguientes elementos globales  --
1190 REMark --     L_FACTOR        -- Factor de crecimiento             --
1200 REMark --     ArrLista(tam)   -- Elementos de la lista             --
1210 REMark --     ArrPuntero(tam) -- Puntero al siguiente elemento     --
1220 REMark --     L_NULO          -- Puntero nulo                      --
1230 REMark --     L_VACIO         -- Puntero vacio                     --
1240 REMark --     L_RAIZ          -- Puntero al nodo raiz              --
1250 REMark --     L_NRO           -- Nro de elementos de la lista      --
1260 REMark --------------------------------------------------------------
1270 :
1280 :
1290 REMark --------------------------------------------------------------
1300 REMark -- LISTA_CREAR -- Crea la lista                             --
1310 REMark --------------------------------------------------------------
1320 DEFine PROCedure LISTA_CREAR
1330   LISTA_NUEVA 9,5 : REMark Espacio para 10 elementos, crece minimo 5
1340 END DEFine 
1350 :
1360 REMark --------------------------------------------------------------
1370 REMark -- LISTA_NUEVA(tam,fac) -- Crea la lista con un tama‰o y un --
1380 REMark --                         factor de crecimiento            --
1390 REMark --------------------------------------------------------------
1400 DEFine PROCedure LISTA_NUEVA(tam,fac)
1410   LET L_FACTOR = fac  : REMark Factor de crecimiento
1420   DIM ArrLista(tam)   : REMark Elementos de la lista
1430   DIM ArrPuntero(tam) : REMark Puntero al siguiente elemento
1440   LISTA_INIT
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- LISTA_INIT -- Inicializa una lista                       --
1490 REMark --------------------------------------------------------------
1500 DEFine PROCedure LISTA_INIT
1510   LOCal i
1520   :
1530   LET L_NULO  = -1     : REMark Puntero nulo
1540   LET L_VACIO = -2     : REMark Puntero vacio
1550   L_RAIZ      = L_NULO : REMark Puntero al nodo raiz
1560   L_NRO       = 0      : REMark Nro de elementos de la lista
1570   :
1580   REMark Inicializa lista de elementos libres
1590   FOR i=0 TO DIMN(ArrPuntero)
1600     ArrPuntero(i) = L_VACIO : REMark elemento vacio
1610   END FOR i
1620 END DEFine 
1630 :
1640 REMark --------------------------------------------------------------
1650 REMark -- b = LISTA_LEN -- Retorna el nro de elementos de la lista --
1660 REMark -- RETORNA: 0 si vacia, >0 = nro de elementos               --
1670 REMark --------------------------------------------------------------
1680 DEFine FuNction LISTA_LEN
1690   RETurn L_NRO
1700 END DEFine 
1710 :
1720 REMark --------------------------------------------------------------
1730 REMark -- b = LISTA_EL_LIBRE -- Retorna elemento libre de la lista --
1740 REMark -- RETORNA:  <0 no hay libres, >=0 nro del elemento         --
1750 REMark --------------------------------------------------------------
1760 DEFine FuNction LISTA_EL_LIBRE
1770   LOCal i
1780   :
1790   FOR i=0 TO DIMN(ArrPuntero)
1800     IF ArrPuntero(i) = L_VACIO THEN RETurn i
1810   END FOR i
1820   RETurn L_NULO
1830 END DEFine 
1840 :
1850 REMark --------------------------------------------------------------
1860 REMark -- b = LISTA_BUSCAR(valor) -- Busca un elemento en la lista --
1870 REMark -- RETORNA:  nro del elemento o NULO si no encontrado       --
1880 REMark --------------------------------------------------------------
1890 DEFine FuNction LISTA_BUSCAR(valor)
1900   LOCal nro,repetir
1910   :
1920   nro = L_NULO
1930   IF L_NRO THEN 
1940     nro = L_RAIZ
1950     REPeat repetir
1960       IF ArrLista(nro) = valor    THEN EXIT repetir
1970       IF ArrLista(nro) > valor    THEN nro = L_NULO : EXIT repetir
1980       IF ArrPuntero(nro) = L_NULO THEN nro = L_NULO : EXIT repetir
1990       nro = ArrPuntero(nro)
2000     END REPeat repetir
2010   END IF 
2020   RETurn nro
2030 END DEFine 
2040 :
2050 :
2060 REMark --------------------------------------------------------------
2070 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista, si     --
2080 REMark --                    esta llena crece al doble             --
2090 REMark --------------------------------------------------------------
2100 DEFine PROCedure LISTA_ADD(dato)
2110   LOCal repetir,nro,pos,ant
2120   :
2130   REMark Busco nodo libre, crece si hace falta y ubico el elemento
2140   REPeat repetir
2150     nro = LISTA_EL_LIBRE
2160     IF nro <> L_NULO THEN EXIT repetir
2170     LISTA_CAMBIA(DIMN(ArrLista)*2)
2180   END REPeat repetir
2190   ArrLista(nro) = dato
2200   :
2210   REMark Si es el primer nodo, lo ubico en la raiz
2220   IF L_RAIZ = L_NULO THEN 
2230     ArrPuntero(nro) = L_NULO
2240     L_RAIZ = nro
2250   ELSE 
2260     REMark Si no es el primero, buscamos su posici–n recorriendo
2270     pos = L_RAIZ
2280     ant = L_NULO
2290     REPeat repetir
2300       REMark Si he econtrado su posici–n
2310       IF (ArrLista(pos) >= dato) THEN 
2320         REMark Seg™n sea ahora el primer elemento o no
2330         IF ant = L_NULO THEN 
2340           ArrPuntero(nro) = L_RAIZ
2350           L_RAIZ = nro
2360         ELSE 
2370           ArrPuntero(nro) = ArrPuntero(ant)
2380           ArrPuntero(ant) = nro
2390         END IF 
2400         EXIT repetir
2410       END IF 
2420       REMark Si he llegado al final, lo a‰ado como utimo elemento
2430       IF ArrPuntero(pos)=L_NULO THEN 
2440         ArrPuntero(pos) = nro
2450         ArrPuntero(nro) = L_NULO
2460         EXIT repetir
2470       END IF 
2480       ant = pos
2490       pos = ArrPuntero(pos)
2500     END REPeat repetir
2510   END IF 
2520   REMark Sumo un elemento a la lista
2530   L_NRO = L_NRO + 1
2540   :
2550 END DEFine 
2560 :
2570 REMark --------------------------------------------------------------
2580 REMark -- v = LISTA_VER(n) -- Muestra el elemento n de la lista    --
2590 REMark -- RETORNA: Valor del elemento                              --
2600 REMark --------------------------------------------------------------
2610 DEFine FuNction LISTA_VER(nro)
2620   LOCal pos,i
2630   :
2640   IF LISTA_LEN = 0 THEN 
2650     PRINT"Error: Lista vacia"
2660     STOP
2670   END IF 
2680   :
2690   pos = L_RAIZ
2700   FOR i=0 TO nro-1
2710     IF ArrPuntero(pos)=L_NULO THEN 
2720       PRINT "ERROR: No hay tantos elementos"
2730       STOP
2740     END IF 
2750     pos = ArrPuntero(pos)
2760   END FOR i
2770   RETurn ArrLista(pos)
2780 END DEFine 
2790 :
2800 REMark --------------------------------------------------------------
2810 REMark -- LISTA_DELETE(n)  -- Borra el elemento n de la lista      --
2820 REMark --------------------------------------------------------------
2830 DEFine PROCedure LISTA_DELETE(n)
2840   LOCal pos,i
2850   :
2860   IF n < 0 THEN 
2870     PRINT "ERROR: Intenta eliminar elementos negativos"
2880     STOP
2890   END IF 
2900   :
2910   pos = L_RAIZ
2920   ant = L_NULO
2930   FOR i=0 TO n-1
2940     IF ArrPuntero(pos)=L_NULO THEN 
2950       PRINT "ERROR: Intenta eliminar elementos que no existen"
2960       STOP
2970     END IF 
2980     ant = pos
2990     pos = ArrPuntero(pos)
3000   END FOR i
3010   :
3020   IF ant = L_NULO THEN 
3030     L_RAIZ = ArrPuntero(pos)
3040   ELSE 
3050     ArrPuntero(ant)=ArrPuntero(pos)
3060   END IF 
3070   ArrPuntero(pos) = L_VACIO
3080   :: ArrLista(pos)   = 0
3090   :
3100   REMark reducir elementos de la lista
3110   L_NRO = L_NRO - 1
3120 END DEFine 
3130 :
3140 REMark --------------------------------------------------------------
3150 REMark -- LISTA_CAMBIA -- Cambia el tama‰o de la lista             --
3160 REMark --------------------------------------------------------------
3170 DEFine PROCedure LISTA_CAMBIA(tam)
3180   LOCal b(DIMN(ArrLista)),minimo,i,elementos
3190   :
3200   REMark Guardo la lista en el auxiliar de forma compacta
3210   elementos = L_NRO
3220   FOR i=0 TO elementos-1
3230     b(i)=LISTA_VER(i)
3240   END FOR i
3250   :
3260   REMark calculo tama‰os m“nimos
3270   minimo = L_NRO + L_FACTOR
3280   IF tam < minimo   THEN tam = minimo
3290   IF tam < L_FACTOR THEN tam = tam + L_FACTOR
3300   :
3310   REMark Creo la nueva lista y la relleno
3320   LISTA_NUEVA tam,L_FACTOR
3330   :
3340   IF elementos <> 0 THEN 
3350     L_RAIZ = 0
3360     L_NRO  = elementos
3370     FOR i=0 TO elementos-1
3380       ArrLista(i)=b(i)
3390       IF i <> 0 THEN ArrPuntero(i-1) = i
3400       ArrPuntero(i) = L_NULO
3410     END FOR i
3420   END IF 
3430 END DEFine 


Para poder verificar que esta lista enlazada funciona uso un pequeño programa de pruebas, en el se ve siempre la lista y sus enlaces, los punteros nulos, los elementos libres, etc. Tras cada prueba se presentan los elementos que componen la lista, en la que se debe verificar que todos están ordenados.

100 REMark ----------------------------------------
110 REMark -- Manejo de errores                  --
120 REMark ----------------------------------------
130 WHEN ERRor 
140   PRINT "Se ha producido un error ";ERNUM;' en la linea ';ERLIN;" "
150   REPORT #1,ERNUM
160   STOP
170 END WHEN 
180 :
190 MODE 4: PAPER 0 : CLS
200 n$="mdv1_ed_lista_arreglo"
210 PRINT "Cargando ";n$
220 MERGE n$
230 :
240 REMark ----------------------------------------
250 REMark -- Rutinas de pruebas                 --
260 REMark ----------------------------------------
270 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
280 p2$=""
290 t1=DATE
300 :
310 PRINT "Creacion de la lista"
320 LISTA_CREAR : ver : PRINT
330 :
340 PRINT "PRUEBA 1: Introduce elementos en orden, inversos y aleatorios"
350 LISTA_CREAR : FOR i=1 TO 3 : mete(i)
360 verlista
370 LISTA_CREAR : FOR i=3 TO 1 STEP -1 : mete(i)
380 verlista
390 LISTA_CREAR : FOR i=1 TO 5 : mete(RND(1 TO 9))
400 verlista
410 :
420 PRINT "PRUEBA 2: Introduce 9, elimina 5, introduce 3, elimina 4"
430 LISTA_CREAR
440 FOR i=1 TO 9   : mete(i)
450 FOR i=1 TO 5   : borra(0)
460 FOR i=10 TO 12 : mete(i)
470 FOR i=1 TO 3   : borra(i)
480 verlista
490 :
500 PRINT "PRUEBA 3: Introduce 9, Extrae 2, introduce 10 y reduce"
510 LISTA_CREAR
520 FOR i=1 TO 9   : mete(i)
530 FOR i=1 TO 2   : borra(i)
540 FOR i=10 TO 19 : mete(i)
550 verlista
560 PRINT "CM "; : LISTA_CAMBIA 0 : ver
570 verlista
580 :
590 PRINT "PRUEBA 4: Buscar algunos elementos"
600 FOR i= 0 TO 3 STEP 3 : PRINT "BUSCO ";i;" = ";LISTA_BUSCAR(i)
610 PRINT
620 :
630 PRINT "PRUEBA 5: Extrae elementos hasta error por vacia"
640 FOR i=1 TO 17  : borra(0)
650 t2=DATE
660 PRINT "Tard– ";t2-t1;" segundos"
670 borra(0)
680 STOP
690 :
700 DEFine PROCedure mete(a)
710   PRINT "EN ";a;":"; : LISTA_ADD(a) : ver
720 END DEFine 
730 :
740 DEFine PROCedure borra(a)
750   PRINT "BO ";LISTA_VER(a);":"; : LISTA_DELETE(a) : ver
760 END DEFine 
770 :
780 DEFine PROCedure verlista
790   p2$=""
800   FOR xx=0 TO LISTA_LEN-1 :  p2$ = p2$ & LISTA_VER(xx) & ","
810   PRINT "LISTA: ";p2$ : PRINT
820 END DEFine 
830 :
840 DEFine PROCedure ver
850   LOCal xx
860   :
870   IF LISTA_LEN = 0 THEN PRINT "v"; : ELSE PRINT "_";
880   IF L_RAIZ=L_NULO THEN PRINT "*"; : ELSE PRINT L_RAIZ;":";
890   FOR xx=0 TO DIMN(ArrLista)
900     PRINT !"(";xx;")";ArrLista(xx);
910     IF ArrPuntero(xx)=-1 THEN PRINT "*";
920     IF ArrPuntero(xx)=-2 THEN PRINT "v";
930     IF ArrPuntero(xx)>0  THEN PRINT ArrPuntero(xx);
940   END FOR xx
950   PRINT
960 END DEFine 

Como siempre aquí todo lo desarrollado hasta el momento.

No hay comentarios:

Publicar un comentario