1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

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

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

  1. Syalon

    Syalon Гость

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

    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

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

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

    Код:
    #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;
    }
    Понимаю программа чрезвычайно сложная, но может быть кто-нибудь уже сталкивался с подобной задачей и укажет на ошибку в алгоритме. Это последнее задание перед экзаменом. Даже не представляете как я буду счастлив, если наконец удастся решить его.
     
Загрузка...

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