From 1e06a5801e11f5d0af80178625ba4bb49adcfa51 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 23 Mar 2003 07:10:16 +0000 Subject: [PATCH] =?utf8?q?Import=20inicial=20despu=C3=A9s=20del=20"/var=20?= =?utf8?q?incident".=20:(?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- TP_Busq.pas | 667 ++++++++++++++++++ busq_l.pas | 217 ++++++ datos.txt | 47 ++ ... tree reorganization hashing insertion.htm | 79 +++ ...rent's reorganization scheme insertion.htm | 62 ++ docs/Double hashing insertion.htm | 57 ++ docs/Hashing.htm | 415 +++++++++++ docs/Heapsort.htm | 54 ++ docs/Interpolation (in-place) sort.htm | 63 ++ docs/Linear probing hashing search.htm | 50 ++ docs/Linear probing sort.htm | 67 ++ docs/Ordered hashing insertion.htm | 59 ++ docs/Quadratic hashing insertion.htm | 54 ++ docs/Shellsort.htm | 64 ++ .../Stacks, Queues, Lists and Hash Tables.htm | 436 ++++++++++++ .../dsmenu.gif | Bin 0 -> 2749 bytes .../menu.gif | Bin 0 -> 1653 bytes .../previous.gif | Bin 0 -> 1645 bytes ej1.pas | 78 ++ ej2.pas | 120 ++++ ej3.pas | 77 ++ orden.html | 282 ++++++++ orden.pas | 280 ++++++++ 23 files changed, 3228 insertions(+) create mode 100644 TP_Busq.pas create mode 100644 busq_l.pas create mode 100644 datos.txt create mode 100644 docs/Binary tree reorganization hashing insertion.htm create mode 100644 docs/Brent's reorganization scheme insertion.htm create mode 100644 docs/Double hashing insertion.htm create mode 100644 docs/Hashing.htm create mode 100644 docs/Heapsort.htm create mode 100644 docs/Interpolation (in-place) sort.htm create mode 100644 docs/Linear probing hashing search.htm create mode 100644 docs/Linear probing sort.htm create mode 100644 docs/Ordered hashing insertion.htm create mode 100644 docs/Quadratic hashing insertion.htm create mode 100644 docs/Shellsort.htm create mode 100644 docs/Stacks, Queues, Lists and Hash Tables.htm create mode 100644 docs/Stacks, Queues, Lists and Hash Tables_archivos/dsmenu.gif create mode 100644 docs/Stacks, Queues, Lists and Hash Tables_archivos/menu.gif create mode 100644 docs/Stacks, Queues, Lists and Hash Tables_archivos/previous.gif create mode 100644 ej1.pas create mode 100644 ej2.pas create mode 100644 ej3.pas create mode 100644 orden.html create mode 100644 orden.pas diff --git a/TP_Busq.pas b/TP_Busq.pas new file mode 100644 index 0000000..b02a6bb --- /dev/null +++ b/TP_Busq.pas @@ -0,0 +1,667 @@ +Program Estudio_Busquedas; + +{encabezado} + +uses Crt; + +{declaracion de constantes} + +const + +primera=1; +ultima=100; +ultimamas1=ultima+1; + +{declaracion de tipos} + +type + tipollave=integer; + subindices=primera..ultima; {subindices para el vector} + aumentado=primera..ultimamas1; + T_Consultas= 1..8; {son ocho consultas} + tipovector=array [subindices] of integer; + Array_of_arrays= array [T_consultas] of tipovector; + tipo_busq= array[T_consultas] of string; + +{declaracion de variables} + +var + vector:tipovector; + idx, clave: integer; {variable de indice} + caso: T_Consultas; {subindice de los arrays} + ref_vector: array_of_arrays; + {vector para almacen de vectores utilizados} + + consultas: array[T_consultas] of integer; + {vector para almacen de consultas efectuadas} + + busqueda: array[T_consultas] of integer; + {vector para almacen del valor a buscar} + + Tipo_b: Tipo_busq; + {vector para almacen de tipo de consultas} + linea_t:string; + ciclo,x,i,a,b:integer; {a y b son variables 'comodin' arbitrariamente empleadas} + r,s,t:real; + + grDriver: Integer; + grMode: Integer; {variables para el modo grafico} + + + +{---------------------------------------------------------------------} + +{seccion algorítmica} +{procedimientos y funciones} + + +{----------------------------------------------------------} +{PROCEDIMIENTOS PARA VISUALIZACION EN PANTALLA} + +{-----------------------------------------------------------------} +procedure Presentacion; + +var a,b:integer; + +begin + + textbackground(White); + textcolor(Black); + for a:=9 to 15 do for b:=25 to 55 do begin gotoxy(b,a); + write(' '); + end; + gotoxy(31,10);write('METODOS DE BUSQUEDA'); + gotoxy(31,12);write('-estudio simulado-'); + gotoxy(34,14);write('72.40 C:7'); + textcolor(black+blink); + gotoxy(25,17);write('Pulse una tecla para continuar'); + textbackground(Cyan); + textcolor(black); + readkey; +end;{fin del procedimiento} + + +{-----------------------------------------------------------------} +procedure Salida; + +var a,b:integer; + +begin + + textbackground(cyan); + textcolor(black); + for a:=2 to 6 do for b:=25 to 55 do begin gotoxy(b,a); + write(' '); + end; + gotoxy(31,2);write('TRABAJO PRACTICO #3'); + gotoxy(31,3);write('Creado por el Gr#06'); + gotoxy(34,5);write('>NOV 1999'); + textcolor(black+blink); + + textcolor(black); + readkey; +end;{fin del procedimiento} + + +{----------------------------------------------------------} +Procedure Imprime_en(a,b: integer;texto:string); + begin + gotoxy(a,b); + Writeln (texto); + end; {fin del procedimiento} + + +{----------------------------------------------------------} +Procedure Muestra_barra(color:byte;valor:real;fila:integer); + + var a:integer; + + begin + + textbackground(color); + for a:=15 to round(valor*50+15) do imprime_en(a,fila,' '); + + end; + +{----------------------------------------------------------} + + +{----------------------------------------------------------} +{Exportacion hacia archivo de texto} + +procedure Graba_en_Archivo( var Clave: integer; + var V100: tipovector; + n_cons: integer; + TipoB: string; + Proba: Integer); + +{encabezado}{proc} +{declaracion de variables} + +var +reporte : text; {archivo de salida con formato texto} +a_salida,texto,linea, conv : string; + cont: integer; + +{seccion algorítmica}{proc} + +begin + + str(Proba,conv); {conversion del numero de probadilidad} + a_salida:='C:\reporte'+conv+'.txt'; + assign(reporte,a_salida); + {$I-} {deshabilita el control sobre los archivos} + append(reporte); + if not (ioresult=0) then rewrite(reporte); {abre el archivo} + + texto:=''; + for a:=1 to 10 do texto:='-'+texto; + writeln(reporte,texto); {linea divisoria} + texto:= 'BUSQUEDA ' + TipoB; + writeln(reporte, texto); {exhibe tipo de busqueda} + texto:=''; + for a:=1 to 10 do texto:='-'+texto; + writeln(reporte,texto); {linea divisoria} + str(Clave,conv); {conversion del numero de ciclos} + texto:= 'NUMERO de CICLOS: '+ conv; + str(n_cons,conv); + writeln(reporte, texto); {informa cantidad de iteraciones} + texto:= 'CONSULTAS efectuadas: '+ conv; + writeln(reporte, texto); {cantidad de consultas efectuadas} + texto:= 'VECTOR obtenido'; + writeln(reporte, texto); {informa cantidad de iteraciones} + writeln(reporte); + + {informacion en pantalla} + textcolor(black); + Imprime_en(7,17,'Grabando Estadisticas en archivo'); + textcolor(red); + for a:=5 to (Proba*2+5) do imprime_en(a,18,'.' ); + textcolor(black); + + + for cont := 1 to high(V100) do + + begin + imprime_en(5,17,'-'); + imprime_en(5,17,'\'); + imprime_en(5,17,'|'); + imprime_en(5,17,'/'); + imprime_en(5,17,'-'); + imprime_en(5,17,'\'); + imprime_en(5,17,'|'); + imprime_en(5,17,'/'); + + + str(V100[cont],conv); {conversion del contenido de los vectores} + texto:=' '; + for a:=1 to (7-length(conv)) do texto:=texto+' '; {separacion uniforme} + linea := linea + conv + texto; {concatena el vector} + if cont mod 10 = 0 then + begin + writeln(reporte, linea); {linea de exportacion hacia archivo} {imprime el vector} + linea := ''; + + end; + end; + + writeln(reporte); + close(reporte); +end; {fin del procedimiento} + +{----------------------------------------------------------} +{PROCEDIMIENTOS PARA MANIPULACION Y CREACION DE VECTORES} +{----------------------------------------------------------} +{generacion aleatoria del vector} +{este procedimiento se ejecuta cada vez que el programa es corrido, y carga el vector para muestrear las busquedas} + +procedure vectoraleatorio(dimension:integer;var aleatorio:tipovector); +var i:integer; + begin + Randomize; + for i:=1 to dimension do aleatorio[i]:=trunc((random*65535)-32768); + end;{fin del procedimiento} + +{----------------------------------------------------------} +{generacion aleatoria de los subindices} +{los valores a,b,c continen las proporciones a emplearse para estimar la probabilidad de aparacion; "y" es un valor aleatorio +(en el programa se usará la funcion random para cargar este vector); i,j,k son los "cortes en el vector", que determinarán +los rangos deonde actuan las probabilidades} + +function subindice(y,a,b,c:real;i,j,k:integer):integer; + begin + if y<=a then subindice:=trunc((y*(i-1)/a)+1) + else if y<=b then subindice:=trunc((y*(j-i)-(a*j)+(b*i))/(b-a)) + else subindice:=trunc((y*(k-j)-(b*k)+(c*j))/(c-b)); + end;{fin de la funcion} + +{------------------------------------------------------------------} + +{----------------------------------------------------------} +{obtencion del valor para el subindice} +{esta funcion devuelve el valor para un indice de un vector} + +function valor(subindice:integer;vector:tipovector):integer; + + begin + valor:=vector[subindice]; + end;{fin de la funcion} + +{----------------------------------------------------------} +{permutacion de probabilidades} +{para una correcta evaluacion de los sistemas, es necesario contemplar todas las posibilidades} + +procedure perm(c:integer;var m,n,o:real); + +begin + m:=0; + n:=0; + o:=0; {el ultimo valor de ser simpre 1!!} + + + case c of +1: + begin + m:=0.15; + n:=0.5; + o:=1; {el ultimo valor de ser simpre 1!!} + end; +2: + begin + m:=0.5; + n:=0.15; + o:=1; {el ultimo valor de ser simpre 1!!} + end; +3: + begin + m:=0.5; + n:=1; {el ultimo valor de ser simpre 1!!} + o:=0.15; + end; +4: + begin + m:=0.15; + n:=1; {el ultimo valor de ser simpre 1!!} + o:=0.5; + end; +5: + begin + m:=1; + n:=0.5; {el ultimo valor de ser simpre 1!!} + o:=0.15; + end; +6: + begin + m:=1; {el ultimo valor de ser simpre 1!!} + n:=0.15; + o:=0.5; + end; +end + +end;{fin del procedimiento} + +{---------------------------------------------------------------} +{ordenado del vector} +{utiliza para esto un procedimiento de iteracion, e incluye la posibilidad de ordenar un vector de culaquier dimension +permitiendole gran flexibilidad } + +procedure ordenarvector(dimension:integer;vec1:tipovector;var vec2:tipovector); + +var +j,k,ultimo:integer; + +begin +ultimo:=1; +k:=1; +vec2[1]:=vec1[1]; +while ultimo<=dimension do + begin + if vec1[ultimo+1]>=vec2[ultimo] + then vec2[ultimo+1]:=vec1[ultimo+1] + else begin + j:= 1; + while vec1[ultimo+1]>=vec2[j] do inc(j); + for k:=ultimo+1 downto j do vec2[k]:=vec2[k-1]; + vec2[j]:=vec1[ultimo+1]; + end; + inc(ultimo); + end; +end;{fin del procedimiento} + { } +{---------------------------------------------------------------} +{con este procedimiento, se carga un vector que va a contener y administrar todos los vectores empleados para la busqueda} + +Procedure Asignar_Referencia (var r_vector:array_of_arrays;vect:tipovector); + Var + Vect_o:tipovector; + begin + r_vector[1] := vect; {desordenado para busqueda basica} + r_vector[2] := vect; {desordenado para puesta al frente} + r_vector[3] := vect; {desordenado para trasposicion} + ordenarvector(ultima,vect,vect_o); + r_vector[4] := vect_o; {ordenado para busqueda optimizada} + r_vector[5] := vect_o; {ordenado para busqueda binaria} + r_vector[6] := vect_o; {ordenado para busqueda por saltos} + r_vector[7] := vect_o; {ordenado para interpolacion} + r_vector[8] := vect_o; {ordenado para interpolacion/sec} + end;{fin del procedimiento} + + +{---------------------------------------------------------------} +{con este procedimiento, se carga un vector que va a contener y administrar todos los vectores empleados para la busqueda} + +Procedure Tipo_Busqueda (var b_vector:tipo_busq ); + begin + b_vector[1] := 'secuencial basica (exhibe el vector original)'; + b_vector[2] := 'con puesta al frente'; + b_vector[3] := 'con trasposicion'; + b_vector[4] := 'optimizada'; + b_vector[5] := 'binaria'; + b_vector[6] := 'por saltos'; + b_vector[7] := 'por interpolacion'; + b_vector[8] := 'por interpolacion + secuencial'; + end;{fin del procedimiento} + + +{----------------------------------------------------------} +{FUNCIONES DE BUSQUEDA} +{-----------------------------------------------------------------} +{busqueda secuencial basica} + +function SEQB (var a: tipovector; x:integer): integer; + var + i: integer; + begin +for i:=1 to 100 do + if x=a[i] then + SEQB:= i; + exit; + end; {fin del procedimiento} + +{----------------------------------------------------------} +{busqueda secuencial con traslado al frente del elemento} + +function MRU(var a:tipovector ; x:integer): integer; + var + i: integer; cambio: integer; + begin + for i:=1 to 100 do + if x=a[i] then + begin + cambio:=a[i]; + a[i]:= a[1]; + a[1]:=cambio; + MRU:= i; + exit; + end; + end; {fin del procedimiento} + +{----------------------------------------------------------} +{busqueda secuencial con trasposicion al elemento anterior} + +function MFU(var a:tipovector; x:integer): integer; + var + i: integer; cambio: integer; + begin; + if x=a[1] then exit; + for i:=1 to 100 do + if x=a[i] then + begin; + cambio:=a[i];; + a[i]:=a[i-1]; + a[i-1]:=cambio; + MFU:=i; + exit; + end; + end; {fin del procedimiento} + +{----------------------------------------------------------} +{busqueda binaria - recursiva} + +function BINR(var a:tipovector;clave:integer;Min,Max,Ct:integer):integer; +var + medio:integer; +begin + inc(Ct); + medio:=(Min+Max) div 2; + if (Min <= Max) and (a[medio] <> clave) then + begin + if clave < a[medio] + then + begin + Max:=medio-1; + end + else + begin + Min:=medio+1; + end; + ct:=BINR(a,clave,Min,Max,ct); + end; +BINR:=ct; +end; {fin del procedimiento} + +{----------------------------------------------------------} +{busqueda por saltos} + +function SALT (var a: tipovector; x,Min,Max,salto:integer): integer; + var + prop,i: integer; + begin +prop:=round(Max/salto); +for i:=Min to (prop) do + if x=a[i*salto] then + begin + SALT:=i; + exit; + + end + else if x1 then + salto:=salto div 2 + else salto :=1; {por si acaso llego a uno antes de hallar el valor} + i:=SALT(a,x,Min,Max,salto); + exit; + end; + + + + end; {fin del procedimiento} + +{----------------------------------------------------------} + + +{----------------------------------------------------------} +{busqueda por interpolacion - recursiva} +{Este procedimiento realiza la busque de un numero n en un vector vec (el +cual debe encontrarse ordenado de menor a mayor) y devuelve un valor cont +que aclara cuantos ciclos de busqueda realizo} + +function INTR (var vec:tipovector;n:integer;PriInd,UltInd,Ct:integer):integer; +var + r,prinum,ultnum:integer; + numerador,denominador:word; + pend,y:real; + +Begin + + prinum:=vec[priind]; + ultnum:=vec[ultind]; + inc(Ct); + + begin + if ultnum=prinum then INTR:=ct else + begin + NUMERADOR:=ultind-priind; + DENOMINADOR:=ultnum-prinum; + pend:=NUMERADOR/DENOMINADOR; + y:=pend*n-pend*prinum+priind; {desarrollo de la ecuacion de una recta + que pasa por dos puntos} + r:=round(y); + if vec[r]=n then INTR:=ct + else begin + if vec[r]>n then ultind:=r-1 + else priind:=r+1; + ct:=INTR(vec,n,priind,ultind,ct); + end; + + + end; + end; +end; {fin del procedimiento} + +{----------------------------------------------------------} +{busqueda por interpolacion + secuencial} +{Este procedimiento realiza la busque de un numero n en un vector vec (el +cual debe encontrarse ordenado de menor a mayor). Realiza una busqueda por +interpolacio y si no lo encuentra lo buscaca por la busqueda secuencial +y devuelve un valor priind que aclara cuantos ciclos de busqueda realizo} + +function sec_de_intysec (var v:tipovector;k:integer;x:integer):integer; + +{usada posteriormente} + +var p,n,busc:integer; + +Begin + + if v[x]k) do + begin + inc(p); + inc(busc); + end; +sec_de_intysec:=busc; +end; {fin del procedimiento} + +function INTS(var vec:tipovector;n:integer):integer; +{esta es la funcion que se usará en el programa principal} +var + + r,priind,ultind,prinum,ultnum:integer; + pend,y:real; + +Begin + + priind:=low(vec); + + ultind:=high(vec); + prinum:=vec[priind]; + ultnum:=vec[ultind]; + pend:=(ultind-priind)/(ultnum-prinum); + y:=pend*n; + r:=round(y); + if r<=0 then r:=priind; + if r>ultind then r:=ultind; + if vec[r]<>n then INTS:=sec_de_intysec (vec,n,r); +end; {fin del procedimiento} + +{----------------------------------------------------------} +{programa principal} +{----------------------------------------------------------} + +begin + + + +clrscr; + +Presentacion; + +Tipo_busqueda (Tipo_b); {define el nombre de las busquedas que se van a usar} +Randomize; {inicializa la funcion random} + +{por cada distribucion de probabilidades se deberá generar un ciclo} + +for i:=1 to 6 do + begin + {inicializacion del numero de consultas} + for caso:=1 to 8 do Consultas[caso]:=0; + + {creacion del vector original} + vectoraleatorio(100,vector); + {carga de probalidades} + perm(i,r,s,t); + + clrscr; + + textbackground(black); + for a:=1 to 80 do for b:=1 to 5 do imprime_en(a,b,' '); + textcolor(white); + imprime_en(5,5,'DISTRIBUCION DE PROBABILIDADES'); + + + textbackground(white+blink); + textcolor(black); + for a:=1 to 80 do for b:=6 to 11 do imprime_en(a,b,' '); + imprime_en(5,6,'ALTERNATIVA'); + str(i,linea_t); + imprime_en(17,6,linea_t); + imprime_en(5,8,'SECCION>>'); + imprime_en(5,9,'1ERA.:'); + imprime_en(5,10,'2DA:'); + imprime_en(5,11,'3RA.:'); + + Str(round(r*100),linea_t); + imprime_en(12,9,linea_t); + Str(round(s*100),linea_t); + imprime_en(12,10,linea_t); + Str(round(t*100),linea_t); + imprime_en(12,11,linea_t); + + textbackground(cyan); + for a:=1 to 80 do imprime_en(a,7,' '); + + Muestra_barra(green,r,9); + Muestra_barra(red,s,10); + Muestra_barra(blue,t,11); + textbackground(white); + textbackground(cyan); + textcolor(black); + + {carga de referencias} + Asignar_Referencia (ref_vector,vector); + + for ciclo:=1 to 10000 do + begin + x:=subindice(random,r,s,t,30,60,100); + for caso:=1 to 8 do + busqueda[caso]:=valor(x,ref_vector[caso]); + {asigna para cada vector el valor correspondiente + al subindice hallado previamente} + consultas[1]:=SEQB(ref_vector[1],busqueda[1]); + consultas[2]:=MRU(ref_vector[2],busqueda[2]); + consultas[3]:=MFU(ref_vector[3],busqueda[3]); + consultas[4]:=SEQB(ref_vector[4],busqueda[4]); + consultas[5]:=BINR(ref_vector[5],busqueda[5],primera,ultima,0); + consultas[6]:=SALT(ref_vector[6],busqueda[6],1,100,2); + consultas[7]:=INTR(ref_vector[7],busqueda[7],primera,ultima,0); + consultas[8]:=INTS(ref_vector[8],busqueda[8]); + + {en caso de estar en un valor "estadistico"} + if (ciclo=100) or (ciclo=500) or (ciclo=1000) or (ciclo=5000) or (ciclo=10000) then + for caso := 1 to 8 do + Graba_en_Archivo (ciclo,ref_vector[caso],consultas[caso],tipo_b[caso],i); +{esto es una sola instruccion} + end; + end; + {Pantalla de salida} + clrscr; + textbackground(black); + for a:=8 to 72 do for b:=10 to 15 do imprime_en(a,b,' '); + textbackground(white); + for a:=7 to 71 do for b:=11 to 17 do imprime_en(a,b,' '); + textcolor(black); + + Imprime_en(10,12,'El programa programa finaliz¢ exitosamente.'); + Imprime_en(10,13,'Busque los resultados en la Raiz de su disco local (C:\)'); + Imprime_en(10,14,''); + Salida; {cartel de salida} + + +end. {fin del programa} + diff --git a/busq_l.pas b/busq_l.pas new file mode 100644 index 0000000..8aeb0a7 --- /dev/null +++ b/busq_l.pas @@ -0,0 +1,217 @@ + (**************************************) + (**************************************) + (** **) + (** ALGORITMOS DE BUSQUEDA EN PASCAL **) + (** **) + (**************************************) + (**************************************) + +(*************************************************************************** + * + * Busqueda Secuencial + * + * Recorre el vector y compara hasta encontrar el elemento. + * Devuelve el indice del elemento. + * + ***************************************************************************) + +function bSecuencial(var v: Vector; { Vector en donde se va a buscar } + d: Dato) { Dato a buscar (igual que el elemento de v } + : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta } + + var + i, resultado: Integer; + + begin + resultado := 0; + for i := 1 to TAM do { TAM es el tama¤o del vector } + if v[i] = d then begin { Si encontro el dato d en v ... } + resultado := i; { Asigna el indice actual al resultado } + break; { Finaliza el ciclo for } + end; { if } + bSecuencial := resultado; + end; { function bSecuencial } + +{===========================================================================} + +(*************************************************************************** + * + * Busqueda Secuencial Auto-organizada moviendo al frente el elemento encontrado + * + * Recorre el vector y compara hasta encontrar el elemento. Al encontrar el + * elemento, lo mueve automaticamente al inicio del vector. + * Devuelve true si se encontro o false si no se encontro. + * + ***************************************************************************) + +function bSecuencialAutoOrganizadaMoverAlFrente + (var v: Vector; { Vector en donde se va a buscar } + d: Dato) { Dato a buscar (igual que el elemento de v } + : Boolean; { True si lo encontr¢, False si no lo hizo. La posicion es 1 siempre } + +(*************************************************************************** + * + * Mueve el elemento que se encuentra en el indice i hasta el inicio, + * desplazando al resto de los indices hacia abajo. + * + ***************************************************************************) + + procedure moverAlFrente(var v: Vector; { Vector a procesar } + pos: Integer); { Indice a mover al frente } + + var + tmp: Dato; + i: Integer; + + begin + if pos > 1 then begin + tmp := v[1]; + v[1] := v[pos]; + for i := pos - 2 downto 1 do + v[i+1] := v[i+2]; + v[2] := tmp; + end; { if pos > 1 } + end; { procedure moverAlFrente } + + (*******************************************************************) + + { continuacion de la funcion bSecuencialAutoOrganizadaMoverAlFrente } + + var + i: Integer; + resultado: Boolean; + + begin + resultado := false; + for i := 1 to TAM do { TAM es el tama¤o del vector } + if v[i] = d then begin { Si encontro el dato d en v ... } + moverAlFrente(v, i); { Mueve al frente el elemento en i } + resultado := true; { Asigna true al resultado } + break; { Finaliza el ciclo for } + end; { if } + bSecuencialAutoOrganizadaMoverAlFrente := resultado; + end; { function bSecuencialAutoOrganizadaMoverAlFrente } + +{===========================================================================} + +(*************************************************************************** + * + * Busqueda Secuencial Auto-organizada moviendo el elemento encontrado a la + * posicion del elemento anterior. + * + * Recorre el vector y compara hasta encontrar el elemento. Al encontrar el + * elemento, lo mueve automaticamente a la posicion anterior del vector. + * Devuelve el indice del elemento. + * + ***************************************************************************) + +function bSecuencialAutoOrganizadaMoverAnterior + (var v: Vector; { Vector en donde se va a buscar } + d: Dato) { Dato a buscar (igual que el elemento de v } + : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta } + + var + i, resultado: Integer; + aux: Dato; + + begin + resultado := 0; + if v[1] = d then + resultado := 1 + else + for i := 2 to TAM do { TAM es el tama¤o del vector } + if v[i] = d then { Si encontro el dato d en v ... } + aux := v[i]; { Realiza el intercambio del elemento } + v[i] := v[i-1]; { encontrado con el primer elemento } + v[i-1] := aux; { del vector v } + resultado := i - 1; { Pone como resultado a la nueva posicion de d } + break; { Finaliza el ciclo for } + end; { if } + bSecuencialAutoOrganizadaMoverAnterior := resultado; + end; { function bSecuencialAutoOrganizadaMoverAnterior } + +{===========================================================================} + +(*************************************************************************** + * + * Busqueda Binaria Recursiva. + * + * Requiere que el vector este ordenado de menor a mayor (creciente). + * Parte el vector al medio y compara. Si es igual, lo encontro y devuelve + * la posicion. Si el valor buscado es menor, toma la primera mitad y le + * la segunda mitad y le aplica la funcion recursivamente. + * Devuelve el indice del elemento. + * + ***************************************************************************) + +function bBinariaRecursiva(var v: Vector; { Vector en donde se va a buscar } + ini, { Indice por el cual empieza la busqueda } + fin: Integer;{ Indice por el cual termina la busqueda } + d: Dato) { Dato a buscar (igual que el elemento de v } + : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta } + + var + medio: Integer; + + begin + if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... } + bBinariaRecursiva := 0 { Asigna 0 al resultado, indicando que no encontro el dato } + else begin { Si esta entre los valores ... } + medio := ini + ((fin - ini) div 2); { Parte el vector en dos con el valor medio } + if v[medio] = d then { Si el dato esta en la posicion del medio ... } + bBinariaRecursiva := medio { Asigna a la funcion el valor de dicho indice } + else if v[medio] < d then { Si el valor intermedio es menor que el buscado ... } + { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio } + { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector } + { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces } + { si se encuentra el valor buscado, estara en la segunda mitad del vector } + bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d) + else { Si el valor intermedio es mayor que el buscado ... } + { Igual que el anterior pero lo busca en la primera mitad } + bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d); + end; { if (v[ini] > d) or (v[fin] < d) } + end; { bBinariaRecursiva } + +{===========================================================================} + +(*************************************************************************** + * + * Busqueda Binaria Recursiva. + * + * Requiere que el vector este ordenado de menor a mayor (creciente). + * Parte el vector al medio y compara. Si es igual, lo encontro y devuelve + * la posicion. Si el valor buscado es menor, toma la primera mitad y le + * la segunda mitad y le aplica la funcion recursivamente. + * Devuelve el indice del elemento. + * + ***************************************************************************) + +function bInterpolacionRecursiva + (var v: Vector; { Vector en donde se va a buscar } + ini, { Indice por el cual empieza la busqueda } + fin: Integer;{ Indice por el cual termina la busqueda } + d: Dato) { Dato a buscar (igual que el elemento de v } + : Integer; { Indice en donde se encuentra el dato buscado o cero si no esta } + + var + medio: Integer; + + begin + if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... } + bBinariaRecursiva := 0 { Asigna 0 al resultado, indicando que no encontro el dato } + else begin { Si esta entre los valores ... } + medio := ini + ((fin - ini) div 2); { Parte el vector en dos con el valor medio } + if v[medio] = d then { Si el dato esta en la posicion del medio ... } + bBinariaRecursiva := medio { Asigna a la funcion el valor de dicho indice } + else if v[medio] < d then { Si el valor intermedio es menor que el buscado ... } + { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio } + { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector } + { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces } + { si se encuentra el valor buscado, estara en la segunda mitad del vector } + bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d) + else { Si el valor intermedio es mayor que el buscado ... } + { Igual que el anterior pero lo busca en la primera mitad } + bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d); + end; { if (v[ini] > d) or (v[fin] < d) } + end; { bBinariaRecursiva } + diff --git a/datos.txt b/datos.txt new file mode 100644 index 0000000..6687659 --- /dev/null +++ b/datos.txt @@ -0,0 +1,47 @@ +233 +44 +3433 +34 +23 +1 +55 +-12 +9988 +8 +88 +23 +2331 +1232 +232 +232 +121 +23 +-23 +-123 +-11231 +12 +1233 +123 +31 +1 +12233 +123 +-231 +653 +-653 +5334 +-55 +-53445 +3453 +4567 +45456 +7777 +545 +-767 +-563 +345 +6555 +-45 +5658 +4585 +334 \ No newline at end of file diff --git a/docs/Binary tree reorganization hashing insertion.htm b/docs/Binary tree reorganization hashing insertion.htm new file mode 100644 index 0000000..76ae4c7 --- /dev/null +++ b/docs/Binary tree reorganization hashing insertion.htm @@ -0,0 +1,79 @@ + +Binary tree reorganization hashing: insertion + + +

+

+ + +
+ +
+ +
+
+ +
+

+
+

Binary tree reorganization hashing: insertion +


+
+ + +
+ +
+ + procedure insert( key : typekey; var r : dataarray ); + var i, inc, init, j : integer; + + function SearchMove ( init, inc, level : integer ) : integer; + {*** Find the first hole (empty location) at the given depth + in the binary tree spanned by a key ***} + label 999; + var i, inc1, j, k : integer; + begin + i := (init + inc*level) mod m; + if empty(r[i]) or deleted(r[i]) then SearchMove := i + else begin + for j:=level-1 downto 0 do begin + i := (init + inc*j) mod m; + inc1 := increment( r[i].k ); + k := SearchMove( (i+inc1) mod m, inc1, level-j-1 ); + if k>-1 then begin + {*** A hole was found, move forward ***} + r[k] := r[i]; + SearchMove := i; + goto 999 {*** return ***} + end + end; + {*** Could not find hole ***} + SearchMove := -1; + end; + 999: + end; + + begin + init := hashfunction( key ); + inc := increment( key ); + i := 0; j := -1; + while (i<=n) and (j<0) and (n<m) do begin + j := SearchMove( init, inc, i ); + i := i+1 + end; + if j>-1 then begin + {*** A hole was found, insert key ***} + r[j].k := key; + n := n+1 + end + else Error {*** table is full ***}; + end; +
+
+

Pascal source (3382.ins.p)

+

+


+© Addison-Wesley Publishing Co. Inc. +
+ diff --git a/docs/Brent's reorganization scheme insertion.htm b/docs/Brent's reorganization scheme insertion.htm new file mode 100644 index 0000000..f301d01 --- /dev/null +++ b/docs/Brent's reorganization scheme insertion.htm @@ -0,0 +1,62 @@ + +Brent's reorganization scheme: insertion + + +

+

+ + +[Home]
+ +[Chapter]
+ +[Contents]
+ + + +[Previous Algorithm]
+ +[Next Algorithm]
+

+
+

Brent's reorganization scheme: insertion +


+
+ + +
+ +
+ + procedure insert( key : typekey; var r : dataarray ); + label 999; + var i, ii, inc, init, j, jj : integer; + + begin + init := hashfunction( key ); + inc := increment( key ); + for i:=0 to n do + for j:=i downto 0 do begin + jj := (init + inc*j) mod m; + ii := (jj + increment(r[jj].k) * (i-j)) mod m; + if empty(r[ii]) or deleted(r[ii]) then begin + {*** move record forward ***} + r[ii] := r[jj]; + {*** insert new in r[jj] ***} + r[jj].k := key; + n := n+1; + goto 999 {*** return ***} + end + end; + Error {*** table full ***}; + 999: + end; +
+
+

C source (3381.ins.c) Pascal source (3381.ins.p) +

+

+


+© Addison-Wesley Publishing Co. Inc. +
+ diff --git a/docs/Double hashing insertion.htm b/docs/Double hashing insertion.htm new file mode 100644 index 0000000..d8c54d1 --- /dev/null +++ b/docs/Double hashing insertion.htm @@ -0,0 +1,57 @@ + +Double hashing: insertion + + +

+

+ + +[Home]
+ +[Chapter]
+ +[Contents]
+ + + +[Previous Algorithm]
+ +[Next Algorithm]
+

+
+

Double hashing: insertion +


+
+ + +
+ +
+ + procedure insert( key : typekey; var r : dataarray ); + var i, inc, last : integer; + + begin + i := hashfunction( key ) ; + inc := increment( key ); + last := (i+(m-1)*inc) mod m; + while (i<>last) and (not empty(r[i])) + and (not deleted(r[i])) and (r[i].k<>key) do + i := (i+inc) mod m; + if empty(r[i]) or deleted(r[i]) then + begin + {*** insert here ***} + r[i].k := key; + n := n+1 + end + else Error {*** table full, or key already in table ***}; + end; +
+
+

C source (335.ins.c) Pascal source (335.ins.p) +

+

+


+© Addison-Wesley Publishing Co. Inc. +
+ diff --git a/docs/Hashing.htm b/docs/Hashing.htm new file mode 100644 index 0000000..a25def2 --- /dev/null +++ b/docs/Hashing.htm @@ -0,0 +1,415 @@ + + +Hashing + + + + + + + + + + + +
home | Hashing
+ + + + + + + +
+

Hashing

V 0.1 +

Hashing is a method to store data in an array so that storing, + searching, inserting and deleting data is fast (in theory it's O(1)). For + this every record needs an unique key. +

The basic idea is not to search for the correct position of a record + with comparisons but to compute the position within the array. The + function that returns the position is called the 'hash function' and the + array is called a 'hash table'. +

In our examples our key is an integer value as is the actual data. +

[note that I use pascal syntax since this is easily readable by + everybody I asume] + 


+type
+  THash_Record = record
+    key   : integer;
+    data  : integer;
+  end;
+

+      
the hash table now looks like this: 
+      

+const
+  HASH_LENGTH = 100; { the length of the hash table and so the }
+                     { maximum number of records that can be stored }
+
+type
+  THash_Table = array[0..HASH_LENGTH-1] of THash_Record;
+

+      
If we know that the key is in a small range we could use the key itself 
+      as an index (also called hash address) for our array. However this is very 
+      rarely the case so we have to find some kind of hash function. A very 
+      common and not so bad function is a simple MODulo function: 
+      

+function Hash_Function(key : integer) : integer;
+begin
+  Hash_Function := key MOD HASH_LENGTH;
+end;
+

+      
If we now want to insert a record into the hash we could do it this 
+      way: 
+      

+procedure Insert_Into_Hash( VAR hash : THash_table;
+                                rec  : THash_record);
+begin
+  hash[ Hash_Function(rec.key) ] := rec;
+end;
+

+      
But wait! What happens if two different keys return the same hash 
+      address from the hash function? Well if you have a good hash function this 
+      happens very rarely but it can and will happen. There are two ways to 
+      handle a so called 'hash collision'. 
+      

+      
    
+        
  • collision handling within the hash table 
+        
  • collision handling outside of the hash table 

+      
COLLISION HANDLING OUTSIDE OF THE HASH TABLE ...
... means that 
+      our hash table no longer is an array of records but instead it is an array 
+      of pointers. Each pointer points to a linked list of the hash records. 
+      

+type
+  PHash_Record = ^THash_Record; {a pointer type to the type THash_record }
+  THash_Record = record
+    key   : integer;
+    data  : integer;
+    next  : PHash_Record; { the pointer to the next item in the list }
+  end;
+
+  THash_Table = array[0..HASH_LENGTH-1] of PHash_Record;
+

+      
If now a key return the same 'hash address' like an already stored item 
+      we simply insert the record into the list of this hash entry. 
+      

+procedure Insert_Into_Hash( VAR hash : THash_Table;
+                                rec  : THash_Record);
+VAR
+  hash_address : integer;
+  item         : PHash_record;
+begin
+  hash_address := Hash_Function(rec.key);
+
+  new(item);
+  item^ := rec;
+  item^.next = hash[ hash_address ];
+  hash[ hash_address ] := item;
+end;
+

+      
To get an item out of the hash you can first determine it's hash 
+      address with the hash function and then use a classical linear search to 
+      find the item you want. If you keep the list sorted you could speed read 
+      access up for some cost at inserting items. 
+      

+procedure Get_From_Hash(     hash : THash_Table;
+                             key  : integer;
+                         VAR rec  : THash_Record);
+VAR
+  hash_address : integer;
+  item         : PHash_record;
+begin
+  hash_address := Hash_Function(rec.key);
+
+  item := hash[ hash_address ];
+  while (item <> nil) and (item^.key <> key) do { make sure you have short    }
+    item := item^.next;                         { curcuit bool evaluation, so }
+                                                { that the second comparison  }
+                                                { is never made if item is nil}
+  if (item<>nil) then
+    rec := item^
+  else
+    { ITEM NOT IN LIST! }
+end;
+

+      
If you want to delete an item, you simply remove it from the linked 
+      list: 
+      

+procedure Remove_From_Hash( VAR hash : THash_Table;
+                                key  : integer);
+VAR
+  hash_address : integer;
+  item         : PHash_record;
+  tmp          : PHash_record;
+begin
+  hash_address := Hash_Function(rec.key);
+
+  item := hash[ hash_address ];
+  if (item<>nil) and (item^.key = key) then       { make sure you have short    }
+  begin                                           { curcuit bool evaluation, so }
+    hash[ hash_address ] := item^.next            { that the second comparison  }
+    dispose(item); { deallocate memory }          { is never made if item is nil}
+  end
+  else
+  begin
+    while (item^.next <> nil) and
+          (item^.next^.key <> key) do
+      item := item^.next;
+
+    if (item^.next <> nil) then
+    begin
+      tmp := item^.next;
+      item^.next := tmp^.next;
+      dispose(tmp); { deallocate memory }
+    end
+    else
+      { ITEM NOT IN LIST! }
+  end;
+end;
+

+      
COLLISION HANDLING WITHIN THE HASH TABLE...
... is totally 
+      different. Instead of having a list which can grow up to an arbitrary size 
+      all the data is stored in the hash table itself. This means that we can 
+      never under any circumstance store more records in the hash as our hash is 
+      long. This is obvious but I wanted to point it out. 
+      
    
+        
  • So what to do if the position we want to save our new record to is 
+        already occupied? 
+        
  • And how do we know that it is occupied anyway? 

+      
Let's first solve the latter question since it is quite simply. We have 
+      to store wheter a certain hash element is occupied. We do this by changing 
+      the THash_Record record: 

+type
+  THash_Occupied = (ho_empty, ho_occupied);
+  
+  THash_Record = record
+    occupied : THash_Occupied;
+    key      : integer;
+    data     : integer;
+  end;
+

+      
So now to the former question: What to do if an address is already 
+      occupied. The answer is straightforward: The have to store it at a 
+      different address :) There are several methods to find a new, empty 
+      address. Note that this address should have something to do with the key 
+      since we want to be able to find it easily later. 
+      
linear probing:
We add a constant number (usually 1) to the 
+      position the hash_function returns until we have found an empty place: 

+  pos0 := Hash_Function(key);
+  i := 0;
+  repeat
+    hash_address := (pos0 + i) MOD HASH_LENGTH;
+    inc(i);
+  until Hash[ hash_address].occupied <> ho_occupied;
+

+      
sqared probing:
is very similar to linear probing but we do not 
+      simply add the increasing value but we add it's square. This is usually 
+      better than linear probing: 

+  pos0 := Hash_Function(key);
+  i := 0;
+  repeat
+    hash_address := (pos0 + i*i) MOD HASH_LENGTH;
+    inc(i);
+  until Hash[ hash_address].occupied <> ho_occupied;
+

+      
One disadvantage of all those probing methods is that they tend to 
+      build clusters aroung already occupied areas of the hash table. A soluton 
+      to this problem is 
+      
double hashing:
The idea is to add a value to the hash address 
+      that depends on the key of the item, so that the probing order is spezific 
+      to the key: 

+  hash_address := Hash_Function(key);
+  while Hash[ hash_address].occupied = ho_occupied do
+    hash_address := (hash_address + Hash_Function(key)) MOD HASH_LENGTH;
+  
+  double_hashing := hash_address;
+

+      
Hash_Function(rec.key) and HASH_LENGTH should have a greatest common 
+      factor of 1 so that the complete hash table is probed. This is guaranteed 
+      if HASH_LENGTH is a prime number. 
+      
 
+      
So inserting an item looks like this: 

+procedure Insert_Into_Hash( VAR hash : THash_Table;
+                                rec  : THash_Record);
+VAR
+  hash_address;
+begin
+  
+  <get the hash address, probing for an empty entry>
+  hash[ hash_address ] := rec;
+  rec.occupied := ho_occupied;
+end;
+

+      
To search for an item, you have to first get the hash_address and then 
+      probe until you either find an empty entry or the searched entry. 
+      
Deleting an item is rather simple: Search for the address like when you 
+      search the item and set the occupied value to ho_occupied. But wait! This 
+      would break our searching, since we search until we either find the object 
+      or an empty entry. 
+      
The solution is to modify THash_Occupied a bit so that it reads: 

+  THash_Occupied = (ho_empty, ho_occupied, ho_deleted);
+

+      
If we delete an item we set the occupied state to ho_deleted. When 
+      inserting Items we treat ho_deleted like it was ho_empty and when 
+      searching for an item we treat as if it was ho_occupied. 
+      
 
+      
 
+      
 
+      
 
+      
 
+      
If you have questions, feel free to contact me! 

+      

+    
Last 
+      modified: Sun Aug 1 20:26:14 CEST 1999 by Peter Palfrader 
+  

diff --git a/docs/Heapsort.htm b/docs/Heapsort.htm
new file mode 100644
index 0000000..b3ca70f
--- /dev/null
+++ b/docs/Heapsort.htm
@@ -0,0 +1,54 @@
+
+Heapsort
+
+
+

+

+
+
+[Home]

+
+[Chapter]

+
+[Contents]

+
+
+
+[Previous Algorithm]

+
+[Next Algorithm]

+

+

+
Heapsort
+


+

+
+
+

+
+

+
+     procedure sort( var r : ArrayToSort; lo, up : integer );
+
+     var  i : integer;
+          tempr : ArrayEntry;
+     begin
+     {*** construct heap ***}
+     for i := (up div 2) downto 2 do    siftup(r,i,up);
+     {*** repeatedly extract maximum ***}
+     for i := up downto 2 do begin
+          siftup(r,1,i);
+          tempr := r[1];
+          r[1] := r[i];
+          r[i] := tempr
+          end
+     end;
+

+

+
C source (415.sort.c)  Pascal source (415.sort.p)  
+

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Interpolation (in-place) sort.htm b/docs/Interpolation (in-place) sort.htm
new file mode 100644
index 0000000..98158e0
--- /dev/null
+++ b/docs/Interpolation (in-place) sort.htm	
@@ -0,0 +1,63 @@
+
+Interpolation (in-place) sort
+
+
+

+

+
+
+[Home]

+
+[Contents]

+
+[Chapter]

+[Previous Algorithm]

+
+[Next Algorithm]

+
+

+

+
Interpolation (in-place) sort
+


+

+
+
+

+
+

+
+     sort( r, lo, up )
+     ArrayToSort r;
+     int lo, up;
+
+     {ArrayIndices iwk;
+     ArrayEntry tempr;
+     int i, j;
+
+     for (i=lo; i<=up; i++)   {iwk[i] = 0;   r[i].k = -r[i].k;}
+     iwk[lo] = lo-1;
+     for (i=lo; i<=up; i++)   iwk[ phi(-r[i].k,lo,up) ]++;
+     for (i=lo; i<up;  i++)   iwk[i+1] += iwk[i];
+     for (i=up; i>=lo; i--)   if ( r[i].k<0 )
+          do   {
+               r[i].k = -r[i].k;
+               j = iwk[ phi( r[i].k, lo, up ) ]--;
+               tempr = r[i];
+               r[i] = r[j];
+               r[j] = tempr;
+               } while ( i != j );
+     for ( i=up-1; i>=lo; i-- ) {
+          tempr = r[i];
+          for ( j=i+1; j<=up && (tempr.k>r[j].k); j++ )
+               r[j-1] = r[j];
+          r[j-1] = tempr;
+          }
+     };
+

+

+
C source (416b.sort.c)  

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Linear probing hashing search.htm b/docs/Linear probing hashing search.htm
new file mode 100644
index 0000000..dd10d62
--- /dev/null
+++ b/docs/Linear probing hashing search.htm	
@@ -0,0 +1,50 @@
+
+Linear probing hashing: search
+
+
+

+

+
+
+[Home]

+
+[Chapter]

+
+[Contents]

+
+
+
+[Previous Algorithm]

+
+[Next Algorithm]

+

+

+
Linear probing hashing: search
+


+

+
+
+

+
+

+
+     function search( key : typekey; var r : dataarray ) : integer;
+     var i, last : integer;
+
+     begin
+     i := hashfunction( key ) ;
+     last := (i+n-1) mod m;
+     while (i<>last) and (not empty(r[i])) and (r[i].k<>key) do
+          i := (i+1) mod m;
+     if r[i].k=key  then search := i    {*** found(r[i]) ***}
+               else search := -1;  {*** notfound(key) ***}
+     end;
+

+

+
C source (334.srch.c)  Pascal source (334.srch.p)  
+

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Linear probing sort.htm b/docs/Linear probing sort.htm
new file mode 100644
index 0000000..17bafd1
--- /dev/null
+++ b/docs/Linear probing sort.htm	
@@ -0,0 +1,67 @@
+
+Linear probing sort
+
+
+

+

+
+
+[Home]

+
+[Chapter]

+
+[Contents]

+
+
+
+[Previous Algorithm]

+
+[Next Algorithm]

+

+

+
Linear probing sort
+


+

+
+
+

+
+

+
+     procedure sort( var r : ArrayToSort; lo, up : integer );
+
+     var  i, j : integer;
+          r1 : ArrayToSort;
+     begin
+     r1 := r;
+     for j:=lo to UppBoundr do r[j].k := NoKey;
+     for j:=lo to up do begin
+          i := phi(r1[j].k,lo,m);
+          while r[i].k <> NoKey do begin
+               if r1[j].k < r[i].k then begin
+                    r1[j-1] := r[i];
+                    r[i] := r1[j];
+                    r1[j] := r1[j-1]
+                    end;
+               i := i+1;
+               if i > UppBoundr then Error
+               end;
+          r[i] := r1[j]
+          end;
+     i := lo-1;
+     for j:=lo to UppBoundr do
+          if r[j].k <> NoKey then begin
+               i := i+1;
+               r[i] := r[j]
+               end;
+     for j:=i+1 to UppBoundr do    r[j].k := NoKey;
+     end;
+

+

+
C source (417.sort.c)  Pascal source (417.sort.p)  
+

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Ordered hashing insertion.htm b/docs/Ordered hashing insertion.htm
new file mode 100644
index 0000000..ee97573
--- /dev/null
+++ b/docs/Ordered hashing insertion.htm	
@@ -0,0 +1,59 @@
+
+Ordered hashing: insertion
+
+
+

+

+
+
+

+
+

+
+

+

+
+

+

+

+
Ordered hashing: insertion
+


+

+
+
+

+
+

+
+     procedure insert( key : typekey; var r : dataarray );
+     var i : integer;
+         temp : typekey;
+
+     begin
+     if n>=m then   Error     {*** table is full ***}
+     else begin
+          i := hashfunction( key ) ;
+          while (not empty(r[i])) and (not deleted(r[i]))
+               and (r[i].k<>key) do begin
+               if r[i].k > key then begin
+                    {*** Exchange key and continue ***}
+                    temp := key;   key := r[i].k; r[i].k := temp
+                    end;
+               i := (i+increment(key)) mod m
+               end;
+          if empty(r[i]) or deleted(r[i]) then begin
+               {*** do insertion ***}
+               r[i].k := key;
+               n := n+1
+               end
+          else Error     {*** key already in table ***}
+          end
+     end;
+

+

+
Pascal source (337.ins.p)  

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Quadratic hashing insertion.htm b/docs/Quadratic hashing insertion.htm
new file mode 100644
index 0000000..f3c4e70
--- /dev/null
+++ b/docs/Quadratic hashing insertion.htm	
@@ -0,0 +1,54 @@
+
+Quadratic hashing: insertion
+
+
+

+

+
+
+

+
+

+
+

+

+
+

+

+

+
Quadratic hashing: insertion
+


+

+
+
+

+
+

+
+     procedure insert( key : typekey; var r : dataarray );
+     var i, inc : integer;
+
+     begin
+     i := hashfunction( key );
+     inc := 0;
+     while (inc<m) and (not empty(r[i])) and
+          (not deleted(r[i]))  and (r[i].k<>key) do begin
+               i := (i+inc+1) mod m;
+               inc := inc + 2;
+               end;
+     if empty(r[i]) or deleted(r[i]) then
+               begin
+               {*** insert here ***}
+               r[i].k := key;
+               n := n+1
+               end
+     else Error {*** table full, or key already in table ***};
+     end;
+

+

+
Pascal source (336.ins.p)  

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Shellsort.htm b/docs/Shellsort.htm
new file mode 100644
index 0000000..8d92a5e
--- /dev/null
+++ b/docs/Shellsort.htm
@@ -0,0 +1,64 @@
+
+Shellsort
+
+
+

+

+
+
+[Home]

+
+[Chapter]

+
+[Contents]

+
+
+
+[Previous Algorithm]

+
+[Next Algorithm]

+

+

+
Shellsort
+


+

+
+
+

+
+

+
+     procedure sort( var r : ArrayToSort; lo, up : integer );
+
+     label     999;
+     var  d, i, j : integer;
+          tempr : ArrayEntry;
+     begin
+     d := up-lo+1;
+     while d>1 do begin
+          if d<5 then    d := 1
+               else d := trunc( 0.45454*d );
+          {*** Do linear insertion sort in steps size d ***}
+          for i:=up-d downto lo do begin
+               tempr := r[i];
+               j := i+d;
+               while j <= up do
+                    if tempr.k > r[j].k then begin
+                         r[j-d] := r[j];
+                         j := j+d
+                         end
+                    else goto 999;  {*** break ***}
+               999:
+               r[j-d] := tempr
+               end
+          end
+     end;
+

+

+
C source (414.sort.c)  Pascal source (414.sort.p)  
+

+

+


+© Addison-Wesley Publishing Co. Inc.
+

+
diff --git a/docs/Stacks, Queues, Lists and Hash Tables.htm b/docs/Stacks, Queues, Lists and Hash Tables.htm
new file mode 100644
index 0000000..15e1b04
--- /dev/null
+++ b/docs/Stacks, Queues, Lists and Hash Tables.htm	
@@ -0,0 +1,436 @@
+
+
+Stacks, Queues, Lists and Hash Tables
+
+
+
+
+
Menu bar
Data Structures 
+And Number Systems
© Copyright Brian Brown, 1984-1999. All rights 
+reserved.

+
Part 5
index prev 
+

+

+
+

+
STACKS
A stack is used to provide temporary storage space for 
+values. It is defined as a data structure which operates on a first in, last 
+out basis. Its uses a single pointer (index) to keep track of the 
+information in the stack. 

+
The basic operations associated with a stack are, 

+
    
+  
  • insert (push) an item onto the stack 
+  
  • remove (pop) an item from the stack 

+
The following diagram shows an empty stack of four locations. It looks just 
+like an array, and it has an index pointer pointing to the beginning of the 
+stack (called the TOP of the stack). 

+     +--------+
+     |        |   <------- Stack Pointer       
+     +--------+ 
+     |        |         
+     +--------+ 
+     |        |         
+     +--------+
+     |        |          
+     +--------+
+
+

+
Pushing items onto the stack
The stack pointer is considered to be 
+pointing to a free (empty) slot in the stack. A push operation thus involves 
+copying data into the empty slot of the stack, then adjusting the stack pointer 
+to point to the next free slot. 

+   Module Push
+        stack[stack_pointer] = data;
+        stack_pointer = stack_pointer + 1;
+   Module End
+
+

+
Lets push the value 45 onto the stack. [Note: The stack could hold any data 
+type, not necessarily decimal numbers. We have used numbers for simplicity]. The 
+stack now looks like 

+     +--------+ 
+     |   45   |         
+     +--------+
+     |        |   <------- Stack Pointer       
+     +--------+ 
+     |        |         
+     +--------+ 
+     |        |         
+     +--------+
+
+

+
Note how the stack pointer has been adjusted to point to the next free 
+location in the stack. [Note: for the time being we are ignoring certain 
+problems. We will address these shortly!!!]. 

+
Removing items from the stack
To remove an item, first decrement 
+(subtract 1 from) the stack pointer, then extract the data from that position in 
+the stack. 

+   Module Remove
+        stack_pointer = stack_pointer - 1;
+        data = stack[stack_pointer];
+   Module End
+
+

+
Time now to address the problems of the above implementation
There 
+are a number of problems associated with the above routines for pushing and 
+removing items. 

+
    
+  
  • the push module does not check to see if the stack is full 
+  
  • the remove module does not check to see if the stack is empty 

+
There are a number of solutions to this problem. We shall present a 
+simplified solution. We do not argue that it is the best, just that it is one of 
+a possible number of solutions. 

+   Comment: Assume that the array elements begin at 1
+   Comment: Assume that the maximum elements of the stack is MAX
+
+   Var: stack[MAX] : Integer;
+
+   Module Initialize
+        stack_pointer = 1;
+   Module End
+
+   Module Push
+        if stack_pointer >= MAX then
+           return error
+        else begin
+           stack[stack_pointer] = data;
+           stack_pointer = stack_pointer + 1;
+        end
+   Module End
+
+   Module Remove
+        if stack_pointer <= 1 then
+           return error
+        else begin
+           stack_pointer = stack_pointer - 1;
+           data = stack[stack_pointer];
+        end
+   Module End
+
+

+

+
+

+
QUEUES
Everybody has experience with queues as they are common 
+place. Queues occur in cafeterias, petrol stations, shopping centres, anyplace 
+where many people (customers) line up for few resources (cashier's, salespeople, 
+petrol pumps etc). 

+
The purpose of a queue is to provide some form of buffering. Typical uses of 
+queues in computer systems are, 

+
    
+  
  • process management 
+  
  • buffer between the fast computer and a slow printer 

+
A queue is defined as a data structure which holds a series of items to be 
+processed on a first in first out basis (though some queues can be sorted 
+in priority). The operations associated with a queue are, 

+
    
+  
  • initialize the queue 
+  
  • insert an item in the queue 
+  
  • remove an item from the queue 
+  
  • count the number of empty slots in the queue 
+  
  • count the number of items in the queue 

+
The following diagram shows an empty queue. It is identified as a series of 
+ten locations, and two pointers named front and rear. These two 
+pointers keep track of where the front and rear of the queue is. 

+	  1   2   3   4   5   6   7   8   9  10 
+	+---+---+---+---+---+---+---+---+---+---+ 
+	|   |   |   |   |   |   |   |   |   |   | 
+	+---+---+---+---+---+---+---+---+---+---+ 
+	+---+ 
+	| 1 | Front 
+	+---+ 
+	+---+ 
+	| 10| Rear 
+	+---+ 
+ 
+

+
The front pointer is used to delete items, and the rear pointer insert items. 
+Inserting two items called A and B will rearrange the queue to look like, 
 
+	  1   2   3   4   5   6   7   8   9  10 
+	+---+---+---+---+---+---+---+---+---+---+ 
+	| A | B |   |   |   |   |   |   |   |   | 
+	+---+---+---+---+---+---+---+---+---+---+ 
+	+---+ 
+	| 1 | Front 
+	+---+ 
+	+---+ 
+	| 2 | Rear 
+	+---+ 
+
+

+
The pseudo-code for the various queue operations follows. 
 
+	module initialize 
+		count = 0 
+		head = 1 
+		rear = size of queue 
+	end module initialize 
+ 
+	module insert 
+		if count = size of queue 
+			queue is full and do not insert 
+		else 
+		begin 
+			increment count 
+			increment rear 
+			if rear > size of queue 
+				rear = 1 
+			endif 
+			insert data at queue[rear] 
+		endif 
+	end module insert 
+ 
+	module remove 
+		if count = 0 
+			queue is empty and do not remove 
+		else 
+		begin 
+			data = queue[front] 
+			decrement count 
+			increment front 
+			if front > size of queue 
+				front = 1 
+			endif 
+		endif 
+	end module remove 
+
+	module count 
+		return count 
+	end module count 
+ 
+	module free_space 
+		return queue.size - count 
+	end module free_space 
+ 
+ 
+

+
The implementation of this is left to the student as a programming exercise. 
+

+

+
+

+
LINKED LISTS
Data structures can be arranged in memory in a variety 
+of different ways. Each method has advantages and disadvantages. Arrays for 
+example seem easy to use, where each element is stored sequentially in memory. 
+

+
This type of approach is not efficient in larger computer systems, where a 
+number of users share main memory. In such circumstances, there may not be 
+enough contiguous main memory left to hold a sequentially stored data structure 
+like an array (but there could be enough if all the small free blocks were moved 
+into one large block). 

+
One way to overcome this is to link all elements of data together. Data is 
+arranged into records, and a special item is added to each record called a 
+pointer (a link field), which contains a link to the next record etc. Renaming 
+each record as a node and we have a complex data structure called a linked 
+list. 

+
A linked list is a series of nodes connected together via pointers. 
+Pictorially, it looks like, 
 
+	 Node 1          +---+ Node 2        +---+ Node n 
+	+--------+--+    |  +--------+--+    |  +--------+--+ 
+	|        | ------+  |        | ------+  |        |  | 
+	+--------+--+       +--------+--+       +--------+--+ 
+	   Data   Link        Data    Lnk         Data    Lnk 
+ 
+

+
In Pascal, a node definition looks like, 
 
+	type	ptr = ^node; 
+		node =	record 
+			data : string[20]; 
+			next : ptr; 
+		end; 
+ 
+

+
The following Pascal program declares three nodes, inserts data into each of 
+them, then using a pointer, cycles through the chain from node to node printing 
+out the contents of each node. The value 0 is always stored in the last node of 
+a chain, to indicate the end of the list. 
 
+	program linked_list; 
+	type	ptr = ^node; 
+		node = record 
+			data : string[20]; 
+			next : ptr; 
+			end; 
+	var 
+		node1, node2, node3 : node; 
+		nodeptr : ptr; 
+	begin 
+		node1.data := 'Welcome '; 
+		node1.next := @node2; 
+		node2.data := 'to '; 
+		node2.next := @node3; 
+		node3.data := 'Linked Lists.'; 
+		node3.next := nil; 
+		nodeptr := @node1; 
+		while nodeptr <> nil do 
+		begin 
+			write( nodeptr^.data ); 
+			nodeptr := nodeptr^.next; 
+		end; 
+		writeln; 
+	end. 
+ 
+

+
Linked lists are used in a wide variety of applications. 

+
    
+  
  • directory structures 
+  
  • operating systems for process management 
+  
  • data management in data base systems. 

+
An advantage of storing data using a linked list is that the key sequence can 
+be altered by changing the pointers, not by moving data nodes. This means 
+sorting data is quick, but searching is slower as you must follow the chain from 
+node to node. 

+

+
+

+
HASHING
Hashing is a technique used to improve data access times. 
+Rather than sorting the data according to a key, it computes the location of the 
+data from the key. In simple terms, it computes an index value from the 
+key of the desired record. At that index value, the record is 
+stored/retrieved. 

+
If we had an array of 1000 elements, we would expect our hash function (the 
+method used to calculate the index value) to evenly distribute the keys over 
+this range. In practice this is difficult to achieve. It is possible that two 
+different search keys might generate the same hash value (ie, index), and we 
+call this a collision. 

+
The size of the table (array) is generally a prime number, as this has the 
+least probability of creating collisions. 

+
The following code segment defines an array of records in Pascal which will 
+be used to demonstrate hashing. 
 
+	const	size = 511; 
+	type	data = record 
+			name : string[20]; 
+			age : integer; 
+		end; 
+		hashtable = array[1..size] of data; 
+ 
+

+
Next, lets initialize the table with zero's, so this makes it easy to see if 
+information is already stored at a particular element (important when inserting 
+data later). 
 
+	procedure initialize ( var Table : hashtable ); 
+	var i : integer; 
+	begin 
+		for i := 1 to size do 
+		begin 
+			Table[i].name := '                    '; 
+			Table[i].age := 0; 
+		end; 
+	end; 
+ 
+

+
The procedure insert will take the hash value and the data and insert it into 
+the table. If the position is already occupied (ie, a collision occurs) the 
+table will be searched from that point onwards till an empty slot occurs. 
 
+	procedure insert ( Position : integer; Element : data ; var Table : hashtable ); 
+	begin 
+		while Table[Position].name[1] <> ' ' do 
+			Position := (Position + 1) mod size; 
+		Table[Position] := Element; 
+	end; 
+ 
+

+
The procedure hash will generate a hash value from a given data record. In 
+deciding this, it must generate a value between 1 and 511. Obviously, we cannot 
+use the age field of the record, this will generate too many collisions. The 
+best method is to add up the value of all the characters in the persons name, 
+then extract nine bits from it (2^9 = 512) to generate the index value. 

+	procedure hash ( var Position : integer ; Element : data ; var Table : hashtable ); 
+	var i : integer; 
+	begin 
+		i := 1; 
+		position := 0; 
+		while i < 20 do 
+			position := position + ord(Element.name[i]); 
+		position := position mod 511; 
+	end; 
+ 
+

+
The remaining procedures to search and delete are left as a programming 
+exercise for the student. 

+

+
+
INDEXED SEQUENTIAL
This method seeks to make a direct access file 
+appear like a sequence file. The sequencing is achieved via an index table, 
+which holds the keys of the records and their position within the file. 

+
A program reads the index sequentially, and when it locates the key it 
+desires, it reads the record from the indicated position. 

+
The advantages of this method are, 

+
    
+  
  • the records need not be in key sequence 
+  
  • the records may be processed sequentially or directly 

+

+
+
FILE MERGING
This is the process of merging two or more input files 
+into a single output file (which are normally all sequential in nature). The 
+files to be merged are first sorted using the same key sequence, which is 
+preserved in the output file. 

+
A pseudo-code example for a 2-way merge is shown below. 
 
+	program two_way merge 
+	begin 
+		read 1st record of infile1, name as rec1 
+		read 1st record of infile2, name as rec2 
+		while rec1 or rec2 is not an end-of-record 
+		begin 
+			if rec1.key < rec2.key 
+			begin 
+				write rec1 to outfile 
+				read new rec1 from  infile1 
+			end 
+			else 
+			begin 
+				write rec2 to outfile 
+				read new rec2 from infile2 
+			end 
+			endif 
+		endwhile 
+		write end-of-record to outfile 
+	end program two_way merge 
+
+

+

+
+
index prev 
+

+
Home | Other Courses | Feedback | Notes | Tests 

+
© Copyright Brian Brown, 1984-1999. All rights 
+reserved.

diff --git a/docs/Stacks, Queues, Lists and Hash Tables_archivos/dsmenu.gif b/docs/Stacks, Queues, Lists and Hash Tables_archivos/dsmenu.gif
new file mode 100644
index 0000000000000000000000000000000000000000..5a06c7bc25fe2512986b7e78bd87360b07d8262a
GIT binary patch
literal 2749
zcmXAod0fxQAIGPykiyEfg)B{nTq!zK?#iS>HCbodsj{Cg9b~PeLW|OLs8}63M^>#G
zv9ToEiD;D!`7NbGxuZko_wDzaKjtxy$IRpPc)efG*H|Mf6Ju9ND_zuL@**05rG&$3?oJn
z6Nm%EG2#?)A)6Qpj08nO437@51gHdr1c3yx1gQjtgn)#wgs6msBmqgnl0+p*NCZd(
zON2^9NDN2}ON>fPNE}EUOPoqv$WoL9mIRfA7>*NQ0w@83KtLcSkP;{e0t8`#C_#cq
zfJm4~lt_XQKnNy;5+Vo#gki!cVS;c#I3}DDE@Whgz(i0Y#4sX&8K4XZ1_6VZLCTpS03({gFAQq6y8XyBN5Eh8aXvrW62@8qJl9dH22o{9OQjiTV7#57m9LtOf
zjs>SOb(yFTSO_XR&FokB-yfJeybu40<)dV`O4HU9rr(ShH9>D{Rbj@hBj0M;oLN(p
zdHdLRhVv)>r@A3GCQbId6M0z2>8{J1mh#|5O`HY_SNXOH2w+j2Da^<~uZR}Z-@PU`rr;&eJ+3agIi?kX~fr9tbqVe3O#LbpDW6Vl?8}s~1
zeo@{V;?Z>0@>olv(j>jgKct5v{01hqZN3=!%t6r>FJF;=_Dk?_^G!k4wFwJ0wiH}3
z^sM}5rn|xpQoLlTCSUdm5Yak+kd
zu=n%B*dzXF%bY)ay>?mSK*xn0|JnU|d~)K?3in&rZrMEKfVcW5MtvW(*`oBj$g^P7
zqazc16J59brEjtxsOFetEO_14?slNBe@EtWU1phh*eGaJ=Fuq*B^i;=`mA|$yj^4b
z`dRy0l^xK+X4kmIdsaHeSsN)e5Ph|f)(G2b4+z#L7Ef?m9#`$?vM$F-D?vBPv`r`N
zi>s=i?F!H4xG=AjEM#&p1(MJ`!Bc)K-v`yKg9n~lr~7uHgmX44^AocC{$AaY78C=U
zt@kG@dF8~#UCvt*`G?UttGpcAMGIJ0*ZIQhLT@>^H2TM#7m8o{&bjbsOU=%UWnZt}
zzgW@Y`%~fd=d|GW>aMPzF4S5L78F-MzgmB(PW^lj`^QarUZI@+tL~C#-zfK7Y}e!6
zELVNv@0Xs3&hclf)GOk`(Nf){U)rxc-0)X>(Wpr`S{H`B+4Eyc|C>0ucH@UP_trb-{Z8)uN%YCw}gq+z0T&h6O8sm@QI((oCegq
z(~hod{B%u`C&q8sdH&kOx=p!RaQ}?ndD-bPA5331xm)C`{%c|Jo#RbE)rz<-q@-Bd
zz5Af)-ny8GCvjbxl~24HoPEcdck5+T4BA}Jwd+5%E3D7qJwDW}9Hgz78}HGyPVYgU
zovR?9`J2e8`Q^8*3MfEz4gkS3Qmz_w~#cty8L>HRpwGy>_SQMA+F?
zH{{go$6Z=-^up+>8}g|ySByEHES86ZCzx3uQo7*xL;t8brbcUTHs5s*FxUX*
zC!I|O4kUJ3>n#s$oAKGI-d<(n=8yTO$eA6}oO-A^QvZm7rr*4{$>sNTVzp;@J8L1&
z>W$Y!RSlCY>|BJteLlJ6mLE9WM=%8;l4%^J6wnh#lXM|ht^JM)&`{It#_@OTIs$g>vx_wqeQWtde%
z$4{0^&c|iXH&@b0*62Txn%|J^ck6-iuAGDdpt$2#!@64mqw65jB{x=e**Fi}xpE*s
z$lk*9u8EK1C8X`B`lm~T^4>-$?*@Ztp_6(_zFuXX9szFHHLJ==P;
zWA_MOcJjGX@N4(2j;}K}86Q?E()?3BN#kSl9AsFsNj>}Bv?*Gp!pX^Y^DOUEp~|Jb
z%`v;OL$;{9H$A!#FnQ_QhHek1Q#CQcUBTte+sT(36W5>6Gq5dh(J|7}RoHHIF^O*P
zOa*e0%^4HIbP`^)EehB%9SSKGJ!6YXONeu=c7ETO&Lwkf-vxZJ
zR_m`{ZFbLf;qjt~RZ0Werivf!JT{xWcnWuzUOlIx5N4ce@9kA}YGKgMC9Bn4>H`c{
zCD|W)vu1j2UTNjngyYAe>e{p&bEce+PMML=?YZn|KkCU0in+9PsrsM&sZP3HhB24s
zx*J_we|M}oRvFjVx^U3cU{Uw3bTLECWyB~IK&h-l^O^Pbm
zc57!-*=y(DE3;3!4u)@g5?*rItIhgtvHHe0Zl4NoF79zve)ss%UB)iokq#>;0JHxB
DT|Yu1

