Реализация на С++, Хэш-таблица Опции

[KerK]

Помогите пожалуйста реазлизовать на СИ

есть такой код

Uses CRT;

const n = 100;

type u = ^rec;
     rec = record
           key: integer;
           inf: integer;
           ptr: u;
           end;
     hTab = array [1..n] of rec;


var t : hTab;
    ch : char;
    hKey, i : integer;


function HashFunc(hKey : integer) : integer;
begin
    HashFunc := hKey mod n ;
end;

procedure AddRecord (var t : hTab);
var tmp : u;
    i   : integer;
    r   : rec;

begin
    Write('Vvedite klych dobavljaemoj zapisi    :  ');
    ReadLn(r.key);
    Write('Vvedite niformacionnoe pole zapisi   :  ');
    ReadLn(r.inf);

    r.ptr := nil;

    i := HashFunc(r.key);

    if t[i].key = 0 then
    begin
        t[i] := r;
        WriteLn('Zapis poneshena v poziciju ', i, '.');
    end
    else
    begin
        new(tmp);
        tmp^ := r;
        tmp^.ptr := t[i].ptr;
        t[i].ptr := tmp;
        Writeln('Pozicija ', i, ' zanjata.');
        Writeln('Zapis v cepochre perepolnenija.');
	 end;
	 ReadKey;
end;

procedure FindRec(var t : hTab; hKey : integer);
var
    i : integer;
    p : u;
begin
    i := HashFunc(hKey);
    WriteLn(' Poisk v tablice...');

    if t[i].key = hKey then
    begin
        WriteLn('Zapis najdena v pozicii  ', i);
        WriteLn('Znjachenie inf. polja ravno  : ', t[i].inf);
        ReadKey;
        exit;
    end;
    if t[i].key = 0 then
    begin
        WriteLn('Zapisi v tablice net.');
        ReadKey;
        exit;
    end;

    WriteLn(i, ' - ', t[i].key);
    WriteLn('Poisk v cepochke perepolnenija...');

    p := t[i].ptr;
    while (p <> nil) AND (p^.key <> hKey) do
    begin
      Write(p^.key,' ');
      p := p^.ptr;
   end;

   WriteLn;

   if p <> nil then
   begin
       WriteLn ('Zapis najdena');
       WriteLn ('Znachenie inf. polja -- ', p^.inf);
   end
   else
       WriteLn ('Zapis ne najdena');

   ReadKey;
end;

begin
   for i := 1 to n do
     t[i].key := 0;
   repeat
     ClrScr;

     WriteLn('a================================¬');
     WriteLn('¦ 1 - Zanesenie zapisi v tablicu ¦');
     WriteLn('¦   2 - Poisk zapisi v tablice   ¦');
     WriteLn('¦--------------------------------¦');
     WriteLn('¦           0 - Vixod            ¦');
     WriteLn('L================================-');

     ch := ReadKey;
     WriteLn;

     case ch of
       '1' : begin
               AddRecord(t);
               WriteLn('Press any key');
             end;
       '2' : begin
               Write('Vvedite kljuch iskomoj zapisi  :  ');
               ReadLn(hKey);
               FindRec(t, hKey);
             end;
     end;

   until ch = '0';
end.

Нужно переделать в СИ, возникли проблемы с

Код

type u = ^rec;
     rec = record
           key: integer;
           inf: integer;
           ptr: u;
           end;

Да и вобще с указателями.... если можно объясните пожалуйста...

Код

function HashFunc(hKey : integer) : integer;
begin
    HashFunc := hKey mod n;
end;

еще проблема с этим... mod n


Сообщение отредактировано: KerK - 21.11.2006 12:29

[volvo]

А в std::hash_map уже все реализовано... Или тебе самому хочется?

[KerK]

А в std::hash_map уже все реализовано... Или тебе самому хочется?

А для такой задачи пойдет?

Реализовать в виде класса на языке С++ абстрактный тип данных множество с операциями
добавления элемента, удаления, проверки наличия и т.д.Для хранения элементов
множества использовать хеш-таблицу, элементами множества являются строки ограниченной длины.

если да, то как пользоваться hash_map?

Но лучше самому...т.к. использовать std будет слишком просто, и препод это не оценит... ))

Сообщение отредактировано: KerK - 21.11.2006 12:51

[volvo]

Ну, насчет пойдет или нет - это ты сам решай, дело все в том, что и реализация множеств в STL тоже есть:
STL :: hash_multiset
, однако ты реализуешь это самостоятельно...

если все-таки готовое решение из STL подойдет, то:
STL :: hash_map

Если решишь, что лучше сделать самому - говори, поможем разобраться с указателями...


P.S.

У тебя возникают проблемы с указателем "на самого себя"? Тогда это все просто решается:

struct rec {
  int key;
  int inf;

  struct rec *ptr; // структура уже определена, ты можешь пользоваться ее названием
}

Кстати, зайди вот сюда: Указатель как тип (синтаксис)
Тут было нечто очень похожее (об указателях на структуру)

[KerK]

Лучше буду без STL. Помогите разобраться, вот с этим местом кода...

type u = ^rec;
     rec = record
           key: integer;
           inf: integer;
           ptr: u;
           end;
     hTab = array [1..n] of rec;


var t : hTab;
    ch : char;
    hKey, i : integer;

procedure AddRecord (var t : hTab);
var tmp : u;
    i   : integer;
    r   : rec;

begin
    Write('Vvedite klych dobavljaemoj zapisi    :  ');
    ReadLn(r.key);
    Write('Vvedite niformacionnoe pole zapisi   :  ');
    ReadLn(r.inf);

    r.ptr := nil;

    i := HashFunc(r.key);

    if t[i].key = 0 then
    begin
        t[i] := r;
        WriteLn('Zapis poneshena v poziciju ', i, '.');
    end
    else
    begin
        new(tmp);
        tmp^ := r;
        tmp^.ptr := t[i].ptr;
        t[i].ptr := tmp;
        Writeln('Pozicija ', i, ' zanjata.');
        Writeln('Zapis v cepochre perepolnenija.');
	 end;
	 ReadKey;
end;

Не могу понять, каким макаром реализовать в СИ...

struct rec {
  int key;
  int inf;

  struct rec *ptr; // структура уже определена, ты можешь пользоваться ее названием
}
...
...
...
void HashFunc()
{
int i;
а как быть с
 tmp : u;
 r   : rec;



}