質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

1681閲覧

分離チェイン法でハッシュ表のfind関数とinsert関数を実装したい(C++)

Ryuji_T

総合スコア6

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2021/03/03 07:09

C++初学者です。

分離チェイン法でハッシュ表を実装する課題に取り組んでいます。
find関数とinsert関数についてご教授していただきたいことがあります。色々なネットのページを見て自分なりに考えたのですが、あまり進みませんでした。
以下にコードとエラーメッセージを提示させていただきます。

まだあまりC++について深く理解しておらず、的外れなコードを書いてたり質問をしたりしているかもしれませんがどうかよろしくお願いします。

###ソースコード

C++

1#include<iostream> 2#include<list> 3#include<vector> 4#include<algorithm> 5#include<string> 6#include<new> 7 8using namespace std; 9 10class HashEntry { // key, value をセットで扱う 11 int key; 12 string value; 13 14public: 15 HashEntry(int k, string v) { key = k; value = v; }; 16 HashEntry() { key = 0; value = ""; }; 17 18friend class HashSeparate; 19}; 20 21class HashSeparate { 22 list<HashEntry>* table; // HashEntry の list の配列 23 int table_size; // ハッシュ表のサイズ 24 // 添字は [0 .. table_size-1] の範囲になる 25 int ndata; // 実際に登録されているデータ数 26 27public: 28 HashSeparate( int size ); 29 ~HashSeparate( ); 30 bool Insert( int key, string value ); 31 bool Find( int key, string & v ) const; 32 void Show() const; 33 34private: 35 int hash( int key ) const; // ハッシュ関数 36}; 37 38HashSeparate::HashSeparate( int size ){ 39 table = new list<HashEntry>[size]; 40 table_size = size; 41 ndata = 0; 42} 43 44HashSeparate::~HashSeparate( ){ 45 delete [] table; 46} 47 48// ハッシュ関数の一例.ハッシュ値は [0 .. table_size - 1] になる 49int HashSeparate::hash( int key ) const { 50 return key % table_size; 51}; 52 53 54bool HashSeparate::Insert( int k , string v ){ 55 int hi = hash(k); // ハッシュ値,つまり,配列の添字 56 string str; 57 if( Find( k, str ) ) // 同じkeyがすでに登録された 58 return false; 59 else { 60 table[hi][k]=v; //keyを挿入する 61 //(1)ここの書き方が間違っているのでしょうか。 62 ndata++; // データ数を更新する 63 return true; 64 } 65} 66 67bool HashSeparate::Find( int k , string & v) const { 68 int hi = hash(k); // ハッシュ値 69 list<HashEntry> l = table[hi]; 70 71 // 同じ key がすでに登録されたかを記録する.exists == true なら登録済み 72 bool exists = false; 73 if( !l.empty() ){ 74 list<HashEntry>::iterator itr; 75 for(itr = l.begin(); itr != l.end(); itr++) { 76 if (itr->key == k){ 77 exists = true; // あった 78 // (2)ここには何を追加すればいいのでしょうか。 79 return true; 80 break; 81 } 82 else return false; // なかった 83 } 84 } 85 86 return exists; 87} 88 89//ハッシュ表を表示させる 90void HashSeparate::Show() const { 91 for(int i = 0 ; i < table_size; i++) { 92 list<HashEntry> l = table[i]; 93 if( !l.empty() ){ 94 list<HashEntry>::iterator itr; 95 for(itr = l.begin(); itr != l.end(); itr++) 96 cout << "(" << itr->key << "," << itr->value << "). "; 97 cout << endl; 98 } 99 } 100} 101 102int main() { 103 HashSeparate lectureDay(3); 104 lectureDay.Insert(6, "June 16"); 105 lectureDay.Insert(7, "June 23"); 106 lectureDay.Insert(8, "June 30"); 107 lectureDay.Insert(9, "July 7"); 108 lectureDay.Show(); 109 110 int n = 3; 111 string val; 112 if ( !lectureDay.Find(n, val) ) 113 cout << n << " is not found." << endl; 114 else 115 cout << n << " is found. value = " << val << endl; 116 117 n = 9; 118 if ( !lectureDay.Find(n, val) ) 119 cout << n << " is not found." << endl; 120 else 121 cout << n << " is found. value = " << val << endl; 122 123 return 0; 124} 125

