Форум программистов, компьютерный форум CyberForum.ru

Хеширование: реализовать пользовательский поиск ключа - C++

Восстановить пароль Регистрация
 
ugabuga
1 / 1 / 0
Регистрация: 05.04.2012
Сообщений: 22
17.10.2012, 15:41     Хеширование: реализовать пользовательский поиск ключа #1
Всем привет!

Ребята очень нуждаюсь в вашей помощи.
Есть хеш функция:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <time.h>
using namespace std;
 
 
int hash_table[ArrSize];
void build_hash_table()
{
    memset(hash_table,-1,ArrSize*sizeof(int));const int ArrSize=10;
}
int hash_function(int key)
{
    return key%ArrSize;
}
int rehash(int i)
{
    if(i<ArrSize-1)
        return ++i;
    else
        return 0;
}
int Insert(int key)
{
    int index=hash_function(key);
    cout<<"key is: "<<index<<endl;
    if(hash_table[index]==-1)//indicate free space 
    {
        hash_table[index]=key;
        return 1;
    }
    else
    {
        cout<<"collision detected!"<<endl;
        int new_index=rehash(index);
        while(new_index!=index)
        {
            if(hash_table[new_index]==-1)
            {
                hash_table[new_index]=key;
                return 1;
            }
            new_index=rehash(new_index);
        }
        return 0;
    }
}
int Find(int key)
{
    int index=hash_function(key);
    if(hash_table[index]==key)
        return index;
    else
    {
        int new_index=rehash(index);
        while(new_index !=index)
        {
            if(hash_table[new_index]==key)
                return new_index;
            new_index=rehash(new_index);
        }
        return -1;
    }
}
int main ( ) 
{
    int i;
    int ArrSize;
    cout << "Enter size of Array: "<<endl;
    cin >> ArrSize;
    int *Arr = new int[ArrSize];
 
    for (int i = 0; i < ArrSize; i ++)
    { 
        srand((unsigned)time(NULL));
        Arr[i] = rand()%900+100;
        for(int j = 0; j < i; j++)
        {
            if(Arr[j] == Arr[i])
            {
                Arr[i] = rand()%900+100;
            }
        }
        cout << i <<"| "<< Arr[i] << endl;
    }
    build_hash_table();
    for(int i=0;i<ArrSize;i++)
        Insert(Arr[i]);
    for(i=0;i<ArrSize;i++)
        cout<<hash_table[i]<<endl;
    int y=Find(10);
    if(y==-1)
        cout<<"Element not exists!";
    return 0;
}

ГСЧ реализован, но есть два момента. Мне надо реализовать пользовательский поиск ключа ->> Введите ключ и поиск этого ключа в Рандом массиве. И еще надо убрать константное значение, ибо у меня задача реализовать диапазон чисел от 100 до 1000 и размер массива задается пользователем.
Пробывал изменить const int ArrSize=10; на const int ArrSize=100; Но без успешно, после 10 елемента выдает кракозябры в виде : -1 0 2131239 и.т.п Помоги пожалуйста переделать этот код... Я без силен
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2012, 15:41     Хеширование: реализовать пользовательский поиск ключа
Посмотрите здесь:

C++ C++ Как реализовать поиск на Русском в консоле
Контейнер map: реализовать проверку на уникальность ключа C++
C++ Реализовать ввод данных в структуру и поиск информации в ней
Поиск ключа в бинарном дереве поиска C++
Поиск ключа в массиве C++
C++ Вставить функцию в код по подсчету времени на нахождения ключа в массиве (бинарный поиск)
Реализовать поиск без учёта регистра C++
C++ Реализовать ввод, вывод и поиск данных

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ExcellencE
20 / 20 / 2
Регистрация: 22.08.2011
Сообщений: 79
18.10.2012, 17:55     Хеширование: реализовать пользовательский поиск ключа #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "stdafx.h"
#include <iostream>
#include <time.h>
 
using namespace std;
 
int* hash_table;
int hash_function(int key, int ArrSize)
{
    return key%ArrSize;
}
int rehash(int i, int ArrSize)
{
    if(i<ArrSize-1)
        return ++i;
    else
        return 0;
}
int Insert(int key, int ArrSize)
{
    int index=hash_function(key,ArrSize);
    cout<<"key is: "<<index<<endl;
    if(hash_table[index]==-1)//indicate free space 
    {
        hash_table[index]=key;
        return 1;
    }
    else
    {
        cout<<"collision detected!"<<endl;
        int new_index=rehash(index,ArrSize);
        while(new_index!=index)
        {
            if(hash_table[new_index]==-1)
            {
                hash_table[new_index]=key;
                return 1;
            }
            new_index=rehash(new_index,ArrSize);
        }
        return 0;
    }
}
int Find(int key,int ArrSize)
{
    int index=hash_function(key,ArrSize);
    if(hash_table[index]==key)
        return index;
    else
    {
        int new_index=rehash(index,ArrSize);
        while(new_index !=index)
        {
            if(hash_table[new_index]==key)
                return new_index;
            new_index=rehash(new_index,ArrSize);
        }
        return -1;
    }
}
int main ( ) 
{
    int i;
    int ArrSize;
    cout << "Enter size of Array: "<<endl;
    cin >> ArrSize;
    int *Arr = new int[ArrSize];
    hash_table = new int[ArrSize];
    for(int i=0;i<ArrSize;i++)
        hash_table[i] = -1;
 
    for (int i = 0; i < ArrSize; i ++)
    { 
        srand((unsigned)time(NULL));
        Arr[i] = rand()%900+100;
        for(int j = 0; j < i; j++)
        {
            if(Arr[j] == Arr[i])
            {
                Arr[i] = rand()%900+100;
            }
        }
        cout << i <<"| "<< Arr[i] << endl;
    }
    for(int i=0;i<ArrSize;i++)
        Insert(Arr[i],ArrSize);
    for(i=0;i<ArrSize;i++)
        cout<<hash_table[i]<<endl;
    int y=Find(10,ArrSize);
    if(y==-1)
        cout<<"Element not exists!";
    System::Threading::Thread::Sleep(5000);
    return 0;
}
Yandex
Объявления
18.10.2012, 17:55     Хеширование: реализовать пользовательский поиск ключа
Ответ Создать тему
Опции темы

Текущее время: 08:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru