回溯法与树的遍历
回溯法:其求解过程实质是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而
是隐含在遍历过程中。
题目描述:求含n个元素的集合的幂集。
例:A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}
解题思路:求幂集的过程可看成是依次对集合A中的元素进行取或舍的过程。
选择合适的数据结构——假设以线性表表示集合。
树根结点表示幂集元素的初始状态(空集),叶子结点表示终结状态(幂集的元素),第i层表
示已对前i-1个元素进行了取舍的当前状态
编码:
#include "stdafx.h"
#include< iostream.h>
#define N 10
typedef struct
{
int data[N];
int length;
}SqList;
//输出线性表B
void Output(SqList& B)
{
int i;
if(B.length ==0)
cout<<"空集\n";
else
{
for(i=0;i<B.length ;i++)
cout<<B.data [i]<<"\t";
cout<<endl;
}
}
//求集合A的幂集,其中B为暂存幂集元素的线性表,i表示从第i个元素开始取舍,当
//i>n时则求得幂集的一个元素,并输出
void GetPowerSet(int i,SqList A,SqList& B)
{
int x,k,j;
if(i>=A.length )
Output(B);
else
{
x=A.data [i];
k=B.length ;
B.data [k]=x;
B.length ++;
GetPowerSet(i+1,A,B);
B.length --;
GetPowerSet(i+1,A,B);
}
}
A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}
int main(int argc, char* argv[])
{
SqList A,B;
int i;
cout<<"输入A集合的元素个数\n";
cin>>A.length ;
cout<<"输入A集合的元素\n";
for(i=0;i
cin>>A.data [i];
B.length =0;
GetPowerSet(0,A,B);
return 0;
}
我不解的是第一次执行完output函数后该怎么办,如果继续执行下面的语句,即b.length--和递归函数,那第二次输出的集合显然与答案不符,求大神指点,我记得老师说过还有什么出栈的过程,求指导