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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
#1

Шаблоны. Хеш-функция - C++

26.05.2012, 21:54. Просмотров 2213. Ответов 18
Метки нет (Все метки)

Добрые день.
Есть задание сделать телефонную книгу. Поиск в базе сделать через хеш-функцию.

name - фамилия абонента.
num - номер телефона

Делал вот так () :
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
файл LIST.h
 
#pragma once
 
#include <iostream>
#include <string>
 
template<class T, class M>
class List
{
public:
    List();
    ~List();
 
    void push_back(T name, M num);
    void print();
    void push_front(T name, M num);
    void erase();
    //void erase(T val, M name);
    void clear();
    void find(T name, M num);
 
private:
    struct Node
    {
        Node():Name(0), Num(0), next(NULL)
        {
        }
 
        T Name;
        M Num;
        Node* next;
    };
 
    Node* head;
    Node* tail;
};
Реализация:

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
#include "List.h"
 
#include <iostream>
#include <string>
 
template<class T, class M>
List<T, M>::List():head(0), tail(0)
{
}
 
template<class T, class M>
List<T, M>::~List()
{
    delete head;
    delete tail;
}
 
template<class T, class M>
void List<T, M>::push_back(T name, M num)
{
    Node* Temp;
 
    Temp = new Node;
    Temp->Name = name;
    Temp->Num = num;
 
    if(head == 0)
    {
        head = Temp;
        tail = Temp;
        return;
    }
    tail->next = Temp;
    tail = Temp;
}
 
template<class T, class M>
void List<T, M>::print()
{
    if(head == 0)
    {
        throw std::string("List is empty!");
    }
 
    for(Node* ptr = head; ptr != 0; ptr = ptr->next)
    {
        std::cout << ptr->Name << ' ' << ptr->Num;
    }
    std::cout << '\n';
}
 
template<class T, class M>
void List<T, M>::push_front(T name, M num)
{
    Node* Temp;
    Temp = new Node;
    Temp->Name = name;
    Temp->Num = num;
    Temp->next = head;
    head = Temp;
}
 
template<class T, class M>
void List<T, M>::erase()
{
    if(head == 0)
    {
        throw std::string("List is empty!\n");
    }
    Node* delptr = head->next;
    head = head->next;
    delete delptr;
}
 
template<class T, class M>
void List<T, M>::clear()
{
    while(head != 0)
        erase();
}
 
template<class T, class M>
void List<T, M>::find(T name, M num)
{
    if(head == 0)
    {
        throw std::string("List is empty!\n");
    }
 
    for(Node* ptr = head; ptr != 0; ptr = ptr->next)
    {
        if(ptr->Name == name)
            std::cout<<"Element "<< name <<" is finded\n";
        return;
    }
    std::cout<<"Element "<< name <<" is not finded\n";
}
Сразу прошу обратить внимание, что класс списка далеко не идеален. Есть проблемы с освобождением памяти. Я это знаю, но в данный момент это не так важно.

Далее реализую Хеш-функцию.

Прототип.
C++
1
2
3
4
5
6
7
8
9
10
Файл Hash.h
 
#pragma once
 
#include "List.h"
 
#define SIZE_TABLE      2
 
unsigned int hs(char* str);
int menu();
Реализация.

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 <iostream>
 
#include "Hash.h"
#include "List.h"
 
using namespace std;
 
int main()
{
    int n = 0;
    char* str = NULL;
    str = new char[37];
 
    List<char*, int> symtab[SIZE_TABLE];
 
    unsigned int number = 0;
    unsigned int h = 0;
 
    while (1)
    {
        n = menu();
 
        switch(n)
        {
            // Добавить нового пользователя
        case 1:
            cout << "Vvedite FIO" << endl;
            cin >> str;
            cout << "Vvedite numer" << endl;
            cin >> number;
            h = hs(str);
            (symtab[h]).push_back(str, number);
            break;
            // Найти пользователя
        case 2:
            break;
            // Вывести весь список абонентов
        case 3:
            // Пробегаем по списку.
            for(int k = 0; k < SIZE_TABLE; k++)
            {
                symtab[k].print();
            }
            break;
            // Выход
        case 4:
            exit(1);
            break;
 
        default:
            break;
        }
    }
    
    return 0;
}
 
int menu()
{
    int t = 0;
    cout << "Vibirite punkt munu:" << endl;
    cout << "1 - Vvesti novogo abonenta" << endl;
    cout << "2 - Naiti nomer abonenta" << endl;
    cout << "3 - Vivesti spisok svech abonentov" << endl;
    cout << "4 - Vihod" << endl;
 
    cin >> t;
 
    return t;
}
 
