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

@n3250sasha · Регистрация: 30.10.2011

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]) + " ";
        }
 
}
//---------------------------------------------------------------------------

@n3250sasha · 04.11.2012, 15:55 **[ТС]**

Сделал, может кому-то понадобится

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]) + " ";
        }
}
//---------------------------------------------------------------------------

@_Edith · 07.01.2015, 01:51

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;
}

Новые блоги и статьи Все статьи Все блоги /
Безопасное программирование в Java и предотвращение уязвимостей (SQL-инъекции, XSS и др.) Javaican 19.05.2025 Самые распространёные векторы атак на Java-приложения за последний год выглядят как классический "топ-3 хакерских фаворитов": SQL-инъекции (31%), межсайтовый скриптинг или XSS (28%) и CSRF-атаки. . .	Введение в Q# - язык квантовых вычислений от Microsoft EggHead 19.05.2025 Microsoft вошла в гонку технологических гигантов с собственным языком программирования Q#, специально созданным для разработки квантовых алгоритмов. Но прежде чем погружаться в синтаксические дебри. . .	Безопасность Kubernetes с Falco и обнаружение вторжений Mr. Docker 18.05.2025 Переход организаций к микросервисной архитектуре и контейнерным технологиям сопровождается лавинообразным ростом векторов атак — от тривиальных попыток взлома до многоступенчатых кибератак, способных. . .	Аугментация изображений с Python AI_Generated 18.05.2025 Собрать достаточно большой датасет для обучения нейронной сети — та ещё головная боль. Часами вручную размечать картинки, скармливать их ненасытным алгоритмам и молиться, чтобы модель не сдулась при. . .	Исключения в Java: советы, примеры кода и многое другое Javaican 18.05.2025 Исключения — это объекты, созданные когда программа сталкивается с непредвиденной ситуацией: файл не найден, сетевое соединение разорвано, деление на ноль. . . Список можно продолжать до бесконечности. . . .
Как сделать SSO (Single Sign-On) в C# приложении stackOverflow 18.05.2025 SSO — это механизм, позволяющий пользователю пройти аутентификацию один раз и получить доступ к нескольким приложениям без повторного ввода учетных данных. Вы наверняка сталкивались с ним, когда. . .	Kubernetes с Apache Flink для обработки данных в реальном времени Mr. Docker 17.05.2025 Kubernetes — это целая философия управления распределёнными приложениями. В отличие от "примитивных" решений вроде Docker Swarm, K8s (как его ласково называют в тусовке DevOps-инженеров) предлагает. . .	Использование декораторов в Python py-thonny 17.05.2025 Если вы когда-нибудь задумывались о том, как красиво расширить функциональность кода без лишней возни и дублирования, декораторы в Python — та самая волшебная палочка, которую вы искали. По сути, это. . .	Реализация многопоточных сетевых серверов на Python py-thonny 16.05.2025 Когда сталкиваешься с необходимостью писать высоконагруженные сетевые сервисы, выбор технологии имеет критическое значение. Python, со своей элегантностью и высоким уровнем абстракции, может. . .	C# и IoT: разработка Edge приложений с .NET и Azure IoT UnmanagedCoder 16.05.2025 Мир меняется прямо на наших глазах, и интернет вещей (IoT) — один из главных катализаторов этих перемен. Если всего десять лет назад концепция "умных" устройств вызывала скептические улыбки, то. . .

Опции темы