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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Syalon, 11 ноя 2009.

  1. Syalon

    Syalon Гость

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

    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;
    }
    Понимаю программа чрезвычайно сложная, но может быть кто-нибудь уже сталкивался с подобной задачей и укажет на ошибку в алгоритме. Это последнее задание перед экзаменом. Даже не представляете как я буду счастлив, если наконец удастся решить его.
     
Загрузка...
Похожие Темы - Постройка хэш таблицы
  1. lmike
    Ответов:
    5
    Просмотров:
    548
  2. HelenHelen
    Ответов:
    1
    Просмотров:
    1.560
  3. sasha465
    Ответов:
    0
    Просмотров:
    1.468
  4. VladSh
    Ответов:
    27
    Просмотров:
    8.766

Поделиться этой страницей