// Хеш-функция
unsigned int hs(char* str)
{
    unsigned char* p = NULL;
 
    unsigned int h = 0;
 
    for(p = (unsigned char*)str; *p != '\0'; p++)
    {
        h = 37 * h + (*p);
    }
 
    return (h % SIZE_TABLE);
}
При компиляции выдает ошибки:


Ошибка 3 error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall List<char *,int>::List<char *,int>(void)" (??0?$List@PADH@@QAE@XZ) в функции _main

Ошибка 2 error LNK2019: ссылка на неразрешенный внешний символ "public: void __thiscall List<char *,int>:ush_back(char *,int)" (?push_back@?$List@PADH@@QAEXPADH@Z) в функции _main

Ошибка 1 error LNK2019: ссылка на неразрешенный внешний символ "public: void __thiscall List<char *,int>:rint(void)" (?print@?$List@PADH@@QAEXXZ) в функции _main

Ошибка 4 error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall List<char *,int>::~List<char *,int>(void)" (??1?$List@PADH@@QAE@XZ) в функции _main


Почему так происходит?

Ведь заголовочные файлы включены. Методы в разделе public. Обращение через экземпляр класса.
Все вроде должно работать.

И еще вопрос, подобная реализация хеширования информации имеет право на жизнь ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 21:54     Шаблоны. Хеш-функция
Посмотрите здесь:

Хеш функция - C++
Всем добрый день! В общем, нужно подсчитать кол-во коллизий. За это отвечает функция size_t collisions_count(), но почему-то не...

Хеш функция - C++
Здравствуйте. Помогите с задачей. Таблица строиться по методу цепочек с использованием хэш-функции, возращающий код первой буквы...

Хеш-функция, двойное хеширование - C++
Всем привет! Пишу курсач, нужна хеш-функция, которая принимала бы строку и возвращала некий индекс. Написал нечто вроде unsigned...

