多分探索木の昇順出力
多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが
途中でセグメントエラーが起きてしまいます。
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 ;
}
ぜひ、お力をお貸しください。よろしくお願いします。
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_1_thumbnail_img_sm.png)
お礼
＞そこがレポートのキモなんだから、それ訊いちゃダメでしょう。 回答ありがとうございます。 すみません。どうしても調べられなかったので・・。 英語のページ、参考になりました。 結局、 各ノードが子ノードへのポインタの他に, そのノード中のデータを空間的に全て含む直方体の範囲情報を検索のための索引として持ってるってことでいいんでしょうか？ >これはB+木では? ノードのキーという表現が適切ではありませんでした。