Pascal/Turbo Pascal - Estructura tipo hashing

   
Vista:

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 02/04/2013 16:00:54
saludos, necesito ayuda urgente con trabajo practico Univ...bien, en pascal, debo almacenar nombres y apellidos en un archivo de texto considerando que el nombre a insertar usará las letras que conforman dicho nombre según la codificacion ascii y se insertará en una lista asociada a la celda, luego se debe hacer procedimiento de búsqueda en la tabla hashing y debe mostrar en cual celda se insertó el nombre...no estoy muy claro en lo del uso del hashing...tengo poca información...alguna orientación o ejemplo para lograr lo solicitado? Gracias
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 03/04/2013 17:24:18
Disculpa pe pones en archivo de texto no sera en archivos de registros que es lo normal puedes
pasar la estructura de esos archivos que llamas de texto para poder atenderte mejor.
Sera algo así;

par = record
clave: integer;
cadena : array[1..50] of char;
atributo : char;
end;
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 04/04/2013 00:53:58
Bien...la cosa es así...tengo lo siguiente:

1
2
3
4
5
6
7
8
9
10
11
uses crt;
var
palabra:string;
i:integer;
begin
writeln ('introduzca un texto');
readln (palabra);
for i:=1 to length (palabra) do
writeln (palabra[i],' = ',ord (palabra[i]));
readln;
end.


con esto al introducir un nombre por ejemplo obtengo de cada letra su valor ascii, ahora lo que debe hacerse es que la suma de todos sus caracteres ascii se inserte en una lista asociada a una celda o slot, ejemplo:
si uso 200 slots y deseo insertar un nombre cuya suma ascii me arroja 1012, la llave construida sería:
valor mod x= 1012 mod 199 =196 (en el slot 196 se guarda el registro)

Ahora bien...todos los nombres que registre se almacenaran en un archivo de texto que pueda abrir y al realizar búsqueda hashing me muestre la posición en que se guardó, ejemplo: muestra el nombre en la posición 196...
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 05/04/2013 10:39:34
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
{A ver si esto te ayuda un poco}
 
