9 / 9 / 4
Регистрация: 30.10.2011
Сообщений: 80
1

(Хеширования) Разрешение коллизий при хешировании методом открытой адресации

24.10.2012, 21:43. Показов 3648. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доброго времени суток!
Программа реализует алгоритм решения коллизий методом открытой адресации.
Как сделать пошаговый вывод алгоритма в Label2, тоисть key mod 7 = номер ячейки, если ячейка занята, а остаток от деления, например, = 2 то следуйщий вывод (2+1) mod 7 = 3. Вывод продолжается пока key не попадет в свободную ячейку.

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
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int k[7];
int h(int key);
int rh(int i);
void __fastcall insert( int key );
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
int h(int key)
{
        return key % 7;
}
int rh( int i)
{
        return (i+1) % 7;
}
void __fastcall insert( int key )
{
        int j;
        j=h(key);
        while( (k[j]!=key) && (k[j]!=0))
        {
                j=rh(j);
        }
 
        if (k[j]==0)
        {
                k[j]=key;
        }
}
//------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Label1->Caption="";
Label2->Caption="";
       int i;
       int n;
       randomize();
        
                n=random(100);
                
        for(i=0;i<7;i++)
        {
                insert(n);
        }
 
        for(i=0;i<7;i++)
        {
 
                Label1->Caption=Label1->Caption + IntToStr(k[i]) + " ";
        }
 
}
//---------------------------------------------------------------------------
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.10.2012, 21:43
Ответы с готовыми решениями:

