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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
FYlhtq_163_93
5 / 5 / 1
Регистрация: 27.12.2010
Сообщений: 29
#1

Телефонная книжка и хэш-таблица - C++

22.03.2012, 21:37. Просмотров 1427. Ответов 7
Метки нет (Все метки)

Ребят, помогите кто может! Мне нужно реализовать телефонную книжку в виде хэш-таблицы. ХТ реализую через классы(сначала класс односвязного списка, а таблица представлена как массив списков). Как реализовать добавление элемента в хэш-таблицу? Прикрепляю два кода: класс список:
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
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
 
struct Node
{
    char* phone[10];
    char* name;
    Node *next;
};
typedef Node* Pnode;
 
class List
{
private:
    Pnode Head;
    Pnode Tail;
 
    Pnode Search(char* newphone, char* newname){
        Pnode p=Head;
        while(p!=NULL && newphone!=p->phone && newname!=p->name)    p=p->next;
        return p;
    }
 
    /*
    Pnode Copy_list(Pnode PrevNode, Pnode OrigNode){
        if(OrigNode!=NULL){
            Pnode q = new Node;
            q->phone=OrigNode->phone;
            q->prev=PrevNode;
            q->next=Copy_list(q,OrigNode->next);
            return q;
        }
        return NULL;
    }
    */
 
public:
    int Find(char* newphone, char* newname, char* &count){
        count=1;
        Pnode p=Head;
        while(p!=NULL && newphone!=p->phone && newname!=p->name){   p=p->next; count++;}
        if(p!=NULL) return 1;
        else return 0;
    }
 
    int Add(char* newphone, char* newname){
        Pnode q= Search(newphone, newname) ;
 
        if(q!=NULL && q->phone==newphone  && newname!=p->name) return 0;
 
    //--Create------------------------------------
        Pnode Newnode= new Node;
        Newnode->next=NULL;
        Newnode->phone=newphone;
        Newnode->name=newname;
    //--return newnode----------------------------
    //--add last----------------------------------
            {
            Tail->next=Newnode;
            Tail=Newnode;
            }
        }
       return 1;
    }
 
    void Print(){
        Pnode p=Head;
        int count=1;
 
        while(p!=NULL)
        {
            cout<<"name "<<p->name<<" phone"<<p->phone;
            p=p->next;
        }
    }
 
    int Delete(char* newphone, char* newname){
        Pnode q= Search(newphone, newname);
 
        if(q==NULL) return 0;
    
        if(q->next==Tail){
    //--delete last------------------------
            Tail->prev->next=NULL;
            Tail=Tail->prev;
        }
        delete q;
        return 1;
    }
    
    List(){
        Head=NULL;
        Tail=NULL;
    }
 
    List(List& orig){
        if(this!=&orig)
            if(orig.Head!=NULL){
                Head =new Node;
                Head->phone=orig.Head->phone;
                Head->name=orig.Head->name;
                Head->next=NULL;
 
                Tail=Head;
 
                bool first=true;
                for(Pnode Q=NULL, OrigNode=orig.Head->next ; 
                    OrigNode != NULL ;
                    Tail= Q, OrigNode = OrigNode->next){
                    
                        Q = new Node;
                        Q->phone=OrigNode->phone;
                        Q->name=OrigNode->name;
                    }
 
                if(Tail!=Head) Tail->next=NULL;
            }
            else List();
    }
 
 
    ~List(){
        if(Head!=NULL){
            Pnode p=Head, q=Head->next;
            while(p!=NULL){
                delete p;
                p=q;
                if(q!=NULL) q=q->next;
            }
        }
    }
};
реализация хэша(в list.hpp лежит список):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "list.hpp"
const int hashsize=100;
class hash
{
      List hash[hashsize];
private:
        int hashfunc(char* num){
            int numlast;
            char* numch1;
            numch=&(num[8]);
            return atoi(numch);
        }
public:
      int ins_hash(newphone,newname){
          int hashkey=hashfunc(newphone);
          /*вот тут у меня возникает вопрос*/
          Add(newphone,newname); 
      }
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2012, 21:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Телефонная книжка и хэш-таблица (C++):

Электронная записная телефонная книжка - C++
Очень прошу, помогите с дипломной работой! Тема: Записная книжка. Язык: С++ 5. Электронная записная телефонная книжка: Программа...

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию - C++
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;list&gt; #include...

Описать структуру "телефонная книжка" - C++
здравствуйте! требуется создать телефонную книжку. вводятся n-ое количество имен и номеров телефонов, потом сортируются по алфавиту. ...

Хэш таблица - C++
Подскажите, пожалуйста, как сделать хэш-таблицу в которой у каждого элемента есть шесть полей.(например Имя фамилия возраст...). Что бы...

Хэш-таблица - C++
Ребят, помогите, пожалуйста, решить задачу: Хэш-функция определена как h(k) = k mod 11. Вводится последовательность N натуральных...

Хэш таблица - C++
Как работает метод цепочек, для разрешения коллизий в хэш таблице?

7
OstapBender
583 / 522 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
23.03.2012, 01:48 #2
C++
1
hash[hashkey].Add(...);
так.

только у вас таблица таблиц сейчас выходит.
0
FYlhtq_163_93
5 / 5 / 1
Регистрация: 27.12.2010
Сообщений: 29
23.03.2012, 12:24  [ТС] #3
Да? А где именно такой момент, я его не нашел, уж простите если задаю глупый вопрос, сам в этом толком не понимаю
0
OstapBender
583 / 522 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
23.03.2012, 20:32 #4
FYlhtq_163_93, такой момент он у вас как бы в основе...
Хеш-таблица - это как ассоциативный массив (насколько я помню - это и есть ассоц. массив, где в кач-ве индекса выступает хеш-ключ)
то есть будем считать, что это обычный map<int,info>.
у вас же получилось map<int,list<info>>.

я в свое время реализовал простую хеш таблицу через обычный массив (на вики пример даже есть).
связные списки здесь как-то не в теме... гуру поправьте если ошибся в чём-то.
0
OstapBender
583 / 522 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
23.03.2012, 20:38 #5
знаешь что мне твоя ава напоминает? )
0
Изображения
 
