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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
#1

Хеш таблица с функцией (метод цепочек) - C++

11.10.2013, 11:49. Просмотров 1697. Ответов 6
Метки нет (Все метки)

1) Не смотрите на хеш функцию, она наитупейшая, я еще над ней не работал.
2)Метод цепочек заключается в том, если в ячейке массива есть уже элемент, то создается список и туда уже записывается новые данные. Типо ветка что ли.
3) Проблема: Именно когда создается список (строчка[37], зависает где то в строчке 38-39). Сама по себе программа зависает, но если смотреть дебагом то раз 15 она нормально проходит цикл создания элемента и записывает его в массив и когда доходит то Стурктуры,
то вылетает окошко "Необработанное исключение по адресу 0x013B674B в hash_function.exe: 0xC0000005: нарушение прав доступа при чтении по адресу 0xCDCDCDE5".
Бьюсь второй день. Настроения нет Подскажите пжлст.
p.s. при запуске выбирайте создать таблицу.
p.s.s. если получится убить баг, то и подскажете подходящуюю хэш функцию? ^^ :3
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
#include <iostream>
#include <string>
#include <time.h>
#define segment 1500
 
const int size = 5;
using namespace std;
 
struct Segment{ 
    string key="asdfgh"; //Ключ 
    int sum=0;  //Адрес
    bool empty = true;//Занят ли массив
    bool synonym = false; //Пометка синонима для списка
    Segment* new_segment;
    
};
 
class Hash_table{
public:
    Segment seg;
    int hash_func(int summ, string key);  //Хеш функция
    Segment segments[segment]; // Массив сегментов
    string create_key(string& key); // Создать ключ
    void show_list(); //Показать весь список 
    void find_key(string &key); //Поиск ключа
    //++++ удалить элемент
    void addNewElement(){                           //Добавление нового элемента
        string key_local = create_key(seg.key);
        int adress = hash_func(seg.sum, key_local);
        if (segments[adress].empty == true){
            segments[adress].sum = adress;
            segments[adress].key = key_local;
            segments[adress].empty = false;
        }
        else{
            Segment* newS = new Segment;; //Если ячейка полная, то создаем список           
            while (newS->new_segment != NULL) {
                newS = newS->new_segment;
                newS = new Segment; // Ошибка
                newS->new_segment->key = key_local;
                newS->new_segment->sum = adress;
                segments[adress].synonym = true;
                newS->new_segment = NULL;
            }
        }
    }
};
 
 
 
int main(){
    system("cls"); 
    srand(time(NULL));
    Hash_table hash;
    int your_choice;
    cout << " Hi! What would you do?" << endl;
    cout << "1)Create array" << endl;
    cout << "2)Show array" << endl;
    cout << "3)Find key" << endl;
    cout << "4)Delete key" << endl;
    cout << "->  ";
    cin >> your_choice;
 
    switch (your_choice){
    case 1:
        {
            for (int i = 0; i < segment; i++){
                hash.addNewElement();
            }
            system("cls");
            string y_n;
            cout << "list was created!!! " << endl;
            cout << "Do you want to choose function again y/n?";
            cin >> y_n;
            if (y_n == "y")main();
            break;
          }
    case 2:{
        string y_n;
        hash.show_list();
        cout << "Do you want to choose function again y/n?";
        cin >> y_n;
        if (y_n == "y")main();
        break;
           }
    case 3:{
        cout << "Enter your key type(AcccAA) -> ";
        string find_key="tempmp";
        cin >> find_key;
        hash.find_key(find_key);
        string y_n;
        cout << "Do you want to choose function again y/n?";
        cin >> y_n;
        if (y_n == "y")main();
        break;
           }
    }
    system("pause");
    return 0;
}
 
 
string Hash_table::create_key(string& key){ 
    key = "_temp_";
    for (int i = 0; i < 6; i++){         //Создаем ключ из 6 символов
        if (i == 0 || i == 4 || i == 5)
            key[i] = rand() % 26 + 65;
        else
            key[i] = rand() % 10 + 48;
    }
    return key;
}
 
int Hash_table::hash_func(int summ, string key){    //Наша хеш функция
    summ = (key[0] + key[1] + key[2] + key[3] + key[4] + key[5]);
    return summ;
}
 
void Hash_table::show_list(){
    Segment* newS;
    for (int i = 0; i < segment; i++){
        if (segments[i].synonym == true && segments[i].empty == false){  //Если ячейка заполнена и есть еще список 
            cout <<i+1<< ") key -> " << segments[i].key << "adress -> " << segments[i].sum;
            while (segments[i].new_segment != NULL){            
                newS = &segments[i];
                newS = newS->new_segment;
                cout<<i+1 << ") key - synonym -> " << newS->new_segment->key << "adress - synonym -> " << newS->new_segment->sum;
            }
        }
        else if (segments[i].synonym == false && segments[i].empty == false){ //Если ячейка заполнена и нет списка
            cout<<i+1 << ") key -> " << segments[i].key << "adress -> " << segments[i].sum;
        } 
        else{
            cout <<i+1<< ") Free Adress"<<endl;         
        }
    }
}
 
