Реализация Хеш таблицы., Проблема с вводом ключей в хеш таблицу. Опции

[dron4ik]

Задание. Реализовать метод открытого хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1--->>(((((Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа: код (End) = код (E) + код (n) + код (d). Преобразование числового кода ключа в значение индекса выполнить с помощью простейшей хеш-функции, которая берет остаток от целочисленного деления кода на размер хеш-таблицы делить надо на константу m))). В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.
Программа должна выполнять следующие действия:
• добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
• поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
• вывод текущего состояния таблицы на экран
• удаление заданного ключа из таблицы
Алгоритм удаления:
• вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице
• если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей
• если удаляемый элемент найден в списке, то производится его удаление с изменением указателей
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска.

Все работает вроде верно, но когда сдавал преподу он мне сказал ввести ключ var а потом ввести ключ avr//и программа сразу вылетела...препод сказал что у мя чтото с процедурой добавления и проблема с указтелями....ни как не пойму что и как исправить..помогите пожалуйста.(

program Work3;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const hsize=15;

type PocketArr=record
       Key:Integer;
       Str:String;
     end;

     type Plist=^TList;
     TList=record
        elt:String;
        npt:Plist;
     end;

     ListFL=record
       First,Last:Plist;
       Str:String;
     end;

var HashTable:Array [0..hsize] of ListFL;
    H, k, i: integer;
    Cmp:Integer;

function AddToDList(var obj:ListFL; elt:String):Integer;
var Res:Integer;
    PTemp: PList;
begin
  Res:=0;
  If obj.First=nil then
  begin
    New(PTemp);
    pTemp^.elt:=elt;
    obj.First:=PTemp;
    obj.Last:=PTemp;
    Res:=1;
  end
  else
  begin
    New(PTemp);
    pTemp^.elt:=elt;
    obj.Last^.npt:=Ptemp;
    obj.Last:=pTemp;
  end;
  Result:=Res;
end;

procedure PrintList(obj:ListFL);
var PCurrent: PList;
begin
  if obj.First<>nil then
  begin
    PCurrent:=obj.First;
    while PCurrent<>nil do
    begin
      write(PCurrent^.elt,' ');
      PCurrent:=PCurrent^.npt;
    end;
  end else Write('ãáâ® ');
end;

function FindList(str:String; obj:ListFL):Boolean;
var PCurrent: PList;
    Res:Boolean;
begin
  Res:=False;
  if obj.First<>nil then
  begin
    PCurrent:=obj.First;
    while PCurrent<>nil do
    begin
      Inc(cmp);
      If PCurrent^.elt=Str then
      begin
        Res:=True;
        break;
      end;
      PCurrent:=PCurrent^.npt;
    end;
  end else Res:=False;
  Result:=Res;
end;

procedure PrintArrayList(obj: array of ListFL);
var i:Integer;
begin
  for i:=0 to High(obj) do
  begin
    Write(i,': ');
    Write(obj[i].Str,' ');
    PrintList(HashTable[i]);
    writeln;
  end;
end;

Function Hash(str : string):Integer;
var   Sum,i,Len,Res: Integer;
begin
  Sum:=0;
  Len:= Length(str);
  for i := 1 to Len do Sum:=Sum+ord(str[i]);
  Res:=Sum mod (High(HashTable)+1);
  Result:=Res;
end;

function AddToHAsh(str: String; var arr: array of ListFL):Integer;
var hsh:Integer;
    r:Boolean;
begin
  hsh:=Hash(str);
  Result:=hsh;
  If arr[hsh].Str='' then arr[hsh].Str:=str     //äîáàâëÿåì â êëþ÷
  else begin
    If arr[hsh].Str<>str then AddToDList(arr[hsh],str); //äîáàâëÿåì â ñïèñîê ñ èíäåêñîì hsh
  end;
end;

function DelFromDList(str:String;var obj:ListFL):Integer;
var PCurt,Pprev:PList;
    Res:Integer;
begin
  PCurt:=obj.First;
  while (PCurt<>nil) And (PCurt^.elt<>str) do
  begin
    Pprev:=PCurt;
    PCurt:=PCurt^.npt;
  end;
  If PCurt<>nil then
  begin
    If obj.First=PCurt then
    begin
      obj.First:=PCurt^.npt;
      Dispose(PCurt);
    end else
    begin
      Pprev^.npt:=PCurt^.npt;
      Dispose(PCurt);
    end;
  Res:=1;
  end
  else Res:=0;
  Result:=Res;
end;

function DelFromHash(str: String; var arr: array of ListFL):Integer;
var hsh,res:Integer;
    PTemp:PList;
begin
  hsh:=Hash(str);
  Res:=0;
  If str=arr[hsh].Str then
  begin
    If arr[hsh].First=nil then arr[hsh].Str:=''
    else begin
      PTemp:=arr[hsh].First;
      arr[hsh].First:=PTemp^.npt;
      arr[hsh].Str:=PTemp^.elt;
      Dispose(PTemp);
    end;
    Res:=1;
  end else If DelFromDList(str,arr[hsh])=1 then Res:=1;
  Result:=Res;
end;

function FindInHash(str: String; arr: array of ListFL):Integer;
var hsh,r:Integer;
begin
  hsh:=Hash(str);
  cmp:=0;
  Inc(cmp);
  If str=arr[hsh].Str then R:=hsh else
  begin
    If FindList(str,arr[hsh])=true then R:=hsh else R:=-1;
  end;
  writeln(cmp);
  Result:=R;
end;

procedure ShowMenu;
begin
  WriteLn('0: Add to hash table');
  WriteLn('1: Del from hash table');
  WriteLn('2: Find in hash table');
  WriteLn('3: Print hash table');
  WriteLn('4: Exit');
end;

procedure Command;
var num:Integer;
    cmd: Char;
    str: String;
begin
  Write('Enter command: ');
  ReadLn(cmd);
  case cmd of
    '0':
    begin
      str:='';
      while str='' do
      begin
        Write('Enter String: ');
        ReadLn(str);
      end;
      num:=AddToHAsh(str,HashTable);
      If num=-1 then WriteLn('Add canceled') else WriteLn(num);
    end;
    '1':
    begin
      Write('Enter String: ');
      ReadLn(str);
      If DelFromHash(str,HashTable)=0 then WriteLn('Can`t find string') else WriteLn('Element Successfull deleted');
    end;
    '2':
    begin
      Write('Enter String: ');
      ReadLn(str);
      num:=FindInHash(str,HashTable);
      If num=-1 then WriteLn('Can`t find string') else WriteLn('Element exsist and has key ',num);
    end;
    '3': PrintArrayList(HashTable);
    '4': Exit;
  end;
  Command;
end;

begin
  ShowMenu;
  Command;
end.

[volvo]

Ты при создании нового элемента списка не устанавливаешь ему указатель на следующий элемент в nil:

function AddToDList(var obj:ListFL; elt:String):Integer;
var Res:Integer;
    PTemp: PList;
begin
  Res:=0;
  If obj.First=nil then
  begin
    New(PTemp);
    pTemp^.elt:=elt; pTemp^.npt := nil; // <--- Раз 
    obj.First:=PTemp;
    obj.Last:=PTemp;
    Res:=1;
  end
  else
  begin
    New(PTemp);
    pTemp^.elt:=elt;  pTemp^.npt := nil; // <--- Два
    obj.Last^.npt:=Ptemp;
    obj.Last:=pTemp;
  end;
  Result:=Res;
end;

, хотя эту процедуру можно сделать короче, потому что выделение памяти будет происходить независимо от того, равняется obj.First nil-у или нет, вынеси это в начало процедуры...

[dron4ik]

А как добавить в конец вспомогательного списка элемент который конфликтует с другим? а то он не правильно добавляется.

[volvo]

Что за вспомогательный список? Что где конфликтует? Что неправильно добавляется? Ввел я var, потом ввел avr, потом выбрал "Print hash table" - не увидел, что где неправильно добавляется. Все добавилось и напечаталось:

0: Add to hash table
1: Del from hash table
2: Find in hash table
3: Print hash table
4: Exit
Enter command: 0
Enter String: var
9
Enter command: 0
Enter String: avr
9
Enter command: 3
0:  ?aáד®
1:  ?aáד®
2:  ?aáד®
3:  ?aáד®
4:  ?aáד®
5:  ?aáד®
6:  ?aáד®
7:  ?aáד®
8:  ?aáד®
9: var avr
10:  ?aáד®
11:  ?aáד®
12:  ?aáד®
13:  ?aáד®
14:  ?aáד®
15:  ?aáד®

Что неправильно?

[dron4ik]

если два ключа добавляются в одну ячейку то один ключ добавляется в ячейку а другой в конец вспомогательного список. как это сделать?

[dron4ik]

неужели ни кто незнает?