program ejemplo_hashing;
 uses
    crt;
  const
     max = 200;
   var
     nombre : array[0..max - 1] of string[20];
     entra : string;
     nent, x, y : integer;
     f : text;
 
   function clave(ss : string) : integer;
   var
     k : integer;
     begin
        k := ord(ss[1]) * 23;
        k := k shl 1;
        k := k + ord(ss[2]) * 19;
        k := k mod max;
        clave := k;
     end;
 
    procedure buscaposicion(var kt : integer);
    var
      k : integer;
      begin
         k := 0;
        while (nombre[kt] <> ' ') and (k <= max) do
        begin
          k := k + 1;
          kt := kt + 1;
          if kt >= max then
          kt := 0;
        end;
      if k > max then
      kt := max + 1;
    end;
 
   procedure inicio;
   begin
      for x := 0 to max - 1 do
      nombre[x] := ' ';
   end;
 
   procedure entradadatos;
   var
     fin : boolean;
     tec : char;
   begin
      y := 0;
      nent := 1;
   repeat
      write('Nombre : ');
      readln(entra);
      x := clave(entra);
      buscaposicion(x);
      writeln(x);
      if (x >= 0) and (x <= max - 1) then
      nombre[x] := entra;
      writeln('Desea Entrar Mas Nombres [S/N]');
      repeat
          tec := upcase(readkey);
      until tec in['S','N'];
      if tec = 'N' then
      fin := true
    else
      nent := nent + 1;
    until fin = true;
  end;
 
  procedure guardanombres;
  var
    tc : char;
    i : integer;
  begin
      assign(f,'tempo.dat');
   {$I-} reset(f); {$I+}
   if ioresult = 0 then
   begin
      writeln('El archivo Existe Desea Cambiarlo [S/N]');
      repeat
      tc := upcase(readkey);
      until tc in['S','N'];
      rewrite(f);
      for x := 0 to max - 1 do
      begin
        writeln(f,nombre[x]);
      end;
   end
  else
     begin
      rewrite(f);
      for x := 0 to max - 1 do
      begin
        writeln(f,nombre[x]);
     end;
   end;
      close(f);
   end;
 
  procedure carganombres;
  begin
     assign(f,'tempo.dat');
  {$I-} reset(f); {$I+}
  if ioresult <> 0 then
  begin
      writeln('Archivo No Encontrado pulse [Enter]');
      readln;
      halt(1);
  end;
     y := 0;
     while not eof(f) do
     begin
        readln(f,nombre[y]);
        y := y + 1;
     end;
     close(f);
 end;
 
  procedure busquedanombre;
  var
    pp : integer;
    salir : boolean;
   begin
      write('Entre Nombre : ');
      readln(entra);
      x := clave(entra);
      pp := x;
      salir := false;
     repeat
        if nombre[pp] = entra then
        salir := true
      else
        pp := max + 1;
     until (salir = true) or (pp > max);
     if salir = true then
     writeln('Nombre encontrado : ',nombre[pp],' = ',x)
   else
     writeln('El Nombre no se encuentra');
   readln;
 end;
 
 procedure menu;
 var
   tecla : char;
   aca : boolean;
   begin
      aca := false;
   repeat
      clrscr;
      writeln('**** Menu General ****');
      writeln;
      writeln('   1 : Entrada Nombres');
      writeln('   2 : Guardar Entradas');
      writeln('   3 : cargar Entradas');
      writeln('   4 : Buscar Nombre');
      writeln('   5 : Terminar');
      writeln;
      writeln('<<<< Elija Opcion >>>>');
      repeat
           tecla := readkey;
      until tecla in[#49..#53];
   case tecla of
 #49 : begin clrscr; entradadatos; end;
 #50 : begin clrscr; writeln('Guardando Datos'); delay(200); guardanombres;
          end;
 #51 : begin clrscr; writeln('Cargando Nombres'); delay(200);carganombres;
          end;
 #52 : begin clrscr; busquedanombre; end;
 #53 : aca := true;
   end;
 until aca = true;
 end;
 
 begin
    inicio;
    menu;
 end.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 05/04/2013 15:15:51
Gracias, me pareció muy bueno el código, lo que no entiendo es como a partir de la clave ascii que forma el nombre se guarda en el slot...cómo se puede determinar eso? la función clave puede convertir ese valor? se toma en cuenta el espacio o puede suprimirse? ejemplo: si el nombre es:

Jerzy Dude, su valor ascii será:
J: 74
e: 101
r: 114
z: 122
i: 121

D: 68
u: 117
d: 100
e: 101

Total Ascii: 779
valor mod x= 779 mod 199 = ? (en cual slot se guardaría el registro siendo resto de la división entera?)
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 05/04/2013 15:57:52
Perdona pero no entiendo muy bien tu pregunta referente al slot.. que es para ti esto me supongo
que te refieres al array pero si no es así dime que es.

La posición que toma en el array se la localiza [buscaposicion] que es la encargada de ello fíjate
que se tiene que guardar todo el array para poder cargar los datos tal y como los guardo puesto
que lo realizas sobre un archivo de testo y este tiene que crear las lineas que se cargaran despues
real mente se debería de realizar sobre registros o punteros puesto que los archivos serian menores
de tamaño.
Espero sea esto lo que pides.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 05/04/2013 17:03:19
A ver... el slot es la celda donde se guarda, posicion que ocupa...encontré que para este caso la función hash consiste en la suma de las posiciones en el alfabeto de las letras (ascii) que conforma el nombre:



en donde li es el código ASCII de cada letra que forma el nombre, r es el número de entradas de la tabla de hashing o número de buckets o slots.

Efectivamente sería mejor usar punteros para que la estructura sea dinámica...
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 05/04/2013 19:00:10
En este punto se realiza esa operación

x := clave(entra);
buscaposicion(x);

tomando la clave del nombre entrado y buscando su posición en el array o celda como quieras
llamarla.

Si te fijas en la clave veras que esta esta basada:
entrando [juan] y realizando los cálculos tendríamos lo siguiente:

ord(j) = 106 lo x por 23 con lo cual nos da 2438
2438 shl 1 que nos da 4876
4876 le + ord(u) = 117 lo x 19 = 7099
7099 mod max entradas para no desbordar el array = 99 posición que ocupara en el array
como podrás solo empleo las dos letras primeras para calcular la posición del nombre.
espero esto ayude.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 05/04/2013 21:28:17
Entiendo...un par de dudas, de donde se obtiene el valor * 23 y luego *19 en el procedimeinto?...Y como puedo aplicar el calculo para todo un nombre y apellido sin desbordar el array? Hay alguna manera de hacer esto con punteros?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 05/04/2013 22:56:08
Los números son valores fijos puedes cambiarlos por otros.
Como te comente solo toma dos letras del nombre por tanto no afecta la longitud del texto entrado
ano ser que rebase la longitud del string 255 caracteres.
Si ten en cuenta que es una cadena de texto y se puede manejar punteros.
Aunque es mas complejo de implementar.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 06/04/2013 13:48:52
y si lo quiero implementar para el nombre completo que calculo debo implementar en la funcion?

function clave(ss : string) : integer;
var
k : integer;
begin
k := ord(ss[1]) * 23;
k := k shl 1;
k := k + ord(ss[2]) * 19;
k := k + ord(ss[3]) * 16;{puede ser algo así y permitir por ejemplo hasta 8 letras en un nombre?}
k := k mod max;
clave := k;
end;
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 06/04/2013 17:39:40
Mi consejo seria que descontaras en 4 cada letra que tomes pero mira como queda puesto que el
numero tomado disminuye con lo cual puedes quedarte corto de numero para el array de 200 que
tienes.
function clave(ss : string) : integer;
var
k : integer;
begin
k := ord(ss[1]) * 23;
k := k shl 1;
k := k + ord(ss[2]) * 19;
k := k + ord(ss[3]) * 15;{puede ser algo así y permitir por ejemplo hasta 8 letras en un nombre?}
k := k + ord(ss[4]) * 11;
k := k mod max;
clave := k;
end;

comprueba esta y veras lo que te comento.
Otra forma seria sumar todas las letras por ejemplo [juan antonino] que nos daría [1332] mod max
con esto tienes mas letras pilladas pero eso tu lo veras.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 07/04/2013 00:43:29
Me interesa probar eso ultimo que comentas:

"Otra forma seria sumar todas las letras por ejemplo [juan antonino] que nos daría [1332] mod max
con esto tienes mas letras pilladas pero eso tu lo veras"

¿Puedes ayudarme con el caso de la función que debo aplicar?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por ramon (2072 intervenciones) el 07/04/2013 13:51:06
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{Mira lo que tienes es que cambiar esto solo}
 
function clave(ss : string) : integer;
var
v, k : integer;
begin
  v := 0;
 for k := 1 to length(ss) do
  v := v + ord(ss[k]);
 clave := v mod max;
end;
 
{Si entras el nombre [juan andres] en minúsculas te dará 99 mientras si lo entras [Juan Andres] te
 dará 35 esto tendrás que realizar pruebas con una serie de nombres para ver que no colisionen
 las direcciones en el array suerte}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 07/04/2013 15:18:00
Gracias, acabo de hacer la prueba, en el caso de cuando el valor mod x= 1012 mod 199 =196 (en el slot 196 se guarda el registro), no funcionó...a qué puede deberse? el código me parece impecable!
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Estructura tipo hashing

Publicado por elias (46 intervenciones) el 08/04/2013 22:37:12
Como hago que no tome el espacio entre nombres como parte del calculo para ubicarlo en una posición?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar