lunes, 19 de diciembre de 2016

Traducciones en la Wikipedia

Estas son mis últimas traducciones:

  • La gama de computadores UNIVAC, separado del UNIVAC I a donde redirigía
  • Códigos de caracteres de 6 bits, que fueron muy usados en los UNIVAC y en los DEC por ejemplo, igual que en muchos de los primeros ordenadores.
  • Entrada sobre ordenadores decimales, en general los primeros ordenadores fueron casi todos decimales (con la excepción de los Zuse, el sistema mecánico que empleó en la Z1 para almacenar datos binarios fue una gran idea, y la fuente de sus principales problemas, luego pasó a los relés y se solucionaron) hasta que se impuso el binario.
  • Entrada sobre la empresa Remington Rand
  • Entrada sobre Herman Lukoff y entrada sobre John Grist Brainerd, pioneros poco conocidos de la informática.

viernes, 16 de diciembre de 2016

Programación del Sinclair QL (XX): Estructuras de datos. Presentar el árbol



La presentación de los datos que hacía del árbol no eran muy adecuadas, en las listas se ve mejor pero el árbol cuesta mas de ver presentando en forma lineal los valores de datos y enlaces, por lo que he desarrollado un proceso para ver de manera mas gráfica los árboles, en modo texto, pero queda bastante visible. Hay dos procesos, uno que presenta el árbol que es nuevo, y el que retorna la lista de elementos del árbol en una cadena que he simplificado la visualización.

4890 REMark --------------------------------------------------------------
4900 REMark -- ARBOL_VER_GR -- Presenta en pantalla un arbol            --
4910 REMark --------------------------------------------------------------
4920 DEFine PROCedure ARBOL_VER_GR
4930   LOCal lin,col,a$
4940   :
4950   lin = ARBOL_NIVELES - 1
4960   col = 1 : FOR i=2 TO lin+2 : col = (2 * col)
4970   OPEN#5,con : WINDOW#5, 448,200,32,16
4980   CLS#5 : BORDER#5, 2,2
4990   PRINT#5, "N:";!ARBOL_NIVELES;!"L:";lin;!"C:";col-2,
5000   PRINT #5,ARBOL_ELEMENTOS$
5010   montar 0,col/2-1,col/4,A_RAIZ
5020   INPUT a$
5030   CLOSE#5
5040 END DEFine 
5050 :
5060 DEFine PROCedure montar(l,c,s,nodo)
5070   LOCal i,t
5080   :
5090   IF nodo <> P_NULO THEN 
5100     imprime l+1,c+1, ArrArbol(nodo)
5110     IF ArrDer(nodo) <> P_NULO THEN 
5120       t = c+s+1
5130       FOR i=c+2 TO t-1 : imprime l+1,i,"-"
5140       imprime l+1, t, "\"
5150       imprime l+2, t, "|"
5160     END IF 
5170     IF ArrIzq(nodo) <> P_NULO THEN 
5180       t = c-s+1
5190       FOR i=c TO t+1 STEP -1 : imprime l+1,i,"-"
5200       imprime l+1, t, "/"
5210       imprime l+2, t, "|"
5220     END IF 
5230     montar l+2,c-s,s/2,ArrIzq(nodo)
5240     montar l+2,c+s,s/2,ArrDer(nodo)
5250   END IF 
5260 END DEFine 
5270 :
5280 DEFine PROCedure imprime(l,c,dato$)
5290   IF (l > 0) AND (l < 19) AND (c > 0) AND (c < 73) THEN 
5300     AT#5,l,c : PRINT#5, dato$
5310   END IF 
5320 END DEFine 
5330 :
5340 REMark --------------------------------------------------------------
5350 REMark -- v$ = ARBOL_ELEMENTOS$ -- Muestra la lista de elementos   --
5360 REMark -- RETORNA: Lista ordenada de elementos del arbol           --
5370 REMark --------------------------------------------------------------
5380 DEFine FuNction ARBOL_ELEMENTOS$
5390   LOCal lista$
5400   :
5410   lista$=""
5420   inorden lista$,A_RAIZ
5430   RETurn lista$
5440 END DEFine 
5450 :
5460 DEFine PROCedure inorden(cadena$,nodo)
5470   IF nodo <> P_NULO THEN 
5480     inorden cadena$, ArrIzq(nodo)
5490     IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
5500     cadena$ = cadena$ & ArrArbol(nodo)
5510     inorden cadena$, ArrDer(nodo)
5520   END IF 
5530 END DEFine<0 hay="" libres="" no="">
 
El resultado es el siguiente, no es espectacular pero creo que se ve bien la estructura del árbol, y cuando entremos en los árboles AVL y las rotaciones se verá de forma mas clara como se van moviendo los datos.


Aquí los fuentes de todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

martes, 13 de diciembre de 2016

Programación del Sinclair QL (XIX): Estructura de datos. Arbol binario de Búsqueda



Los arboles son las estructuras mas usadas para almacenar datos, ya que permiten un muy rápido acceso a ellos. La estructura en sencilla, un registro se divide en dos partes, una con los datos que se necesitan guardar y otro con enlaces a los elementos hijos, que será un número mayor o igual a dos.

