Program Tablazat;
(*
 Feladat: a láncolt listás tábla-ábrázolás tesztelése, azaz
 kulcshasonlítások száma és sikerek száma.
 Részletesebben:
 1) Táblafeltöltés véletlen nevekkel.
 2) Táblában levõ nevek keresése.
 3) Táblából nevek törlése (ugyanazt esetleg többször is).
 Megoldási javaslat:
 A generáláskor egy segéd file-ban följegyezzük a fölvett neveket,
 s ebbõl választjuk véletlenszerûen a keresett, majd a törlendõ neveket.
 Kipróbálandó:
 Más és más táblaméretre (MaxN=16, 32, 64, 100).
 Más Hash-fv.-re.
*)
 Uses Newdelay,Crt;
 
 {$i AltRutin.inc -- Általánosan használt rutinok}
 {$i Randnev.inc -- Véletlen név generáláshoz}
 
 Const
 MaxN = 16;
 BN = 100; KN = 200; TN =100; {Beteendõ,keresendõ,törlendõ elemek száma}
 Type
 Kulcs = TNev;
 Elem = TNev;
 ListaElemMut = ^ListaElem;
 ListaElem = Record kulcs:Kulcs; elem:Elem; kov:ListaElemMut End;
 Lista = Record fej:ListaElemMut; db:Word End;
 Index = 0..MaxN-1;
 Tabla = Array [Index] of Lista;
 Var
 t : Tabla;
 i : Integer;
 nev : TNev;
 e : Elem;
 siker: Boolean;
 kulcsHasonlitasok,
 sikerSzam: Integer;
 
 Function Hash(n:TNev):Index;
 Var
 i :Integer;
 cim:Byte;
 Begin
 cim:=0;
 For i:=1 to Length(n) do cim:=cim XOR Ord(n[i]);
 Hash:=cim Mod MaxN;
 End;
 
 Procedure TablaUres(Var t:Tabla);
 Var
 i:Integer;
 Begin
 For i:=0 to MaxN-1 do
 Begin
 t[i].fej:=Nil; t[i].db:=0
 End;
 End;
 
 Procedure TablaKiir(t:Tabla);
 Var
 i :Integer;
 minLH,
 maxLH,
 atlLH, {minimális,maximális,átlagos listahossz}
 db :Integer;
 hol :ListaElemMut;
 Begin
 UjLap('Táblázat -- kiírás'+CrLf,-1);
 db:=0; atlLH:=0; minLH:=BN; maxLH:=0;
 For i:=0 to MaxN-1 do
 Begin
 Inc(atlLH,t[i].db);
 If minLh>t[i].db then minLH:=t[i].db;
 If maxLh<t[i].db then maxLH:=t[i].db;
 If t[i].db>1 then Inc(db,t[i].db-1); {Ütközésszám}
 Write(i:5,'(',t[i].db,'):');
 If t[i].fej<>Nil Then
  Begin
 hol:=t[i].fej;
 While hol^.kov<>Nil do
 Begin
 Write(hol^.kulcs,'/');
 hol:=hol^.kov;
 End;
 Write(hol^.kulcs);
 End;
 Writeln;
 If WhereY>=19 then
 Begin
 UjLap('Táblázat -- kiírás'+CrLf,-1);
 End;
 End;
 If WhereY>=19 then UjLap('Táblázat -- kiírás'+CrLf,-1);
 Writeln(CrLf,' Összes táblában lévõ elemek száma:',BN);
 Writeln(' Összes ütközõ elemek száma:',db);
 Write (' Minimális listahossz:',minLH:3);
 Write (' Maximális listahossz:',maxLH:3);
 Writeln(' Atlagos listahossz:',atlLH/MaxN:5:2);
 BillreVar;
 End;
 
 Procedure Tablaba(Var t:Tabla; e:Elem);
 Var
 i:Integer;
 hol,
 te:ListaElemMut;
 Begin
 If WhereY>=20 then UjLap('Táblázat -- táblába fölvétel'+CrLf,-1);
 i:=Hash(e{kulcs});
 Write('Fölveszem "',e,'"-t',CrLf,' a(z) ',i,'. listába, ahol a következõ ',
 t[i].db,' db elem van:',CrLf,' ->');
 New(te); te^.kulcs:=e; te^.kov:=Nil;
  If t[i].fej=Nil then
 Begin
 t[i].fej:=te; t[i].db:=1;
 End
 Else
 Begin
 Inc(t[i].db);
 hol:=t[i].fej;
 While hol^.kov<>Nil do
 Begin
 Write(hol^.kulcs,'/');
 hol:=hol^.kov;
 End;
 Write(hol^.kulcs);
 hol^.kov:=te;
 End;
 Writeln;
 End;
 
 Procedure TablabolTorol(Var t:Tabla; k:Kulcs; Var van:Boolean);
 Var
 i :Integer;
 elozo,
 hol:ListaElemMut;
 Begin
 If WhereY>=20 then UjLap('Táblázat -- táblából törlés'+CrLf,-1);
 Write('Törlöm a(z) "',k,'"-t, ami a(z) ');
 i:=Hash(k);
 Writeln(i:5,'. indexû, ahol ',t[i].db,' elem van.');
 hol:=t[i].fej;
 If hol<>Nil then
 Begin
 Write(' Mégpedig: '); elozo:=Nil;
 While (hol^.kov<>Nil) and (hol^.kulcs<>k) do
 Begin
 elozo:=hol; Inc(kulcsHasonlitasok);
 Write(hol^.kulcs,','); hol:=hol^.kov;
 End;
 Write(hol^.kulcs);
 If hol^.kulcs=k then
 Begin
 van:=True; e:=hol^.kulcs {.elem}
 End
 Else
 van:=False;
 {EndIf};
 Inc(kulcsHasonlitasok,2);
 If
 van and (elozo=Nil) then {elsõ elem}
 Begin
 Dec(t[i].db);
 t[i].fej:=hol^.kov;
 Dispose(hol);
 End else if
 van then {nem elsõ}
 Begin
 Dec(t[i].db);
 elozo^.kov:=hol^.kov;
 Dispose(hol);
 End
 {EndIf};
 End;
 Writeln;
 End;
 
 Procedure TablabanKeres(t:Tabla; k:Kulcs; Var van:Boolean; Var e:Elem);
 Var
 i :Integer;
 te,
 hol:ListaElemMut;
 Begin
 If WhereY>=20 then UjLap('Táblázat -- keresés táblában'+CrLf,-1);
 Write('Keresem a(z) "',k,'", ami a(z) ');
 i:=Hash(k);
 Writeln(i:5,'. indexû, ahol ',t[i].db,' elem van.');
 hol:=t[i].fej;
 If hol<>Nil then
  Begin
 Write(' Mégpedig (a megtalálásig): ');
 While (hol^.kov<>Nil) and (hol^.kulcs<>k) do
 Begin
 Inc(kulcsHasonlitasok);
 Write(hol^.kulcs,','); hol:=hol^.kov;
 End;
 Write(hol^.kulcs);
 If hol^.kulcs=k then
 Begin
 van:=True; e:=hol^.kulcs {.elem}
 End
 Else
 van:=False;
 {EndIf};
 Inc(kulcsHasonlitasok,2);
 End;
 Writeln;
 End;
 
 Var genNev:File of TNev; {a generált nevek följegyzése ebbe a file-ba}
 