FYlhtq_163_93
5 / 5 / 1
Регистрация: 27.12.2010
Сообщений: 29
11.04.2012, 12:25  [ТС] #6
Цитата Сообщение от FYlhtq_163_93 Посмотреть сообщение
C++
1
newphone!=p->phone
в этом моменте меня напрягает следующее, как в этом и подобных случаях произвести сравнение двух строк, так как выводится сообщение о сравнении двух переменных разного типа char* и char**
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
11.04.2012, 12:47 #7
FYlhtq_163_93, char* сравниваются через strcmp/strncmp...
0
FYlhtq_163_93
5 / 5 / 1
Регистрация: 27.12.2010
Сообщений: 29
18.04.2012, 21:20  [ТС] #8
код до конца исправил, теперь он выглядит так. единственная ошибка возникает теперь после компиляции, ни одна функция не запоминается:
list.hpp:
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
#include<stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
 
using namespace std;
struct Node
{
    char phone[10];
    char* name;
    Node *next;
};
typedef Node* Pnode;
class List{
    Pnode Head;
    Pnode Tail;
private:
 
    Pnode Search(char* newphone, char* newname){
        Pnode p=Head;
        char* phstr=p->phone;
        char* nmstr=p->name;
        while(p!=NULL && strcmp(newphone,phstr)!=0 && strcmp(newname,nmstr)!=0) p=p->next;
        return p;
    }
 
public:
        
    int Find_bp(char* newphone){
        Pnode p=Head;
        char* phstr=p->phone;
        while(p!=NULL && strcmp(newphone,phstr)!=0){    p=p->next; phstr=p->phone;}
        if(p!=NULL) return 1;
        else return 0;
    }
    
    int Find_bn(char* newname){
        Pnode p=Head;
        char* nmstr=p->name;
        while(p!=NULL && strcmp(newname,nmstr)!=0){ p=p->next; nmstr=p->name;}
        if(p!=NULL) return 1;
        else return 0;
    }
 
    int Add(char* newphone, char* newname){
        Pnode q= Search(newphone, newname) ;
 
        if(q!=NULL && strcmp(q->phone,newphone)==0  && strcmp(newname,q->name)==0) return 0;
 
    //--Create------------------------------------
        Pnode Newnode= new Node;
        Newnode->next=NULL;
        strcpy(newphone, Newnode->phone);
        Newnode->name=newname;
    //--return newnode----------------------------
    //--add last----------------------------------
            {
            Tail->next=Newnode;
            Tail=Newnode;
            }
       return 1;
    }
 
    void Print(){
        Pnode p=Head;
        int count=1;
 
        while(p!=NULL)
        {
            cout<<"name: "<<p->name<<" phone:"<<p->phone<<";";
            p=p->next;
        }
    }
    
    int Del_bp(char* newphone){
        Pnode p=Head;
        char* phstr=p->next->phone;
        while(p!=NULL && strcmp(newphone,phstr)!=0){
        p=p->next;
        phstr=p->next->phone;
        }
        Pnode q=p->next;
        if(p!=NULL) {p->next=q->next; delete q;  return 1;}
        else return 0;
    }
    
    int Del_bn(char* newname){
        Pnode p=Head;
        char* nmstr=p->next->name;
        while(p!=NULL && strcmp(newname,nmstr)!=0){
        p=p->next;
        nmstr=p->next->name;
        }
        Pnode q=p->next;
        if(p!=NULL) {p->next=q->next; delete q;  return 1;}
        else return 0;
    }
    
    List(){
        Head=NULL;
        Tail=NULL;
    }
 
