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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
26.05.2012, 21:54     Шаблоны. Хеш-функция #1
Добрые день.
Есть задание сделать телефонную книгу. Поиск в базе сделать через хеш-функцию.

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. Обращение через экземпляр класса.
Все вроде должно работать.

И еще вопрос, подобная реализация хеширования информации имеет право на жизнь ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
27.05.2012, 00:19     Шаблоны. Хеш-функция #2
Реализацию List засунь в List.h в конец. Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
27.05.2012, 02:55     Шаблоны. Хеш-функция #3
Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
А какие собственно справляются?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
 Аватар для diagon
1920 / 1186 / 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
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
27.05.2012, 13:49     Шаблоны. Хеш-функция #8
comeau и, как ни странно, билдер.
Хотя из нового стандарта экспорт шаблонов вроде как убрали.
Вообщето Builder не справляется насколько я знаю...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 14:31     Шаблоны. Хеш-функция #9
Цитата Сообщение от Avazart Посмотреть сообщение
Вообщето Builder не справляется насколько я знаю...
Судя по википедии, билдер поддерживает экспорт шаблонов с 2004 года.
Возможно, вы просто неправильно пользуетесь словом export(либо вообще им не пользуетесь).
P.S. еще один компилятор вспомнил - Intel c++.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 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
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 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
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 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!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 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
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 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
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 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     Шаблоны. Хеш-функция
Еще ссылки по теме:

C++ Объясните как работает хеш-функция
Хеш функция C++
Хеш-таблица C++

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

Или воспользуйтесь поиском по форуму:
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     Шаблоны. Хеш-функция
Ответ Создать тему
Опции темы

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