Почему код дает ошибку сегментации на входах больше 10? - PullRequest
0 голосов
/ 11 мая 2019

Я строю дерево AVL. Когда я даю ввод ниже 10, он работает нормально. но когда я даю больше 10, то коды ломаются и говорят ошибки сегментации и дают неправильный вывод. Это для моего школьного задания.

Ввод этого формата;

D13 D60 D76 D12 A17 D98 A94 D70 D3 A23 A42 D45 A100 D50 A99 A22 A87 A4
A90 D88 A71 A20 D39 D83 A97 A56 D28 A9 D43 A19 D5 A11 A54 A73 D54 A9 A24 A58 D6 D80 A72 A47 A82 A12 A75 D77 D84 D86 A60 D64 D70 D70 A73 A71 A40 D94 D27 A63 D47 A42 A44 A27 A100 A6 D84 A19 D65 A75 A55 A63 A39 D99 A50 D98 A98 D100 D93 A91 A81 D59 D56 D29 D11 D45 D47 D55 D85 D7 D70 A13 A55 A25 D35 D65 A48 D55 A45 D29 A35 A15 IN

и вывод выглядит так:

4 6 9 12 13 15 17 19 20 22 23 24 25 27 35 39 40 42 44 45 48 50 58
60 63 71 72 73 75 81 82 87 90 91 97 98
    #include <iostream>
    #include <string>
    using namespace std;

    /* First we are going to design structure for Nodes. */

    struct Node {
    Node* l = NULL; //r of the node
    Node* r = NULL; //l of the node
    int h = 0; //Height of the node
    int d = 0; //Data Part of the node
    };


    Node* getNode(int d){
      Node* node = new Node();
      node->d = d;
      node->l = NULL;
      node->r = NULL;
      node->h = 1;
      return (node);
    }

    int getH(Node* n) { //Getting the Height of Tree
    if (n == NULL)
        return 0;
    return n->h;
    }

    int getBlnc(Node* n){

    if (n == NULL)
        return 0;
    else {
        return getH(n->l) - getH(n->r);
    }
      }

    int havMaxValue(int j, int k){

    if (j > k)
        return j;
    return k;
    }

    /* AVL Rotatations */


    Node* rR(Node* temNode) //Right Rotation{

    Node* x = temNode->l;

    x->r = temNode;
    temNode->l = x->r;

    temNode->h = havMaxValue(getH(temNode->l), getH(temNode->r)) + 1;
    x->h = havMaxValue(getH(x->l), getH(x->r)) + 1;

    return x;
      }

    Node* lR(Node* TempNode) //LeftRotate
    {
    Node* tempNode2 = TempNode->r;
    Node* TemNode1 = tempNode2->l;

    tempNode2->l = TempNode;
    TempNode->r = TemNode1;

    TempNode->h = (havMaxValue(getH(TempNode->l), getH(TempNode->r)) + 1);
    tempNode2->h = (havMaxValue(getH(tempNode2->l), getH(tempNode2->r)) + 1);
    return tempNode2;
    }

    Node* inNode(Node* tempNode, int value) //Insert New Node
    {

    if (tempNode == NULL)
        return (getNode(value));

    if (value < tempNode->d)
        tempNode->l = inNode(tempNode->l, value);
    else if (value > tempNode->d)
        tempNode->r = inNode(tempNode->r, value);
    else
        return tempNode;

    tempNode->h = 1 + havMaxValue(getH(tempNode->l), getH(tempNode->r));

    int blnc = getBlnc(tempNode); //Balance Variable

    if (blnc > 1 && value < tempNode->l->d)
        return rR(tempNode);

    if (blnc < -1 && value > tempNode->r->d)
        return lR(tempNode);

    if (blnc > 1 && value > tempNode->l->d) {
        tempNode->l = lR(tempNode->l);
        return rR(tempNode);
    }

    if (blnc < -1 && value < tempNode->r->d) {
        tempNode->r = rR(tempNode->r);
        return lR(tempNode);
    }

    return tempNode;
    }

    /* Deletion */

    Node* nodeHavingMinVal(Node* temp) //Mininum Value Node
    {
    Node* tempNode = temp;
    while (tempNode->l != NULL)
        tempNode = tempNode->l;

    return tempNode;
    }

    Node* extractNode(Node* tempNode, int key) //DeleteNode
    {

    if (tempNode == NULL)
        return tempNode;

    if (key < tempNode->d)
        tempNode->l = extractNode(tempNode->l, key);

    else if (key > tempNode->d)
        tempNode->r = extractNode(tempNode->r, key);

    else {
        if ((tempNode->l == NULL) || (tempNode->r == NULL)) {
            Node* TempNode = tempNode->l ? tempNode->l : tempNode->r;

            if (TempNode == NULL) {
                TempNode = tempNode;
                tempNode = NULL;
            }
            else
                *tempNode = *TempNode;
        }
        else {
            Node* TempNode = nodeHavingMinVal(tempNode->r);
            tempNode->d = TempNode->d;
            tempNode->r = extractNode(tempNode->r, TempNode->d);
        }
    }

    if (tempNode == NULL)
        return tempNode;

    tempNode->h = 1 + max(getH(tempNode->l), getH(tempNode->r));

    int blnc = getBlnc(tempNode);

    if (blnc > 1 && getBlnc(tempNode->l) >= 0)
        return rR(tempNode);

    if (blnc > 1 && getBlnc(tempNode->l) < 0) {
        tempNode->l = lR(tempNode->l);
        return rR(tempNode);
    }

    if (blnc < -1 && getBlnc(tempNode->r) <= 0)
        return lR(tempNode);

    if (blnc < -1 && getBlnc(tempNode->r) > 0) {
        tempNode->r = rR(tempNode->r);
        return lR(tempNode);
    }

    return tempNode;
    }

    /* Graph Traversal */

    void POST(Node* node)
    {
    if (node == NULL)
        return;

    POST(node->l);
    POST(node->r);

    cout << node->d << " ";
    }

    void IN(Node* node)
    {
    if (node == NULL)
        return;

    IN(node->l);
    cout << node->d << " ";
    IN(node->r);
    }

    void PRE(Node* node)
    {
    if (node == NULL)
        return;

    cout << node->d << " ";

    PRE(node->l);
    PRE(node->r);
    }

    int main()
    {
    Node* root = NULL;
    char ch[5];
    int num;
    int i = 1;

    top:
       for (; i > 0;) {

        cin >> ch[0];

        if (ch[0] == 'A') {
            int num;
            cin >> num;
            root = inNode(root, num);
            goto top;
        }

        if (ch[0] == 'D') {
            int num;
            cin >> num;
            root = extractNode(root, num); //Delete Node
            if (root == NULL) {
                cout << "EMPTY";
                break;
            }
            goto top;
        }

        cin >> ch[1];
        if (ch[0] == 'I' and ch[1] == 'N') {
            IN(root);
            break;
        }

          cin >> ch[2];
          if (ch[0] == 'P' and ch[1] == 'R' and ch[2] == 'E') {
            PRE(root);
            break;
        }

        cin >> ch[3];
        if (ch[0] == 'P' and ch[1] == 'O' and ch[2] == 'S' and ch[3] == 'T') 
        {
            POST(root);
            break;
        }
    }

    return 0;
    }