Ejemplo de arbol (Fuente: Monografias.com)


Si el número máximo de hijos es dos se denominan árboles binarios, y son los mas usados en programación en general, reservando los árboles de mas ramas para uso en ficheros indexados habitualmente. No voy a explicar mucho mas, hay suficiente información en la Web sobre arboles y su manejo.

Existe un tipo especial de árbol binario, en el que en cada nodo de cada rama, los valores de los elementos que cuelgan del nodo izquierdo son todos menores al valor del propio nodo, y los elementos que cuelgan del nodo derecho son todos valores mayores al del propio nodo, de forma que si recorremos el árbol primero la rama izquierda, luego el nodo, y luego la rama derecha, obtenemos una lista de elementos ordenados en orden creciente. Si la recorremos primero la rama derecha, luego el nodo y después la rama izquierda obtenemos la lista ordenada en forma decreciente. Este tipo de árboles se llaman "Árbol Binario de Búsqueda", y es lo que voy a implementar, ya que estamos hablando de algoritmos de ordenación. 

Voy a usar tres 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), otro arreglo numérico con los enlaces a los punteros de la rama izquierda, y un tercer arreglo con los enlaces a la rama derecha. Estos dos arreglos podrían ser uno solo, pero creo que así está un poco mas claro.

Usaré el arreglo de enlaces a nodos izquierdos para almacenar la lista de elementos libres, pero por que sea mas visual haré lo mismo con los derechos. Esto lo cambiaré mas adelante por algo un poco mejor, ya lo veremos. El manejo de los árboles requiere muchos procedimientos recursivos, aunque usaré iterativos cuando sea posible para que se vean varias técnicas de manejo.

Uso una variable para almacenar el nivel máximo de profundidad del árbol, no tiene uso mas que para enseñarlo en pantalla, pero me permite que se vea algo que deseo demostrar luego. No me voy a complicar mucho cuando compacto el árbol, ya que esta parte la voy a cambiar luego, solo lo pongo de momento para que se vea.

2000 REMark --------------------------------------------------------------
2010 REMark -- ESTRUCTURAS DE DATOS                                     --
2020 REMark --   Modulo....: Arbol binario                              --
2030 REMark --   Objetivo..: Arbol binario usando un arreglo de valores --
2040 REMark --               numericos y dos para los punteros          --
2050 REMark --   Autor.....: javu61, 12/2016                            --
2060 REMark --   Procesos..:                                            --
2070 REMark --     ARBOL_CREAR      -- Crear el arbol                   --
2080 REMark --     ARBOL_NUEVO(tam) -- Crea el arbol con un tama‰o      --
2090 REMark --     b=ARBOL_LEN      -- Nro de elementos del arbol       --
2100 REMark --     b=ARBOL_NIVELES  -- Nro de niveles del arbol         --
2110 REMark --     b=ARBOL_BUSCAR(n)-- Busca un elemento en el arbol    --
2120 REMark --     ARBOL_ADD(dato)  -- Introduce un dato en el arbol    --
2130 REMark --     ARBOL_DELETE(n)  -- Borra el elemento n del arbol    --
2140 REMark --     v$=ARBOL_VER$    -- Muestra los elementos del arbol  --
2150 REMark --     ARBOL_CAMBIA(tam)-- Cambia el tama‰o del arbol       --
2160 REMark --   Procesos de uso interno:                               --
2170 REMark --     ARBOL_INIT       -- Inicializa una arbol             --
2180 REMark --     b=ARBOL_EL_LIBRE -- Retorna elemento libre           --
2190 REMark --     n=ARBOL_NIVELES  -- Retorna nro de niveles del arbol --
2200 REMark --   Elementos.: Se usan los siguientes elementos globales  --
2210 REMark --     A_TAM           -- Tama‰o del arreglo                --
2220 REMark --     A_FACTOR        -- Factor de crecimiento             --
2230 REMark --     ArrArbol(tam)   -- Elementos del arbol               --
2240 REMark --     ArrIzq(tam)     -- Puntero al elemento izquierdo     --
2250 REMark --     ArrDer(tam)     -- Puntero al elemento derecho       --
2260 REMark --     P_NULO          -- Puntero nulo                      --
2270 REMark --     P_VACIO         -- Puntero vacio                     --
2280 REMark --     A_RAIZ          -- Puntero al nodo raiz              --
2290 REMark --     A_NRO           -- Nro de elementos del arbol        --
2300 REMark --     A_NIVELES       -- Nro de niveles del arbol          --
2310 REMark --------------------------------------------------------------
2320 :
2330 :
2340 REMark --------------------------------------------------------------
2350 REMark -- ARBOL_CREAR -- Crea el arbol                             --
2360 REMark --------------------------------------------------------------
2370 DEFine PROCedure ARBOL_CREAR
2380   REMark Espacio para 10 elementos, crece minimo 5
2390   ARBOL_NUEVO 9,5
2400 END DEFine 
2410 :
2420 REMark --------------------------------------------------------------
2430 REMark -- ARBOL_NUEVO(tam,fac) -- Crea el arbol con un tama‰o y un --
2440 REMark --                         factor de crecimiento            --
2450 REMark --------------------------------------------------------------
2460 DEFine PROCedure ARBOL_NUEVO(tam,fac)
2470   LOCal i
2480   :
2490   LET P_NULO   = -1        : REMark Puntero nulo
2500   LET P_VACIO  = -2        : REMark Puntero vacio
2510   LET A_RAIZ   = P_NULO    : REMark Puntero al nodo raiz
2520   LET A_NIVELES= 0         : REMark Nro de niveles del arbol
2530   LET A_NRO    = 0         : REMark Nro de elementos del arbol
2540   LET A_TAM    = tam       : REMark Tama‰o del arreglo
2550   LET A_FACTOR = fac       : REMark Factor de crecimiento
2560   DIM ArrIzq(tam)          : REMark Punteros al elemento izquierdo
2570   DIM ArrDer(tam)          : REMark Punteros al elemento derecho
2580   DIM ArrArbol(tam)        : REMark Elementos del arbol
2590   :
2600   REMark Inicializa arbol de elementos libres
2610   FOR i=0 TO A_TAM : ArrIzq(i) = P_VACIO : ArrDer(i) = P_VACIO
2620 END DEFine 
2630 :
2640 REMark --------------------------------------------------------------
2650 REMark -- b = ARBOL_LEN -- Retorna el nro de elementos del arbol --
2660 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2670 REMark --------------------------------------------------------------
2680 DEFine FuNction ARBOL_LEN
2690   RETurn A_NRO
2700 END DEFine 
2710 :
2720 REMark --------------------------------------------------------------
2730 REMark -- b = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
2740 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2750 REMark --------------------------------------------------------------
2760 DEFine FuNction ARBOL_NIVELES
2770   RETurn A_NIVELES
2780 END DEFine 
2790 :
2800 REMark --------------------------------------------------------------
2810 REMark -- b = ARBOL_EL_LIBRE -- Retorna elemento libre del arbol   --
2820 REMark -- RETORNA:  <0 hay="" libres="" no="">=0 nro del elemento         --
2830 REMark --------------------------------------------------------------
2840 DEFine FuNction ARBOL_EL_LIBRE
2850   LOCal i
2860   :
2870   FOR i=0 TO A_TAM
2880     IF ArrIzq(i) = P_VACIO THEN RETurn i
2890   END FOR i
2900   RETurn P_NULO
2910 END DEFine 
2920 :
2930 REMark --------------------------------------------------------------
2940 REMark -- b = ARBOL_BUSCAR(valor) -- Busca un elemento en el arbol --
2950 REMark -- RETORNA:  nro del elemento o NULO si no encontrado       --
2960 REMark --------------------------------------------------------------
2970 DEFine FuNction ARBOL_BUSCAR(valor)
2980   LOCal nro,repetir
2990   :
3000   nro = A_RAIZ
3010   REPeat repetir
3020     IF nro = P_NULO THEN EXIT repetir
3030     IF ArrArbol(nro) = valor THEN EXIT repetir
3040     IF ArrArbol(nro) < valor THEN 
3050       nro = ArrDer(nro)
3060     ELSE 
3070       nro = ArrDer(nro)
3080     END IF 
3090   END REPeat repetir
3100   RETurn nro
3110 END DEFine 
3120 :
3130 :
3140 REMark --------------------------------------------------------------
3150 REMark -- ARBOL_ADD(dato) -- Introduce un dato en el arbol, si     --
3160 REMark --                    esta llena crece al doble             --
3170 REMark --------------------------------------------------------------
3180 DEFine PROCedure ARBOL_ADD(dato)
3190   LOCal repetir,nro,pos,nivel
3200   :
3210   REMark Busco nodo libre, crece si hace falta y ubico el elemento
3220   REPeat repetir
3230     nro = ARBOL_EL_LIBRE
3240     IF nro <> P_NULO THEN EXIT repetir
3250     ARBOL_CAMBIA(A_TAM*2)
3260   END REPeat repetir
3270   ArrArbol(nro) = dato
3280   ArrIzq(nro) = P_NULO
3290   ArrDer(nro) = P_NULO
3300   nivel = 1
3310   :
3320   REMark Si es el primer nodo, lo ubico en la raiz
3330   IF A_RAIZ = P_NULO THEN 
3340     A_RAIZ = nro
3350   ELSE 
3360     REMark Si no es el primero, buscamos su posicion recorriendo
3370     pos = A_RAIZ
3380     REPeat repetir
3390       nivel = nivel + 1
3400       REMark Si es menor o igual pasamos a la izquierda
3410       IF (ArrArbol(pos) > dato) THEN 
3420         IF (ArrIzq(pos)=P_NULO) THEN 
3430           ArrIzq(pos) = nro
3440           EXIT repetir
3450         END IF 
3460         pos = ArrIzq(pos)
3470       ELSE 
3480         :
3490         REMark Si es mayor pasamos a la derecha
3500         IF (ArrDer(pos)=P_NULO) THEN 
3510           ArrDer(pos) = nro
3520           EXIT repetir
3530         END IF 
3540         pos = ArrDer(pos)
3550       END IF 
3560     END REPeat repetir
3570   END IF 
3580   :
3590   REMark Sumo un elemento al arbol y miro el nivel
3600   A_NRO = A_NRO + 1
3610   IF nivel > A_NIVELES THEN A_NIVELES = nivel
3620   :
3630 END DEFine 
3640 :
3650 REMark --------------------------------------------------------------
3660 REMark -- v$ = ARBOL_VER$ -- Muestra el arbol                      --
3670 REMark -- RETORNA: Lista de elementos del arbol                    --
3680 REMark --------------------------------------------------------------
3690 DEFine FuNction ARBOL_VER$(hastanivel)
3700   LOCal lista$
3710   :
3720   IF ARBOL_LEN = 0 THEN 
3730     PRINT "Error: Arbol vacio"
3740     STOP
3750   END IF 
3760   :
3770   lista$=""
3780   inorden A_RAIZ,hastanivel,lista$,1
3790   RETurn lista$
3800 END DEFine 
3810 :
3820 DEFine PROCedure inorden(nodo,nivel,cadena$,actual)
3830   IF nodo <> P_NULO THEN 
3840     inorden ArrIzq(nodo),nivel,cadena$,actual+1
3850     IF (nivel < 1) OR (nivel = actual) THEN 
3860       IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
3870       cadena$ = cadena$ & "[" & actual & "]" & ArrArbol(nodo)
3880     END IF 
3890     inorden ArrDer(nodo),nivel,cadena$,actual+1
3900   END IF 
3910 END DEFine 
3920 :
3930 REMark --------------------------------------------------------------
3940 REMark -- ARBOL_DELETE(valor) -- Borra un elemento del arbol       --
3950 REMark --------------------------------------------------------------
3960 DEFine PROCedure ARBOL_DELETE(valor)
3970   LOCal nodo,padre,repetir
3980   :
3990   nodo = A_RAIZ
4000   padre = P_NULO
4010   REPeat repetir
4020     IF nodo = P_NULO THEN EXIT repetir
4030     IF ArrArbol(nodo) = valor THEN EXIT repetir
4040     padre = nodo
4050     IF ArrArbol(nodo) < valor THEN nodo = ArrDer(nodo)
4060     IF ArrArbol(nodo) > valor THEN nodo = ArrDer(nodo)
4070   END REPeat repetir
4080   :
4090   IF (nodo = P_NULO) THEN 
4100     PRINT "ERROR: Intenta eliminar un elemento que no existe"
4110     STOP
4120   END IF 
4130   :
4140   ARBOL_BORRAR_NODO nodo,padre : REMark Borrar el nodo
4150   A_NRO = A_NRO - 1            : REMark reducir elementos del arbol
4160   A_NIVELES = ARBOL_MAX_NIVEL  : REMark Recalcula niveles
4170 END DEFine 
4180 :
4190 REMark --------------------------------------------------------------
4200 :
4210 DEFine PROCedure ARBOL_BORRAR_NODO(nodo,padre)
4220   LOCal nuevo
4230   :
4240   :: ArrArbol(nodo) = 0
4250   :
4260   REMark Este elemento sera el que reemplace en el padre
4270   nuevo = P_NULO
4280   :
4290   REMark Si no tiene hijos, se desapunta el padre
4300   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)=P_NULO) THEN 
4310     nuevo = P_NULO
4320   END IF 
4330   :
4340   REMark Solo tiene un hijo, se pasa al padre
4350   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)<>P_NULO) THEN 
4360     nuevo = ArrDer(nodo)
4370   END IF 
4380   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)=P_NULO)  THEN 
4390     nuevo =  ArrIzq(nodo)
4400   END IF 
4410   :
4420   REMark Tiene dos hijos, pasa al padre el derecho y lo borro
4430   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)<>P_NULO) THEN 
4440     nuevo = ArrDer(nodo)
4450     ARBOL_BORRAR_NODO ArrDer(nodo),nodo
4460   END IF 
4470   :
4480   REMark Ahora apunto el padre de forma adecuada
4490   IF padre = P_NULO THEN 
4500     A_RAIZ = nuevo
4510   ELSE 
4520     IF ArrIzq(padre) = nodo THEN ArrIzq(padre) = nuevo
4530     IF ArrDer(padre) = nodo THEN ArrDer(padre) = nuevo
4540   END IF 
4550   ArrIzq(nodo) = P_VACIO
4560   ArrDer(nodo) = P_VACIO
4570 END DEFine 
4580 :
4590 REMark --------------------------------------------------------------
4600 REMark -- ARBOL_CAMBIA -- Cambia el tama‰o del arbol             --
4610 REMark --------------------------------------------------------------
4620 DEFine PROCedure ARBOL_CAMBIA(tam)
4630   LOCal tEle(A_TAM),tIzq(A_TAM),tDer(A_TAM),tTam,tRaiz,tNro,m1,m2,i
4640   :
4650   REMark Guardo el arbol en el auxiliar de forma compacta
4660   tRaiz = A_RAIZ
4670   tNro  = A_NRO
4680   tTam  = A_TAM
4690   m1    = 0      : REMark Ultimo elemento libre de la lista
4700   FOR i=A_TAM TO 0 STEP -1
4710     IF (m1 = 0) AND (tEle(i) <> P_VACIO) THEN 
4720       m1 = i + 1
4730     END IF 
4740     tEle(i)=ArrArbol(i)
4750     tIzq(i)=ArrIzq(i)
4760     tDer(i)=ArrDer(i)
4770   END FOR i
4780   :
4790   REMark calculo tama‰os m“nimos
4800   m2 = A_NRO + A_FACTOR
4810   IF tam < m2       THEN tam = m2
4820   IF tam < A_FACTOR THEN tam = tam + A_FACTOR
4830   IF tam < m1       THEN tam = m1 + A_FACTOR
4840   :
4850   REMark Creo el nuevo arbol y lo relleno
4860   ARBOL_NUEVO tam,A_FACTOR
4870   :
4880   A_RAIZ = tRaiz
4890   A_NRO  = tNro
4900   FOR i=0 TO m1-1
4910     ArrArbol(i) = tEle(i)
4920     ArrIzq(i)   = tIzq(i)
4930     ArrDer(i)   = tDer(i)
4940   END FOR i
4950 END DEFine 
4960 :
4970 :
4980 REMark --------------------------------------------------------------
4990 REMark -- n = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
5000 REMark -- RETORNA: Nivel maximo del arbol                          --
5010 REMark --------------------------------------------------------------
5020 DEFine FuNction ARBOL_MAX_NIVEL
5030   RETurn nivel_inorden(A_RAIZ, 0)
5040 END DEFine 
5050 :
5060 DEFine FuNction nivel_inorden(nodo,actual)
5070   LOCal n1,n2
5080   :
5090   IF nodo = P_NULO THEN 
5100     RETurn actual
5110   ELSE 
5120     n1 = nivel_inorden(ArrIzq(nodo),actual+1)
5130     n2 = nivel_inorden(ArrDer(nodo),actual+1)
5140     IF (n1 > n2) THEN RETurn n1 : ELSE RETurn n2
5150   END IF 
5160 END DEFine
 


Para poder verificar que el árbol funciona uso un pequeño programa de pruebas, en el se ve siempre el árbol y sus enlaces izquierdo y derecho, los punteros nulos, los elementos libres, etc. Tras cada prueba se presenta el árbol y la lista de elementos ordenados que se obtiene del mismo.

100 REMark ----------------------------------------
110 REMark -- Carga                              --
120 REMark ----------------------------------------
130 MODE 4: PAPER 0 : CLS
140 INPUT "Cual prefiere (1)=Simple",t$
150 IF t$<>"1" THEN GO TO 200
160 n$="mdv1_ed_arbol_arreglo" & t$
170 PRINT "Cargando ";n$
180 MERGE n$
190 REMark ----------------------------------------
200 REMark -- Rutinas de pruebas                 --
210 REMark ----------------------------------------
220 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
230 p2$=""
240 t1=DATE
250 :
260 PRINT "Creacion del arbol"
270 crear : ver : PRINT
280 :
290 PRINT "PRUEBA 1: Introduce elementos en orden, inversos y aleatorios"
300 crear : FOR i=1 TO 5         : mete(i)          : END FOR i : verarbol
310 crear : FOR i=5 TO 1 STEP -1 : mete(i)          : END FOR i : verarbol
320 crear : FOR i=1 TO 10        : mete(RND(1 TO 9)): END FOR i : verarbol
330 :
340 PRINT "PRUEBA 2: Introduce 9, elimina 5, introduce 3, elimina 4"
350 crear
360 FOR i=1 TO 9   : mete(i)
370 FOR i=1 TO 5   : borra(i)
380 FOR i=10 TO 12 : mete(i)
390 FOR i=9 TO 11   : borra(i)
400 verarbol
410 :
420 PRINT "PRUEBA 3: Introduce 9, Extrae 2, introduce 10 y reduce"
430 crear
440 FOR i=1 TO 9   : mete(i)
450 FOR i=1 TO 2   : borra(i)
460 FOR i=10 TO 19 : mete(i)
470 verarbol
480 PRINT "CM "; : ARBOL_CAMBIA 0 : ver : verarbol
490 :
500 PRINT "PRUEBA 4: Buscar algunos elementos"
510 crear
520 FOR i=1 TO 9   : mete(i)
530 FOR i= 0 TO 13 STEP 3
540   PRINT "BUSCO ";i;" = ";ARBOL_BUSCAR(i)
550 END FOR i
560 PRINT
570 :
580 PRINT "PRUEBA 5: Extrae elementos hasta error por vacia"
590 FOR i=1 TO ARBOL_LEN : borra(i)
600 t2 = DATE : PRINT "Tarda ";t2-t1;" segundos"
610 borra(0)
620 STOP
630 :
640 :
650 DEFine PROCedure crear
660   ARBOL_CREAR
670 END DEFine 
680 :
690 DEFine PROCedure mete(a)
700   PRINT "EN ";a;":";
710   ARBOL_ADD(a)
720   ver
730 END DEFine 
740 :
750 DEFine PROCedure borra(a)
760   PRINT "BO ";!a;"(";ARBOL_BUSCAR(a);"):";
770   ARBOL_DELETE(a) : ver
780 END DEFine 
790 :
800 DEFine PROCedure verarbol
810   PRINT "ARBOL: ";ARBOL_VER$(0) : PRINT
820 END DEFine 
830 :
840 DEFine PROCedure ver
850   LOCal xx
860   :
870   PRINT "[";ARBOL_LEN;"x";ARBOL_NIVELES;"]";
880   IF A_RAIZ=P_NULO THEN PRINT "*"; : ELSE PRINT A_RAIZ;":";
890   FOR xx=0 TO A_TAM
900     PRINT !"(";xx;")";ArrArbol(xx);
910     IF ArrIzq(xx)=-1 THEN PRINT "*";
920     IF ArrIzq(xx)=-2 THEN PRINT "v";
930     IF ArrIzq(xx)>0  THEN PRINT ArrIzq(xx);
940     IF ArrDer(xx)=-1 THEN PRINT "*";
950     IF ArrDer(xx)=-2 THEN PRINT "v";
960     IF ArrDer(xx)>0  THEN PRINT ArrDer(xx);
970   END FOR xx
980   PRINT
990 END DEFine 

