木構造を用いた辞書検索[その２]

[yude]

たびたび投稿してすみません。
またつまずいてしまったので質問させていただきます。

先ほど
http://dixq.net/forum/viewtopic.php?f=3&t=14504
で質問した者です。

何度も示してはいますが、今回もまずコードを示します。

コード:

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

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])	　//	配列長を計算するマクロ

#define NUMBER_SIZE 2　	// 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が終端ならマークを付ける
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("index = %d\n", p->value); // index表示用
	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("not found\n");
		}
		else{
			int k;
			for(k=0; k<NUMBER_SIZE; k++){
				if(k == j){						//	上のtemp->children[j] == NULL の部分でNULLの場合を調べているので
					continue;					//	k == jの場合は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] = {"0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000"};	//	キーの登録(重複なし)
	char output[2][10] = {"未登録", "登録済み"};		//	結果表示用
	char input[8], del[8];
	trie_t trie;
	
    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);
	
		printf("%s --- %s\n", input, output[search(&trie, input)] );
	}

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

}

今回、行いたいこととしては、ノードの削除を行う前にindex表示用であるp->valueを線形リストで構成し、
ノード削除後、index表示用のp->valueを0にしたいです。

例を示します。

コード:

char keys[][8] = {"0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000"};

このキーにおいて、左から順に１，２，３，４，５，６，７，８とインデックスが割りふられます。
今、削除を行うとき、例えば入力として 0001と入力したとします。
このとき、それまで0001に割り振られていたインデックスである 1 を線形リスト構造化し、0001のインデックスを0にしたいのです。
同様に削除において1000が入力されたときインデックスである 8 を線形リストにし、1000のインデックスを0に。
同様に0010が入力されたときインデックスである 2 を線形リストにし、0010のインデックスを0に。


このようにして削除して使っていないインデックスを 1->8->2 というように線形リスト化したいのです。

また、ノードの削除ができる場合とできていない場合があり、おそらくdeletion関数が原因だと思うのですが、どの辺が怪しいのかも教えていただければありがたいです。