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