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

Хэш-таблица - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 62, средняя оценка - 4.68
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
22.12.2010, 22:14     Хэш-таблица #1
Задание реализовать динамическую хеш-таблицу с открытой адресацией для хранения строк (операции вставки и поиска). Таблица должна увеличивать свой размер в двое при достижении 50% заполнения.

Операции вставки и поиска я уже сделала и они работают, а вот с увлечением проблемы не знаю как сделать, понимаю что если первоначально таблица была размера m то должна стать 2m, т е мы долны ввести новый массив и.... дальше мозги глохнут

Вот вставка и поиск в хэш-таблице с открытой адресацией
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
#include "stdafx.h"
#include "string.h"
#include "iostream"
#include "conio.h"
#include "locale.h"
 
using namespace std;
 
const int m=5;
const int a=127;
int c1=5, c2=3;
char*  H[m]={0};
char k[];
 
int h1(char s[],int n)
{
    if (n>0) return ((a*h1(s, n-1))+s[n-1])%m;
        else return 0;  
};
 
int h(char k[], int i, int n)
{
    if(i<(m-1)) return ((h1(k, n)+c1*i+c2*i*i)%m);
    else return 0;
};
 
int Hash_Insert(char* H[m], char k[]) //вставка элемента
{
    int i=0; //номер иследования
    do
    { int n = strlen(k);
        int j=h( k, i, n);
        {
            if(H[j]==NULL) 
                {
                     H[j]=k;
                     cout << j << endl;
                    return j;
                }
                else i++;
        }
    }
    while(i!=m);
        return NULL;
};
 
int Hash_Search(char* H[m], char k[])// поиск элемента
{
    int i=0;
    int j=0;
 
    do
    {
    int n = strlen(k);
 
         j=h(k, i, n);
        if(H[j]!=0 && strcmp(H[j],k)==0){
            cout<<" "<< endl;
        cout << j << endl;
        return j;}
        else i++;   
    }
    while(H[j]!=NULL && i!=m);
        return -1;
};
 
 
 