Cuando ejecutéis las pruebas os daréis cuenta de que si introduzco los elementos de forma ordenada todos van a parar siempre a la rama derecha, quedando la izquierda vacía, por lo que tenemos una lista en lugar de un árbol. Cuando los introduzco de forma aleatoria se van llenando las ramas izquierda y derecha mas o menos a la par. Esto nos indica que un árbol binario de búsqueda solo será eficiente si los elemento se introducen al azar y producen un árbol en el que las ramas sean todas mas o menos del mismo tamaño, pues sin ese equilibrio pierde mucha efectividad en altas y bajas, peor lo que es peor, hace mas lentas las búsquedas, siendo nuestro objetivo que estas sean lo mas eficientes posibles. En la siguiente entrada montaremos arboles binarios de búsqueda equilibrados mediante las técnicas de rotación simple y doble, produciendo árboles AVR.

Como siempre aquí todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

lunes, 12 de diciembre de 2016

Variante del cable RGB de la SNES

Ha surgido una variante del cable RGB para las SNES, que no se si servirá para las Nintendo-64 con salida RGB o no. En esta entrada expliqué los cables de video existentes para las variedades de maquinas de nintendo con el mismo conector de salida, SNES/SNES 2/AV Famicom/N64/Game Cube, en ella explicaba que los cables deben no usar condensador para las SNES y si para las N64 y Cube, aunque esto hay que probarlo siempre ya que depende de la maquina y el televisor mas que de otra cosa.

