向量<pointer>：插入(迭代器，指针)插入垃圾值

Question

我正在编写一个递归函数来打印所有可能的键排列，这将给出相同的二叉搜索树。

在每个节点上，我将下一个可能的节点存储在向量中(即删除该节点并添加其子节点(并递归调用该函数。 一旦没有更多的节点要添加，我就会打印密钥(我知道我可以使用向量而不是堆栈，但我只是在学习向量(。

#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);

它不是插入包含存储在 t 中的键 12 的节点的地址，而是插入(我希望是(垃圾值"ox31"。现在这显然搞砸了进一步的执行。

为什么要插入这样的值？这更有趣，因为这个问题没有发生在更高级别的递归中(总共有大约 9 或 10 个级别(。

Answer 1

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(如果它尚未失效(。

您可能希望使用索引而不是迭代器来迭代列表，因为您正在对其进行大量修改。