我正在尝试编写一个程序,按字典顺序输出数字字符串的下一个排列,但出现内存错误:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted
我以前从未遇到过这个问题,有什么想法吗?这是完整的程序:
#include<iostream>
#include<vector>
using namespace std;
vector<char> Next_Permutation(vector<char> InList);
void Reverse_Tail(vector<char>& List,int k);
vector<char> Swap(vector<char> InputList,int k, int l);
vector<char> GetInput();
int Find_K(vector<char> List);
int Find_l(vector<char> List,int k);
int Factorial(int n);
int main(){
vector<char> Input = GetInput();//Getting initial input use 1234 for test
int limit = Factorial(Input.size()); // finds how many permutations will be made
vector<char>* AllPerms = new vector<char>[limit]; //AllPerms is the collection of all permutations(it is an array of vectors where each vector is a permutation)
AllPerms[0] = Input; //setting intial permutation;
for(int i=1;i<2;i++){
// here is where i believe the program crashes. I've tried test = Next_Permutation(AllPerms[i-1]) then
// doing AllPerms[i] = Test and the program runs through the first line fine but crashed on AllPerms[i] = Test?
AllPerms[i] = (Next_Permutation(AllPerms[i-1]));
}
for(int j=0; j < limit;j++){
for(int i=0;i<AllPerms[j].size();i++){
cout << AllPerms[j][i] << " " ;
}
cout << endl;
}
//cout << endl << "K = " << K << endl<< "l = " << l << endl<< endl;
cout << endl<< endl;
return 0;
}
int Factorial(int n){
if(n==0)
return 1;
else
return n*Factorial(n-1);
}
vector<char> Next_Permutation(vector<char> InList){
int K = Find_K(InList);
int l = Find_l(InList,K);
vector<char> Output = Swap(InList,K,l);
Reverse_Tail(Output,K);
}
void Reverse_Tail(vector<char>& List,int k){
int i = k+1;
int lim = (List.size() - i)/2;
int len = List.size()-1;
while(i < (List.size() - lim -1)){
List = Swap(List,i,len);
len--;
i++;
}
}
vector<char> Swap(vector<char> InputList,int k, int l){
vector<char> OutList = InputList;
int Temp = OutList[l];
OutList[l] = InputList[k];
OutList[k] = Temp;
return OutList;
}
int Find_l(vector<char> List,int k){
int l=List.size()-1;
while(List[l] < List[k]){
l--;
}
return l;
}
int Find_K(vector<char> List){
int k = List.size()-2;
while(List[k] > List[k+1]){
k--;
}
if(k == List.size()-1){
return -1;
}
return k;
}
vector<char> GetInput(){
vector<char> InputString;
cout << "Please input the string of symbols you would like to gain all permutations of: ";
char temp = 0 ;
while( temp != '\n' ){
cin.get(temp);
InputString.push_back(temp);
}
InputString.pop_back();
return InputString;
}
最佳答案
您不会从 Next_Permutation
返回值。未能从除 main
之外的任何函数返回值会调用未定义的行为,在这种情况下编译器和程序可以自由地做任何他们喜欢的事情。我的 Solaris 编译器拒绝接受该程序,而我的 Linux 编译器编译该程序,但随后程序崩溃,因为 free
在某个时刻检测到无效指针。两者都是处理未定义事物的有效方法。
当你有未定义的行为时,花很多精力去弄清楚为什么你的程序表现异常通常是不明智的,因为无论你看到什么都不一定能被其他人重现,甚至可能不能被 你。确保您有一个有效的程序,然后开始调试。尽管您可能会合法地用完内存,但更有可能是在尝试复制一开始甚至不是有效对象的内容时抛出异常。
您的编译器可能会提供一些诊断信息,但您可能必须在运行时请求它们。如果您使用的是 g++,请确保包含 -Wall
选项,它会启用“所有”警告。 (有一些模糊的未启用,但您通常不需要担心它们。)
关于c++ - 内存问题,不知道为什么。什么():std::bad_alloc,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7273854/