締切済み

多分探索木の昇順出力

2011/10/16 00:43

多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが途中でセグメントエラーが起きてしまいます。 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 ; } ぜひ、お力をお貸しください。よろしくお願いします。