C言語で B-treeを実装するプログラムを書きました。
まだtreeに挿入する関数しか書いておりませんが。。
まず空の根を作ってからそこにどんどん要素を挿入していくのですが、どうも要素が
挿入されていないように思えます。
どこがいけないのか分かる方いらっしゃいませんか?
よろしくお願いします。
#include <stdio.h>
#define T 10
struct b_tree{
int key[2*T-1];
struct b_tree *node[2*T];
int size;
int leaf;//この節点が葉であったら1とする
};
void BTreeCreate(void);
void BTreeSplitChild(struct b_tree x,int i,struct b_tree y);
void BTreeInsert(struct b_tree t,int k);
void BTreeInsertNonfull(struct b_tree x,int k);
void PrintBtree(struct b_tree x);
struct b_tree root;
int main (int argc, const char * argv[]) {
// insert code here...
/*int t;*/
char command;
int key;
BTreeCreate();
/*scanf("%d",&t);*/
while (1) {
scanf("%c %d",&command,&key);
if (command=='E') break;
if(command=='I') BTreeInsert(root,key);//木にkeyを挿入
}
PrintBtree(root);//木を表示
return 0;
}
void BTreeCreate(void){//空のB-木の生成
struct b_tree x;
x.leaf=1;
x.size=0;
root=x;
}
void BTreeSplitChild(struct b_tree x,int i,struct b_tree y){
/*B-木における節点の分割をする節点xのi番目の枝の先にある節点yが飽和であった
場合にyをyの中央値で分ける。yの中央値はxの新たなkeyとなりxの枝数は1つ増える*/
int j;
struct b_tree z;
z.leaf=y.leaf; //zが葉であるかどうかはyが葉であるかどうかに依る
z.size=T-1; //また新しくできるxの子zは最小数のkey(T-1)を持たせる
for (j=1; j<= T-1; j++) {
z.key[j]=y.key[j+1]; //yの中央値よりおおきい値(T-1個)をzに渡す
}
if(y.leaf==0){ //またyが個をもつ場合は枝もzに渡す
for (j=1; j<=T; j++)
z.node[j]=y.node[T+j];
}
y.size=T-1; //そしてyのサイズも中央値とzに渡した分小さくなる
for (j= x.size+1; j>=i+1; j--) { //xにyの中央値を渡すのでx枝の右半分を1つずつ右へずらす
x.node[j+1]=x.node[j];
}
x.node[i+1]=&z; //i+1番目の枝に新たな子zのポインタを与える
for (j=x.size; j>=i; j--) { //値も右へずらす
x.key[j+1]=x.key[j];
}
x.key[i]=y.key[T]; //xのi番目の値をyの中央値とする。
x.size=x.size+1; //xは1サイズup
}
void BTreeInsert(struct b_tree t,int k){
int Tsub=T; //条件部にTが使えなかったのでTsubに退避
struct b_tree r,s;
r=t;
if (r.size == Tsub) {
/*根が飽和だった場合を考える新たな親を必要とするため
それをsとする。するとsは葉ではなく、sizeは0,
そして元々の根rのポインタを与える*/
s.leaf=0;
s.size=0;
s.node[1]=&r;
root=s;
BTreeSplitChild(s,1,r);
BTreeInsertNonfull(r,k);
}
else {
BTreeInsertNonfull(r,k);
}
}
void BTreeInsertNonfull(struct b_tree x,int k){
/*未飽和の節点xにkを挿入しようと考える。*/
int i;
int Tsub=T;
if (x.leaf==1) {
/*もし、xが葉であれば大小関係を考えて挿入。その際他のkey
を右へ1つずつずらす。またxのサイズを1up*/
while (i>=1 && k<x.key[i]) {
x.key[i+1]=x.key[i];
i--;
}
x.key[i+1]=k;
x.size++;
}
else {
/*もしxが葉でなければどこの枝をたどればいいのか考える*/
while (i>=1 && k<x.key[i]) {
i--;
}
i++;
if ((*x.node[i]).size == 2*Tsub-1) {
/*たどる枝の先が飽和であった場合分割する*/
BTreeSplitChild(x, i, *x.node[i]);
if (k > x.key[i]) {
i++;
}
}
BTreeInsertNonfull(*x.node[i],k);//枝をたどる
}
}
void PrintBtree(struct b_tree x){
printf("abc");
printf("%d",x.leaf);//実行するとleafが1のままなので、数が挿入されていない?
int i,l;
if(x.leaf==1){
for (i=1; i<=x.size; i++) {
printf("%d def",x.key[i]);
}
if(l==0)printf("\n");
}else {
for (i=1; i<=x.size; i++) {
printf("%d ghi",x.key[i]);
}
if(l==0)printf("\n");
l++;
printf(" jkl");
for (i=1; i <= x.size+1; i++) {
PrintBtree(*x.node[i]);
}
}
printf("\n");
}
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
そりゃそ~だ.
#include <stdio.h>
int x;
void foo(int t)
{
t = 7;
}
int main()
{
x = 3;
foo(x);
printf("%d\n", x);
return 0;
}
というプログラムで何が出力されると思いますか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
std::set<int> で、ある値が何...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語での引数の省略方法
-
return 1L
-
複数桁10進数の*桁目だけを抽出...
-
C#のコンパイルエラーCS0120に...
-
「指定されたキャストは有効で...
-
C言語 エラーの原因がわからな...
-
C言語のサイコロシミュレート
-
ラップ関数とはどんなものですか?
-
困ってます…nCrを求めるC言語...
-
C言語の配列をC++のvectorに高...
-
int16_t の _t は何?
-
構造体の勉強中です 合計点の高...
-
Arduinoのプログラムにエラーが...
-
C言語の関数で戻り値を返す必要...
-
C言語で分からないところがあり...
-
文字列の構造体キャスト
-
素数問題
-
引数 戻り値 return文について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
AtCoderABC135の問題Cについて
-
C言語 エラーの原因がわからな...
-
複数桁10進数の*桁目だけを抽出...
-
【C++】関数ポインタの使い方
-
実数の整数部,小数部の取得
-
ラップ関数とはどんなものですか?
-
if と配列の組み合わせ
-
return 1L
-
read関数をノンブロッキングで...
-
(int *)の意味
-
std::set<int> で、ある値が何...
-
Win32APIで作るコンボボックス...
-
C++でvectorにテキストファイル...
-
「{ } で囲むだけ」は正しい?
-
足して100になるような乱数のア...
-
Arduinoのプログラムにエラーが...
-
課題でつまってます・・・
おすすめ情報