literal 0
HcmV?d00001

diff --git a/docs/Stacks, Queues, Lists and Hash Tables_archivos/menu.gif b/docs/Stacks, Queues, Lists and Hash Tables_archivos/menu.gif
new file mode 100644
index 0000000000000000000000000000000000000000..d66133c3a6e8ef5473e8874d791c8a13bae1fbcd
GIT binary patch
literal 1653
zcmeH`|4$Ql7{?1-O=+tXXbY3!C@Zy5L2w9&Y|?rZ%1(#nm{m_`$3d9Gtr}P)o8*92
z!3YB;QV>}!C(d|o#eJNRobHeV_vL;dS{%$~s}o&7Msy=nXBT$(XDoXqpS(Yx=XvsZ
zz9dhs(U7spnkA46o(Ps8UL4|u5d4c+0)n6(lA4=aASsTfeK3pwKvOh_Vi*Z105}-I
zdq|oBK8oTf+D8JG&FrCrDtEebYj$6YFDxLy^p5;MzGI)^yifaMKX^-Z#^
z+HAM(*z#9*^pl_4&XBDdMJ-VgaW*upQ(J?!PEFqk>&iO#;JC@E`J_F4P3n+NE&jGw
z;g$_pa>k@liO%F9oqkQ*h5U|)1H%&z`^6;p$JN$h{m#&QW253u2i2@qo-kFb9QM$b
z710EKP@OM7j|AQx49^kWy`IyDIoGK3Cxwz)*kH8=z4^@!?fRz=uN<&y@al>~!(>Xs
zwM0h`7aG4B>5a0@f|>T*hn-pSFW+dYe-G=ejT$dIGi;w4Om_`h+DpfpJ)d>CS}$Ru
zP}Sa#w%F=||ET}D<;sP{q}cm9|7?=o+2OtiH;Lh8=PE8u*~U+G?)j?fr8~blV$%O9
zD2y}=;1%h>Z8d)vt)pQ1y3h2VD=GnYOt8?y~;#8p-xU&xW1xUVo5mWrl|p
z>5@}MBq`E?>yovwMK9H)t{fqoZ~7Ur^NZ||zAghX6RFY8GLe0m{+YhDPXA0~Y^xu3
z!Fh`tg&|_`V}ZONI_RV%I{QrQ&PiQekY|7Oha&?wPLA1kC1u~8EH_<^+bv6HM?072
znB(AgSADG%hMgMn-weK3bA^y)PATsc|MHGmXT}qqy^yh@AUM2Gnl>72tQjkO-#GPG
zLrKQ2+w+ZSq0zRtvL+vum=JY`MJUaBvQK6xVputIT0MZMzE{SHjH9Wa5}v)uZls~8
zO@z+
zg$on*eRM)mdx0Y9aH{cn;(5Hr(KV?quY9i2=kC#cN5~9HtGaxX`-G}xci(^Yb~#cgMYBo^cNMDWOl9~678T`sB%4_P}}
oBvGmfNGf_nF#A_sDv$Yn=GWf&`OAOSZWb}OT9`*cL4wWy0uAC3I{*Lx

literal 0
HcmV?d00001

diff --git a/docs/Stacks, Queues, Lists and Hash Tables_archivos/previous.gif b/docs/Stacks, Queues, Lists and Hash Tables_archivos/previous.gif
new file mode 100644
index 0000000000000000000000000000000000000000..4f55ab59702d197ff599ccdedeecc7ded6f0d74d
GIT binary patch
literal 1645
zcmeHGk55xq7_H@%_DQ8bC=o%)djo98WNV!uIMz@o)#?L_ykZB9ic}<6e});@gq4t6T^1J>h3l)&#j#gqgl-;bn28ib(k2}nCS>}v!;9X&scVnoAce=^WA&S
zm)w
zq42(_L)J!6OAr)<6b#Z#5YSVIPzFHIY-s>6NRn2XW`sgvm=)7Of_<8XfVE8rsi?-n
zFbu_Jp{EJb%1-5f{AVWM^?D<0m&HC?cT%l^`Q9~XNM%^sC3?$p6C1Y-KV-yRrQXLa&wI+X~XHZ
z_UhTzXIDXy;mj9}aR*U+q~W?cWB)VZkFBMVfpvJtY!<$vp`aQT3*wrJK3;OPQdyF`
zjGyMSYh5)N>+9~_s&`%JO-L{qhAt<%@=p3H@+eQ){8XnUxmk{%`*jWXE^}gkcHX0j
zwaJ37@04`n-tJCj!AeBda@ajzJ&`AIY+6Nlv2CA}bp2Mp8W}#(vR-lD?eM&OlqQ|<
z85VMNHn9dJXRtz1mLX6mA`REJpyo=n7R@r~i~EeT;-Sy#W;wNSRXdt8MB+~kg^2D9
z$H`ZEu*;H`L9ZRjer|BY7(HIDyE*f5-Mo&>xkdA`g_)O6bq-=NbETf~(?d$JhKt50
zy}wX~hkI^rDD5&JXy&qr@fUmTOI^=i+`_rLr=rBeYgDy8H1bu9`*>|JZFsE1@;T1A
zPxZU)2hzPRQEcTHb@Zd+r1z3G2LoQy!EctHtSMh+RvP&$+Gb;T71|H+digNr=*-yM
z>Z~riZ@N|Am3MBZJ*PVG*0xcV+ZR_l>h*~P4HCQa&l_9I+fxECfmn`@-zmZR8WY-6
zmzK394qd6L9FsqsUbp7kOR(}g?6tsc9X6qJToq8O?v*Iv*0GJbCQPdSBk^ES>3Nmn
z*dg_U+R5!XzI|0)S${W<-S`r%(2l3PD~Ul3`L-BYZiwgPP3Yw#mhUh1mha7}+J59v
zY0@xm1^BwdKE%csq)680NZJxNI(a>#$u?fadJ&n}^Z`D;>E~%&`($)_Qa{in*3-Kj
p+%zjk#T7@eo3Y@lk$-;o9E*Puf 0 then begin
+               Writeln('Error en la posici¢n: ', Code);
+               exit;
+            end;
+            v[i] := k;
+            i := i + 1;
+       end;
+       close(f);
+       visualiza(v, 'Datos Originales');
+  end; { leerDatos }
+
+  (*****************************************************)
+
+  procedure ordenarDecreciente(var v: Vector);
+
+  var
+     i, j, aux: integer;
+
+  begin
+       for i := 1 to MAX do
+           for j := i + 1 to MAX do
+               if v[i] < v[j] then begin
+                  aux := v[i];
+                  v[i] := v[j];
+                  v[j] := aux;
+               end;
+  end; { ordenarDecreciente }
+
+  (*****************************************************)
+
+var
+   v: Vector;
+
+begin
+     leerDatos(v);
+     ordenarDecreciente(v);
+     visualiza(v, 'Datos Ordenados');
+end.
\ No newline at end of file
diff --git a/ej2.pas b/ej2.pas
new file mode 100644
index 0000000..e7b8969
--- /dev/null
+++ b/ej2.pas
@@ -0,0 +1,120 @@
+program Ejercicio2;
+
+const
+     MAX_FILAS = 7;
+     MAX_COLUMNAS = 6;
+
+type
+    Datos = record
+                  i: integer;
+                  j: integer;
+            end;
+    Matriz = array [1..MAX_FILAS, 1..MAX_COLUMNAS] of integer;
+    Vector = array [1..MAX_FILAS+MAX_COLUMNAS] of Datos;
+
+
+  (*****************************************************)
+
+  procedure visualiza(var m: Matriz; titulo: String);
+
+  var
+     i, j: integer;
+
+  begin
+       writeln(titulo);
+       writeln;
+       for i := 1 to MAX_FILAS do begin
+           for j := 1 to MAX_COLUMNAS do
+               write('  ', m[i,j]: 8);
+           writeln;
+       end;
+       writeln;
+  end; { visualiza }
+
+  (*****************************************************)
+
+  procedure leerDatos(var m: Matriz);
+
+  var
+     f: Text;
+     i, j, k, code: integer;
+     s: String;
+
+  begin
+       assign(f, 'datos.txt');
+       reset(f);
+       i := 1;
+       j := 1;
+       while (not eof(f)) and (i <= MAX_FILAS) and (j <= MAX_COLUMNAS) do begin
+            readln(f, s);
+            val(s, k, code);
+            if code <> 0 then begin
+               Writeln('Error en la posici¢n: ', Code);
+               exit;
+            end;
+            m[i,j] := k;
+            if j < MAX_COLUMNAS then
+               j := j + 1
+            else begin
+                i := i + 1;
+                j := 1;
+            end;
+       end;
+       close(f);
+  end; { leerDatos }
+
+  (*****************************************************)
+
+  function buscarMayor(var m: Matriz): integer;
+
+  var
+     i, j, max: integer;
+
+  begin
+       max := - MAXINT;
+       for i := 1 to MAX_FILAS do
+           for j := 1 to MAX_COLUMNAS do
+               if m[i,j] > max then
+                  max := m[i,j];
+       buscarMayor := max;
+  end; { buscarMayor }
+
+  (*****************************************************)
+
+  procedure buscarIndices(var m: Matriz; max: integer; var indices: Vector);
+
+  var
+     i, j, k: integer;
+
+  begin
+       k := 1;
+       for i := 1 to MAX_FILAS do
+           for j := 1 to MAX_COLUMNAS do
+               if m[i,j] = max then begin
+                  indices[k].i := i;
+                  indices[k].j := j;
+                  k := k + 1;
+               end;
+  end; { buscarIndices }
+
+  (*****************************************************)
+
+var
+   m: Matriz;
+   i, max: integer;
+   indices: Vector;
+
+begin
+     leerDatos(m);
+     visualiza(m, 'Datos');
+     writeln;
+     max := buscarMayor(m);
+     writeln(' Valor Maximo: ', max);
+     writeln(' Se encuantra en los indices: ');
+     buscarIndices(m, max, indices);
+     for i := 1 to MAX_FILAS + MAX_COLUMNAS do
+         if (indices[i].i > 0) and (indices[i].j > 0) then
+            writeln(' | ', indices[i].i, ' | ', indices[i].j, ' |')
+         else
+            break;
+end.
\ No newline at end of file
diff --git a/ej3.pas b/ej3.pas
new file mode 100644
index 0000000..5419b2f
--- /dev/null
+++ b/ej3.pas
@@ -0,0 +1,77 @@
+program Ejercicio3;
+
+const
+     MAX = 10;
+
+type
+    Vector = array [1..MAX] of integer;
+
+
+  (*****************************************************)
+
+  procedure leerDatos(var v: Vector);
+
+  var
+     i: integer;
+
+  begin
+       for i := 1 to MAX do begin
+           write('Numero: ');
+           readln(v[i]);
+       end;
+  end; { leerDatos }
+
+  (*****************************************************)
+
+  procedure ordenarDecreciente(var v: Vector);
+
+  var
+     i, j, aux: integer;
+
+  begin
+       for i := 1 to MAX do
+           for j := i + 1 to MAX do
+               if v[i] < v[j] then begin
+                  aux := v[i];
+                  v[i] := v[j];
+                  v[j] := aux;
+               end;
+  end; { ordenarDecreciente }
+
+  (*****************************************************)
+
+  function buscaBinaria(var v: Vector; num, ini, fin: integer): integer;
+
+  var
+     medio: integer;
+
+  begin
+       if (v[ini] < num) or (v[fin] > num) then
+          buscaBinaria := 0
+       else begin
+          medio := ini + ((fin - ini) div 2);
+          if num = v[medio] then
+             buscaBinaria := medio
+          else
+             if num < v[medio] then
+                buscaBinaria := buscaBinaria(v, num, medio + 1, fin)
+             else
+                buscaBinaria := buscaBinaria(v, num, ini, medio - 1);
+       end;
+  end;
+
+  (*****************************************************)
+
+var
+   v: Vector;
+   indice: integer;
+
+begin
+     leerDatos(v);
+     ordenarDecreciente(v);
+     indice := buscaBinaria(v, 333, 1, MAX);
+     if indice = 0 then
+        writeln('NO SE ENCONTRO EL NUMERO ''333'' ENTRE LOS INGRESADOS')
+     else
+        writeln('El numero ''333'' se encuentra en la posicion ', indice, '.');
+end.
\ No newline at end of file
diff --git a/orden.html b/orden.html
new file mode 100644
index 0000000..959dabf
--- /dev/null
+++ b/orden.html
@@ -0,0 +1,282 @@
+orden.pas
+          (**************************************************)
+          (*                                                *)
+          (*           ALGORITMOS DE ORDENAMIENTO           *)
+          (*           ========== == ============           *)
+          (*                                                *)
+          (**************************************************)
+
+program Ordenamientos;
+
+const
+    MAX = 15;
+
+type
+    Dato = Integer;
+    Vector = array [1..MAX] of Dato;
+
+
+(****************************************************
+ *
+ * BUBBLE SORT.
+ *
+ ****************************************************)
+
+ procedure bubbleSort(var v: Vector;      { Vector a ordenar }
+                          min,            { Valor de donde se comienza a ordenar }
+                          max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, aux: integer;
+
+   begin
+        if min < max then
+           for i := max - 1 downto min do
+               for j := min to i do
+                   if v[j] > v[j+1] then begin
+                      aux := v[j];
+                      v[j] := v[j+1];
+                      v[j+1] := aux;
+                   end;
+   end; { bubbleSort }
+
+(****************************************************
+ *
+ * BUBBLE SORT MEJORADO.
+ *
+ ****************************************************)
+
+ procedure bubbleSortMejor(var v: Vector;      { Vector a ordenar }
+                               min,            { Valor de donde se comienza a ordenar }
+                               max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, aux: integer;
+      huboInt: Boolean;
+
+   begin
+        huboInt := false;
+        i := max - 1;
+        if min < max then
+           repeat
+               for j := min to i do
+                   if v[j] > v[j+1] then begin
+                      aux := v[j];
+                      v[j] := v[j+1];
+                      v[j+1] := aux;
+                      huboInt := true;
+                   end;
+               i := i - 1;
+           until not huboInt;
+   end; { bubbleSortMejor }
+
+(****************************************************
+ *
+ * SHAKE SORT (o Bubble Sort Bidireccional).
+ *
+ ****************************************************)
+
+ procedure shakeSort(var v: Vector;      { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, fin, ini, aux, tmp: integer;
+
+   begin
+        fin := max - 1;
+        ini := min;
+        if min < max then
+           repeat
+               tmp := ini;
+               for i := ini to fin do
+                   if v[i] > v[i+1] then begin
+                      aux := v[i];
+                      v[i] := v[i+1];
+                      v[i+1] := aux;
+                      tmp := i;
+                   end;
+               fin := tmp;
+               for i := fin downto ini do
+                   if v[i] > v[i+1] then begin
+                      aux := v[i];
+                      v[i] := v[i+1];
+                      v[i+1] := aux;
+                      tmp := i;
+                   end;
+               ini := tmp;
+           until ini >= fin;
+   end; { shakeSort }
+
+(****************************************************
+ *
+ * INSERTION SORT.
+ *
+ ****************************************************)
+
+ procedure insertionSort(var v: Vector;  { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j: integer;
+      tmp: Dato;
+      huboInt: Boolean;
+
+   begin
+        if min < max then
+           for i := min + 1 to max do begin
+             tmp := v[i];
+             j := i - 1;
+             huboInt := true;
+             while (j >= 1) and huboInt do
+                if v[j] > tmp then begin
+                   v[j+1] := v[j];
+                   j := j - 1;
+                end else
+                   huboInt := false;
+             v[j+1] := tmp;
+           end;
+   end; { insertionSort }
+
+(****************************************************
+ *
+ * QUICK SORT.
+ *
+ ****************************************************)
+
+ procedure quickSort(var v: Vector;      { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      ini, fin, medio: integer;
+      aux, tmp: Dato;
+
+   begin
+        if min >= max then
+           exit;
+        ini := min;
+        fin := max;
+        medio := (min + max) div 2;
+        tmp := v[medio];
+        repeat
+           while v[ini] < tmp do
+                 ini := ini + 1;
+           while v[fin] > tmp do
+                 fin := fin - 1;
+           if ini <= fin then begin
+              if ini < fin then begin
+                 aux := v[ini];
+                 v[ini] := v[fin];
+                 v[fin] := aux;
+              end;
+              ini := ini + 1;
+              fin := fin - 1;
+           end;
+        until ini > fin;
+        if min < fin then
+           quickSort(v, min, fin);
+        if max > ini then
+           quickSort(v, ini, max);
+   end; { quickSort }
+
+(****************************************************
+ *
+ * SHELL'S SORT.
+ *
+ ****************************************************)
+
+ procedure Shellsort( var v : Vector;       { Vector a ordenar }
+                          min,              { Valor de donde se comienza a ordenar }
+                          max : Integer );  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, medio : Integer;
+      tmp : Dato;
+
+   begin
+        medio := max - min + 1;
+        while medio > 1 do begin
+           if medio < 5 then
+              medio := 1
+           else
+              medio := trunc( 0.45454 * medio );
+          {*** Do linear insertion sort in steps size d ***}
+          for i := max - medio downto min do begin
+              tmp := v[i];
+              j := i + medio;
+              while j <= max do
+                 if tmp > v[j] then begin
+                    v[j-medio] := v[j];
+                    j := j + medio
+                 end else
+                    break;
+              v[j-medio] := tmp
+          end;
+        end;
+   end; { Shellsort }
+
+
+(************************************************************************)
+
+ procedure verVector(var v: Vector; s: String);
+
+   var
+      i: Integer;
+
+   begin
+        (** MUESTRA VECTOR **)
+        writeln(s);
+        for i := 1 to MAX do
+            write(' | ', v[i]);
+        writeln(' | ');
+        writeln;
+   end; { verVector }
+
+
+(************************************************************************)
+
+ procedure cargarVector(var v: Vector);
+
+   var
+      i: Integer;
+
+   begin
+        (** INICIALIZA VECTOR **)
+        for i := 1 to MAX do
+            v[i] := round(random * 100);
+   end; { cargarVector }
+
+
+(************************************************************************)
+(************************************************************************)
+(*                       PROGRAMA PRINCIPAL                             *)
+
+var
+   i: Integer;
+   v, w: Vector;
+
+begin
+     cargarVector(w);
+     v := w;
+     verVector(v, 'Desordenado:');
+     bubbleSort(v, 1, MAX);
+     verVector(v, 'Bubble Sort:');
+     bubbleSortMejor(v, 1, MAX);
+     verVector(v, 'Bubble Sort Mejorado:');
+     v := w;
+     shakeSort(v, 1, MAX);
+     verVector(v, 'Shake Sort (Bubble Sort Bidireccional):');
+     v := w;
+     insertionSort(v, 1, MAX);
+     verVector(v, 'Insertion Sort:');
+     v := w;
+     quickSort(v, 1, MAX);
+     verVector(v, 'Quick Sort:');
+     v := w;
+     shellSort(v, 1, MAX);
+     verVector(v, 'Shell''s Sort:');
+end.
+
+

diff --git a/orden.pas b/orden.pas
new file mode 100644
index 0000000..7a6fa73
--- /dev/null
+++ b/orden.pas
@@ -0,0 +1,280 @@
+          (**************************************************)
+          (*                                                *)
+          (*           ALGORITMOS DE ORDENAMIENTO           *)
+          (*           ========== == ============           *)
+          (*                                                *)
+          (**************************************************)
+
+program Ordenamientos;
+
+const
+    MAX = 15;
+
+type
+    Dato = Integer;
+    Vector = array [1..MAX] of Dato;
+
+
+(****************************************************
+ *
+ * BUBBLE SORT.
+ *
+ ****************************************************)
+
+ procedure bubbleSort(var v: Vector;      { Vector a ordenar }
+                          min,            { Valor de donde se comienza a ordenar }
+                          max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, aux: integer;
+
+   begin
+        if min < max then
+           for i := max - 1 downto min do
+               for j := min to i do
+                   if v[j] > v[j+1] then begin
+                      aux := v[j];
+                      v[j] := v[j+1];
+                      v[j+1] := aux;
+                   end;
+   end; { bubbleSort }
+
+(****************************************************
+ *
+ * BUBBLE SORT MEJORADO.
+ *
+ ****************************************************)
+
+ procedure bubbleSortMejor(var v: Vector;      { Vector a ordenar }
+                               min,            { Valor de donde se comienza a ordenar }
+                               max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, aux: integer;
+      huboInt: Boolean;
+
+   begin
+        huboInt := false;
+        i := max - 1;
+        if min < max then
+           repeat
+               for j := min to i do
+                   if v[j] > v[j+1] then begin
+                      aux := v[j];
+                      v[j] := v[j+1];
+                      v[j+1] := aux;
+                      huboInt := true;
+                   end;
+               i := i - 1;
+           until not huboInt;
+   end; { bubbleSortMejor }
+
+(****************************************************
+ *
+ * SHAKE SORT (o Bubble Sort Bidireccional).
+ *
+ ****************************************************)
+
+ procedure shakeSort(var v: Vector;      { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, fin, ini, aux, tmp: integer;
+
+   begin
+        fin := max - 1;
+        ini := min;
+        if min < max then
+           repeat
+               tmp := ini;
+               for i := ini to fin do
+                   if v[i] > v[i+1] then begin
+                      aux := v[i];
+                      v[i] := v[i+1];
+                      v[i+1] := aux;
+                      tmp := i;
+                   end;
+               fin := tmp;
+               for i := fin downto ini do
+                   if v[i] > v[i+1] then begin
+                      aux := v[i];
+                      v[i] := v[i+1];
+                      v[i+1] := aux;
+                      tmp := i;
+                   end;
+               ini := tmp;
+           until ini >= fin;
+   end; { shakeSort }
+
+(****************************************************
+ *
+ * INSERTION SORT.
+ *
+ ****************************************************)
+
+ procedure insertionSort(var v: Vector;  { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      i, j: integer;
+      tmp: Dato;
+      huboInt: Boolean;
+
+   begin
+        if min < max then
+           for i := min + 1 to max do begin
+             tmp := v[i];
+             j := i - 1;
+             huboInt := true;
+             while (j >= 1) and huboInt do
+                if v[j] > tmp then begin
+                   v[j+1] := v[j];
+                   j := j - 1;
+                end else
+                   huboInt := false;
+             v[j+1] := tmp;
+           end;
+   end; { insertionSort }
+
+(****************************************************
+ *
+ * QUICK SORT.
+ *
+ ****************************************************)
+
+ procedure quickSort(var v: Vector;      { Vector a ordenar }
+                         min,            { Valor de donde se comienza a ordenar }
+                         max: Integer);  { Valor en donde se termina de ordenar }
+
+   var
+      ini, fin, medio: integer;
+      aux, tmp: Dato;
+
+   begin
+        if min >= max then
+           exit;
+        ini := min;
+        fin := max;
+        medio := (min + max) div 2;
+        tmp := v[medio];
+        repeat
+           while v[ini] < tmp do
+                 ini := ini + 1;
+           while v[fin] > tmp do
+                 fin := fin - 1;
+           if ini <= fin then begin
+              if ini < fin then begin
+                 aux := v[ini];
+                 v[ini] := v[fin];
+                 v[fin] := aux;
+              end;
+              ini := ini + 1;
+              fin := fin - 1;
+           end;
+        until ini > fin;
+        if min < fin then
+           quickSort(v, min, fin);
+        if max > ini then
+           quickSort(v, ini, max);
+   end; { quickSort }
+
+(****************************************************
+ *
+ * SHELL'S SORT.
+ *
+ ****************************************************)
+
+ procedure Shellsort( var v : Vector;       { Vector a ordenar }
+                          min,              { Valor de donde se comienza a ordenar }
+                          max : Integer );  { Valor en donde se termina de ordenar }
+
+   var
+      i, j, medio : Integer;
+      tmp : Dato;
+
+   begin
+        medio := max - min + 1;
+        while medio > 1 do begin
+           if medio < 5 then
+              medio := 1
+           else
+              medio := trunc( 0.45454 * medio );
+          {*** Do linear insertion sort in steps size d ***}
+          for i := max - medio downto min do begin
+              tmp := v[i];
+              j := i + medio;
+              while j <= max do
+                 if tmp > v[j] then begin
+                    v[j-medio] := v[j];
+                    j := j + medio
+                 end else
+                    break;
+              v[j-medio] := tmp
+          end;
+        end;
+   end; { Shellsort }
+
+
+(************************************************************************)
+
+ procedure verVector(var v: Vector; s: String);
+
+   var
+      i: Integer;
+
+   begin
+        (** MUESTRA VECTOR **)
+        writeln(s);
+        for i := 1 to MAX do
+            write(' | ', v[i]);
+        writeln(' | ');
+        writeln;
+   end; { verVector }
+
+
+(************************************************************************)
+
+ procedure cargarVector(var v: Vector);
+
+   var
+      i: Integer;
+
+   begin
+        (** INICIALIZA VECTOR **)
+        for i := 1 to MAX do
+            v[i] := round(random * 100);
+   end; { cargarVector }
+
+
+(************************************************************************)
+(************************************************************************)
+(*                       PROGRAMA PRINCIPAL                             *)
+
+var
+   i: Integer;
+   v, w: Vector;
+
+begin
+     cargarVector(w);
+     v := w;
+     verVector(v, 'Desordenado:');
+     bubbleSort(v, 1, MAX);
+     verVector(v, 'Bubble Sort:');
+     bubbleSortMejor(v, 1, MAX);
+     verVector(v, 'Bubble Sort Mejorado:');
+     v := w;
+     shakeSort(v, 1, MAX);
+     verVector(v, 'Shake Sort (Bubble Sort Bidireccional):');
+     v := w;
+     insertionSort(v, 1, MAX);
+     verVector(v, 'Insertion Sort:');
+     v := w;
+     quickSort(v, 1, MAX);
+     verVector(v, 'Quick Sort:');
+     v := w;
+     shellSort(v, 1, MAX);
+     verVector(v, 'Shell''s Sort:');
+end.
+
-- 
2.43.0