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.2
- 回答日時:
>xが外で定義されているので7ではないですか?
実際に試してみましょう
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# 未解決の外部シンボル _printfが関数_mainで参照されました 1 2022/09/18 15:28
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# c言語でユーザ関数を利用して入力された文字列を反転させるプログラムを作りたいです。 3 2023/01/29 19:47
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「指定されたキャストは有効で...
-
複数桁10進数の*桁目だけを抽出...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語での引数の省略方法
-
【C++】関数ポインタの使い方
-
比較回数と交換回数表示について
-
C言語で三目並べをするプログラ...
-
if と配列の組み合わせ
-
商と剰余を同時に求める(C言語)
-
C言語での奇数の和
-
ラップ関数とはどんなものですか?
-
Arduinoのプログラムにエラーが...
-
C言語
-
並列プログラミングのπ計算につ...
-
C言語 エラーの原因がわからな...
-
インライン展開されているか確...
-
GlobalAllocの変数を関数に引き...
-
HANDLEて何ですか?
-
read関数をノンブロッキングで...
-
C++でvectorにテキストファイル...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報