/****************************/
/* ハッシュ法               */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <string.h>

/*****************************************/
/* クラス List（衝突リスト，二分探索木） */
/*****************************************/
class List
{
		char *st;
		List *left, *right;

	public :
					// コンストラクタ
		List ()
		{
			st    = NULL;
			left  = NULL;
			right = NULL;
		}

		List (char *s)
		{
			left  = NULL;
			right = NULL;
			st    = new char [strlen(s)+1];
			strcpy(st, s);
		}
					// デストラクタ
		~List ()
		{
			if (st != NULL)
				delete [] st;
		}
					// データの追加
					//      dt : Listクラスのオブジェクト
					//      return : =1 : 追加
					//               =0 : 同じデータが存在
		int add(List *dt)
		{
			List *lt = this;
			int k, sw = -1;
							// トップ
			if (lt->st == NULL) {
				lt->st = new char [strlen(dt->st)+1];
				strcpy(lt->st, dt->st);
				sw = 1;
			}
							// トップでない
			else {
				while (sw < 0) {
					k = strcmp(dt->st, lt->st);
									// 同じデータがある
					if (k == 0)
						sw = 0;
									// 大きい
					else if (k > 0) {
						if (lt->right == NULL) {
							lt->right = dt;
							sw        = 1;
						}
						else
							lt = lt->right;
					}
									// 小さい
					else {
						if (lt->left == NULL) {
							lt->left = dt;
							sw        = 1;
						}
						else
							lt = lt->left;
					}
				}
			}
		
			return sw;
		}
					// データの削除
					//      st : 文字列
					//      return : =1 : 削除した
					//               =0 : 削除できなかった
		int del(char *st)
		{
			List *lt, *lt1 = this, *lt2 = this, *dt;
			int k, rl = 0, sw = 0;
		
			if (lt2->st != NULL) {
				while (sw == 0 && lt2 != NULL) {
					k = strcmp(st, lt2->st);
							// 削除
					if (k == 0) {
						sw = 1;
						if (lt2->right == NULL) {
									// 子供無し
							if (lt2->left == NULL) {
								if (rl == 0)
									lt2->st = NULL;
								else {
									if (rl > 0)
										lt1->right = NULL;
									else
										lt1->left = NULL;
								}
							}
									// 右無し
							else {
								if (rl == 0) {
									lt2->st    = (lt2->left)->st;
									lt2->right = (lt2->left)->right;
									lt2->left  = (lt2->left)->left;
								}
								else {
									if (rl > 0)
										lt1->right = lt2->left;
									else
										lt1->left = lt2->left;
								}
							}
						}
		
						else {
									// 左無し
							if (lt2->left == NULL) {
								if (rl == 0) {
									lt2->st    = (lt2->right)->st;
									lt2->left  = (lt2->right)->left;
									lt2->right = (lt2->right)->right;
								}
								else {
									if (rl > 0)
										lt1->right = lt2->right;
									else
										lt1->left = lt2->right;
								}
							}
									// 左右あり
							else {
								dt = lt2->left;
								if (rl == 0) {
									lt         = lt2->right;
									lt2->st    = lt->st;
									lt2->right = lt->right;
									lt2->left  = lt->left;
								}
								else {
									if (rl > 0)
										lt1->right = lt2->right;
									else
										lt1->left = lt2->right;
								}
								lt1->add(dt);
							}
						}
					}
							// 次のデータ
					else {
						lt1 = lt2;
						if (k > 0) {
							lt2 = lt2->right;
							rl  = 1;
						}
						else {
							lt2 = lt2->left;
							rl  = -1;
						}
					}
				}
			}
		
			return sw;
		}
					// データの探索
					//      st : 文字列
					//      return : =1 : 見つかった
					//               =0 : 見つからない
		int search(char *st)
		{
			List *lt = this;
			int k, sw = 0;
		
			if (lt->st != NULL) {
				while (sw == 0 && lt != NULL) {
					k = strcmp(st, lt->st);
							// 見つかった
					if (k == 0)
						sw = 1;
							// 次のデータ
					else if (k > 0)
						lt = lt->right;
					else
						lt = lt->left;
				}
			}
		
			return sw;
		}
};

/***********************************/
/* クラス Hash（ハッシュテーブル） */
/***********************************/
class Hash {
		int size;   // ハッシュテーブルの大きさ
		List **table;   // 衝突リスト
					// ハッシュ関数
					//      s : 文字列
		int hash(char *s)
		{
			unsigned int hash = 0, g;
			int i1, len;

			len = strlen(s);
			for (i1 = 0; i1 < len; i1++ ) {
				hash = (hash << 4) + s[i1];   // 左に4ビットシフトし文字を加える
				g    = hash & 0xf0000000;   // ビット毎のＡＮＤ
				if (g != 0) {
					hash ^= g >> 24;   // 排他的論理和
					hash ^= g;
				}
			}

			return hash % size;
		}

	public:
					// コンストラクタ
		Hash(int sz)
		{
			int i1;
			size  = sz;
			table = new List * [size];
			for (i1 = 0; i1 < size; i1++)
				table[i1] = new List();
		}
					// データの追加
					//      str : データ（文字列）
					//      return : =1 : 追加
					//               =0 : 同じデータが存在
		int add(char *str)
		{
			List *lt = new List(str);
			return table[hash(str)]->add(lt);
		}
					// データの削除
					//      str : データ（文字列）
					//      return : =1 : 削除した
					//               =0 : 削除できなかった
		int del(char *str)
		{
			return table[hash(str)]->del(str);
		}
					// データの探索
					//      str : データ（文字列）
					//      return : =1 : 見つかった
					//               =0 : 見つからない
		int search(char *str)
		{
			return table[hash(str)]->search(str);
		}
};

/****************/
/* main program */
/****************/
int main()
{
	int k, size, sw = 1;
	char st[100];

	printf("テーブルサイズ？ ");
	scanf("%d", &size);
	Hash H(size);

	while (sw > 0) {
		printf("1:追加，2:削除，3:探索，0:終了？ ");
		scanf("%d", &sw);
		switch (sw) {
			case 1:   // 追加
				printf("   データを入力してください ");
				scanf("%s", st);
				k  = H.add(st);
				if (k > 0)
					printf("      %s を追加しました\n", st);
				else
					printf("      既に同じデータが存在します\n");
				break;
			case 2:   // 削除
				printf("   データを入力してください ");
				scanf("%s", st);
				k = H.del(st);
				if (k > 0)
					printf("      %s を削除しました\n", st);
				else
					printf("      %s を削除できませんでした\n", st);
				break;
			case 3:   // 探索
				printf("   データを入力してください ");
				scanf("%s", st);
				k = H.search(st);
				if (k > 0)
					printf("      %s が見つかりました\n", st);
				else
					printf("      %s は見つかりませんでした\n", st);
				break;
			default :
				sw = 0;
				break;
		}
	}

	return 0;
}