    List(List& orig){
        Pnode Head;
        Pnode Tail;
        if(this!=&orig)
            if(orig.Head!=NULL){
                Head =new Node;
                for(int i=0;i++;i<10){Head->phone[i]=orig.Head->phone[i];}
                Head->name=orig.Head->name;
                Head->next=NULL;
 
                Tail=Head;
 
                bool first=true;
                for(Pnode Q=NULL, OrigNode=orig.Head->next ; 
                    OrigNode != NULL ;
                    Tail= Q, OrigNode = OrigNode->next){
                    
                        Q = new Node;
                        for(int i=0;i++;i<10){Q->phone[i]=OrigNode->phone[i];}
                        Q->name=OrigNode->name;
                    }
 
                if(Tail!=Head) Tail->next=NULL;
            }
            else List();
    }
 
 
    ~List(){
        if(Head!=NULL){
            Pnode p=Head, q=Head->next;
            while(p!=NULL){
                delete p;
                p=q;
                if(q!=NULL) q=q->next;
            }
        }
    }
};
hash.cpp:
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
#include "list.hpp"
const int hashsize=100;
class chash
{
      List hash[hashsize];
private:
        int hashfunc(char num[10]){
            int numlast;
            char numch[2];
            numch[0]=num[8];
            numch[1]=num[9];
            return atoi(numch);
        }
public:
      
      void ins_hash(char phone[10],char name[]){
        int hashkey=hashfunc(phone);
        hash[hashkey].Add(phone, name);
      }
      int find_bp_hash(char phone[10]){
          int hashkey=hashfunc(phone);
          return hash[hashkey].Find_bp(phone);
          }
      int find_bn_hash(char name[]){int c;
            while(hash[c].Find_bn(name)==0)c++;
            return hash[c].Find_bn(name);
      }
      int del_bp_hash(char phone[10]){int c;
          int hashkey=hashfunc(phone);
          return hash[hashkey].Del_bp(phone);
      }
      int del_bn_hash(char name[]){int c;
          while(hash[c].Del_bn(name)==0)c++;
            return hash[c].Del_bn(name);
      }
      void print_hash_one(int hashkey){
          hash[hashkey].Print();
      }  
      void print_hash_all(){
          for(int i=0; i<hashsize; i++)hash[i].Print();
      }
      ~chash(){for(int i=0; i<hashsize; i++)hash[i].~List();}
};
 
int main(){
 
    char namestr[255],phonestr[10];
    char* str;
    chash obj;
    int again=1;
    while(again)
    {
        int newdata=0;
        printf("What you want to do with your yellow book, dear?=)");
        printf("\n");
        printf("\n");
        printf("...........  add:phone_name");
        printf("\n");
        printf("...........  del_phone:phone");
        printf("\n");
        printf("...........  del_name:name");
        printf("\n");
        printf("...........  find_phone:phone");
        printf("\n");
        printf("...........  find_name:name");
        printf("\n");
        printf("...........  print_all_book");
        printf("\n");
        printf("...........  print_str:string_number");
        /*printf("\n");
        printf("...........  clear");*/
        printf("\n");
        printf("...........  exit");
        printf("\n"); printf("\n");
 
        cin>>str;
        printf("\n");
 
        if( strncmp("add:",str,4)==0){
            for(int i=0;i++;i<10){phonestr[i]=str[4+i];}
            int j=0;
                while(str[15+j]!=' '){namestr[j]=str[15+j];j++;}
 
            obj.ins_hash(phonestr,namestr);     
        }
        char h[2];
        if( strncmp("print_all_book:",str,15)==0) obj.print_hash_all();
        if( strncmp("print_str:",str,10)==0){h[1]=str[10]; h[2]=str[11]; obj.print_hash_one(atoi(h));}
        
        if( strncmp("find_phone:",str,11)==0){
            for(int i=0;i++;i<10)phonestr[i]=str[11+i];
 
            if(obj.find_bp_hash(phonestr)) printf("Phone number \'%d\' is found",newdata);
            else printf("Not found");
            }
 
        if( strncmp("find_name:",str,10)==0){
            int j;
            while(str[10+j]!=' '){namestr[j]=str[10+j];j++;}
 
            if(obj.find_bn_hash(namestr)) printf("This name is found",newdata);
            else printf("Not found");
            }
        if( strncmp("del_phone:",str,10)==0){
            for(int i=0;i++;i<10){phonestr[i]=str[11+i];}
 
            if(obj.del_bp_hash(phonestr)) printf("Phone number and name \'%d\' are delete",newdata);
            else printf("Not found");
            }
 
        if( strncmp("del_name:",str,9)==0){
            int j;
            while(str[10+j]!=' '){namestr[j]=str[10+j];j++;}
 
            if(obj.del_bn_hash(namestr)) printf("This name with his(her) number are delete",newdata);
            else printf("Not found");
            }
        if( strncmp("exit",str,4)==0) again=0;
        printf("\n");
    }
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2012, 21:20
Привет! Вот еще темы с ответами:

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

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

Высокопроизводительная хэш-таблица - C++
Кто-нибудь знает проверенную в бою готовую реализацию высокопроизводительной хэш-таблицы или хотя бы материалы какие? Требования: ...

Хэш-таблица, ошибка - C++
Всем добрый день. Нужна помощь. За основу взять ПРИМЕР1 хэш-таблицы с прямой адресацией (разобраться с примером). Изменить функцию...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
18.04.2012, 21:20
Ответ Создать тему
Опции темы

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