###エラーメッセージ

bool HashSeparate::Insert(int, std::string)’ 内: エラー: no match for ‘operator[]’ (operand types are ‘std::list<HashEntry>’ and ‘int’) table[hi][k]=v; //(1)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

table[hi] は list なので、table[hi][k] = v;
table[hi].push_back(HashEntry(k, v)); または
table[hi].emplace_back(k, v); に変更すればいいんじゃないのかな?

追記
質問のコードを見て、修正してみました。

diff

1 else { 2- table[hi][k]=v; //keyを挿入する 3- //(1)ここの書き方が間違っているのでしょうか。 4+ table[hi].emplace_back(k, v); 5 ndata++; // データ数を更新する 6 7- list<HashEntry> l = table[hi]; 8+ list<HashEntry>& l = table[hi]; 9 10- // 同じ key がすでに登録されたかを記録する.exists == true なら登録済み 11- bool exists = false; 12 if( !l.empty() ){ 13 list<HashEntry>::iterator itr; 14 for(itr = l.begin(); itr != l.end(); itr++) { 15 if (itr->key == k){ 16- exists = true; // あった 17- // (2)ここには何を追加すればいいのでしょうか。 18+ v = itr->value; 19 return true; 20- break; 21 } 22- else return false; // なかった 23 } 24 } 25 26- return exists; 27+ return false; 28 }

これでいいのでしょうか?

投稿2021/03/09 03:33

編集2021/03/09 05:16
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Ryuji_T

2021/03/15 12:07

返信が大変遅くなり申し訳ございません。ありがとうございます。プログラムはうまくいきました。しかし恐縮ですが、自分はイテレータの意味をまだあまりわかっておらず、「v = itr->value;」の意味を教えていただくことはできますでしょうか。
kazuma-s

2021/03/16 08:51 編集

itr はイテレータで、これを使ってリストの要素を順番に見ていきます。 key が一致する要素が見つかったので、その値の文字列 itr->value を v にコピーします。 v は main の string val への参照ですから、そこに見つかった文字列が入ります。
Ryuji_T

2021/03/17 16:52

理解できました。ありがとうございました。
guest

0

C++

1 table[hi][k]=v; //keyを挿入する 2 //(1)ここの書き方が間違っているのでしょうか。

間違ってますね。
list<HashEntry>* table; なんだから

table[hi]で得られるのは list<HashEntry>&、listにはoperator[]は定義されていないから
table[hi][k] できない。

投稿2021/03/03 14:17

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Ryuji_T

2021/03/07 03:12

返信が遅くなってすいません。table[hi]のkにstring型のvalueを入れる操作をしたいのですが、どういうふうに直せばいいのでしょうか。
episteme

2021/03/07 03:37

listの末尾に追加したいのであれば push_back/emplace_back では?
Ryuji_T

2021/03/07 04:16

table[hi].push_back(k);というふうに直したところ、 no matching function for call to ‘std::list<HashEntry>::push_back(int&)’ table[hi].push_back(k); というエラーが表示されたのですが、型があってないということでしょうか...?
episteme

2021/03/07 05:53

list<HashEntry> なんだから int が push_back できないのは自明では?
kazuma-s

2021/03/07 06:08

HashEntry(int k) { key = k; value = ””; }; というコンストラクタが定義されていれば、int が push_back できるでしょう。でも定義されていませんね。
Ryuji_T

2021/03/09 02:07

episteme様 「list<HashEntry> なんだから int が push_back できないのは自明では?」についてもう少し詳しく教えていただけますか
Ryuji_T

2021/03/09 02:12 編集

kazuma-s様 ありがとうございます。 その方法で試してみたところコンパイルが通りました。 ほかのところを変更せずに(1)の行だけを書き直すことは可能でしょうか。
episteme

2021/03/09 02:58

わからん。てかそこ以外読んでいない。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問