木構造を用いた辞書検索

[yude]

こんにちは。以前、以下のトピックで質問していたものです。

http://dixq.net/forum/viewtopic.php?t=14435&p=114843

一応、課題提出はできたところまでで提出したのですが、
今回は残りのできなかったところをしようと思い、質問させていただきます。

まずコードを示します。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])	//	配列長を計算するマクロ
#define NUMBER_SIZE 3	// Number size
#define CHAR_TO_INDEX(ch) ((int)ch - (int)'0')	//	charからインデックスに変換するマクロ
 
// trieノード用テーブル
typedef struct trie_node trie_node_t;
struct trie_node
{
    int value;
    trie_node_t *children[NUMBER_SIZE];	// NUMBER_SIZE 分だけ子を持つ
};
 
// trieの活動用テーブル
typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;		//	ルートポインタ
    int count;				//	終端文字なら1以上の値を付ける
};

//	エラー表示関数
void error(char *str)
{
	printf("%s\n", str);
	exit(1);
}

// trieノードの記憶領域を作成する関数
trie_node_t *getNode(void)
{
    int i;
    trie_node_t *pNode;
  
    pNode = (trie_node_t *)malloc(sizeof(trie_node_t));

 	if(pNode == NULL)		//	メモリ確保失敗
 		error("Not Enough Memory");
 		
    if( pNode != NULL){		// メモリ確保が成功
        pNode->value = 0;	//	フラグを0に初期化
        for(i = 0; i < NUMBER_SIZE; i++){
            pNode->children[i] = NULL;		//	ナンバーサイズ分の初期化
        }
    }
 
    return pNode;
}
 
// trie の初期化関数 (rootはダミーノード)
void initialize(trie_t *pTrie)
{
    pTrie->root = getNode();		// ダミーノード確保
    pTrie->count = 0;				// 0で初期化
}
 
// keyが存在しない場合、trieに挿入
// keyがtrieのプレフィックスである場合, ノードをマーク。
void insert(trie_t *pTrie, char key[])
{
    int level, index, length = strlen(key);
    trie_node_t *p;	//	trie_node_tを指す活動用ポインタ
 
    pTrie->count++;	
    p = pTrie->root;
	
    for(level=0; level<length; level++){
        index = CHAR_TO_INDEX(key[level]);

		if( p->children[index] == NULL){
            p->children[index] = getNode();
        }
 
        p = p->children[index];		//次のポインタへ
    }
 
    // 終端文字としてマークを付ける
    p->value = pTrie->count;
}
 
// keyがトライに存在するなら1, 存在しないなら0を返す
int search(trie_t *pTrie, char key[])
{
    int level, index;
    int length = strlen(key);
    trie_node_t *p;			// 活動用ポインタ
 
    p = pTrie->root;
 
    for(level=0; level<length; level++){
        index = CHAR_TO_INDEX(key[level]);
 
        if( p->children[index] == NULL )	// 見つからない場合
			return 0;
 
        p = p->children[index];				//	次のポインタへ
    }

	printf("p->value = %d\n", p->value);　　// インデックス表示用
	return (0 != p && p->value);
}

//削除関数
void deletion(trie_t *tree, char key[])
{
	int i, j, found;				//	foundはフラグ用
	int length = strlen(key);
	trie_node_t *temp = tree->root;	//	tempは活動用ポインタ	

	for(i=0; i<length; i++){
		j = CHAR_TO_INDEX(key[i]);
		if(temp->children[j] == NULL){
			printf("[%d]bit目まで見つからず\n", i+1);
		}
		else{
			int k;
			for(k=0; k<NUMBER_SIZE; k++){
				if(k == j){						//	上のtemp->children[j] == NULL の部分でNULLの場合を調べているので
					continue;					//	j==kの場合はcontinueで飛ばす
				}
				else if( temp->children[k] ){	//	NULLじゃない場合
					found = 1;					//	foundフラグを1にする
					temp = temp->children[j];	//	次のポインタへ
					break;
				}
				else
					found = 0;
			}
			if(!found){							//	見つからなかったら(found = 0 の場合)
				temp->children[j] = NULL;
				break;
			}
		}	// else文の終わり
	}		// for文の終わり
}


// main関数
int main(void)
{
	int i;
    　char keys[][8] = {"1000", "100", "100", "0100", "0101", "0110", "0111", "1000"};	//	キーの登録
	char input[8], del[8];
	trie_t trie;
 
    char output[2][10] = {"未登録", "登録済み"};		//	結果表示用

    initialize(&trie);						//	trieの構造体を初期化

    // Trieを構成
    for(i=0; i<ARRAY_SIZE(keys); i++){
        insert(&trie, keys[i]);				//挿入関数へ登録してあるキーを一字ずつ渡していく
    }
 
    // keyの探索	とりあえず5回探してみる
	for(i=0;i<5;i++){		
		printf("Search data : ");
		scanf("%s", input);
		//scanf("%d", &trie->count);
		printf("%s --- %s\n", input, output[search(&trie, input)] );	//search関数はデータが登録してあれば0を，未登録なら1を返す関数
	}

	// keyの削除	こちらもとりあえず5回削除を行ってみる
	for(i=0;i<5;i++){		
		printf("\ndelete data : ");
		scanf("%s", del);

		deletion(&trie, del);	
		printf("%s --- %s\n", del, output[search(&trie, del)] );
	}
	
    return 0;

}

入力を行い、keyに登録したデータがあれば登録済みと返し、
入力されたデータが登録されていないのなら未登録と返します。

質問したいこととしては、

コード:

char keys[][8] = {"1000", "100", "100", "0100", "0101", "0110", "0111", "1000"};	//	キーの登録

というようにキーの登録をしている場合、1000に1というインデックスを付け、100に2というインデックスを付けたいのですが、
上のようにキーが重複している場合、1000が8に、100が3となってしまいます。
原因としては67行目で

コード:

 pTrie->count++;

とカウントアップしているからだと思うのですが、どのようにすればよいでしょうか。

[yude]

環境の書き忘れがあったので追記しておきます。

環境
　OS : windows 7
コンパイラ : Borand C++

コードがC++となっていますが、これは間違いでC言語での記述となっています。

[yude]

すみません、自己解決しました。

前提として「キーの重複はない」というものがあることを忘れていました。