Ahora ha surgido una variante del cable RGB para la SNES. Sabemos que la salida del euroconector o scart necesita cuatro señales para el manejo de vídeo, rojo, verde, azul y el sincronismo compuesto. Esta última señal se saca de la señal de vídeo compuesto habitualmente, pero se ha descubierto que es mejor obtener de la señal de luminancia, que también los incluye, y por las pruebas que he visto da un resultado mucho mejor (aunque no lo he podido probar todavía, pero las imágenes que se ven por Internet del cable que se ha denomiado Chekerboar dejan claro que la señal es mucho mejor. El cambio es muy sencillo, solo hay que sacar la señal  que va al pin 20 del SCART a través del pin 7 de la Nintendo, en lugar de a través del pin 5. Hay que mantener la resistencia entre el pin 7 y masa, que yo en mi imagen pongo entre los pines 18 y 20 del euroconector, pero que normalmente en los cables está en el conector de Nintendo.


No tengo constancia de si esta modificación serviría igualmente para las N64 (las que llevan soporte RGB que no son todas) y las Game Cube.

viernes, 9 de diciembre de 2016

Mas traducciones en la Wikipedia

He realizado algunas traducciones mas para la wikipedia, ya que considero que es un buen lugar para almacenar información que sea útil a todo el mundo, además siempre aprendo cosas nuevas.

  • Micromation fue una empresa americana de micro ordenadores, que fabricaba ordenadores multi usurio a base de montar un aplaca con un procesador para cada uno. Que yo sepa no llegaron a España, eran caros pero de lo mejor del momento.
  • Como me gusta mucho DEC y sus PDP (aunque no he tenido la suerte de usar nunca uno), he traducido la página sobre los DECmate, los microordenadores compatibles con los PDP-8.
  • Relacionado con lo anterior, el microprocesador Intersil 6100 era el corazón de los DECmate, una CPU de un PDP-8 en un solo chip, aunque mucho mas lento.
  • Relacionado con los PDP, las páginas para 12 bits y para 18 bits no estaban en español. También he añadido una plantilla para que enlace con todos los anchos de bits y la he ubicado en todas las páginas relacionadas.
Seguiré con otras traducciones que faltan muchas cosas de empresas y ordenadores antiguos que tanto me gustan.

miércoles, 7 de diciembre de 2016

Programación del Sinclair QL (XVIII): Ordenación por inserción usando una lista enlazada



Como ya tenemos las rutinas de manejo de las listas enlazadas con sus elementos ordenados, la voy a usar como algoritmo de ordenación general, simplemente tomo los algoritmos de lista enlazada y los simplifico al máximo, creo la lista con tamaño exacto para los elementos a ordenar, la relleno, y luego la recorro modificando el arreglo original, y al final resultando un algoritmo muy sencillo, aunque para ordenar una lista necesita otras dos adicionales, por lo que gasta bastante más memoria.

ALGORITMO Insercion_lista (arreglo, primero, ultimo)
 
  raiz ← null  
  tamaño ← ultimo - primero + 1
  CREAR_ARREGLO Datos(tamaño)
  CREAR_ARREGLO Enlaces(tamaño)

  BUCLE i DESDE primero HASTA ultimo
    LISTA_ORDENADA_INSERTAR(arreglo(i), Datos, Enlaces, raiz)
  FIN BUCLE
    
  pos ← raiz
  BUCLE i DESDE primero HASTA ultimo
    arreglo(nro) ← Datos(pos)
    pos ← Enlaces(pos)
  FIN BUCLE

ALGORITMO LISTA_ORDENADA_INSERTAR (valor, ListaDatos, ListaNodos, NodoRaiz)
 
   // Busco un nodo libre
   nro ← BUSCAR_ELEMENTO_LIBRE
   SI nro = NULL ENTONCES
      ERROR No hay espacio libre
      SALIR DEL ALGORITMO
   FIN SI

   // Ubico el elemento
   ListaDatos(nro) = Valor

   // Si es el primer nodo lo ubico en la raiz
   SI (NodoRaiz ES NULO) ENTONCES 
     ListaNodos(nro) ← NULL
     NodoRaiz ← nro
   FIN SI
 
   // Si no es el primero buscamos su posición
   SI (NodoRaiz NOES NULO) ENTONCES  
     pos ← NodoRaiz  // Nodo por el que vamos
     ant ← NULL      // Nodo anterior al que vamos
     REPETIR
       encontrado ← Falso 
       
       // Si he encontrado un elemento mayor o igual, debo ubicarlo antes
       SI (ListaDatos(pos) ≥ Valor) ENTONCES 
         // Si es el primer elemento, hay que ubicarlo en la raiz
         SI (ant ES NULO) ENTONCES 
           ListaNodos(nro) ← NodoRaiz
           NodoRaiz        ← nro
           encontrado      ← Cierto 
         FIN SI
  
         // Si no es el primer elemento, hay que ubicarlo tras el anterior
         SI (ant NOES NULO) ENTONCES 
           ListaNodos(nro) ← ListaNodos(ant)
           ListaNodos(ant) ← nro
           encontrado      ← Cierto 
         FIN SI
       FIN SI
       
       // Si se ha llegado al final se pone el último
       SI (ListaNodos(pos) ES NULO) ENTONCES 
         ListaNodos(pos) ← nro
         ListaNodos(nro) ← NULL
         encontrado      ← Cierto
      END IF 
      
      //No encontrado seguimos iterando
      SI (NO encontrado) ENTONCES 
        ant ← pos
        pos ← ListaNodos(pos)
      FIN SI
     HASTA QUE (encontrado)
   FIN SI 


Aquí el programa completo en SuperBASIC correspondiente, son las rutinas desarrolladas en el manejo de listas pero simplificadas al máximo dejando solo lo necesario. Para gastar un poco menos de memoria y optimizar algo las velocidades (aunque en SuperBASIC la velocidad no se nota por su forma de trabajar), habría que hacer que la lista de punteros sea de enteros en lugar de reales. De momento no lo voy a hacer así.

20000 REMark ---------------------------------------------
20010 REMark -- ALGORITMOS DE ORDENACION                --
20020 REMark --   Modulo....: Insercion con lista       --
20030 REMark --   Objetivo..: Ordena un arreglo usando  --
20040 REMark --               enlazada                  --
20050 REMark --   Autor.....: javu61, 12/2016           --
20060 REMark --   Parametros:                           --
20070 REMark --     arreglo -- Arreglo a ordenar        --
20080 REMark --     sentido -- FALSO = Ascendente       --
20090 REMark --     primero -- primer elemento          --
20100 REMark --     ultimo  -- ultimo elemento          --
20110 REMark --                Si ultimo=0 -- Todos     --
20120 REMark ---------------------------------------------
20130 DEFine PROCedure Insercion_Lista (arreglo,sentido,primero,ultimo)
20140   LOCal pos,nro
20150   :
20160   IF ultimo = 0 THEN ultimo=DIMN(arreglo)
20170   :
20180   REMark Crear los elementos de la lista
20190   LET L_NULO   = -1        : REMark Puntero nulo
20200   LET L_RAIZ   = L_NULO    : REMark Puntero al nodo raiz
20210   DIM ArrPuntero(ultimo-primero) : REMark Puntero siguiente elemento
20220   DIM ArrLista(ultimo-primero)   : REMark Elementos de la lista
20230   :
20240   REMark Rellenar la lista
20250   FOR pos = primero TO ultimo : LISTA_ADD pos,arreglo(pos),sentido
20260   :
20270   REMark A partir de la lista montar el arreglo ordenado
20290   FOR nro=primero TO ultimo
20300     MUEVE ArrLista(L_RAIZ), arreglo(nro)
20310     L_RAIZ= ArrPuntero(L_RAIZ)
20320   END FOR nro
20330 END DEFine 
20340 :
20350 REMark -------------------------------------------------------------
20360 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista        --
20370 REMark -------------------------------------------------------------
20380 DEFine PROCedure LISTA_ADD(nro,dato,sentido)
20390   LOCal repetir,pos,ant
20400   :
20410   REMark Ubico el elemento
20420   ArrLista(nro) = dato
20430   :
20440   REMark Si es el primer nodo, lo ubico en la raiz
20450   IF L_RAIZ = L_NULO THEN 
20460     ArrPuntero(nro) = L_NULO
20470     L_RAIZ = nro
20480   ELSE 
20490     REMark Si no es el primero, buscamos su posición recorriendo
20500     pos = L_RAIZ
20510     ant = L_NULO
20520     REPeat repetir
20530       REMark Si he econtrado su posición
20540       IF COMPARA(ArrLista(pos), dato, sentido) &gt;= 0 THEN 
20550         REMark Segun sea ahora el primer elemento o no
20560         IF ant = L_NULO THEN 
20570           ArrPuntero(nro) = L_RAIZ
20580           L_RAIZ = nro
20590         ELSE 
20600           ArrPuntero(nro) = ArrPuntero(ant)
20610           ArrPuntero(ant) = nro
20620         END IF 
20630         EXIT repetir
20640       END IF 
20650       REMark Si he llegado al final, lo añado como utimo elemento
20660       IF ArrPuntero(pos)=L_NULO THEN 
20670         ArrPuntero(pos) = nro
20680         ArrPuntero(nro) = L_NULO
20690         EXIT repetir
20700       END IF 
20710       ant = pos
20720       pos = ArrPuntero(pos)
20730     END REPeat repetir
20740   END IF 
20750 END DEFine 
20760 :
20770 :


Las pruebas de las rutinas de ordenación por inserción desarrolladas hasta el momento dan el siguiente resultado con 50 elementos, vemos que Shell es el mas rápido en el caso medio y es bastante bueno para listas ordenadas o en orden inverso, además no requiere mucha memoria. La inserción pura y la inserción con lista enlazada tardan mas o menos lo mismo en el caso medio, ya que son muy similares en cuanto a la cantidad de elementos a recorrer para insertar uno en su lugar, pero por su forma de trabajar la inserción pura es la mas rápida para listas ordenadas mientras la de lista enlazada es la peor, y para listas en orden inverso se cambian las tornas.



He dividido los programas en dos grupos, aquí todo lo desarrollado sobre estructuras de datos y sus pruebas hasta el momento, y aquí todo lo desarrollado sobre ordenación hasta el momento.

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, &gt;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:  &lt;0 no hay libres, &gt;=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) &gt; 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 &lt;&gt; 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) &gt;= 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 &lt; 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 &lt; minimo   THEN tam = minimo
3290   IF tam &lt; 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 &lt;&gt; 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 &lt;&gt; 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$ &amp; LISTA_VER(xx) &amp; ","
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)&gt;0  THEN PRINT ArrPuntero(xx);
940   END FOR xx
950   PRINT
960 END DEFine 

Como siempre aquí todo lo desarrollado hasta el momento.

viernes, 2 de diciembre de 2016

Mis contribuciones en la Wikipedia

El otro día buscando información sobre lenguajes de programación vi que no había entrada en castellano en la Wikipedia sobre PL/M, el lenguaje desarrollado por Gary Kildall en Intel, que luego utilizó para desarrollar su CP/M. Al lanzar la traducción de la página ahora sale un magnífico asistente que te ayuda mucho en la traducción, y esto me ha echo recopilar aquí las entradas sobre computación que he traducido o ampliado en la Wikipedia, recordando un poco la falta de ayudas de hace unos años y lo cómodo que hoy día para traducciones y mejoras:

  • Tras hacerme con una en 2011, creé la entrada sobre la C64 Direct-to-TV a partir de la traducción manual de la entrada en inglés.
  • En 2012 amplié la entrada sobre la Z1 a partir de información en ingles de varias fuentes, ampliando los apartados de historia y diseño, añadiendo el resto de apartados, ampliando enlaces y referencias. Todo lo hice manualmente.
  • En junio de este año 2016 creé la página sobre los Intellec usando el asistente de traducción, que ayudaba pero no era todavía comparable al actual.
  • Ahora acabo de traducir la entrada sobre PL/M, usando el nuevo asistente de traducción, que es muy bueno, a poco que puedas entender el idioma de origen es muy cómodo y rápido, ya que te pone los dos textos uno junto al otro, te propone la traducción automática, y solo tienes que ir revisando y ajustando. Además, la entrada en Francés me permitió añadir alguna referencia, y la entrada en Polaco es muy buena por lo que añadí algunas cosas y enlaces de esa página, a pesar de no entender el idioma, si comprendía lo que querían decir.
  • Luego traduje una entrada muy relacionada con la anterior sobre el S.O. ISIS de Intel con el asistente, nuevamente la entrada en Polaco es muy buena por lo que añadí algunas cosas y enlaces de esa página.