VPF::[C++] хеш таблица!!! - Форум программистов

werywery

Дата 30.10.2009, 11:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 29.10.2009

Репутация: нет
Всего: нет

Здравствуйте всем!!!

если вас не затруднит подскажите пожулуйста.......

Вобщем, прога строит хеш таблицу элементы которой, как вы видите, генерируются с помощью датчика случайных чисел.... Хэш-функция: f(x)=x/11....
Теперь непосредственно вопрос - в этой программе я осуществил алгоритм разрешение коллизий методом цепочек,.....
подскажите пожалуйста, как ее реализовать с помощью метода разрешения конфликта - квадратичные пробы...(то есть, если я правильно понял, квадратичные пробы предполагают что каждая ячейка пустая, и всегда можно узнать занята ли ячейка, алгоритм опробывает все ячейки по-кругу пока не встретит открытый адрес).... все роде так просто, но никак не выходит...

Код


//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

const n=4, m=47;
int a[m];
int f;
struct node
  {
  int data;
  node *next;
  };
node ah[m/n];

void refresh_all();
int rando(int nn);
int cash(int x);


//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}


//---------------------------------------------------------------------------

void __fastcall TForm1::N3Click(TObject *Sender)
{
Close();
}


//---------------------------------------------------------------------------

void __fastcall TForm1::FormActivate(TObject *Sender)
{
for (int i=0; i<m; i++)
  Form1->StringGrid->Cells[0][i+1]=IntToStr(i+1);
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button_closeClick(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------


void random_all()
{
if ((n==0) || (m==0))
  return;
for (int i=0; i<m; i++)
 a[i]=((random(9)+1)*1000+random(999));
};
//---------------------------


void checkarray()
{
int check=0;
for (int i=0; i<m; i++)
  {
  for (int j=0; j<m; j++)
    if (i!=j)
      if (a[j]==a[i])
        {
        a[j]=((random(9)+1)*1000+random(999));
        check=1;
        break;
        };
  if (check)
    break;
  };
if (check)
  checkarray();
};
//---------------------------------
int heshf(int x)
{
return (x/11)%m;
};
//--------------------------------------



void hesh()
{
int count;
count=m/2;
node *temp;
for (int i=0; i<=count; i++)
  {
  ah[i].data=0;
  ah[i].next=0;
  temp=&ah[i];
  node *temp2;
  do{
    temp2=temp->next;
    free(temp);
    }while(temp=temp2);
  };
int index;

for (int i=0; i<m; i++)
  {
  index=heshf(a[i]);
  if (index>=count)
    index=index/count;
  if (0==ah[index].data)
    ah[index].data=a[i];
    else {
      temp=&ah[index];
      do{
      if (!temp->next)
         {
         temp->next=new node;
         temp=temp->next;
         temp->data=a[i];
         temp->next=0;
         };
      }while(temp=temp->next);
      };
  };
};
//------------------------------------



void show_all()
{
Form1->StringGrid->RowCount=m;
Form1->StringGrid_cash->RowCount=(m/2)+1;
for (int i=0; i<m; i++)
  {
  Form1->StringGrid->Cells[0][i+1]=IntToStr(i);
  Form1->StringGrid->Cells[1][i+1]=IntToStr(a[i]);
  };
Form1->StringGrid_cash->ColCount=m+1;
for (int i=0; i<m+1; i++)
  for (int j=0; j<m+1; j++)
    Form1->StringGrid_cash->Cells[j][i+1]=" ";
Form1->StringGrid_cash->ColCount=2;

int countprob=0, empt=0;
double sum=0;

node *temp;
for (int i=0; i<=m/2; i++)
  {

  countprob=0;
  if (ah[i].data==0)
    empt++;

  Form1->StringGrid_cash->Cells[0][i+1]=IntToStr(i);
  temp=&ah[i];
  int j=1;
  do{
    countprob++;
    if (temp->data)
      Form1->StringGrid_cash->Cells[j][i+1]=IntToStr(temp->data);
    j++;
    }
    while(temp=temp->next);
  if (Form1->StringGrid_cash->ColCount<j)
    Form1->StringGrid_cash->ColCount=j;

  sum=sum+((1+countprob)/2)*countprob;

  };

Form1->Label5->Caption=FloatToStr(sum/m);
Form1->Label6->Caption=FloatToStr((double)m/(double)(m+empt));
};



void __fastcall TForm1::N5Click(TObject *Sender)
{
ShowMessage("Программа строит хеш-таблицу, содержащую\nпоследовательность из 47 эл-ов, размерноти 4.\nХеш-функция - сумма цифр числа\nМетод решения - цепочки\n\n\");
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button_exeClick(TObject *Sender)
{
random_all();
checkarray();
hesh();
show_all();
}
//---------------------------------------------------------------------------

void __fastcall TForm1::N7Click(TObject *Sender)
{
  ShowMessage("для запуска программы нажмите Выполнить,\n для завершения работы нажмите Закрыть");
}
//---------------------------------------------------------------------------

Avaj

Дата 30.10.2009, 12:55 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 212
Регистрация: 14.7.2008
Где: Владивосток.

Репутация: нет
Всего: 3

С квадратичными пробами дела обстоят почти так же как и с линейными.

Лин. пробы: Hi = (H0+i) mod N;

Квадр.: Hi = (H0+i^2) mod N;

И уберите ваш GUI, зачем он вам, если вы разбираетесь с алгоритмом?

werywery

Дата 30.10.2009, 15:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 29.10.2009

Репутация: нет
Всего: нет

Покажите пожалуйста на данном примере, как будет выглядеть функция решения коллизий.....???

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »