Solved

B-Tree in C++ HELP!!! Comes with my source file

Posted on 2003-11-10
5
469 Views
Last Modified: 2007-12-19
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 sector length=1000 and there are 10,000 sectors.

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 need help implementing these and if someone could help me tweak my code! any help will be appreciated.

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
Comment
Question by:djchiena
5 Comments
 

Expert Comment

by:CPOsosky
ID: 9717305
Your missing a closing brace in the void Btree::insert(int a) function above your test function.


Add another }//else right above the last else in the function.

-CPOsosky
0
 

Expert Comment

by:CPOsosky
ID: 9717318
                        while(k!=hold){
                              help->key[k]=help->key[k-1];
                              k--;
                         }

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

}//insert


should be

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

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

}//insert
0
 

Author Comment

by:djchiena
ID: 9737200
Thanks for all the help guys...I have finally compiled the program error free but here is my next problem...I need to change around my test() function around because it does not not seem to print out the tree correctly or it doesnt like to end after I enter some values. Can someone help me code a proper test function.  Help will be greatly appreciated and will not be overlooked...here is the test() function on this code but I think i need a new one that will ask a user to input, delete, search, and print...

void Btree::Test(){
      returnints returning;
      returnleafs returning1;
      leafnode d,y,z;
      
      
      int k;
      cout << "Please enter some integers and type 0 to end input: ";
      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];

}
0
 
LVL 9

Expert Comment

by:tinchos
ID: 10248853
No comment has been added lately, so it's time to clean up this TA.
I will leave the following recommendation for this question in the Cleanup topic area:

PAQ with points refunded

Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer
0
 

Accepted Solution

by:
modulo earned 0 total points
ID: 10308122
PAQed, with points refunded (350)

modulo
Community Support Moderator
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

831 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