如何插入结构在B树 [英] how to insert structure in a btree
本文介绍了如何插入结构在B树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个B树可以在插入值，我怎么能修改它插入结构（如图所示），而不是一个关键;我必须用卷数，必须从结构节点访问结构名。我该怎么办呢？
结构名
{
FIRST_NAME的char [16];
焦姓氏[16];
INT roll_number;
};
其中name是结构的阵列。到目前为止，我已经写了code插入结构元素，但我无法继续办理;请帮我。
的#define M 3;
结构节点
{
INT N; / * N＆LT;在节点键并购将号总是小于B树的顺序* /
结构节点* P [M]。 / *（n + 1个指针将被使用）* /
INT键[M-1]; / *名称的数组* /
} *根= NULL;枚举键状态{复制，SearchFailure，成功，InsertIt，LessKeys};
无效插入（INT键）;
无效显示（结构节点*根，INT）;
枚举键状态插件（结构节点* R，诠释的x，INT * Y，结构节点** U）;
INT searchPos（INT X，INT * key_arr，INT N）;主要（）
{
INT的选择，关键;
的printf（B树节点％d个\\ n个创造，M）;
而（1）{
的printf（1.Insert \\ n）;
的printf（2.Quit \\ n）;
的printf（请输入您的选择：）;
scanf函数（％d个，＆安培;选择）;
开关（选择）{
情况1：
的printf（请输入值：）;
scanf函数（％D键）;
插入（键）;
打破;
案例2：
出口（1）;
默认：
的printf（错误的选择\\ n）;
打破;
} / *开关*结束/
} / *而结束* /
} / *的main（）的结束* /无效插入（结构分类*）
{
结构节点* newnode;
INT upKey;
枚举键状态值;
值=插件（根，钥匙，和放大器; upKey，＆安培; newnode）;
如果（价值==重复）
的printf（键已有的\\ n）;
如果（价值== InsertIt）{
结构节点*铲除=根;
根=的malloc（sizeof的（结构节点））;
根 - ＆GT; N = 1;
根 - ＆GT;键[0] = upKey;
根 - 指p [0] =拔根;
根 - 指p [1] = newnode;
} / *如果结束* /
} / *插入（）结束* /
枚举键状态插件（结构节点* PTR，INT键，为int * upKey，结构节点** newnode）
{
结构节点* NEWPTR，* lastPtr;
INT POS，I，N，splitPos;
INT则newkey，中的lastKey;
INT检查= 1;
枚举键状态值;
如果（PTR == NULL）{
* newnode = NULL;
* upKey =键;
返回InsertIt;
}
N = ptr-将N;
POS = searchPos（键，ptr-＆GT;键，N）;
如果（POS＆LT; N＆放大器;＆放大器;关键== ptr-＆GT;键[POS]）
返回重复;
值=插件（ptr-指p [POS]键，和放大器;则newkey，＆安培; NEWPTR）;
如果（值！= InsertIt）
返回值;
/ *如果在节点关键字小于M-1，其中M为B树的顺序* /
如果（N＆LT，M - 1）{
POS = searchPos（则newkey，ptr-＆GT;键，N）;
/ *移位键和指针右侧插入新的密钥* /
对于（I = N; I＆GT; POS;我 - ）{
ptr-＆GT;按键[I] = ptr-＆GT;按键[I-1];
ptr-指p第[i + 1] = ptr-指p [I];
}
/ *钥匙插在准确位置* /
ptr-＆GT;键[POS] =则newkey;
ptr-指p [位置pos + 1] = NEWPTR;
++ ptr-将N; / *递增在节点密钥的数量* /
返回成功;
} / *如果结束* /
/ *如果在节点键是最大和节点位置插入是上* /
如果（POS ==米 - 1）{
=的lastKey则newkey;
lastPtr = NEWPTR;
}其他/ *如果在节点键是最大和节点的位置被插入时不会持续* /
{
=的lastKey＆ptr- GT;键[M-2];
lastPtr = ptr-指p [M-1];
为（ⅰ= M-2; I＆GT; POS;我 - ）{
ptr-＆GT;按键[I] = ptr-＆GT;按键[I-1];
ptr-指p第[i + 1] = ptr-指p [I];
}
ptr-＆GT;键[POS] =则newkey;
ptr-指p [位置pos + 1] = NEWPTR;
}
splitPos =（M - 1）/ 2;
（* upKey）= ptr-＆GT;键[splitPos]
（* newnode）=的malloc（sizeof的（结构节点））; / *拆分后右节点* /
ptr-＆GT; N = splitPos; /*没有。左分裂节点钥匙* /
（* newnode） - 将N = M-1-splitPos; / *号。右分裂节点键* /
对于（I = 0; I＆≤（* newnode） - 将N;我++）{
（* newnode） - 指p [I] = ptr-指p [1 + splitPos + 1〕;
如果（ⅰ≤（* newnode） - 将N - 1）
（* newnode） - GT;键[I] = ptr-＆GT;键[1 + splitPos + 1];
其他
（* newnode） - GT;钥匙由[i] =中的lastKey;
}
（* newnode） - 指p [（* newnode） - 将N] = lastPtr;
返回InsertIt;
} / *插件（）结束* /无效搜索（INT键）
{
INT POS，I，N;
结构节点* PTR =根;
的printf（搜索路径：\\ n）;
而（PTR）{
N = ptr-将N;
对于（I = 0; I＆下; ptr-将N;我+ +）
的printf（％d个，ptr-＆GT;键[I]）;
的printf（\\ n）;
POS = searchPos（键，ptr-＆GT;键，N）;
如果（POS＆LT; N＆放大器;＆放大器;关键== ptr-＆GT;键[POS]）{
的printf（去年dispalyed节点的\\ n％d处发现钥匙％D键，I）;
返回;
}
PTR = ptr-指p [POS];
}
的printf（键％d为不可用的\\ n，键）;
} / *搜索（）结束* /
INT searchPos（INT键，为int * key_arr，INT N）
{
INT POS = 0;
而（POS＆LT; N＆放大器;＆放大器;键＆GT; key_arr [POS]）
POS ++;
返回POS;
} / * searchPos（）结束* /
解决方案
在你的节点，你应该能够只需更换结构的定义关键与结构名称，并使用类似根 - ＆GT;的名字 - ＆GT; roll_number 你的比较。可能有一些其他的清理做的，但是这是基本的想法。
I have a B-tree that can insert values in, how can i modify it to insert a structure (as shown) instead of a key; I have to use roll number and have to access the structure name from structure node. How can i do it?
struct name
{
char first_name[16];
char last_name[16];
int roll_number;
};
where name is a array of structure. So far I've written code to insert the structure elements, but i am unable to proceed further; please help me out.
#define M 3;
struct node
{
int n; /* n < M No. of keys in node will always less than order of Btree */
struct node *p[M]; /* (n+1 pointers will be in use) */
int key[M-1]; /*array of names*/
} *root=NULL;
enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
void insert(int key);
void display(struct node *root,int);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
main()
{
int choice,key;
printf("Creation of B tree for node %d\n",M);
while(1) {
printf("1.Insert\n");
printf("2.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice) {
case 1:
printf("Enter the value : ");
scanf("%d",key);
insert(key);
break;
case 2:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
void insert(struct classifier *)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf("Key already available\n");
if (value == InsertIt) {
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/
enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
int check = 1;
enum KeyStatus value;
if (ptr == NULL) {
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M - 1) {
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i--) {
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is last*/
if (pos == M - 1) {
lastKey = newKey;
lastPtr = newPtr;
} else /*If keys in node are maximum and position of node to be inserted is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i--) {
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M - 1)/2;
(*upKey) = ptr->keys[splitPos];
(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++) {
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/
void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf("Search path:\n");
while (ptr) {
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(" %d",ptr->keys[i]);
printf("\n");
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos]) {
printf("Key %d found in position %d of last dispalyed node\n",key,i);
return;
}
ptr = ptr->p[pos];
}
printf("Key %d is not available\n",key);
}/*End of search()*/
int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/
解决方案
In your definition of node, you should be able to just replace struct key with struct name, and use something like root->name->roll_number for your comparisons. There might be some other clean-up to do, but that's the basic idea.
这篇关于如何插入结构在B树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
