ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Introduction to Linux - A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free.
1. Try to get as far as you can with the problem.
2. Post some code (or even pseudo code) to let us know you made some minimal effort
3. Ask a specific question about exactly where you're "stuck".
optiony/n) node I has left subtree
optiony/n) node I has right subtree
OK, here's a copy of my homework assignment on what I suspect is a similar (the same?) topic from a couple of years ago:
Binary searching B-tree blocks for keys is an important for DBMS systems.
The keys are arrays, and are contiguous in the B-tree block.
Lower performance systems, e.g., Oracle, store the keys as arrays of bytes.
Higher performance DBMS systems, e.g. MKF, store the keys as arrays of
longwords: When comparing the target key against a key in the B-tree block,
you must do 4 times as many compares when the keys are arrays of bytes
compared to the case when the keys are arrays of longwords. Therefore, in
this exercise the keys are arrays of longwords. (The most significant
longword is first.)
In a B-tree block, a key is the value of the key column(s) followed by an
address pointer. The address pointer points to a lower level B-tree block,
or to a row in a data block. In this exercise as in MKF, the key arrays are
When you search for a target key, you may or may not find it. If you find
it, you need to find the first duplicate, if there are duplicates.
If you don't find it, you need the index of the point at which you should
insert the target key (after first shifting all the keys from that point
onward up by one key position).
Write a binary search routine to search a B-tree block for a target key that
satisfies the following signature:
The array a holds the keys. key[i] starts at a[i * key_lw]. The index
of the first key is 0 (and it starts at a), and the index of the last key
is n - 1 (and it starts at a[(n-1) * key_lw]).
n >= 0.
The key_lw parameter is the number of longwords in a key. 1 <= key_lw <= 4.
The target_p parameter points to the first longword of the target key.
If the key is found, 1 is returned, else 0.
If the key is found, *index_p is set to the index of the first key
in the array that has a value identical to the target key (i.e., duplicate
keys are allowed in the array).
If the key is not found, *index_p is set to the insertion point (i.e.,
the index of the key minimally greater than the target key), or, if the target
key is greater than all the keys in the array a, *index_p is set to 'n'.
Your goal is to write a the fastest B-tree key search routine in the world.
That is, no one can write a faster routine.
The key_lw parameter is the number of longwords (unsigned 32 bit integers)
per key. This value can range from one to four. Your routine should work
for any n >= 0.
Put the binary_search routine in the attached file called "binsearch.c".
Do not create your own file. Edit the attached file.
I suppose I could post my solution, verbatim.
But instead, let me ask these questions:
1. What exactly does your "create()" function do?
2. Where exactly does the "option" parameter come from?
... and ...
3. "a" is an array of exactly what?
(or, to put it differently: "what exacty is the definition of 'item'?"