Solved

B-Tree in C++ HELP!!!

Posted on 2003-11-03
13
479 Views
Last Modified: 2012-06-27
I have been given a project on implementing a B-tree in C++ in which a huge array of strings of length 50 is used to simulate a Hard drive sector.  The const string length=1000.

The project I have to do is pretty much insert, delete, search, print (preorder and postorder traversal), and do what my manager calls a "garbage collector", where it is a linked list of free items.

I have done a previous assignment from my old college day but it does not seem to be working.  I don't want to post my code on here since people will start taking it for their class homeworks and whatnot so I am ready to e-mail this code out to anyone who want to takle this thing with me. PLEASE SOMEONE HELP ME!!!!!!!!!!!
0
Comment
Question by:djchiena
  • 5
  • 4
13 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9676531
I can help you a bit conceptually but not much with the code ...
you should be posting code here as it increases the value of the PAQ database...

>but it does not seem to be working
you can post the relevant section of code which is not working ... run your program through a debugger to locate the problem
0
 

Author Comment

by:djchiena
ID: 9678645
Well here's my code for it...It is giving me 5 errors when I compile it where my functions declared in the Class Btree where "void test();" "void test1();", "void printall()", and "void main();" are giving me this error:

"local function definitions are illegal"

Also, my printall doesn't print it in preorder and postorder traversal and I do not have that "garbage collector funtion". Someone help get this thing figured out!!!

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

struct pointerpack;

int L, M;  //global variables, L is max # of items in leaf, M is max # of branches for node

struct internalnode{
      internalnode();
      vector<int> key;
      pointerpack *child;
      int count();
};




internalnode::internalnode(){
      child=0;
}

struct leafnode{
      leafnode();
      vector<int> list;
      void printList();
      void inserttoleaf(int a);
      bool deletefromleaf(int a);
      int count();

};

leafnode::leafnode(){
      
}


int leafnode::count(){
      int i=0;
      while(list[i]!=list.back()){
            i++;
      }
      i++;
      return i;
}


bool leafnode::deletefromleaf(int a){
      if(!list.empty()){
            if(a==list.back()){
                  list.pop_back();
                  return true;
            }
            else{
                  int i=0;
                  
                  while(list[i]!=list.back()){
                        if(list[i]==a)
                              break;
                        else
                              i++;
                  }//

                  if(list[i]==list.back())
                        return false;

                  else{
                        while(list[i]!=list.back()){
                              list[i]=list[i+1];
                              i++;
                        }
                        list.pop_back();
                        return true;
                  }//else
            }//else
      }//if

      else
            return false;

      

}//delete
      

                        




void leafnode::inserttoleaf(int a){
  if(list.empty())
            list.push_back(a);
  else      
      if(a>list.back())
            list.push_back(a);
      else{
            int i=0;
            int stop;
            while(list[i]<a){
                  i++;
            }
            
            stop=i;
            
            list.push_back(0);
            while(list.back()!=list[i]){
                  i++;
            }

            while(i!=stop){
                  list[i]=list[i-1];
                  i--;
            }

            list[i]=a;
      }
}


void leafnode::printList(){
      int i=0;
      while((list[i]!=list.back())){
            cout << list[i] << endl;
            i++;
      }
      cout << list[i] << endl;
}//printList


struct returnleafs{
      leafnode *temp1;
      leafnode *temp2;
};


struct returnints{
      internalnode *temp3;
      internalnode *temp4;
};







struct pointerpack{
      pointerpack();
      internalnode *ptr;
      leafnode *pointer;
      pointerpack *next;
};

pointerpack::pointerpack(){
      ptr=0;
      pointer=0;
      next=0;
}


int internalnode::count(){
      pointerpack *counter=child;
      int i=1;
      while(counter->next!=0){
            counter=counter->next;
            i++;
      }
      return i;
}


class Btree{
public:
      internalnode *root;

      

      
      Btree();
      leafnode mergeleaf(leafnode A, leafnode B);
      returnleafs splitleaf(leafnode A);
      internalnode mergeint(internalnode A, internalnode B);
      returnints splitint(internalnode A);
      
      
      void insert(int a);
      void del(int a);
      int search(int a);
      void printall();

      void Test();
      void Test1();
};

