btree Programm Absturz möglicherweise aufgrund von Zeigern

Question

Ich versuche, einen b-Baum in der Reihenfolge der Ebene zu drucken, aber es stürzt weiter ab. Ich bin nicht sicher, was der wahre Grund ist, aber ich denke, es stürzt wegen der Zeiger. Ich versuche, eine Funktion zu verwenden, die ich online gefunden habe, die durch jede Ebene geht und es in eine Warteschlange stellt und es druckt, aber ive lief in dieses Problem. Wenn jemand einen anderen Weg hat, es zu tun, lass es mich wissen.

// C++ program for B-Tree insertion 
    #include<iostream> 
    #include <queue> 
    using namespace std; 
    int ComparisonCount = 0; 
    // A BTree node 
    class BTreeNode 
    { 
     int *keys; // An array of keys 
     int t;  // Minimum degree (defines the range for number of keys) 
     BTreeNode **C; // An array of child pointers 
     int n;  // Current number of keys 
     bool leaf; // Is true when node is leaf. Otherwise false 
    public: 
     BTreeNode(int _t, bool _leaf); // Constructor 

             // A utility function to insert a new key in the subtree rooted with 
             // this node. The assumption is, the node must be non-full when this 
             // function is called 
     void insertNonFull(int k); 

     // A utility function to split the child y of this node. i is index of y in 
     // child array C[]. The Child y must be full when this function is called 
     void splitChild(int i, BTreeNode *y); 

     // A function to traverse all nodes in a subtree rooted with this node 
     void traverse(); 

     // A function to search a key in subtree rooted with this node. 
     BTreeNode *search(int k); // returns NULL if k is not present. 

            // Make BTree friend of this so that we can access private members of this 
            // class in BTree functions 
     friend class BTree; 
    }; 

    // A BTree 
    class BTree 
    { 
     BTreeNode *root; // Pointer to root node 
     int t; // Minimum degree 
    public: 
     // Constructor (Initializes tree as empty) 
     BTree(int _t) 
     { 
      root = NULL; t = _t; 
     } 

     // function to traverse the tree 
     void traverse() 
     { 
      if (root != NULL) root->traverse(); 
     } 

     // function to search a key in this tree 
     BTreeNode* search(int k) 
     { 
      return (root == NULL) ? NULL : root->search(k); 
     } 

     // The main function that inserts a new key in this B-Tree 
     void insert(int k); 
    }; 

    // Constructor for BTreeNode class 
    BTreeNode::BTreeNode(int t1, bool leaf1) 
    { 
     // Copy the given minimum degree and leaf property 
     t = t1; 
     leaf = leaf1; 

     // Allocate memory for maximum number of possible keys 
     // and child pointers 
     keys = new int[2 * t - 1]; 
     C = new BTreeNode *[2 * t]; 

     // Initialize the number of keys as 0 
     n = 0; 
    } 

    // Function to traverse all nodes in a subtree rooted with this node 
    /*void BTreeNode::traverse() 
    { 
     // There are n keys and n+1 children, travers through n keys 
     // and first n children 
     int i; 
     for (i = 0; i < n; i++) 
     { 
      // If this is not leaf, then before printing key[i], 
      // traverse the subtree rooted with child C[i]. 
      if (leaf == false) 
      { 
       ComparisonCount++; 
       C[i]->traverse(); 
      } 
      cout << " " << keys[i]; 
     } 

     // Print the subtree rooted with last child 
     if (leaf == false) 
     { 
      ComparisonCount++; 
      C[i]->traverse(); 
     } 
    }*/ 

    // Function to search key k in subtree rooted with this node 
    BTreeNode *BTreeNode::search(int k) 
    { 
     // Find the first key greater than or equal to k 
     int i = 0; 
     while (i < n && k > keys[i]) 
      i++; 

     // If the found key is equal to k, return this node 
     if (keys[i] == k) 
     { 
      ComparisonCount++; 
      return this; 
     } 
     // If key is not found here and this is a leaf node 
     if (leaf == true) 
     { 
      ComparisonCount++; 
      return NULL; 
     } 

     // Go to the appropriate child 
     return C[i]->search(k); 
    } 

    // The main function that inserts a new key in this B-Tree 
    void BTree::insert(int k) 
    { 
     // If tree is empty 
     if (root == NULL) 
     { 
      ComparisonCount++; 
      // Allocate memory for root 
      root = new BTreeNode(t, true); 
      root->keys[0] = k; // Insert key 
      root->n = 1; // Update number of keys in root 
     } 
     else // If tree is not empty 
     { 
      // If root is full, then tree grows in height 
      if (root->n == 2 * t - 1) 
      { 
       ComparisonCount++; 
       // Allocate memory for new root 
       BTreeNode *s = new BTreeNode(t, false); 

       // Make old root as child of new root 
       s->C[0] = root; 

       // Split the old root and move 1 key to the new root 
       s->splitChild(0, root); 

       // New root has two children now. Decide which of the 
       // two children is going to have new key 
       int i = 0; 
       if (s->keys[0] < k) 
       { 
        ComparisonCount++; 
        i++; 
       }s->C[i]->insertNonFull(k); 

       // Change root 
       root = s; 
      } 
      else // If root is not full, call insertNonFull for root 
       root->insertNonFull(k); 
     } 
    } 

    // A utility function to insert a new key in this node 
    // The assumption is, the node must be non-full when this 
    // function is called 
    void BTreeNode::insertNonFull(int k) 
    { 
     // Initialize index as index of rightmost element 
     int i = n - 1; 

     // If this is a leaf node 
     if (leaf == true) 
     { 
      ComparisonCount++; 
      // The following loop does two things 
      // a) Finds the location of new key to be inserted 
      // b) Moves all greater keys to one place ahead 
      while (i >= 0 && keys[i] > k) 
      { 
       keys[i + 1] = keys[i]; 
       i--; 
      } 

      // Insert the new key at found location 
      keys[i + 1] = k; 
      n = n + 1; 
     } 
     else // If this node is not leaf 
     { 
      // Find the child which is going to have the new key 
      while (i >= 0 && keys[i] > k) 
       i--; 

      // See if the found child is full 
      if (C[i + 1]->n == 2 * t - 1) 
      { 
       ComparisonCount++; 
       // If the child is full, then split it 
       splitChild(i + 1, C[i + 1]); 

       // After split, the middle key of C[i] goes up and 
       // C[i] is splitted into two. See which of the two 
       // is going to have the new key 
       if (keys[i + 1] < k) 
        i++; 
      } 
      C[i + 1]->insertNonFull(k); 
     } 
    } 

    // A utility function to split the child y of this node 
    // Note that y must be full when this function is called 
    void BTreeNode::splitChild(int i, BTreeNode *y) 
    { 
     // Create a new node which is going to store (t-1) keys 
     // of y 
     BTreeNode *z = new BTreeNode(y->t, y->leaf); 
     z->n = t - 1; 

     // Copy the last (t-1) keys of y to z 
     for (int j = 0; j < t - 1; j++) 
      z->keys[j] = y->keys[j + t]; 

     // Copy the last t children of y to z 
     if (y->leaf == false) 
     { 
      ComparisonCount++; 
      for (int j = 0; j < t; j++) 
       z->C[j] = y->C[j + t]; 
     } 

     // Reduce the number of keys in y 
     y->n = t - 1; 

     // Since this node is going to have a new child, 
     // create space of new child 
     for (int j = n; j >= i + 1; j--) 
      C[j + 1] = C[j]; 

     // Link the new child to this node 
     C[i + 1] = z; 

     // A key of y will move to this node. Find location of 
     // new key and move all greater keys one space ahead 
     for (int j = n - 1; j >= i; j--) 
      keys[j + 1] = keys[j]; 

     // Copy the middle key of y to this node 
     keys[i] = y->keys[t - 1]; 

     // Increment count of keys in this node 
     n = n + 1; 
    } 
    void BTreeNode::traverse() 
    { 
     std::queue<BTreeNode*> queue; 
     queue.push(this); 
     while (!queue.empty()) 
     { 
      BTreeNode* current = queue.front(); 
      queue.pop(); 
      int i; 
      for (i = 0; i < n; i++) 
      { 
       if (leaf == false) 
        queue.push(current->C[i]); 
        cout << " " << current->keys[i] << endl; 
      } 
      if (leaf == false) 
       queue.push(current->C[i]); 
     } 
    } 

    // Driver program to test above functions 
    int main() 
    { 
     BTree t(4); // A B-Tree with minium degree 4 
     srand(29324); 
     for (int i = 0; i<200; i++) 
     { 
      int p = rand() % 10000; 
      t.insert(p); 
     } 

     cout << "Traversal of the constucted tree is "; 
     t.traverse(); 

     int k = 6; 
     (t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present"; 

     k = 28; 
     (t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present"; 

     cout << "There are " << ComparisonCount << " comparison." << endl; 
     system("pause"); 
     return 0; 
    } 

Answer 1

Ihr Traversal-Code verwendet die Feldwerte für this, als ob sie die Werte für die current Knoten in der Schleife waren.

Sie müssen wie diese current-> vor dem Mitglied Referenzen in der Schleife halten (in den Zeilen, die mit „// *“):

while (!queue.empty()) 
    { 
     BTreeNode* current = queue.front(); 
     queue.pop(); 
     int i; 
     for (i = 0; i < current->n; i++) //* 
     { 
      if (current->leaf == false) //* 
       queue.push(current->C[i]); 
       cout << " " << current->keys[i] << endl; 
     } 
     if (current->leaf == false) //* 
      queue.push(current->C[i]); 
    } 

Dies ist ein starker Indikator, dass alle Sachen mit current-> qualifiziert in Wirklichkeit in einer Funktion leben will, wo es this ist und daher nicht explizit benannt werden muss.

Ihr Code ist besser organisiert und angenehmer zu lesen als die meisten Debug-Anfragen, die wir hier bekommen, aber es ist immer noch ziemlich spröde und es enthält ziemlich viele stinkende Bits wie if (current->leaf == false) anstelle von if (not current->is_leaf).

Sie können es auf Code Review post, wenn Sie es in funktionierende Form haben; Ich bin mir sicher, dass die erfahrenen Programmierer, die dort herumhängen, Ihnen viele wertvolle Ratschläge geben können, wie Sie Ihren Code verbessern können.

Um Prototyping und die Entwicklung zu erleichtern würde ich folgende empfehlen dringend:

• Verwendung std::vector<> statt nackter Arrays während der Prototypenphase
• Invalidier ungültige Einträge während der Entwicklung/Prototyping (Set-Tasten auf -1 und Zeiger auf 0)
• Verwendung assert() zur Dokumentation - und Überprüfung - lokale Invarianten
• Schreibfunktionen, die die strukturellen Invarianten überprüfen genau und nennen sie vor/nach jeder Funktion, die die Struktur
• kompilieren Sie Ihren Code mit /Wall /Wextra und reinigen Sie es modifiziert, so dass es immer kompiliert ohne Warnungen

Auch, int nicht wahllos verwenden; Der Basistyp für Dinge, die nicht negativ werden können, ist unsigned (Knotengrad, aktuelle Schlüsselanzahl usw.).

P.S .: Es wäre einfacher, einen übereinstimmenden B-Baum aufzubauen, indem die Reihenfolge der Anzahl der Schlüssel festgelegt wird (d. H. Die Anzahl der Schlüssel kann für einige K zwischen K und 2 * K variieren). Das Festlegen der Reihenfolge für die Anzahl der Zeiger macht die Sache schwieriger, und eine Konsequenz ist, dass die Anzahl der Schlüssel für 'Ordnung' 2 (wo ein Knoten zwischen 2 und 4 Zeigern haben darf) zwischen 1 und 3 variieren kann. Für die meisten Leute, die sich mit B-Bäumen beschäftigen, die ein ziemlich unerwarteter Anblick sein werden!