多分探索木の昇順出力
多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが
途中でセグメントエラーが起きてしまいます。
void out_MS(NODE *p){
int i,n=0 ;
for(i = 0; i <= p->nkeys; ++i)
if (p->refs[i] != NULL)
out_MS(p->refs[i]) ;
while(p->keys[n+1]!='\0'){
printf("No:%3d \"%s\"\n",count,p->keys[n]) ;
count++;
n++;
}
}
この、多分木に使われている、構造体は以下のとおりです
#define KK 16
typedef struct node{ // 多分探索木、B(B*)木構造体
char *keys[KK] ; // キー配列
int nkeys ; // キーの個数(実際の)
struct node *refs[KK + 1] ; // 子への参照欄
} NODE ;
この構造体に以下の関数で、10万要素の単語（ランダム）に追加していきます。
int add(NODE *root, char *inv) {
NODE *now , // 当該節
*prnt ; // nowの親節
int pos ; // 節内のキーの追加位置
prnt = now = root ;
while(now != NULL) { // キーの探索
pos = binsearch(now->keys, now->nkeys, inv) ; // 二分探索
if (pos < now->nkeys && strcmp(inv,now->keys[pos])==0) // 探索値はある
return FLS ; // 追加の必要なし
if (now->nkeys == KK) { // 当該節に無い、節内に空きが無い
prnt = now ;
now = now->refs[pos] ; // 子の節へ
}else if (pos <= now->nkeys) // 当該節に無い－追加位置が範囲内
break ;
}
if (now != NULL) // 当該節は在る
store_key(now, inv, pos, &(now->nkeys)) ; // 当該節にキーを追加格納
else { // 当該節は無い－新規生成
if (now != root) { // nowは根ではない
now = set_key(KK, inv) ; // キーを新節に格納
prnt->refs[pos] = now ; // 親節の参照欄に新節の番地を格納
}else
return FLS ;
}
return 1 ;
}
上記の関数で使われている、store_key set_key binserch の関数は以下のとおりです
void store_key(NODE *trgt, char *inv, int pos, int *nkeys) {
if (trgt->keys[pos] == INTV) // 当該位置は空
trgt->keys[pos] = strdup(inv) ; // 当該位置に格納
else { // 当該位置に入っている
shift_element(trgt, 'R', pos, *nkeys) ; // 要素を移動
trgt->keys[pos] = strdup(inv) ; // 当該位置に格納
}
++*nkeys ;
return ;
}
int binsearch(char *array[], int size, char *inv){ // 二分探索
int mid, // 当該位置
low, // 探索範囲の下限
high ; // 探索範囲の下限
if (size == 0) // キーは格納されていない
return 0 ;
if (strcmp(inv,array[0])<0) // 探索範囲以下
return 0 ;
if (0 < strcmp(inv,array[size - 1] )) // 探索範囲以上
return size ;
low = 0 ; // 下限設定
high= size - 1 ; // 上限設定
while(0 <= high - low) { // 二分探索本体
mid = (high + low) >> 1 ; // 中間位置を調べる
if (strcmp(inv,array[mid])==0) // 入力値が一致したとき
return mid ;
if (strcmp(inv,array[mid])<0) // 入力値が小さいとき
high = mid - 1;
else // 入力値が大きいとき
low = mid + 1 ;
}
return low ;
}
NODE *set_key(int size, char *key) {
NODE *new ;
new = crt_node(size) ; // 節の生成
new->keys[0] = strdup(key) ; // 配列の先頭に入力値を格納
new->nkeys = 1 ; // 節内の実際の要素数
return new ;
}
ぜひ、お力をお貸しください。よろしくお願いします。
