Hash1.h |
---|
// Hash1.h #ifndef __HASH1_H__INCLUDED__ #define __HASH1_H__INCLUDED__ // ハッシュ表のサイズ(素数) const unsigned HASH_SIZE = 11; // ハッシュに登録しない値 const int HASH_UNUSED = -1; // 二分探索木のノード struct SNode { const char* key; int value; SNode* pNext[2]; }; // ハッシュ struct SHash { SNode* pNode[HASH_SIZE]; }; void InitHash(SHash& hash); // 初期化 int HashFind(SHash& hash, const char* key); // データを検索 bool HashAdd(SHash& hash, const char* key, int value); // データを追加 void HashFree(SHash& hash); // 全削除 void HashDisp(SHash& hash); // データ全体を表示 #endif // #ifndef __HASH1_H__INCLUDED__ |
Hash1.cpp |
// Hash1.cpp #include <iostream.h> #include <iomanip.h> #include <string.h> #include "Hash1.h" //////////////////////////////////////////////////////////////////////////////// // static 関数のプロトタイプ宣言 // ハッシュ法のルーチン // ハッシュ関数 static int HashFunc(const char* key); // データを検索(ノードを返す) static SNode*& HashFindNode(SHash& hash, const char* key); // 二分探索木操作関数 // 初期化 static bool InitNode(SNode* pNode, const char* key, int value); // ノードを探す static SNode*& TreeFindNode(SNode*& pNode, const char* key); // 全削除 static void TreeFree(SNode*& pNode); // 二分探索木全体の表示 static int TreeDisp(SNode* pNode, int nDepth); //////////////////////////////////////////////////////////////////////////////// // ハッシュ法のルーチン // 初期化 void InitHash(SHash& hash) { for(int i = 0; i < HASH_SIZE; i++) hash.pNode[i] = NULL; } // ハッシュ関数 // 先頭と最後と中央の文字コードの合計を HASH_SIZE で割った余りを返します static int HashFunc(const char* key) { int nLen = strlen(key); if(nLen == 0) return 0; nLen--; return ((unsigned)key[0] + key[nLen / 2] + key[nLen]) % HASH_SIZE; } // データを検索(ノードを返す) static SNode*& HashFindNode(SHash& hash, const char* key) { return TreeFindNode(hash.pNode[HashFunc(key)], key); } // データを検索 int HashFind(SHash& hash, const char* key) { SNode* pNode = HashFindNode(hash, key); return pNode == NULL ? HASH_UNUSED : pNode->value; } // データを追加 bool HashAdd(SHash& hash, const char* key, int value) { SNode*& pNode = HashFindNode(hash, key); if(pNode != NULL) pNode->value = value; else { pNode = new SNode; if(pNode == NULL) return false; if(!InitNode(pNode, key, value)) { delete pNode; pNode = NULL; return false; } } return true; } // 全削除 void HashFree(SHash& hash) { for(int i = 0; i < HASH_SIZE; i++) { TreeFree(hash.pNode[i]); hash.pNode[i] = NULL; } } // データ全体を表示 void HashDisp(SHash& hash) { int nData = 0; // データの総数 for(int i = 0; i < HASH_SIZE; i++) { cout << "ハッシュ値 " << i << endl; int nDataNode = TreeDisp(hash.pNode[i], 0); cout << "データ数 " << nDataNode << endl; nData += nDataNode; char letter; cin >> letter; } cout << "総データ数 " << nData << endl; } //////////////////////////////////////////////////////////////////////////////// // 二分探索木操作関数 // 初期化 static bool InitNode(SNode* pNode, const char* key, int value) { pNode->key = strdup(key); if(key == NULL) return false; pNode->value = value; pNode->pNext[0] = NULL; pNode->pNext[1] = NULL; return true; } // ノードを探す static SNode*& TreeFindNode(SNode*& pNode, const char* key) { if(pNode == NULL) return pNode; int fComp = strcmp(pNode->key, key); if(fComp == 0) return pNode; return TreeFindNode(pNode->pNext[fComp < 0], key); } // 全削除 static void TreeFree(SNode*& pNode) { if(pNode == NULL) return; TreeFree(pNode->pNext[0]); TreeFree(pNode->pNext[1]); delete pNode; pNode = NULL; } // 二分探索木全体の表示 static int TreeDisp(SNode* pNode, int nDepth) { if(pNode == NULL) return 0; int nData = 1; nData += TreeDisp(pNode->pNext[0], nDepth + 1); cout << setw(nDepth * 2) << "" << pNode->key << " : " << pNode->value << endl; nData += TreeDisp(pNode->pNext[1], nDepth + 1); return nData; } |
Hash2.cpp |
// Hash2.cpp #include <iostream.h> #include <string.h> #include "Hash1.h" // 基本操作 static bool AddData(SHash& hash); // データの追加 static bool FindData(SHash& hash); // データの検索 int main() { SHash hash; InitHash(hash); while(AddData(hash)); while(FindData(hash)); HashDisp(hash); return 0; } static bool AddData(SHash& hash) { char key[1024]; int value; cout << "文字列と値を入力して下さい > " << flush; cin >> key >> value; if(strcmp(key, "q") == 0 || value == HASH_UNUSED) return false; return HashAdd(hash, key, value); } static bool FindData(SHash& hash) { char key[1024]; cout << "検索する文字列を入力して下さい > " << flush; cin >> key; if(strcmp(key, "q") == 0) return false; int value = HashFind(hash, key); if(value == HASH_UNUSED) cout << "見つかりません" << endl; else cout << "値は " << value << " です。" << endl; return true; } |
実行結果例 |
文字列と値を入力して下さい > Hash1.h 0 文字列と値を入力して下さい > #ifndef 1 文字列と値を入力して下さい > __HASH_H__INCLUDED__ 2 文字列と値を入力して下さい > #define 3 文字列と値を入力して下さい > const 4 文字列と値を入力して下さい > unsigned 5 文字列と値を入力して下さい > HASH_SIZE 6 文字列と値を入力して下さい > 11 7 文字列と値を入力して下さい > int 8 文字列と値を入力して下さい > HASH_UNUSED 9 文字列と値を入力して下さい > -1 10 文字列と値を入力して下さい > struct 11 文字列と値を入力して下さい > SNode 12 文字列と値を入力して下さい > char 13 文字列と値を入力して下さい > key 14 文字列と値を入力して下さい > value 15 文字列と値を入力して下さい > pNext[2] 16 文字列と値を入力して下さい > SHash 17 文字列と値を入力して下さい > pNode 18 文字列と値を入力して下さい > void 19 文字列と値を入力して下さい > InitHash 20 文字列と値を入力して下さい > hash 21 文字列と値を入力して下さい > HashFind 22 文字列と値を入力して下さい > bool 23 文字列と値を入力して下さい > HashAdd 24 文字列と値を入力して下さい > HashFree 25 文字列と値を入力して下さい > HashDisp 26 文字列と値を入力して下さい > #endif 27 文字列と値を入力して下さい > Hash1.cpp 28 文字列と値を入力して下さい > #include 29 文字列と値を入力して下さい > <iostream.h> 30 文字列と値を入力して下さい > <iomanip.h> 31 文字列と値を入力して下さい > <string.h> 32 文字列と値を入力して下さい > "Hash1.h" 33 文字列と値を入力して下さい > static 34 文字列と値を入力して下さい > HashFindNode 35 文字列と値を入力して下さい > InitNode 36 文字列と値を入力して下さい > TreeFindNode 37 文字列と値を入力して下さい > TreeFree 38 文字列と値を入力して下さい > TreeDisp 39 文字列と値を入力して下さい > nDepth 40 文字列と値を入力して下さい > for 41 文字列と値を入力して下さい > i 42 文字列と値を入力して下さい > hash.pNode[i] 43 文字列と値を入力して下さい > NULL 44 文字列と値を入力して下さい > nLen 45 文字列と値を入力して下さい > strlen 46 文字列と値を入力して下さい > return 47 文字列と値を入力して下さい > -- 48 文字列と値を入力して下さい > / 49 文字列と値を入力して下さい > ?: 50 文字列と値を入力して下さい > pNode->value 51 文字列と値を入力して下さい > != 52 文字列と値を入力して下さい > false 53 文字列と値を入力して下さい > delete 54 文字列と値を入力して下さい > true 55 文字列と値を入力して下さい > cout 56 文字列と値を入力して下さい > << 57 文字列と値を入力して下さい > endl 58 文字列と値を入力して下さい > nDataNode 59 文字列と値を入力して下さい > nData 60 文字列と値を入力して下さい > letter 61 文字列と値を入力して下さい > cin 62 文字列と値を入力して下さい > >> 63 文字列と値を入力して下さい > strdup 64 文字列と値を入力して下さい > if 65 文字列と値を入力して下さい > fComp 66 文字列と値を入力して下さい > strcmp 67 文字列と値を入力して下さい > new 68 文字列と値を入力して下さい > setw 69 文字列と値を入力して下さい > Hash2.cpp 70 文字列と値を入力して下さい > AddData 71 文字列と値を入力して下さい > FindData 72 文字列と値を入力して下さい > main 73 文字列と値を入力して下さい > 1024 74 文字列と値を入力して下さい > "q" 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 文字列と値を入力して下さい > q -1 検索する文字列を入力して下さい > value 値は 15 です。 検索する文字列を入力して下さい > int 値は 8 です。 検索する文字列を入力して下さい > ハッシュ関数 値は 88 です。 検索する文字列を入力して下さい > letter 値は 61 です。 検索する文字列を入力して下さい > cin 値は 62 です。 検索する文字列を入力して下さい > >> 値は 63 です。 検索する文字列を入力して下さい > SHash 値は 17 です。 検索する文字列を入力して下さい > FindData 値は 72 です。 検索する文字列を入力して下さい > #include 値は 29 です。 検索する文字列を入力して下さい > "q" 値は 75 です。 検索する文字列を入力して下さい > double 見つかりません 検索する文字列を入力して下さい > ハッシュ 値は 80 です。 検索する文字列を入力して下さい > 全削除 値は 84 です。 検索する文字列を入力して下さい > delete 値は 54 です。 検索する文字列を入力して下さい > while 見つかりません 検索する文字列を入力して下さい > new 値は 68 です。 検索する文字列を入力して下さい > Hash1.h 値は 0 です。 検索する文字列を入力して下さい > <iostream.h> 値は 30 です。 検索する文字列を入力して下さい > q ハッシュ値 0 TreeDisp : 39 TreeFree : 38 endl : 58 hash.pNode[i] : 43 nDataNode : 59 new : 68 strcmp : 67 strdup : 64 ハッシュ関数 : 88 基本操作 : 96 二分探索木操作関数 : 90 データ数 11 n ハッシュ値 1 <iomanip.h> : 31 HashAdd : 24 HashFind : 22 delete : 54 int : 8 true : 55 初期化 : 81 データ数 7 n ハッシュ値 2 Hash1.cpp : 28 HashDisp : 26 HashFree : 25 最後の追加要素 : 99 データ数 4 n ハッシュ値 3 -- : 48 FindData : 72 Hash2.cpp : 70 HashFindNode : 35 false : 53 static : 34 unsigned : 5 ハッシュ表のサイズ(素数) : 77 関数のプロトタイプ宣言 : 86 二分探索木のノード : 79 データ数 10 n ハッシュ値 4 #include : 29 11 : 7 << : 57 InitNode : 36 TreeFindNode : 37 if : 65 struct : 11 データ全体を表示 : 85 データ数 8 n ハッシュ値 5 "q" : 75 #endif : 27 #ifndef : 1 <iostream.h> : 30 HASH_SIZE : 6 HASH_UNUSED : 9 Hash1.h : 0 pNode : 18 pNode->value : 51 setw : 69 先頭と最後と中央の文字コードの合計 : 93 データ数 11 n ハッシュ値 6 != : 52 1024 : 74 cin : 62 const : 4 fComp : 66 pNext[2] : 16 データの検索 : 98 データを検索 : 82 ハッシュ法のテストプログラム : 76 データ数 9 n ハッシュ値 7 "Hash1.h" : 33 #define : 3 -1 : 10 <string.h> : 32 InitHash : 20 cout : 56 i : 42 nData : 60 nDepth : 40 二分探索木全体の表示 : 92 データ数 10 n ハッシュ値 8 ?: : 50 NULL : 44 for : 41 hash : 21 letter : 61 main : 73 value : 15 データの総数 : 95 ハッシュ : 80 全削除 : 84 データ数 10 n ハッシュ値 9 / : 49 SHash : 17 SNode : 12 bool : 23 char : 13 strlen : 46 データの追加 : 97 データを検索(ノードを返す) : 89 データを追加 : 83 ノードを探す : 91 割った余りを返します : 94 データ数 11 n ハッシュ値 10 >> : 63 AddData : 71 __HASH_H__INCLUDED__ : 2 key : 14 nLen : 45 return : 47 void : 19 ハッシュに登録しない値 : 78 ハッシュ法のルーチン : 87 データ数 9 n 総データ数 100 |
Last update was done on 2001.2.13
この講座の著作権はロベールが保有しています