void Hash_table::find_key(string &key){
    bool founded = false; //Флаг для окончания поиска
    int find_goal; //Адрес вводимого ключа для поиска
    int temp_summ = 0; //Инициализация временнгой суммы
    int counter = 1;
    find_goal = hash_func(temp_summ,key);
    while (founded == false){  
        for (int i = 0; i < segment; i++){
            if (segments[i].empty == false && segments[i].synonym == false){
                if (find_goal == segments[i].sum){
                    cout<<"Succes:your number of key is -> " << find_goal;
                    founded == true;
                }
            }
            else if (segments[i].empty == false && segments[i].synonym == true){
                if (find_goal == segments[i].sum && key==segments[i].key){
                    cout << "Succes:your number of key is -> " << find_goal;
                    founded == true;
                }
                else {
                    Segment* newS;
                    newS = &segments[i];
                    newS = newS->new_segment;
                    if (find_goal == newS->sum){
                        cout << "Succes:your number of key is -> " << find_goal << "and it was in " << counter << " position in list"<<endl;
                        founded == true;
                    }
                    counter++;
                }
            }
        }
    }
}
Добавлено через 16 часов 54 минуты
Uppppp
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2013, 11:49     Хеш таблица с функцией (метод цепочек)
Посмотрите здесь:

C++ Хеш Таблица
хеш-таблица C++
C++ Хэш-таблица. Метод цепочек. C++
Хеш таблица C++
C++ хеш таблица
C++ Хэширование метод цепочек
Хэш - таблица методом цепочек C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
11.10.2013, 12:22     Хеш таблица с функцией (метод цепочек) #2
Ну вот создали Вы на 36 строке в куче объект типа Segment. И сразу проверяете его поле new_segment. А чему оно равно? А хрен его знает, оно ж нигде не инициализовано.
Дальше Вы присваиваете указателю newS значение этого new_segment, тут сразу же теряется указатель на первоначально выделенный Segment, утечка памяти.
Потом вдруг опять создаете в куче еще один Segment, и newS начинает указывать уже на него. Логика этого ускользает от моего понимания, но технически ошибки тут нет.
У нового Segment'а опять-таки не инициализирован new_segment, но теперь Вы не просто проверяете его, Вы пытаетесь что-то записать по этому неизвестному адресу. Привет, segmentation fault.

Подозреваю, Вы работаете с msvc. Под дебагом он выделенную память забивает значениями 0xCD, отсюда и адрес 0xCDCDCDE5.
Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
11.10.2013, 19:02  [ТС]     Хеш таблица с функцией (метод цепочек) #3
Цитата Сообщение от Fyret Посмотреть сообщение
Ну вот создали Вы на 36 строке в куче объект
Спасибо что ответили, сейчас буду фиксить и кстати, что вы подразумеваете под кучей? Очень неоформленный и говенный код?
если так то я самоучка и пока стараюсь писать задачи, хоть и безграмотно
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
11.10.2013, 19:26     Хеш таблица с функцией (метод цепочек) #4
Куча
Croessmah
Модератор
Эксперт CЭксперт С++
12675 / 7183 / 801
Регистрация: 27.09.2012
Сообщений: 17,712
Записей в блоге: 2
Завершенные тесты: 1
11.10.2013, 19:28     Хеш таблица с функцией (метод цепочек) #5
Цитата Сообщение от Warezovvv Посмотреть сообщение
Очень неоформленный и говенный код?
Ну это зависит от автора кода
любую кучу можно превратить в кучу
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
11.10.2013, 20:18     Хеш таблица с функцией (метод цепочек) #6
Цитата Сообщение от Warezovvv Посмотреть сообщение
Очень неоформленный и говенный код?
Редко видешь таких самоучек. На самом деле, код очень даже не плохой. Хотя бы английский правильный. Стиль кода не лучший, но для самоучки-новичка очень и очень даже ничего. Сам начинал с худшего =)

Из кода - в Си++ очень неудобная модель памяти. Код не очень очевиден - нет конструктора. Попробуйте создать для начала простой список по мотивам:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T> class List {
public:
    List ();
    void add ( T t, int i = 0 );
    void get ( int i );
private:
    class Node {
    public:
         T el;
         Node *next;
         Node *prev;
         Node ( T *e = NULL );
    }
}
Ну и отнаследуй List и Segment от чего-то общего. А там что-нибудь придумай, чтобы их отличать.

На самом деле, такие места нетривиальны в Си++. Очень и очень не просты. Поэтому и советую начать с чего-то попроще.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2013, 20:36     Хеш таблица с функцией (метод цепочек)
Еще ссылки по теме:

Хеш-таблица (метод цепочек) C++
C++ Хэш-таблица (метод цепочек)
Хеш-таблица C++
Хеш-таблица C++

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

Или воспользуйтесь поиском по форуму:
Warezovvv
9 / 9 / 2
Регистрация: 09.12.2012
Сообщений: 219
11.10.2013, 20:36  [ТС]     Хеш таблица с функцией (метод цепочек) #7
Цитата Сообщение от AnyOne697 Посмотреть сообщение
Редко видешь таких самоучек. На самом деле, код очень даже не плохой. Хотя бы английский правильный. Стиль кода не лучший, но для самоучки-новичка очень и очень даже ничего. Сам начинал с худшего =)

Из кода - в Си++ очень неудобная модель памяти. Код не очень очевиден - нет конструктора. Попробуйте создать для начала простой список по мотивам:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T> class List {
public:
    List ();
    void add ( T t, int i = 0 );
    void get ( int i );
private:
    class Node {
    public:
         T el;
         Node *next;
         Node *prev;
         Node ( T *e = NULL );
    }
}
Ну и отнаследуй List и Segment от чего-то общего. А там что-нибудь придумай, чтобы их отличать.

На самом деле, такие места нетривиальны в Си++. Очень и очень не просты. Поэтому и советую начать с чего-то попроще.
Спасибо, Щас Страуструпа открою на шаблонах, прочту, а то я в Лафоре прочитал и забыл

Fyret, и тебе спасибо ^^
Yandex
Объявления
11.10.2013, 20:36     Хеш таблица с функцией (метод цепочек)
Ответ Создать тему
Опции темы

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