- 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.
lunes, 19 de diciembre de 2016
Traducciones en la Wikipedia
Estas son mis últimas traducciones:
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
<0 hay="" libres="" no="">Errara corregida el 16/07/24 en la línea 3050
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 = ArrIzq(nro) : REMark errara corregida 16/07/24 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, pero 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.
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.
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) >= 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, >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.
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.
Suscribirse a:
Entradas (Atom)