Begin
 UjLap('Táblázat -- táblába fölvétel'+CrLf,0);
 TablaUres(t);
 Assign(genNev,'_GenNev_.tmp'); ReWrite(genNev);
 For i:=1 to BN do
 Begin
 nev:=RandomNev;
 Write(genNev,nev);
 Tablaba(t,nev);
 End;
 TablaKiir(t);
 {Keresés:}
 UjLap('Táblázat -- keresés táblában'+CrLf,-1);
 kulcsHasonlitasok:=0; sikerSzam:=0;
 For i:=1 to KN do
 Begin
(* nev:=RandomNev;*)
 Seek(genNev,Random(BN)); Read(genNev,nev);
 TablabanKeres(t,nev,siker,e);
 If siker then Inc(sikerSzam);
 End;
 Writeln(CrLf,' Összes keresési kísérletek száma:',KN);
 Writeln(' Sikerek száma:',sikerSzam);
 Writeln(' Kulcshasonlítások száma:',kulcsHasonlitasok);
 {Törlés:}
 UjLap('Táblázat -- táblából törlés'+CrLf,-1);
 kulcsHasonlitasok:=0; sikerSzam:=0;
 For i:=1 to TN do
 Begin
(* nev:=RandomNev;*)
 Seek(genNev,Random(BN)); Read(genNev,nev);
 TablabolTorol(t,nev,siker);
 If siker then Inc(sikerSzam);
 End;
 Writeln(CrLf,' Összes törlési kísérletek száma:',TN);
 Writeln(' Sikerek száma:',sikerSzam);
 Writeln(' Kulcshasonlítások száma:',kulcsHasonlitasok);
 TablaKiir(t);
 
{
 TablaKiir(t);
}
Close(genNev);
 
End.