Объясните как работает хеш-функция - C++
int Hash_Function1(DrugStore object) { int result = 0; for (int i = 0; i &lt; SSize+1; i++) result = result +...

Нужна хеш-функция для программы на языке С++ - C++
К моей программе необходимо прикрутить функцию для вычисления хеша. Подскажите, пожалуйста, работоспособный исходник хеш-функции для...

Метод открытого хеширования и хеш-функция, основанная на методе деления с остатком - C++
Ещё раз здравствуйте! Есть такое задание: Написать программу, которая реализует метод открытого хеширования и хеш-функцией,...

Функция с переменным числом аргументов (через шаблоны) - C++
Доброго времени суток! Встал вопрос с реализацией такой функции. template&lt;typename... Args&gt; returntype functionname(const Args&amp;......

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
27.05.2012, 00:19     Шаблоны. Хеш-функция #2
Реализацию List засунь в List.h в конец. Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 02:55     Шаблоны. Хеш-функция #3
Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
А какие собственно справляются?
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 05:51     Шаблоны. Хеш-функция #4
Цитата Сообщение от Avazart Посмотреть сообщение
А какие собственно справляются?
comeau и, как ни странно, билдер.
Хотя из нового стандарта экспорт шаблонов вроде как убрали.
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 10:03  [ТС]     Шаблоны. Хеш-функция #5
Благодарю, все работает.
Как-то этот момент упускают в учебниках.
А как быть тогда с сокрытием реализации кода, если допустим код распространяется в библиотеке?
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 10:06     Шаблоны. Хеш-функция #6
Цитата Сообщение от Geniok Посмотреть сообщение
А как быть тогда с сокрытием реализации кода, если допустим код распространяется в библиотеке?
Обфускация. По другому никак.
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 10:23  [ТС]     Шаблоны. Хеш-функция #7
Будьте добры, подскажите еще такой момент.
В функцию добавления элемента в список я передаю указатель.
Поэтому получается такая ситуация, что при добавлении в список во всех элементах списка строка Name указывает на одну и ту же область памяти. То есть по сути имена не сохраняются, сохраняется только последнее введенное имя.
Как можно переписать функцию, чтобы под каждое имя выделялась своя область памяти, но при этом функция оставалась шаблонной ?
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 13:49     Шаблоны. Хеш-функция #8
comeau и, как ни странно, билдер.
Хотя из нового стандарта экспорт шаблонов вроде как убрали.
Вообщето Builder не справляется насколько я знаю...
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 14:31     Шаблоны. Хеш-функция #9
Цитата Сообщение от Avazart Посмотреть сообщение
Вообщето Builder не справляется насколько я знаю...
Судя по википедии, билдер поддерживает экспорт шаблонов с 2004 года.
Возможно, вы просто неправильно пользуетесь словом export(либо вообще им не пользуетесь).
P.S. еще один компилятор вспомнил - Intel c++.
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 15:14     Шаблоны. Хеш-функция #10
вы просто неправильно пользуетесь словом export(либо вообще им не пользуетесь).
Возможно...пробовал давно еще кажеться на 6-й версии.
Как я понимаю export надо писать в h-файле перед объявлением шаблона ?

Добавлено через 20 минут
Заголовок:
C++
1
2
3
4
5
6
7
8
#ifndef Unit4H
#define Unit4H
//---------------------------------------------------------------------------
export
template<class T>
void swap(T& a,T& b);
//---------------------------------------------------------------------------
#endif
Реализация
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//---------------------------------------------------------------------------
#pragma hdrstop
#include "Unit4.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
//---------------------------------------------------------------------------
template<class T>
void swap(T& a,T& b)
{
T temp= a;
a =  b;
b =  temp;
}
//---------------------------------------------------------------------------
Приминение
C++
1
2
3
4
5
6
7
8
9
#include "Unit4.h"
//---------------------------------------------------------------------------
void __fastcall TForm3::FormCreate(TObject *Sender)
{
int a=3,b=5;
swap(a,b);
Caption= a;
}
//---------------------------------------------------------------------------
[ILINK32 Error] Error: Unresolved external 'void swap<int>(int&, int&)' referenced from C:\USERS\FUJITSU\DOCUMENTS\RAD STUDIO\PROJECTS\DEBUG_BUILD\UNIT3.OBJ
Шаблоны классов и функций
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 16:27  [ТС]     Шаблоны. Хеш-функция #11
Сделал без шаблонов, так как смысла в данном конкретном случае в них нет.
Подскажите пожалуйста насчет освобождения памяти. В каком месте у меня возможна утечка и как лучше всего сделать.

C++ (Qt)
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
class List
{
public:
    List();
    ~List();
 
    void push(char* name, int num);
    void print();
    void erase();
    //void erase(T val, M name);
    void clear();
    void find(char* name, int num);
 
private:
    struct Node
    {
        Node():Num(0), next(0)
        {
            Name = new char;
        }
 
        char* Name;
        int Num;
        Node* next;
    };
 
    Node* head;
    Node* tail;
 
    char* strCopy(char* in, char* to);
};
Реализация:

C++ (Qt)
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
List::List():head(0), tail(0)
{
}
 
List::~List()
{
    delete head;
    delete tail;
}
 
void List::push(char* name, int num)
{
    Node* Temp = new Node;
 
    Temp->Name = strCopy(Temp->Name, name);
    
    Temp->Num = num;
 
    if(head == 0)
    {
        head = Temp;
        tail = Temp;
        return;
    }
    tail->next = Temp;
    tail = Temp;
}
 
 
void List::print()
{
    if(head == 0)
    {
        throw std::string("List is empty!");
    }
 
    for(Node* ptr = head; ptr != 0; ptr = ptr->next)
    {
            std::cout << ptr->Name << ' ' << ptr->Num;
    }
    std::cout << '\n';
}
 
void List::erase()
{
    if(head == 0)
    {
        return;
    }
    Node* delptr = head->next;
    head = head->next;
    delete delptr;
}
 
void List::clear()
{
    while(head != 0)
        erase();
}
 
 
void List::find(char* name, int num)
{
    if(head == 0)
    {
        return;
    }
 
    for(Node* ptr = head; ptr != 0; ptr = ptr->next)
    {
        if(ptr->Name == name)
            std::cout<<"Element "<< name <<" is finded\n";
        return;
    }
    std::cout<<"Element "<< name <<" is not finded\n";
}
 
char* List::strCopy(char* in, char* to)
{
    char* tmp = in;
 
    while(*in++ = *to++)
        ;
    return tmp;
}
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 16:40     Шаблоны. Хеш-функция #12
C++
1
2
3
4
5
List::~List()
{
    delete head;
    delete tail;
}
Тут ты ведь удаляешь только крайнии узлы, а внутрении?

Добавлено через 3 минуты
Как вариант в структуре Node сделай деструктор в котором он не только будет удалять себя, но и элемент next.(!=NULL)
в итоге delete head вызовет цепную реакцию.
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 18:33  [ТС]     Шаблоны. Хеш-функция #13
Цитата Сообщение от Avazart Посмотреть сообщение
C++
1
2
3
4
5
List::~List()
{
    delete head;
    delete tail;
}
Тут ты ведь удаляешь только крайнии узлы, а внутрении?

Добавлено через 3 минуты
Как вариант в структуре Node сделай деструктор в котором он не только будет удалять себя, но и элемент next.(!=NULL)
в итоге delete head вызовет цепную реакцию.

Спасибо за ответ!
Потому и спросил, что удаляю только крайние узлы, значит то, что в середине остается занято.

Если вас правильно понял. должно быть что-то типа этого:

C++ (Qt)
1
2
3
4
5
~Node()
    {
            while(next != 0)
                delete next;
    }
?
Если да, то не подходит. компилятор пишет: Ошибка 1 error C2523: List::~Node: несовпадение тегов деструктор
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 18:38     Шаблоны. Хеш-функция #14
C++
1
2
3
4
5
~Node()
    {
     if(next)  delete next;
     delete Name;  // Name это что один символ??? По вашему коду именно так
    }
Но я не увере потому как у вас я еще заметил erase поэтому это не подойдет, но в любом случае нужен деструктор Node
C++
1
2
3
4
~Node()
 {
     delete Name;  // Name это что один символ??? По вашему коду именно так
  }
Что бы освободить память от создаваемого динамически char объекта
gray_fox
What a waste!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 3
27.05.2012, 18:41     Шаблоны. Хеш-функция #15
Цитата Сообщение от Geniok Посмотреть сообщение
должно быть что-то типа этого
не, стоит написать деструктор листа, чтобы он проходил по всем нодам и очищал память. примерно так:
C++
1
2
3
4
5
6
7
~List() {
   while (head != 0) {
      Node * tmp = head;
      head = head->next;
      delete tmp;
   }
}
Добавлено через 2 минуты
а в деструкторе нода удалять только то, что выделяли в конструкторе:
C++
1
2
3
~Node() {
   delete[] Name;   // если Name не массив, то delete Name;
}
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 18:46     Шаблоны. Хеш-функция #16
C++
1
2
3
4
List::~List()
{
   clear() // думаю так но вы там проверьте по своему коду
}
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 20:15  [ТС]     Шаблоны. Хеш-функция #17
Цитата Сообщение от Avazart Посмотреть сообщение
C++
1
2
3
4
5
~Node()
    {
     if(next)  delete next;
     delete Name;  // Name это что один символ??? По вашему коду именно так
    }
Но я не увере потому как у вас я еще заметил erase поэтому это не подойдет, но в любом случае нужен деструктор Node
C++
1
2
3
4
~Node()
 {
     delete Name;  // Name это что один символ??? По вашему коду именно так
  }
Что бы освободить память от создаваемого динамически char объекта
Name - это массив символов. В Name должна содержаться фамилия. По идее.
Именно поэтому объявление
C++ (Qt)
1
char* Name
а не

C++ (Qt)
1
char Name
Добавлено через 47 секунд
Цитата Сообщение от gray_fox Посмотреть сообщение
не, стоит написать деструктор листа, чтобы он проходил по всем нодам и очищал память. примерно так:
C++
1
2
3
4
5
6
7
~List() {
   while (head != 0) {
      Node * tmp = head;
      head = head->next;
      delete tmp;
   }
}
Добавлено через 2 минуты
а в деструкторе нода удалять только то, что выделяли в конструкторе:
C++
1
2
3
~Node() {
   delete[] Name;   // если Name не массив, то delete Name;
}
Вот теперь понятно. Большое спасибо за помощь!
Avazart
7101 / 5278 / 267
Регистрация: 10.12.2010
Сообщений: 23,284
Записей в блоге: 17
27.05.2012, 20:23     Шаблоны. Хеш-функция #18
Почему тогда
C++
1
2
3
4
Node():Num(0), next(0)
{
Name = new char;//  А не Name = new char[size]  - читайте про работу со строками и выделение памяти динамически
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2012, 21:02     Шаблоны. Хеш-функция
Еще ссылки по теме:

Каким образом unordered_map выдает правильное значение для ключа, если его хеш функция допускает коллизии? - C++
Читаю книгу джосаттис стандартная библиотека c++, там в разделе про unordered_map есть описание данного контейнера Раз уж каждый...

хеш таблица - C++
в чем ошибка #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iterator&gt; #include &lt;algorithm&gt; #include &lt;string&gt; struct...

хеш функции - C++
здраствуйте! собственно проблема в хеш функциях. не могу разобратся в принципе (гугль и книги читал). сам принцип хеширования понятен, а...

Хеш строки - C++
Как можно получить хеш строки на C++ с использованием только стандартных библиотек? Думал так: unsigned long long hash(char *str,size_t...

Хеш-таблица - C++
В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер...


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

Или воспользуйтесь поиском по форуму:
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 21:02  [ТС]     Шаблоны. Хеш-функция #19
Цитата Сообщение от Avazart Посмотреть сообщение
Почему тогда
C++
1
2
3
4
Node():Num(0), next(0)
{
Name = new char;//  А не Name = new char[size]  - читайте про работу со строками и выделение памяти динамически
}
Вы опять же правы. сначала был массив. а потом когда я сюда код переносил, я массив удалил, но удивительно что в Visual Studio компилируется и прекрасно работает.

Еще раз большое спасибо за замечание, сейчас исправлю.
Yandex
Объявления
27.05.2012, 21:02     Шаблоны. Хеш-функция
Ответ Создать тему
Опции темы

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