// 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
#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
#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