ハッシュ探索②（オープンアドレス法） | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第７章

// main.c

#include <stdio.h>
#include <string.h>
#include "hash.h"

static void create_hash(void);
static void delete_hash(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_add(void);
static enum CmdRetValue_tag cmd_remove(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag cmd_exit(void);
static void add_elem(int value);
static void remove_elem(int value);
static int search_elem(int value);
static void get_line(char* buf, size_t size);

// コマンド
enum Cmd_tag {
    CMD_ADD,
    CMD_REMOVE,
    CMD_SEARCH,
    CMD_EXIT,

    CMD_NUM
};

// コマンド文字列の種類
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

// コマンドの戻り値
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};
// コマンド文字列
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "a", "add" },
    { "r", "remove" },
    { "s", "search" },
    { "e", "exit" }
};

// コマンド実行関数
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_add,
    cmd_remove,
    cmd_search,
    cmd_exit
};


static Hash gHash;


int main(void)
{
    create_hash();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_hash();

    return 0;
}

/*
    ハッシュ表を作成
*/
void create_hash(void)
{
    gHash = hash_create( 101 ); // 素数が好ましい
}

/*
    ハッシュ表を削除
*/
void delete_hash(void)
{
    hash_delete( gHash );
    gHash = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力してください。" );
    printf( "　データを登録: %s (%s)\n", CMD_STR[CMD_ADD][CMD_STR_SHORT], CMD_STR[CMD_ADD][CMD_STR_LONG] );
    printf( "　データを削除: %s (%s)\n", CMD_STR[CMD_REMOVE][CMD_STR_SHORT], CMD_STR[CMD_REMOVE][CMD_STR_LONG] );
    printf( "　データを探索: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
    printf( "　終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける

    戻り値：
        終了コマンドを入力されたら 0 を返す。
        それ以外のときは 0以外の値を返す。
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    get_line( buf, sizeof(buf) );

    enum Cmd_tag cmd = CMD_NUM;
    for( int i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[cmd]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    addコマンドの実行
*/
enum CmdRetValue_tag cmd_add(void)
{
    char buf[40];
    int value;

    puts( "追加する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    add_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    removeコマンドの実行
*/
enum CmdRetValue_tag cmd_remove(void)
{
    char buf[40];
    int value;

    puts( "削除する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    remove_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    searchコマンドの実行
*/
enum CmdRetValue_tag cmd_search(void)
{
    char buf[40];
    int value;

    puts( "探索する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( search_elem( value ) ){
        puts( "見つかりました。" );
    }
    else{
        puts( "見つかりませんでした。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を追加する

    引数：
        value:  追加する要素の数値データ。
*/
void add_elem(int value)
{
    hash_add( gHash, value );
}

/*
    要素を削除する

    引数：
        value:  削除する要素の数値データ。
*/
void remove_elem(int value)
{
    hash_remove( gHash, value );
}

/*
    要素を探索する

    引数：
        value:  探索する要素の数値データ。
    戻り値：
        発見できたら 0以外、発見できなければ 0 を返す。
*/
int search_elem(int value)
{
    return hash_search( gHash, value ) != NULL;
}

/*
    標準入力から１行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取れる最大文字数は size - 1 文字。

    引数：
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値：
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    // 末尾に改行文字があれば削除する
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}

// hash.c

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


enum{
    EMPTY    = -1,      // 空であることを表す値
    DELETED  = -2,      // データが削除されたことを表す値
};


struct Hash_tag {
    int*             table; // ハッシュ表
    size_t           size;  // data の要素数
};

static size_t hash_func(Hash hash, int key);
static size_t rehash_func(Hash hash, size_t index);
static void* xmalloc(size_t size);


/*
    ハッシュ表を作る
*/
Hash hash_create(size_t size)
{
    struct Hash_tag* hash = xmalloc( sizeof(struct Hash_tag) );
    hash->table = xmalloc( sizeof(int) * size );
    for( size_t i = 0; i < size; ++i ){
        hash->table[i] = EMPTY;
    }
    hash->size = size;

    return hash;
}

/*
    ハッシュ表を削除する
*/
void hash_delete(Hash hash)
{
    free( hash->table );
    free( hash );
}

/*
    ハッシュ表にデータを追加する
*/
void hash_add(Hash hash, int data)
{
    // 特別な値と同じ値を持つデータは許可しない
    assert(data != EMPTY && data != DELETED);

    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら、そこへ格納
        if( p->table[index] == EMPTY || p->table[index] == DELETED ){
            p->table[index] = data;
            return;
        }

        index = rehash_func( hash, index );
    }
    assert(!"hash_add failed.");
}

/*
    ハッシュ表からデータを削除する
*/
void hash_remove(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index] == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら削除
        if( p->table[index] != DELETED ){
            if( p->table[index] == data ){
                p->table[index] = DELETED;
                return;
            }
        }

        index = rehash_func( hash, index );
    }
}

/*
    ハッシュ表からデータを探索する
*/
int* hash_search(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index] == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら終了
        if( p->table[index] != DELETED ){
            if( p->table[index] == data ){
                return &p->table[index];
            }
        }

        index = rehash_func( hash, index );
    }

    return NULL;
}




/*
    ハッシュ関数
*/
size_t hash_func(Hash hash, int key)
{
    return key % hash->size;
}

/*
    再ハッシュ関数
*/
size_t rehash_func(Hash hash, size_t index)
{
    return (index + 1) % hash->size;
}

/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

// hash.h

#ifndef HASH_H_INCLUDED
#define HASH_H_INCLUDED


typedef struct Hash_tag* Hash;


/*
    ハッシュ表を作る

    引数：
        size:   ハッシュ表の大きさ
    戻り値：
        作成されたハッシュ表。
        使い終わったら、hash_delete関数に渡して削除する。
*/
Hash hash_create(size_t size);

/*
    ハッシュ表を削除する

    引数：
        hash:   hash_create関数で作成したハッシュ表
*/
void hash_delete(Hash hash);

/*
    ハッシュ表にデータを追加する

    引数：
        hash:   hash_create関数で作成したハッシュ表
        data:   追加するデータ
*/
void hash_add(Hash hash, int data);

/*
    ハッシュ表からデータを削除する

    引数：
        hash:   hash_create関数で作成したハッシュ表
        data:   削除するデータ
*/
void hash_remove(Hash hash, int data);

/*
    ハッシュ表からデータを探索する

    引数：
        hash:   hash_create関数で作成したハッシュ表
        data:   探索するデータ
    戻り値：
        ハッシュ表の要素へのポインタ。
        見つからなければ NULL。
*/
int* hash_search(Hash hash, int data);

#endif

/*
    再ハッシュ関数
*/
size_t rehash_func(Hash hash, size_t index)
{
    return (index + 1) % hash->size;
}

/*
    ２次ハッシュ関数
*/
inline size_t second_hash_func(Hash hash, size_t key)
{
    return 2;
}

/*
    再ハッシュ関数
*/
size_t rehash_func(Hash hash, size_t index)
{
    return (index + second_hash_func(hash, index)) % hash->size;
}