kkarnez
asked on
Strange problem with b-trees, and C functions in general
Subject: Strange problem with b-trees, and C functions in general
Hi to everyone...
I need your answer to a strange subject
that has to do with b-trees.
I want to built a function that will create a b-tree and will return its root node.
As parameters to the function I must pass the degree of the tree, the type of key and the key size.
For example:
CreateTree(root,degree,att rType,attr Length)
This function creats a tree of 'degree' and returns its root.
attrType here gives the type of he key
('i' for int,'f' for float and 'c' for string)
attLength gives the size of the key
(4 for int,4 for float and 1-255 for the string)
struct item{
'attrType' key;
struct node *p;
};
struct node{
struct node *p0;
struct item matrix[2*('degree')];
};
Where ' ' indicate a parameter to function
CreateTree(root,degree,att rType,attr Length)
Please help me... How can I do this????
I think this problem is impossible....
ps. (I think unions can't be used since I must pass the key length...)
Thanks for your help...(if any)
Hi to everyone...
I need your answer to a strange subject
that has to do with b-trees.
I want to built a function that will create a b-tree and will return its root node.
As parameters to the function I must pass the degree of the tree, the type of key and the key size.
For example:
CreateTree(root,degree,att
This function creats a tree of 'degree' and returns its root.
attrType here gives the type of he key
('i' for int,'f' for float and 'c' for string)
attLength gives the size of the key
(4 for int,4 for float and 1-255 for the string)
struct item{
'attrType' key;
struct node *p;
};
struct node{
struct node *p0;
struct item matrix[2*('degree')];
};
Where ' ' indicate a parameter to function
CreateTree(root,degree,att
Please help me... How can I do this????
I think this problem is impossible....
ps. (I think unions can't be used since I must pass the key length...)
Thanks for your help...(if any)
Try this 2 functions.
typedef struct node {
void *pdata;
struct node **pplinks;
} NODE;
typedef struct {
char type;
int length;
int degree;
NODE *pnode;
} ROOT_NODE;
void CreateNodeEntry(ROOT_NODE *proot, NODE **ppnode)
{
*ppnode = (NODE *)calloc (1, sizeof(NODE));
(*ppnode)->pdata = calloc (proot->length, 1);
(*ppnode)->pplinks=(struct node **)calloc (proot->degree, sizeof(NODE *));
}
void CreateTree (ROOT_NODE **pproot, int degree, char attrType, int attrLength)
{
*pproot = (ROOT_NODE *)calloc (1, sizeof(ROOT_NODE));
(*pproot)->type=attrType;
(*pproot)->degree=degree;
(*pproot)->length=attrLeng th;
CreateNodeEntry (*pproot, &((*pproot)->pnode));
}
CreateTree will create your tree and with CreateNodeEntry you will allocate memory for every node you need. There are no error checkings inside these to functions (Enough memory free, attrLength == 4 for attrType == 'i', ...) but I hope this will help to solve your problems.
Robert B. Rossmann
typedef struct node {
void *pdata;
struct node **pplinks;
} NODE;
typedef struct {
char type;
int length;
int degree;
NODE *pnode;
} ROOT_NODE;
void CreateNodeEntry(ROOT_NODE *proot, NODE **ppnode)
{
*ppnode = (NODE *)calloc (1, sizeof(NODE));
(*ppnode)->pdata = calloc (proot->length, 1);
(*ppnode)->pplinks=(struct
}
void CreateTree (ROOT_NODE **pproot, int degree, char attrType, int attrLength)
{
*pproot = (ROOT_NODE *)calloc (1, sizeof(ROOT_NODE));
(*pproot)->type=attrType;
(*pproot)->degree=degree;
(*pproot)->length=attrLeng
CreateNodeEntry (*pproot, &((*pproot)->pnode));
}
CreateTree will create your tree and with CreateNodeEntry you will allocate memory for every node you need. There are no error checkings inside these to functions (Enough memory free, attrLength == 4 for attrType == 'i', ...) but I hope this will help to solve your problems.
Robert B. Rossmann
I suggest you move to C++, then you can do this in a typesave and elegant way, using templates.
Furthermore I think rbr's idea of using pointers is the best way to go in C.
.luc.
Furthermore I think rbr's idea of using pointers is the best way to go in C.
.luc.
I have all the sources to create and use Btrees in Pascal, I have done it when I was student, it's possible to easily translate the sources in C
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I was looking at writing a b-tree myself, but opted for some source code that I found in simtel. This code will do the job I need, with minor tinkering. You may find that this code will do what you need. The code will most certainly demonstrate how to create a (new)root node.
This source code is located at this URL
http://oak.oakland.edu/pub/simtelnet/msdos/c/bplus11.zip
Please note that this is shareware code.
This source code is located at this URL
http://oak.oakland.edu/pub/simtelnet/msdos/c/bplus11.zip
Please note that this is shareware code.
It's not impossible, but it sounds like an assignment.
Won't things become easier if we use
typedef ROOT_NODE *ROOT_NODEPTR;
and reduce all the pointer stuff
gosh...see less stars then
typedef ROOT_NODE *ROOT_NODEPTR;
and reduce all the pointer stuff
gosh...see less stars then
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER