Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Хеш функция - 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++
Ещё раз здравствуйте! Есть такое задание: Написать программу, которая реализует метод открытого хеширования и хеш-функцией,...

18
Gepar
1181 / 537 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
27.05.2012, 00:19 #2
Реализацию List засунь в List.h в конец. Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
0
Avazart
Эксперт С++
7574 / 5559 / 327
Регистрация: 10.12.2010
Сообщений: 24,935
Записей в блоге: 17
27.05.2012, 02:55 #3
Некоторые компиляторы не справляются с компиляцией и линковкой кода шаблона, когда он в нескольких файлах.
А какие собственно справляются?
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 05:51 #4
Цитата Сообщение от Avazart Посмотреть сообщение
А какие собственно справляются?
comeau и, как ни странно, билдер.
Хотя из нового стандарта экспорт шаблонов вроде как убрали.
0
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 10:03  [ТС] #5
Благодарю, все работает.
Как-то этот момент упускают в учебниках.
А как быть тогда с сокрытием реализации кода, если допустим код распространяется в библиотеке?
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 10:06 #6
Цитата Сообщение от Geniok Посмотреть сообщение
А как быть тогда с сокрытием реализации кода, если допустим код распространяется в библиотеке?
Обфускация. По другому никак.
0
Geniok
1 / 1 / 0
Регистрация: 20.09.2009
Сообщений: 29
27.05.2012, 10:23  [ТС] #7
Будьте добры, подскажите еще такой момент.
В функцию добавления элемента в список я передаю указатель.
Поэтому получается такая ситуация, что при добавлении в список во всех элементах списка строка Name указывает на одну и ту же область памяти. То есть по сути имена не сохраняются, сохраняется только последнее введенное имя.
Как можно переписать функцию, чтобы под каждое имя выделялась своя область памяти, но при этом функция оставалась шаблонной ?
0
Avazart
Эксперт С++
7574 / 5559 / 327
Регистрация: 10.12.2010
Сообщений: 24,935
Записей в блоге: 17
27.05.2012, 13:49 #8
comeau и, как ни странно, билдер.
Хотя из нового стандарта экспорт шаблонов вроде как убрали.
Вообщето Builder не справляется насколько я знаю...
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.05.2012, 14:31 #9
Цитата Сообщение от Avazart Посмотреть сообщение
Вообщето Builder не справляется насколько я знаю...
Судя по википедии, билдер поддерживает экспорт шаблонов с 2004 года.
Возможно, вы просто неправильно пользуетесь словом export(либо вообще им не пользуетесь).
P.S. еще один компилятор вспомнил - Intel c++.
0
Avazart
Эксперт С++
7574 / 5559 / 327
Регистрация: 10.12.2010
Сообщений: 24,935
Записей в блоге: 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
Шаблоны классов и функций
0
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;
}
0
Avazart
Эксперт С++
7574 / 5559 / 327
Регистрация: 10.12.2010
Сообщений: 24,935
Записей в блоге: 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 вызовет цепную реакцию.
0
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: несовпадение тегов деструктор
0
Avazart
Эксперт С++
7574 / 5559 / 327
Регистрация: 10.12.2010
Сообщений: 24,935
Записей в блоге: 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 объекта
0
gray_fox
What a waste!
1551 / 1256 / 74
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2012, 18:41
Привет! Вот еще темы с ответами:

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

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

«Шаблоны шаблонов» vs «шаблоны с параметрами-шаблонами». - C++
«Шаблоны шаблонов» vs «шаблоны с параметрами-шаблонами». Есть ли разница в этих понятиях? Если есть, то в чём? И где (в каких...

Шаблоны. Плохо понимаемые моменты из книги "Шаблоны С++. Справочник разработчика". (Вандевурд, Джосаттис) - C++
Так как изучаю эту книгу, то в некоторых местах возникают вопросы. Чтобы не плодить много тем, корни у которых одни, решил создать эту...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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