Q&A
> 文字列を入力するとメッセージが止まらず、無限に流れている。
具体的に何を入力したのでしょうか?
charなのですからk,vともに1文字までしか入りませんよね？
c++でハッシュテーブルを実装したいです
を参考にして、ハッシュテーブルを実装しています。
リンク先のコードは正しく動くのですが、これをintではなく、charで実装したいです。
ソースコードを
int k-> char k
int v ->char v
と安直に変更すると、「コンパイルは通りますが、正しく挙動しません」
型を変えたことによって他にも変えるべきところがあるのだと推察しておりますが、詳しく分かりません。（ハッシュ関数の計算の部分でしょうか？）
ご教授頂けましたら幸いです。
発生している問題・エラーメッセージ
文字列を入力するとメッセージが止まらず、無限に流れている。
該当のソースコード
c++
1#include<iostream> 2#include<cstdlib> 3#include<string> 4#include<cstdio> 5using namespace std; 6const int T_S = 200; 7class HashTableEntry { 8 public: 9 char k; 10 char v; 11 HashTableEntry(char k, char v) { 12 this->k= k; 13 this->v = v; 14 } 15}; 16class HashMapTable { 17 private: 18 HashTableEntry **t; 19 public: 20 HashMapTable() { 21 t = new HashTableEntry * [T_S]; 22 for (int i = 0; i< T_S; i++) { 23 t[i] = NULL; 24 } 25 } 26 int HashFunc(char k) { 27 return (k % T_S); 28 } 29 void Insert(char k, char v) { 30 int h = HashFunc(k); 31 while (t[h] != NULL && t[h]->k != k) { 32 h = HashFunc(h + 1); 33 } 34 if (t[h] != NULL) 35 delete t[h]; 36 t[h] = new HashTableEntry(k, v); 37 } 38 int SearchKey(char k) { 39 int h = HashFunc(k); 40 while (t[h] != NULL && t[h]->k != k) { 41 h = HashFunc(h + 1); 42 } 43 if (t[h] == NULL) 44 return -1; 45 else 46 return t[h]->v; 47 } 48 void Remove(char k) { 49 int h = HashFunc(k); 50 while (t[h] != NULL) { 51 if (t[h]->k == k) 52 break; 53 h = HashFunc(h + 1); 54 } 55 if (t[h] == NULL) { 56 cout<<"No Element found at key "<<k<<endl; 57 return; 58 } else { 59 delete t[h]; 60 } 61 cout<<"Element Deleted"<<endl; 62 } 63 ~HashMapTable() { 64 for (int i = 0; i < T_S; i++) { 65 if (t[i] != NULL) 66 delete t[i]; 67 delete[] t; 68 } 69 } 70}; 71int main() { 72 HashMapTable hash; 73 char k, v; 74 int c; 75 while (1) { 76 cout<<"1.Insert element into the table"<<endl; 77 cout<<"2.Search element from the key"<<endl; 78 cout<<"3.Delete element at a key"<<endl; 79 cout<<"4.Exit"<<endl; 80 cout<<"Enter your choice: "; 81 cin>>c; 82 switch(c) { 83 case 1: 84 cout<<"Enter element to be inserted: "; 85 cin>>v; 86 cout<<"Enter key at which element to be inserted: "; 87 cin>>k; 88 hash.Insert(k, v); 89 break; 90 case 2: 91 cout<<"Enter key of the element to be searched: "; 92 cin>>k; 93 if (hash.SearchKey(k) == -1) { 94 cout<<"No element found at key "<<k<<endl; 95 continue; 96 } else { 97 cout<<"Element at key "<<k<<" : "; 98 cout<<hash.SearchKey(k)<<endl; 99 } 100 break; 101 case 3: 102 cout<<"Enter key of the element to be deleted: "; 103 cin>>k; 104 hash.Remove(k); 105 break; 106 case 4: 107 exit(1); 108 default: 109 cout<<"\nEnter correct option\n"; 110 } 111 } 112 return 0; 113}
試したこと
int k-> char k
int v ->char v
と変更してみた。
補足情報（FW/ツールのバージョンなど）
ここにより詳細な情報を記載してください。
回答2件
0
多くの環境で、charは符号付きの8ビットなので、値の範囲は-128～+127までです。「200で割ったあまり」すら、正しく表せないことがありますので、それが影響しているかもしれません。
投稿2021/06/11 09:26
総合スコア145184
0
アドバイスも踏まえ、ポインタを使い実現できそうです。
皆様ありがとうございました。
c++#include
1#include <cstdlib> 2#include <string> 3#include <cstdio> 4using namespace std; 5const int T_S = 107; 6class HashTableEntry 7{ 8public: 9 char *k; 10 char *v; 11 HashTableEntry(char *k, char *v) 12 { 13 this->k = k; 14 this->v = v; 15 } 16}; 17class HashMapTable 18{ 19private: 20 HashTableEntry **t; 21 22public: 23 HashMapTable() 24 { 25 t = new HashTableEntry *[T_S]; 26 for (int i = 0; i < T_S; i++) 27 { 28 t[i] = NULL; 29 } 30 } 31 int HashFunc(char *key) 32 { 33 int i = 0; 34 int s = 1; 35 while (*key != 0) 36 { 37 i += *key; 38 key++; 39 } 40 return (i % T_S); 41 } 42 void Insert(char *k, char *v) 43 { 44 int h = HashFunc(k); 45 46 if (t[h] != NULL) 47 delete t[h]; 48 t[h] = new HashTableEntry(k, v); 49 } 50 char *SearchKey(char *k) 51 { 52 int h = HashFunc(k); 53 54 if (t[h] == NULL) 55 return NULL; 56 else 57 return t[h]->v; 58 } 59 void Remove(char *k) 60 { 61 int h = HashFunc(k); 62 if (t[h] == NULL) 63 { 64 cout << "No Element found at key " << k << endl; 65 return; 66 } 67 else 68 { 69 delete t[h]; 70 } 71 cout << "Element Deleted" << endl; 72 } 73 ~HashMapTable() 74 { 75 for (int i = 0; i < T_S; i++) 76 { 77 if (t[i] != NULL) 78 delete t[i]; 79 delete[] t; 80 } 81 } 82}; 83int main() 84{ 85 HashMapTable hash; 86 char k[200]; 87 char v[200]; 88 int c; 89 while (1) 90 { 91 cout << "1.Insert element into the table" << endl; 92 cout << "2.Search element from the key" << endl; 93 cout << "3.Delete element at a key" << endl; 94 cout << "4.Exit" << endl; 95 cout << "Enter your choice: "; 96 cin >> c; 97 switch (c) 98 { 99 case 1: 100 cout << "Enter element to be inserted: "; 101 cin >> v; 102 cout << "Enter key at which element to be inserted: "; 103 cin >> k; 104 hash.Insert(k, v); 105 break; 106 case 2: 107 cout << "Enter key of the element to be searched: "; 108 cin >> k; 109 if (hash.SearchKey(k) == NULL) 110 { 111 cout << "No element found at key " << k << endl; 112 continue; 113 } 114 else 115 { 116 cout << "Element at key " << k << " : "; 117 cout << hash.SearchKey(k) << endl; 118 } 119 break; 120 case 3: 121 cout << "Enter key of the element to be deleted: "; 122 cin >> k; 123 hash.Remove(k); 124 break; 125 case 4: 126 exit(1); 127 default: 128 cout << "\nEnter correct option\n"; 129 } 130 } 131 return 0; 132}
投稿2021/06/12 01:44
編集2021/06/12 02:07
総合スコア6
k,vがchar*なので、もとの変数が解放されると不正なポインタになる
SearchKeyにてkの同一性を検証していないのでハッシュ(107種類)が同一だと誤ったvを取得する
といった問題があります。
実際に使うのであれば
#include<unordered_map>
std::unordered_map<std::string, std::string> hash;
となります。
あなたの回答
tips
プレビュー
