Постройка хэш-таблицы

  • Автор темы Syalon
  • Дата начала
S

Syalon

Гость
#1
Здравствуйте, Уважаемые программисты! Прошу вашей помощи в решении такого задания:

1. Построить хэш-таблицу методом линейных проб для слов заданного текста. Текст находится в некотором файле. Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.
2. Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Файл с текстом должен быть тот же, что и п.1. Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.
Программу написать на Си.

Уже долго не мог осилить задачу, благо нашел нужные алгоритмы. Программа вроде как запускается, но выдает неверные данные. А именно:

Файл содержит 174 слова. Вот данные которые должна выдавать программа:

Lineinie probi:
Number of the words in file= 174 // Количество слов в тексте
Rasmer HashTable= 118 // Размер таблицы
Number collision= 214 // Число коллизий

Kvadratichnie probi:
Number of the words in file= 174
Rasmer HashTable= 129
Number collision= 46

А вот данные которые она выдает:

Lineinie probi:
Number of the words in file= 116
Rasmer HashTable= 77 // Заметьте, все данные это 2\3 от правильного результата!
Number collision= 30

Kvadratichnie probi:
Number of the words in file= 116 // Почему-то прога не выдает результат по квадратиным пробам.
Rasmer HashTable= 77
Number collision= 30

Эксперементальным путем я выяснил что программа "пропускает" каждое третье слово в тексте, т.е. почему-то игнорирует их.

Код программы:

C++:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const int maxn=10000;
struct node
{
char znac[20];
int key;
};

int kolcol;
int kolsl;
int ObTable;

node hashtable[maxn];

int hash(char* s)
{
int result=0;
int i=0;
for (i=0; i<strlen(s); i++)
{
result=(255*result+abs(s[i]))%kolsl;
}
return result;
}

//линейные пробы
int linhash(char* s)
{
//получаем хэш-код слова
int hs=hash(s);
int num=hs;
//идем по массиву пока не найдем ему место
//сразу же считаем количество коллизий
while (1)
{
//если в ячейке таблицы уже есть значение
//то коллизия и переходим к следующему полю
if (hashtable[num].key!=0)
{
kolcol++;
//строки равны то выходим
if (strcmp(hashtable[num].znac,s)==0) break;
num++;
//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<kolsl) kolsl=num;
if (num>maxn) num=num%maxn;
}
else
{
ObTable++;
strcpy(hashtable[num].znac,s);
hashtable[num].key=hs;
break;
}
}
return 0;
}

//квадратичные пробы
int kvhash(char* s)
{
//получаем хэш-код слова
int hs=hash(s);
int num=hs;
int zn=1;
int i=1;
//идем по массиву пока не найдем ему место
//сразу же считаем количество коллизий
while (1)
{
//если в ячейке таблицы уже есть значение
//то коллизия и переходим к следующему полю
if (hashtable[num].key!=0)
{
kolcol++;
//строки равны то выходим
if (strcmp(hashtable[num].znac,s)==0) break;
//находим новую позицию как квадрат, меняем знак
num=(num+i*zn)*(num+i*zn); zn=-zn; 
if (zn==1) i++;
//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<maxn) kolsl=num;
//проверяем, не вышли ли за пределы массива
if (num>maxn) num=num%maxn;
if (num<0) num=1;
}
else
{
ObTable++;
strcpy(hashtable[num].znac,s);
hashtable[num].key=hs;
break;
}
}
return 0;
} 


int main()
{

char s[20];
int KolSlFile=0;
kolsl=200;
ObTable=0;
kolcol=0;
FILE* f = fopen( "file.txt", "rt" );
//очищаем хеш-таблицу
memset(hashtable,NULL,sizeof(hashtable));
while (!feof(f))
{
KolSlFile++;
fgets( s, sizeof(s), f );
if (strcmp(s," ")==0) continue;
linhash(s);
}
fclose(f);
printf("Lineinie probi:\n Number of the words in file= %i\n Rasmer HashTable= %i\n Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
f = fopen( "file.txt", "rt" );
memset(hashtable,0,sizeof(hashtable));
KolSlFile=0;
ObTable=0;
kolcol=0;
while (!feof(f))
{
KolSlFile++;
fgets( s, sizeof(s), f );
if (strcmp(s," ")==0) continue;
kvhash(s);
}
printf("Kvadratichnie probi:\n Number of the words in file= %i\n Rasmer HashTable= %i\n Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
fclose(f);
getchar();

return 0;
}
Понимаю программа чрезвычайно сложная, но может быть кто-нибудь уже сталкивался с подобной задачей и укажет на ошибку в алгоритме. Это последнее задание перед экзаменом. Даже не представляете как я буду счастлив, если наконец удастся решить его.