ハッシュ法

テキストp.112のハッシュ法の実装を行う。

 

ChainHash.h

#ifndef __ChainHash
#define __ChainHash

#include "Member.h"

typedef struct __node {
	Member  data;
	struct __node *next;
} Node;

typedef struct {
	int size;
	Node **table;
} ChainHash;

int Initialize(ChainHash *h, int size);

Node *Search(const ChainHash *h, const Member *x);

int Add(ChainHash *h, const Member *x);

int Remove(ChainHash *h, const Member *x);

void Dump(const ChainHash *h);

void Clear(ChainHash *h);

void Terminate(ChainHash *h);

#endif

ChainHash.c

#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ChainHash.h"

static int hash(int key, int size) 
{
	return key % size;
}

static void SetNode(Node *n, const Member *x, const Node *next)
{
	n->data = *x;
	n->next = next;
}

int Initialize(ChainHash *h, int size)
{
	int i;

	if((h->table = calloc(size, sizeof(Node *))) == NULL) {
		h->size = 0;
		return 0;
	}
	h->size = size;
	for (i = 0; i < size; i++)
		h->table[i] = NULL;
	return 1;
}

Node *Search(const ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];

	while (p != NULL) {
		if (p->data.no == x->no)
			return p;
		p = p->next;
	}
	return NULL;
}

int Add(ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];
	Node *temp;
	while (p != NULL) {
		if (p->data.no == x->no)
			return 1;
		p = p->next;
	}
	if ((temp = calloc(1, sizeof(Node))) == NULL)
		return 2;
	SetNode(temp, x, h->table[key]);
	h->table[key] = temp;
	return 0;
}

int Remove(ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];
	Node **pp = &h->table[key];
	while (p != NULL) {
		if (p->data.no == x->no) {
			*pp = p->next;
			free(p);
			return 0;
		}
		pp = &p->next;
		p = p->next;
	}
	return 1;
}

void Dump(const ChainHash *h)
{
	int i;
	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];
		printf("%02d  ", i);
		while (p != NULL) {
			printf("→ %d (%s) ", p->data.no, p->data.name);
			p = p->next;
		}
		putchar('\n');
	}
}

void Clear(ChainHash *h)
{
	int i;
	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];
		while (p != NULL) {
			Node *next = p->next;
			free(p);
			p = next;
		}
		h->table[i] = NULL;
	}
}
 
void Terminate(ChainHash *h)
{
	Clear(h);
	free(h->table);
	h->size = 0;
}

ChainHashTest.c

#include <stdio.h>
#include "Member.h"
#include "ChainHash.h"

typedef enum {
	TERMINATE, ADD, DELETE, SEARCH, CLEAR, DUMP
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > DUMP);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	ChainHash hash;
	Initialize(&hash, 13);
	do {
		int result;
		Member x;
		Node *temp;
		switch (menu = SelectMenu()) {
		case ADD:
			x = ScanMember("追加", MEMBER_NO | MEMBER_NAME);
			result = Add(&hash, &x);
			if (result)
				printf("エラー：追加に失敗しました(%s)。\n", (result == 1) ? "登録済み" : "メモリ不足");
			break;
		case DELETE:
			x = ScanMember("削除", MEMBER_NO);
			result = Remove(&hash, &x);
			if (result == 1)
				printf("エラー：その番号のデータは存在しません。\n");
			break;
		case SEARCH:
			x = ScanMember("探索", MEMBER_NO);
			temp = Search(&hash, &x);
			if (temp == NULL)
				printf("探索に失敗しました。\n");
			else { 
				printf("探索に成功しました。\n");
				PrintLnMember(&temp->data);
			}
			break;
		case CLEAR:
			Clear(&hash);
			break;
		case DUMP:
			Dump(&hash);
			break;
		}
	} while (menu != TERMINATE);
	Terminate(&hash);
	return 0;
}