vector <pointer>:: insert (итератор, указатель) вставка значения мусора - PullRequest
Новая
       35

vector <pointer>:: insert (итератор, указатель) вставка значения мусора

0 голосов
/ 19 октября 2019

Я пишу рекурсивную функцию для печати всех возможных перестановок ключей, которые дадут одно и то же дерево бинарного поиска.

На каждом узле я сохраняю следующие возможные узлы в векторе (т.е. удаляюузел и добавление его потомков) и рекурсивный вызов функции. Я печатаю ключи, когда больше нет узлов для добавления (я знаю, что могу использовать вектор вместо стека, но я просто изучаю векторы). 

#include<bits/stdc++.h>
#define child c
using namespace std;

typedef
struct bstnode
{
    bstnode *lc;
    int x;
    int data;
    bstnode *rc;
}* BSTPTR;

//Prints the inorder of a BST
void printIn(BSTPTR T)
{
    if(T)
    {
        printIn(T->lc);
        cout<<T->data<<' ';
        printIn(T->rc);
    }
}

//adds an element to a BST
void add(BSTPTR &T,int k)
{
    if(T)
    {
        if(k < T->data)
            add(T->lc,k);
        else
            add(T->rc,k);
    }
    else
    {
        BSTPTR t = new bstnode;
        t->data = k;
        t->lc=t->rc=NULL;
        T = t;
    }
}

//prints all the permutations in question
void printPermute(vector<BSTPTR> &LIST,BSTPTR T,stack<int> p)
{
    if(LIST.size()==0)
    {
        stack<int> q;
        int n=p.size();

        while(!p.empty())
        {
            q.push(p.top());
            p.pop();
        }
        int flag=1;
        int i=0,A[]={18,12,15,5,9,36,72,45,30};
        while(!q.empty())
        {
            int x=q.top();
            if(A[i++]!=x)
            flag=0;
            cout<<x<<' ';
            q.pop();
            p.push(x);
        }
        if(flag)
        {
            int f=9;
            f++;
        }
        cout<<endl;
    }
    else
    {
        for(auto i=LIST.begin();i<LIST.end();++i)
        {
            BSTPTR t=*i;
            p.push(t->data);

            LIST.erase(i);

            if(t->lc)
            {
                LIST.push_back(t->lc);
                if(t->rc)
                {
                    LIST.push_back(t->rc);
                    printPermute(LIST,t,p);
                    LIST.pop_back();
                }
                else
                {
                    printPermute(LIST,t,p);
                }
                LIST.pop_back();
            }
            else
            {
                if(t->rc)
                {
                    LIST.push_back(t->rc);
                    printPermute(LIST,t,p);
                    LIST.pop_back();
                }
                else
                {
                    printPermute(LIST,t,p);
                }
            }
            p.pop();
            LIST.insert(i,t);
        }
    }
}

//this is a helping function to asitis(BSTPTR) assigns the value of x for each node
void assignX(BSTPTR T,int &x)
{
    if(T)
    {
        if(T->lc == NULL)
        {
            T->x = x++;
            assignX(T->rc, x);
        }
        else
        {
            assignX(T->lc, x);
            T->x = x++;
            assignX(T->rc, x);
        }
    }
}

//prints the tree as it would look on paper. This is to give an intuitive idea of the tree's structure

void asItIs(BSTPTR T)
{
    int prev;
    assignX(T,prev=1);
    prev=0;
    queue<BSTPTR> q;
    q.push(T);
    q.push(NULL);
    while(q.size()>1)
    {
        BSTPTR t = q.front();
        q.pop();

        if(t)
        {
            for(int i=0;i<t->x-1-prev;++i)
                cout<<' ';

            cout<<t->data;
            prev = t->x;

            if(t->lc)
                q.push(t->lc);
            if(t->rc)
                q.push(t->rc);
        }
        else
        {
            cout<<endl;
            prev = 0;
            q.push(t);
        }
    }
    cout<<endl;
}


int main()
{
    BSTPTR T = NULL;
    cout<<"Enter the numbers in the tree:\n";
    int i=0,A[] = {18,12,36,5,15,30,72,9,45,-5};

    while(A[i]>=0)
    {
        add(T,A[i++]);
    }

    printIn(T);
    cout<<endl;

    asItIs(T);
    vector<BSTPTR> LIST;
    stack<int> p;
    LIST.push_back(T);
    // cout<<LIST.size();
    printPermute(LIST,T,p);
}

Так что мой код печатает все возможные перестановкиначиная с 18 12, но когда он должен вставить узел, содержащий 12 в конце цикла во второй рекурсии: 

//main::printPermute(only 1 iteration of for loop is there)::printPermute(at the end of 1st iteration out of 2 iterations
LIST.insert(i,t);

вместо вставки адреса этого узла, связывающегося с ключом 12, который хранится в t, он вставляет (я надеюсь, что это) значение мусора "ox31". Теперь это явно портит выполнение Фуртура.

Почему оно вставляет такое значение? Это более интригующе, потому что эта проблема не возникала на более высоких уровнях рекурсии (всего их 9 или 10).

1 Ответ

0 голосов
/ 19 октября 2019 
 for(auto i=LIST.begin();i<LIST.end();++i) {
   LIST.erase(i);
   LIST.insert(i,t);
   ...

Вызов erase делает недействительным итератор для удаляемого элемента, а именно i. Затем LIST.insert(i,t) демонстрирует неопределенное поведение при доступе к недействительному итератору.

Кроме того, LIST.push_back() может сделать недействительными все итераторы в списке, включая i (если он еще не был аннулирован).

Возможно, вы захотите использовать индекс, а не итератор, для итерации по списку, поскольку вы так сильно его модифицируете.

...