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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
FYlhtq_163_93
 Аватар для FYlhtq_163_93
5 / 5 / 1
Регистрация: 27.12.2010
Сообщений: 29
22.03.2012, 21:37     Телефонная книжка и хэш-таблица #1
Ребят, помогите кто может! Мне нужно реализовать телефонную книжку в виде хэш-таблицы. ХТ реализую через классы(сначала класс односвязного списка, а таблица представлена как массив списков). Как реализовать добавление элемента в хэш-таблицу? Прикрепляю два кода: класс список:
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); 
      }
};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2012, 21:37     Телефонная книжка и хэш-таблица
Посмотрите здесь:

C++ Хэш таблица
C++ телефонная книжка в c++
Хэш-таблица C++
Хэш-таблица, ошибка C++
C++ Хэш-таблица
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
23.03.2012, 01:48     Телефонная книжка и хэш-таблица #2
C++
1
hash[hashkey].Add(...);
так.

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

я в свое время реализовал простую хеш таблицу через обычный массив (на вики пример даже есть).
связные списки здесь как-то не в теме... гуру поправьте если ошибся в чём-то.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
23.03.2012, 20:38     Телефонная книжка и хэш-таблица #5
знаешь что мне твоя ава напоминает? )
Изображения
 
FYlhtq_163_93
 Аватар для 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**
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
11.04.2012, 12:47     Телефонная книжка и хэш-таблица #7
FYlhtq_163_93, char* сравниваются через strcmp/strncmp...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2012, 21:20     Телефонная книжка и хэш-таблица
Еще ссылки по теме:

Хэш-таблица C++
C++ Хэш таблица
Высокопроизводительная хэш-таблица C++

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

Или воспользуйтесь поиском по форуму:
FYlhtq_163_93
 Аватар для 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;
}
Yandex
Объявления
18.04.2012, 21:20     Телефонная книжка и хэш-таблица
Ответ Создать тему
Опции темы

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