IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> Реализация на С++, Хэш-таблица
KerK
сообщение 21.11.2006 12:23
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


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

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


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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 21.11.2006 12:29
Сообщение #2


Гость






А в std::hash_map уже все реализовано... Или тебе самому хочется? smile.gif
 К началу страницы 
+ Ответить 
KerK
сообщение 21.11.2006 12:42
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 21.11.2006 12:29) *

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


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

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

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

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

Сообщение отредактировано: KerK - 21.11.2006 12:51
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 21.11.2006 12:59
Сообщение #4


Гость






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

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

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


P.S.

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

struct rec {
  int key;
  int inf;

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


Кстати, зайди вот сюда: Указатель как тип (синтаксис)
Тут было нечто очень похожее (об указателях на структуру)
 К началу страницы 
+ Ответить 
KerK
сообщение 21.11.2006 13:16
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Лучше буду без 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;



}



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 17.07.2025 21:19
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"