Btree::Btree(){
root=0;
}



leafnode Btree::mergeleaf(leafnode A, leafnode B){
      
      int i=0;
      
      while((B.list[i]!=B.list.back())){
          A.list.push_back(B.list[i]);
            i++;
      }
      A.list.push_back(B.list[i]);
      return A;
}//merge

returnleafs Btree::splitleaf(leafnode A){
      returnleafs returning;
      int count=0;
      while((A.list[count]!=A.list.back())){
            count++;
      }
      count++;
      int b=ceil(count/2);
      int i=0;
      returning.temp1=new leafnode;
      returning.temp2=new leafnode;
      while(i<=b-1){
            returning.temp1->list.push_back(A.list[i]);
            i++;
      }
      
      while(i<=count-1){
            returning.temp2->list.push_back(A.list[i]);
            i++;
      }

      return returning;
}//split


internalnode Btree::mergeint(internalnode A, internalnode B){
      pointerpack *current;
      current=A.child;
      while(current->next!=0){
            current=current->next;
      }
      current->next=B.child;
      int i=0;
      while(B.key[i]!=B.key.back()){
      A.key.push_back(B.key[i]);
      i++;
      }
      A.key.push_back(B.key[i]);
      return A;
}

returnints Btree::splitint(internalnode A){
      returnints returning;
      returning.temp3=new internalnode;
      returning.temp4=new internalnode;
      pointerpack *currently;
      currently=A.child;
      int i=1;
      while(currently->next!=0){
            currently=currently->next;
            i++;
      }
      int count=ceil(i/2);
      pointerpack *head;
      
      pointerpack *current=0;
      pointerpack *current1=0;
      head=A.child;
      current=returning.temp3->child=head;
      
      int set=1;
      while(set<=count){
            current=current->next;
            set++;
      }

      current1=current->next;
      
      returning.temp4->child=current1;
      current->next=0;
      
      set=0;
      int count1=0;
      while(A.key[count1]!=A.key.back()){
            count1++;
      }
      count1++;
      int number=ceil(count1/2);
      
      while(set<=number-1){
      returning.temp3->key.push_back(A.key[set]);      
      set++;
      }
      set++;
      
      while(set<=count1-1){
            returning.temp4->key.push_back(A.key[set]);
            set++;
      }
      return returning;
      
}