1 Ответ

2 голосов
/ 11 мая 2019

Ваше дерево становится недействительным, что приводит к extractNode, вызывающему себя неограниченное количество раз и вызывающему переполнение стека. Самый простой способ проверить, где все идет не так, как надо, - написать функцию для обхода всего дерева и вызывать ее (с ведением журнала) после каждой модификации. Последняя модификация перед segfault - это проблема.

Вы можете подтвердить это, изменив свой код следующим образом:

Node* extractNode(Node* tempNode, int key, int depth) //DeleteNode
{
if (depth > 10)
    printf("depth=%d\n", depth);

if (tempNode == NULL)
    return tempNode;

if (key < tempNode->d)
    tempNode->l = extractNode(tempNode->l, key, depth + 1);

else if (key > tempNode->d)
    tempNode->r = extractNode(tempNode->r, key, depth + 1);

else {
    if ((tempNode->l == NULL) || (tempNode->r == NULL)) {
        Node* TempNode = tempNode->l ? tempNode->l : tempNode->r

И так далее. Первоначально назовите это с глубиной ноля. Вы увидите, что глубина быстро увеличивается, а затем стек переполняется.

глубина = 11
Глубина = 12
Глубина = 13
<< <strong>много много строк >>
глубина = 104724
глубина = 104725
глубина = 104726
глубина = 104727
глубина = 104728
Глубина = 104729
глубина = 104730
глубина = 104731
глубина = 104732
глубина = 104733
глубина = 104734
Ошибка сегментации

...