Паскаль (I семестр) / K02-172 / 09 / hash

{$M 64000,0,600000}
{$R+}
program hash_sort;
(*
(c) 2005 Dima Zolotukhin aka 'Zlogic' <zlogic@gmail.com>
Redistributable under GNU GPL license
*)

const
MAX_N = 10;

type
str_message = string[70];
str_word = string[20];
pnode = ^node;
node = record
data:str_word;
next:pnode;
end;
hash = array[1..MAX_N]of pnode;

procedure print_menu;
begin
writeln;
writeln('<< Њ…Ќћ •ќ-‘Ћђ’€ђЋ‚Љ€ >>');
writeln('1 „®Ў ўЁвм н«Ґ¬Ґ­в');
writeln('2 “¤ «Ёвм н«Ґ¬Ґ­в');
writeln('3 Ќ ©вЁ н«Ґ¬Ґ­в');
writeln('4 ‚л室');
end;

function get_word(message:str_message):str_word;
var
response:str_word;
begin
write(message,'> ');
readln(response);
get_word:=response;
end;

function get_int(message:str_message):integer;
var
response:integer;
begin
write(message,'> ');
readln(response);
get_int:=response;
end;

function calc_hash(s:str_word):integer;
var
sum:longint;
i:byte;
begin
sum:=0;
for i:=1 to length(s)do{¤«п Є ¦¤®Ј® бЁ¬ў®« }
sum:=sum+ord(s[i]);{бзЁв Ґ¬ б㬬г}
calc_hash:=(sum mod MAX_N) + 1;{бзЁв Ґ¬ ®бв в®Є ЇаЁ ¤Ґ«Ґ­ЁЁ ­  ¬ Єб}
end;

procedure add_to_end(var _node_pointer:pnode;data_to_add:str_word);
var
new_node_pointer:pnode;
last_node_pointer:pnode;
begin
new(new_node_pointer);{ᮧ¤ Ґ¬ ­®ўл© н«Ґ¬Ґ­в бЇЁбЄ }
new_node_pointer^.next:=NIL;
new_node_pointer^.data:=data_to_add;
last_node_pointer:=_node_pointer;
while(last_node_pointer^.next<>NIL) and (last_node_pointer<>NIL)do{ЁйҐ¬ Ї®б«Ґ¤­Ё© н«Ґ¬Ґ­в}
last_node_pointer:=last_node_pointer^.next;
if(_node_pointer<>NIL)then{Ґб«Ё ¤® нв®Ј® Ўл« Їгбв®© бЇЁб®Є}
last_node_pointer^.next:=new_node_pointer{ЇаЁбў Ёў Ґ¬ Ґ¬г ­®ў®Ґ §­ зҐ­ЁҐ}
else{Ё­ зҐ}
_node_pointer:=new_node_pointer;{¤®Ў ў«пҐ¬ ­®ўл© н«Ґ¬Ґ­в}
end;

procedure add_hash(var _hash:hash;data_to_add:str_word);
begin
add_to_end(_hash[calc_hash(data_to_add)],data_to_add);
end;

function delete_at_start(var _node_pointer:pnode):boolean;
var
deleted_node_pointer:pnode;
begin
if _node_pointer<>NIL then{Ґб«Ё бЇЁб®Є ­Ґ Їгбв}
begin
deleted_node_pointer:=_node_pointer;{б®е࠭塞  ¤аҐб г¤ «пҐ¬®Ј® н«Ґ¬Ґ­в }
_node_pointer:=_node_pointer^.next;{¤ўЁЈ Ґ¬ Ї®Ё­вҐа}
dispose(deleted_node_pointer);{г¤ «пҐ¬}
delete_at_start:=true;
end
else{Ё­ зҐ}
delete_at_start:=false;{®иЁЎЄ }
end;


function delete_by_value(var _node_pointer:pnode;data_to_delete:str_word):boolean;
var
current_node_pointer,previous_node_pointer:pnode;
begin
delete_by_value:=false;
current_node_pointer:=_node_pointer;
previous_node_pointer:=NIL;
if _node_pointer<>NIL then{Ґб«Ё бЇЁб®Є ­Ґ Їгбв}
begin
while (current_node_pointer<>NIL) and (current_node_pointer^.data<>data_to_delete)do{Ї®Є  !гўЁ¤Ё¬ н«Ґ¬Ґ­в Ё !Є®­Ґж бЇЁбЄ }
begin
previous_node_pointer:=current_node_pointer;{¤ўЁЈ Ґ¬бп ўЇҐаҐ¤}
current_node_pointer:=current_node_pointer^.next;
end;
if current_node_pointer<>NIL then{Ґб«Ё н«Ґ¬Ґ­в ­ ©¤Ґ­}
begin
delete_by_value:=true;
if previous_node_pointer<>NIL then{Ґб«Ё ­Ґ ў ­ з «Ґ}
begin
delete_at_start(current_node_pointer);{г¤ «пҐ¬ ⥪гйЁ© н«Ґ¬Ґ­в}
previous_node_pointer^.next:=current_node_pointer;{б®е࠭塞 ббл«Єг}
end
else{Ё­ зҐ}
delete_at_start(_node_pointer);{г¤ «пҐ¬ Ё§ ­ з « }
end;
end;
end;

function delete_hash(var _hash:hash;data_to_add:str_word):boolean;
begin
delete_hash:=delete_by_value(_hash[calc_hash(data_to_add)],data_to_add);
end;

function find_element(_node_pointer:pnode;data_to_find:str_word):boolean;
begin
while (_node_pointer<>NIL) and (_node_pointer^.data<>data_to_find)do
_node_pointer:=_node_pointer^.next;
find_element:=_node_pointer<>NIL;
end;

function find_hash(var _hash:hash;data_to_add:str_word):boolean;
begin
find_hash:=find_element(_hash[calc_hash(data_to_add)],data_to_add);
end;

var
exit:boolean;
response:byte;
_hash:hash;
i:integer;
begin
exit:=false;
for i:=1 to MAX_N do{§ Ї®«­пҐ¬ ­г«п¬Ё}
_hash[i]:=NIL;
while not exit do{Ї®Є  ­Ґ ­г¦­® ўл©вЁ}
begin
print_menu;{Ї®Є §лў Ґ¬ ¬Ґ­о}
response:=get_int('‚лЎҐаЁвҐ ў аЁ ­в');{зЁв Ґ¬ ®вўҐв Ї®«м§®ў вҐ«п}
writeln;
case response of
1:add_hash(_hash,get_word('‚ўҐ¤ЁвҐ, зв® ¤®Ў ўЁвм ў ¬ ббЁў'));{¤®Ў ў«Ґ­ЁҐ н«Ґ¬Ґ­в  ў ¬ ббЁў}
2:if(not delete_hash(_hash,get_word('‚ўҐ¤ЁвҐ, зв® г¤ «Ёвм Ё§ ¬ ббЁў ')))then{г¤ «Ґ­ЁҐ н«Ґ¬Ґ­в  Ё§ ¬ ббЁў }
writeln('<< ќ‹…Њ…Ќ’ Ќ… ЌЂ‰„…Ќ >>');
3:if(find_hash(_hash,get_word('‚ўҐ¤ЁвҐ, зв® ­г¦­® ­ ©вЁ')))then{Ї®ЁбЄ н«Ґ¬Ґ­в  ў ениҐ}
writeln('<< ќ‹…Њ…Ќ’ ЌЂ‰„…Ќ >>')
else
writeln('<< ќ‹…Њ…Ќ’ Ќ… ЌЂ‰„…Ќ >>');
4:exit:=true;{ўл室}
end;
end;
end.