void Btree::insert(int a){
      returnints returner;
      returnleafs returning;
      if(root==0)
            root=new internalnode;
      internalnode *help=root;
      
      internalnode *hold=0;
      leafnode *keep=0;
      if(help->child==0){
            help->child=new pointerpack;
            keep=new leafnode;
            keep->inserttoleaf(a);
            help->child->pointer=keep;
            help->child->next=0;
      
      }

      else{
            if(help->child->ptr==0){            //one level
                  if(help->key.empty()){  //only one leafnode
                        help->child->pointer->inserttoleaf(a);
                        if(help->child->pointer->count()>L){
                              leafnode helper=*help->child->pointer;
                              returning=splitleaf(helper);
                              pointerpack *one1, *two2;
                              leafnode *one, *two;

                              one=returning.temp1;
                              two=returning.temp2;
                              
                              
                              
                              one1=new pointerpack;
                              two2=new pointerpack;
                              help->child=one1;
                              one1->pointer=one;
                              two2->pointer=two;
                              one1->next=two2;
                              two2->next=0;
                              
                              
                                                

                              
                              help->key.push_back(help->child->pointer->list.back());
                              
                              
                        }//if

                  }//if

                  else{
                        int k=0;
                        while((help->key[k]<a)&&(help->key[k]!=help->key.back())){
                              k++;
                        }
                        if((help->key[k]==help->key.back())&&(a>help->key[k]))
                              k++;
                        pointerpack *tempor=help->child;
                        int count=0;
                        while(count<k){
                              tempor=tempor->next;
                              count++;
                        }//while
                        tempor->pointer->inserttoleaf(a);
                        help->key[k]=tempor->pointer->list.back();
                        if(tempor->pointer->count()>L){
                              returnleafs junior;
                              pointerpack *holder=tempor->next;
                              pointerpack *insert=new pointerpack;
                              junior=splitleaf(*tempor->pointer);
                              tempor->pointer=junior.temp1;
                              insert->pointer=junior.temp2;
                              tempor->next=insert;
                              insert->next=holder;
                              help->key[k]=tempor->pointer->list.back();
                              
                                    
                              k++;
                              int hold=k;
                              help->key.push_back(0);
                              while(help->key.back()!=help->key[k]){
                                    k++;
                              }

                              while(k!=hold){
                                    help->key[k]=help->key[k-1];
                                    k--;
                              }

                              help->key[k]=insert->pointer->list.back();
                        }//if
                  
                  }//else
            }//if

}//insert



void Btree::Test(){
      returnints returning;
      returnleafs returning1;
      leafnode d,y,z;
      
      
      int k;
      cin >> k;
      while(k!=0){
            d.list.push_back(k);
            cin>>k;
      }
      cout <<endl;
      cin >> k;
      while(k!=0){
            y.list.push_back(k);
            cin>>k;
      }
      cout << endl;      
      cin >> k;
      while(k!=0){
            z.list.push_back(k);
            cin>>k;
      }
      returning1=splitleaf(z);
      z=mergeleaf(*returning1.temp1, *returning1.temp2);
      
      
      internalnode one, two, three;
      pointerpack *current, *anoth, anoth2;
      current=new pointerpack;
      anoth=new pointerpack;
      pointerpack *anoth1=new pointerpack;
      anoth->pointer=&y;
      anoth1->pointer=&z;
      one.child=current;
      one.child->pointer=&d;
      
      one.child->next=anoth;

      
      anoth->next=anoth1;
      
      anoth1->next=0;
      
      
      
      one.key.push_back(5);
      one.key.push_back(10);
            one.key.push_back(15);
      one.key.push_back(20);
      
      returning=splitint(one);
      pointerpack *help;
      
      help=returning.temp3->child;
      help->pointer->printList();
      help->next->pointer->printList();
      help=returning.temp4->child;
      help->pointer->printList();
      cout << returning.temp3->key[0];
      cout << returning.temp3->key[1];
cout << returning.temp4->key[0];

};


void Btree::Test1(){
      L=3;      
      int k;
      cin >> k;
      while(k!=0){
            
            
            insert(k);
            
            cin>>k;
      }
 
}

void Btree::printall(){
      pointerpack *what=root->child;
      while(what!=0){
            what->pointer->printList();
            what=what->next;
      }
}

void main(){
      Btree C;
      C.Test();
      C.printall();
}







      

0
 
LVL 69

Expert Comment

by:Callandor
ID: 9680536
Could it be that you haven't declared the functions in your .h file?  Fix that first, and you'll be able to single-step through your code to solve the other problems.
0
 

Author Comment

by:djchiena
ID: 9680851
I didn't make any .h files but i did include a .h in the #include headers and the errors didn't come up except one...the vector.h file does not exist.  I'm coding this through Visual C++. I think i may have lost my vector.h file but I don't remember making such a file 3 years ago.  When I take the .h off the #include <vector.h>, it gave me those errors I posted earlier but they disappear once I put the .h back on. Weird I must say. At least I am getting some kind of progress.
0
 

Author Comment

by:djchiena
ID: 9715903
Any other ideas guys...HELP ME!!! I need to get this thing finished by next week.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 45

Expert Comment

by:sunnycoder
ID: 9720086
I can help you write it in C... I am way out of touch for C++ (its been years since I used it in any form)
0
 

Author Comment

by:djchiena
ID: 9720181
C is fine with me...
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9720198
errr... you are not expecting me to write the whole code... are you ?
0
 

Author Comment

by:djchiena
ID: 9722079
I don't expect anyone to write the whole code out. Just let me know what parts you think do not work and see if you can code it if you can.
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 500 total points
ID: 9722261
>Just let me know what parts you think do not work and see if you can code it if you can.
I would never go through so much of C++ code.... I can write C code for the same in shorter duration ;o)
here are links to (hopefully) working implementations of B tree ... see if they serve your purpose

http://www.manlug.mcc.ac.uk/MailArchives/Man-LUG/2002/msg00023.html

this has source for C++ implementation
http://www.programmersheaven.com/zone3/cat451/index.htm
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

A short article about a problem I had getting the GPS LocationListener working.
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now