int _tmain()
{   
    char a[m]="asy";
    int r=h1(a, 3);
    printf("%d\n",r);  // вывод h1
    int e=h("asy", 0, 3);
    printf("%d\n", e);
    
    Hash_Insert(H, "asy");
    Hash_Insert(H, "asyi");
    Hash_Insert(H, "asyo");
 
    Hash_Search(H, "asyo");
 
    _getch();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2010, 22:14     Хэш-таблица
Посмотрите здесь:

C++ Хэш таблица
Хэш-таблица, ошибка C++
C++ Хэш-таблица
Телефонная книжка и хэш-таблица C++
Хэш-таблица C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
24.12.2010, 14:13  [ТС]     Хэш-таблица #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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include "stdafx.h"
#include "string.h"
#include "iostream"
#include "conio.h"
#include "locale.h"
 
using namespace std;
 
const int m=6;
const int a=127;
int c1=5, c2=3, g=0;
char*  H[m]={0};
char k[];
 
 
int h1(char s[],int n)
{
    if (n>0) return ((a*h1(s, n-1))+s[n-1])%m;
        else return 0;  
};
 
int h(char k[], int i, int n)
{
    if(i<(m-1)) return ((h1(k, n)+c1*i+c2*i*i)%m);
    else return 0;
};
 
int Hash_Insert(char* H[m], char k[]) //вставка элемента
{
    int i=0; //номер иследования
    do
    { int n = strlen(k);
        int j=h( k, i, n);
        {
            if(H[j]==NULL) 
                {
                     H[j]=k;
                     cout << j << endl;
                    
                        g++;
                     cout << "количество элементов в таблице" << endl;
                     cout << g << endl;
                     if(g==m/2 && H[j]!=0)
                     {
                                            char** u = new char* [2*m];
                                            cout << "увелечение хэш таблицы в двое:" << endl;
                                            for(i=0; i<m; i++)
                                            {
                                                if(H[i]!=NULL)
                                                    Hash_Insert(u, H[i]);
                                                    cout << i << endl;
                                            }   
                     }
                return j;
                }
                else i++;
        }
    }
    while(i!=m);
        return NULL;
};
 
 
int Hash_Search(char* H[m], char k[])// поиск элемента
{
    int i=0;
    int j=0;
    do
    {
    int n = strlen(k);
         j=h(k, i, n);
        if(H[j]!=0 && strcmp(H[j],k)==0){
            cout<<" "<< endl;
        cout << j << endl;
        return j;}
        else i++;   
    }
    while(H[j]!=NULL && i!=m);
        return -1;
};
 
 
int _tmain()
{   setlocale (LC_ALL, "Russian");
    char a[m]="asy";
    int r=h1(a, 3);
    cout << "Вывод h1:" << endl;
    printf("%d\n",r);  // вывод h1
    int e=h("asy", 0, 3);
    cout << "Вывод h:" << endl;
    printf("%d\n", e);
 
cout << "Вывод вставки asy:" << endl;
    Hash_Insert(H, "asy");
cout << "Вывод вставки asyi:" << endl;
    Hash_Insert(H, "asyi");
cout << "Вывод вставки asyo:" << endl;
    Hash_Insert(H, "asyo");
cout << "Вывод вставки asyp:" << endl;
    Hash_Insert(H, "asyp");
 
cout << "\nВывод поиска asyo:" << endl;
    Hash_Search(H, "asyo");
 
 
 
    _getch();
    return 0;
}
Вот, добавила условие на увеличение хэш-таблицы
C++
1
2
3
4
5
6
7
8
9
10
11
 if(g==m/2 && H[j]!=0)
{
      char** u = new char* [2*m];
cout << "увелечение хэш таблицы в двое:" << endl;
            for(i=0; i<m; i++)
                {
                if(H[i]!=NULL)
                Hash_Insert(u, H[i]);
                cout << i << endl;
                }   
                     }
но тут проблемы с тем что мне надо вывести увеличиный массив который содержит эл-ты первоначального массива, а после сделать так что бы массуив увеличенный стал основным - короче я запуталась, помогите кто может, пж

Добавлено через 15 часов 56 минут
неужели никто с массивом помочь 6не может???
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
24.12.2010, 14:34     Хэш-таблица #3
Цитата Сообщение от White Luna Посмотреть сообщение
неужели никто с массивом помочь 6не может???
А здесь Вам кто-то чем то обязан? В следующий раз подобные высказывани будут караться как оффтоп. Говорите по делу.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
26.12.2010, 18:49  [ТС]     Хэш-таблица #4
Теперь у меня почему то возникает отрицательная длина строки,.. я в ступоре, с чем это может быть связано/???

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
#include "stdafx.h"
#include "string.h"
#include "iostream"
#include "conio.h"
#include "locale.h"
 
using namespace std;
 
int m=6;
const int a=127;
int c1=5, c2=3, g=0;
char** H;
char k[];
 
int h1(char s[],int n)
{
    if (n>0) return ((a*h1(s, n-1))+s[n-1])%m;
        else return 0;  
};
 
int h(char k[], int i, int n)
{
    if(i<(m-1)) return ((h1(k, n)+c1*i+c2*i*i)%m);
    else return 0;
};
 
int Hash_Insert(char** H, char k[]) //вставка элемента
{
    
    int i=0; //номер иследования
 
    do
    { int n = strlen(k);
 
        int j=h(k, i, n);
        {
 
            if(H[j]!=NULL) 
                {
 
                     H[j]=k;
                     cout << j << endl;
                        g++;
                     cout << "                    количество элементов в таблице" << endl;
                     printf("           %d\n", g);
                     if(g==m/2 && H[j]!=0)
                     {
                           char** u = new char* [2*m];
                            cout << "увелечение хэш таблицы в двое:\n" << endl;
g=0;
                            for(int y=0; y<m; y++)
                            {
                                
                                if(H[y]!=NULL)
                                {
                                    Hash_Insert(u, H[y]); 
                                    cout << k << endl;
                    
                                    g++;
                                    printf("            %d\n", g);
                                }
                                m *=2;  
                            }
                            delete [] u ;
                     }
                return j;
                }
            else i++;
        }
    }
    while(i!=m);
        return NULL;
};
 
int Hash_Search(char** H, char k[])// поиск элемента
{
    int i=0;
    int j=0;
    do
    {
    int n = strlen(k);
         j=h(k, i, n);
        if(H[j]!=0 && strcmp(H[j],k) == 0)
        {
            cout<<" "<< endl;
            cout << j << endl;
            return j;
        }
        else i++;   
    }
    while(H[j]!=NULL && i!=m);
        return -1;
};
 
int _tmain()
{   
    setlocale (LC_ALL, "Russian");
    char** H = new char* [m];
    int n;
for ( int i=0; i<m; i++)
{
    H[i]=new char [m];
}
    char a[]="asy";
    int r=h1(a, 3);
    cout << "Вывод h1:" << endl;
    printf("%d\n",r);  // вывод h1
    int e=h("asy", 0, 3);
    cout << "Вывод h:" << endl;
    printf("%d\n", e);
 
cout << "Вывод вставки asy:" << endl;
    Hash_Insert(H, "asy");
cout << "Вывод вставки asyp:" << endl;
    Hash_Insert(H, "asyp");
cout << "Вывод вставки asyt:" << endl;
    Hash_Insert(H, "asyt");
cout << "Вывод вставки asyp:" << endl;
    Hash_Insert(H, "asyp");
 
cout << "\nВывод поиска asyt:" << endl;
    Hash_Search(H, "asyt");
 
    _getch();
    return 0;
}
Yandex
Объявления
26.12.2010, 18:49     Хэш-таблица
Ответ Создать тему
Опции темы

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