Решение коллизий методом открытой адресации(не важно C# или C++)
Посмотрите пожалуйста на код. Не могу понять в чем проблема. Алгоритм с книги Т.Кормена ( ссилка -...

Преданамеренное создание коллизий при хешировании.
Доброе время суток всем. Не знаю, правильно ли я выбрал раздел, но меня интересует информация по...

Разрешение коллизий
Здравствуйте, необходимо мнение и опыт бывалых разработчиков. Дано: Веб-приложение. Серверная...

Разрешение коллизий
Скажите пожалуйста, какими методами решаются коллизии в БД, Про оптимистичный/пессимистичный...

2
9 / 9 / 4
Регистрация: 30.10.2011
Сообщений: 80
04.11.2012, 15: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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int k[7];
int h(int key);
int rh(int i);
void __fastcall insert( int key );
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
int h(int key)
{
        return key % 7;
}
int rh( int i)
{
        Form1->Label2->Caption=Form1->Label2->Caption + IntToStr(i+1);
        return (i+1) % 7;
}
void __fastcall insert( int key )
{
        int j,l,q,q1=1;
        j=h(key);
        while( (k[j]!=key) && (k[j]!=0))
        {
                j=rh(j);
                Form1->Label2->Caption=Form1->Label2->Caption + " mod 7 =" +IntToStr(j)+ "\n";
        }
                if (k[j]==0)
                {
                        k[j]=key;
                }
}
//------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Label1->Caption="";
Label2->Caption="";
       int i;
        randomize();
        int n;
 
                n=random(100);
 
        Form1->Label2->Caption=Form1->Label2->Caption + IntToStr(n)+ " mod 7 =" +IntToStr(h(n))+ "\n";
 
        //for(i=0;i<7;i++)
        {
                insert(n);
        }
 
        for(i=0;i<7;i++)
        {
 
                Label1->Caption=Label1->Caption + IntToStr(k[i]) + " ";
        }
}
//---------------------------------------------------------------------------
2
1 / 1 / 1
Регистрация: 02.04.2011
Сообщений: 99
07.01.2015, 01:51 3
n3250sasha, Если ты меня слышишь, пожалуйста помоги реализовать метод открытой адресации.
Кстати у меня правильно метод деления реализован? помоги плиз
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <iostream>
#include <clocale>
#include <string>
#include <windows.h>
 
using namespace std;
 
#define свободно true
#define занято false
 
const int n = 9;
bool fl[n];
 
int h(int key, int n)
{
    return (key % n);
}
 
int menu()
{
    system("cls");
 
    cout << "ВЫБЕРИТЕ ИНТЕРЕСУЮЩИЕ ВАС ДЕЙСТВИЕ:" << endl;
    cout << "1 - поиск определенного элемента" << endl;
    cout << "2 - просмотр хеш таблицы" << endl;
    cout << "3 - удаление элемента из таблицы" << endl;
    cout << "4 - выход из программы" << endl;
 
    int a = -1;
 
    while ((a > 4) || (a < 1))
    {
        cout << "введите число, из списка действий" << endl;
        if (!(cin >> a))
            cin.clear();
    }
 
    return a;
}
 
bool insert(int data, int* htable, bool* isEmpty, int n)
{
    int key = h(data, n);
 
    for (unsigned i = key; i < n; ++i)
        if (isEmpty[i])
        {
            htable[i] = data;
            isEmpty[i] = false;
            return true;
        }
 
    for (unsigned i = 0; i < key; ++i)
        if (isEmpty[i])
        {
            htable[i] = data;
            isEmpty[i] = false;
            return true;
        }
 
    return false;
}
 
int found(int data, int *a, int n)
{
    int key = h(data, n);
 
    if (fl[key] == занято)
    {
        if (a[key] == data)
            return key;
    }
 
    for (int i = key + 1; i < n; ++i)
    {
        if (fl[i] == занято)
        {
            if (a[key] == data)
                return i;
        }
    }
 
    for (int i = key - 1; i > -1; --i)
    {
        if (fl[i] == занято)
        {
            if (a[key] == data)
                return i;
        }
    }
 
    return -1;
}
 
int main()
{
    setlocale(LC_ALL, "");
 
    int a[n], data;
 
    int key, boolean;
    bool flag, work = true;
 
    for (int i = 0; i < n; ++i)
    {
        fl[i] = свободно;
        a[i] = 0;
    }
 
    cout << "Введите data's" << endl;
 
    while (cin >> data)
    {
        bool success = insert(data, a, fl, n);
 
        if (!success)
        {
            cout << "превышен лимит, введенно больше чем " << n << " элементов" << endl;
 
            system("pause");
 
            break;
        }
    }
 
    cin.clear();
 
    while (work)
        switch (menu())
    {
        case 1:
            system("cls");
 
            cout << "введите элемент который нужно найти" << endl;
            cin >> data;
 
            boolean = found(data, a, n);
 
            if (boolean == -1)
            {
                cout << "такого элемента нет!" << endl;
            }
 
            else
            {
                cout << "элемен " << data << " найден и его кэш - " << boolean << endl;
            }
 
            system("pause");
 
            break;
 
        case 2:
            system("cls");
 
            for (int i = 0; i < n; ++i)
            {
                if (fl[i] == занято)
                {
                    cout.width(3);
                    cout << right << i << ": ";
                    cout << a[i];
                    cout << endl;
                }
            }
 
            system("pause");
 
            break;
 
        case 3:
            system("cls");
 
            cout << "введите элемент который нужно удалить" << endl;
            cin >> data;
 
            boolean = found(data, a, n);
 
            if (boolean == -1)
            {
                cout << "такого элемента нет!" << endl;
            }
 
            else
            {
                fl[boolean] = свободно;
            }
 
            cout << "Элемент удален!" << endl;
 
            system("pause");
 
            break;
 
        case 4:
            work = false;
    }
 
    return 0;
}
0
07.01.2015, 01:51
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2015, 01:51
Помогаю со студенческими работами здесь

Разрешение коллизий в dictionary
Всем привет, у меня возник вопрос как разрешаются коллизии dictionary. Я прекрасно понимаю что...

Коллизия при открытом и закрытом хешировании
Кто может в двух словах объяснить данную тему?

При хешировании разных слов функция md5() выводит одно и то же значение
Сталкивался кто-нибудь с проблемой, что при хешировании разных слов, функция md5() выводит одно и...

Какие две хеш функции можно использовать для строк при двойном хешировании?
Какие две хеш функции можно использовать для строк при двойном хешировании?


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru