Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

RFpro.ru: Программирование на Delphi и Lazarus


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 10270
∙ повысить рейтинг »
Орловский Дмитрий
Статус: Мастер-Эксперт
Рейтинг: 7137
∙ повысить рейтинг »
Boriss
Статус: Академик
Рейтинг: 2404
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Delphi и Lazarus

Номер выпуска:1622
Дата выхода:02.04.2012, 14:30
Администратор рассылки:Киселёва Алёна aka Verena (Академик)
Подписчиков / экспертов:146 / 98
Вопросов / ответов:1 / 1

Консультация # 185661: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Нужно написать программу, реализующую комбинированный способ организации таблицы идентификаторов. Идентификаторы берутся из файла. Для организации таблицы используется простейшая хэш-функция "Сумма кодов первой и второй букв", а при возникновении коллизий и...


Консультация # 185661:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Нужно написать программу, реализующую комбинированный способ организации таблицы идентификаторов. Идентификаторы берутся из файла.
Для организации таблицы используется простейшая хэш-функция "Сумма кодов первой и второй букв",
а при возникновении коллизий используется бинарное дерево.


Вот программа http://rfpro.ru/upload/7776
Большая часть задания в ней сделана,но в ней нужно еще создать второй stringgrid для поиска коллизий и выводить все коллизии в stringgrid, а также
сообщать среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.
Помогите пожалуйста мне это реализовать, т.к. мне совсем непонятно как это сделать.

Немного теории:
Ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции, называется коллизией.

Дата отправки: 25.03.2012, 14:11
Вопрос задал: novij2011 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »


Консультирует Сергей Бендер (Профессионал):

Здравствуйте, novij2011!

Можно добавить вот такую рекурсивную процедуру

Код :
procedure TForm1.Output(IDIndex:integer);
begin

     if IDTable[IDIndex].Left <> 0 then Output(IDTable[IDIndex].Left);
     sg2.Cols[0].Add(IDTable[IDIndex].Name);
     if IDTable[IDIndex].Right <> 0 then Output(IDTable[IDIndex].Right);
end;


Плюс соответствующие исправления в Button1Click и определении TForm1
Итого, вот как выглядит Unit1.pas

Код :
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, ID, ExtCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    ESearch: TEdit;
    sg: TStringGrid;
    Edit1: TEdit;
    Label1: TLabel;
    sg2: TStringGrid;
    Label2: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Output(IDIndex:integer);

  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
   IDTable: array of TID;
  HashTable: array of integer;
  CollisionQuantity: integer;
  CompareQuantity: integer;

implementation

{$R *.dfm}

procedure MakeTreeNode(HashIndex:integer; IDIndex:integer);
begin
  if IDTable[HashIndex].Name<IDTable[IDIndex].Name then
  begin
    if IDTable[HashIndex].Right = 0 then
      IDTable[HashIndex].Right := IDIndex
      else
      MakeTreeNode(IDTable[HashIndex].Right,IDIndex);
  end;
  if IDTable[HashIndex].Name>IDTable[IDIndex].Name then
  begin
    if IDTable[HashIndex].Left = 0 then
      IDTable[HashIndex].Left := IDIndex
      else
      MakeTreeNode(IDTable[HashIndex].Left,IDIndex);
  end;
end;
procedure HashTreeBuild(N:integer);
var
  i:integer;
begin
  for i:=1 to N do
  begin
    if HashTable[IDTable[i].Hash]=0  then
      HashTable[IDTable[i].Hash] := i
    else
    begin
      Inc(CollisionQuantity);
      MakeTreeNode(HashTable[IDTable[i].Hash],i);
    end;
  end;
end;
function GetIDIndex(SearchID:TID;HashIndex:integer):integer;
begin
 if IDTable[HashIndex].Name=SearchID.Name then
    begin
        Inc(CompareQuantity);
        Result:=HashIndex;
        exit;
    end;
    if IDTable[HashIndex].Name<SearchID.Name then
    begin
        Inc(CompareQuantity);
        if IDTable[HashIndex].Right<>0 then
        begin
          result:= GetIDIndex(SearchID,IDTable[HashIndex].Right);
          exit;
        end
        else
        begin
          result := 0;
          exit;
        end;
    end
    else
    begin
        inc(CompareQuantity);
        if IDTable[HashIndex].Left=1 then
        begin
          result := GetIDIndex(SearchID,IDTable[HashIndex].Left);

          exit;
        end
        else
        begin
          result := 0;
          exit;
        end;
    end
end;

procedure TForm1.Output(IDIndex:integer);
begin

     if IDTable[IDIndex].Left <> 0 then Output(IDTable[IDIndex].Left);
     sg2.Cols[0].Add(IDTable[IDIndex].Name);
     if IDTable[IDIndex].Right <> 0 then Output(IDTable[IDIndex].Right);
end;

procedure TForm1.Button1Click(Sender: TObject);

var
d1,d3:TDateTime;
  Hash:integer;
  SearchID:TID;
  SearchString : string;
  HashIndex:integer;
  IDIndex:integer;
  i,j:integer;
begin
d1:=Now();
  SearchString := eSearch.Text;
  SearchID := TID.Create;
  SearchID.Name := SearchString;
  Hash := SearchID.Hash;
  HashIndex := HashTable[Hash];
  CompareQuantity := 0;

  IDIndex := GetIDIndex(SearchID,HashIndex);

  memo1.Clear;

  if IDIndex<>0 then
  begin





    memo1.Lines.Add('Èäåíòèôèêàòîð íàéäåí, åãî èíäåêñ = :'+IntToStr(IDIndex));
    memo1.Lines.Add('Ñðàâíåíèé:'+IntToStr(CompareQuantity));
      memo1.Lines.Add('Êîëëèçèé:'+IntToStr(CollisionQuantity));

  end

  else
  begin
    memo1.Lines.Add('Èäåíòèôèêàòîð íå íàéäåí');
    memo1.Lines.Add('Ñðàâíåíèé:'+IntToStr(CompareQuantity));
      memo1.Lines.Add('Êîëëèçèé:'+IntToStr(CollisionQuantity));

  end  ;
    d3:=Now();

  edit1.Text:=formatdatetime('hh:mm:ss:ms',(d1-d3));
  if CollisionQuantity >=1 then begin
     sg2.cells[0,0]:='¹ ID. c êîëëèçèåé';
     sg2.cells[1,0]:=(IntToStr(IDIndex));
     i:=2;
     qwe(IDIndex);
  end;


end;


procedure TForm1.FormCreate(Sender: TObject);
var
  N:integer;
  i:integer;
begin
  memo1.Lines.LoadFromFile('Input.txt');
  N := memo1.Lines.Count;

  SetLength(IDTable,N+1);
  for i:=0 to N do
  begin
    IDTable[i] := TID.Create;
    IDTable[i].Name :=  memo1.Lines.Strings[i-1];
  end;

  SetLength(HashTable,256);
  for i:=0 to 255 do HashTable[i] := 0;

  HashTreeBuild(N);

  sg.Rows[0].Add('èíäåêñ');
  sg.Rows[0].Add('èìÿ èäåíò.');
  sg.Rows[0].Add('õýø-ôóíêöèÿ');
  sg.Rows[0].Add('ïîëå Left');
  sg.Rows[0].Add('ïîëå Right');

  for i := 1 to N do
  begin
    sg.Rows[i].Add(IntToStr(i));
    sg.Rows[i].Add(IDTable[i].Name);
    sg.Rows[i].Add(IntToStr(IDTable[i].Hash));
    sg.Rows[i].Add(IntToStr(IDTable[i].Left));
    sg.Rows[i].Add(IntToStr(IDTable[i].Right));
    sg.RowCount := sg.RowCount+1;
  end;
  memo1.Clear;
  memo1.Lines.Add('Ââåäèòå èìÿ èäåíòèôèêàòîðà');
  memo1.Lines.Add('Êîëëèçèé:'+IntToStr(CollisionQuantity));

end;

end.

Консультировал: Сергей Бендер (Профессионал)
Дата отправки: 02.04.2012, 14:13
Рейтинг ответа:

НЕ одобряю 0 одобряю!


Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!



В избранное