C++编程实例：全排列

C++编程实例：全排列

　　1、将一个n维数组初始化，第0位填1，第1位填2.。。。。。 第n-1位填n；

　　2、将数组看为两部分，一个是已排好的，剩下是待排的，分别用两个指针指向；

　　3、将第一个字符，依次与后n-1个字符交换值，每次交换得到一个新的首数字；

　　4、剩下的n-1个数字按2、3步骤重复直至所有数组完成排列；

　　使用c++实现，代码还有些繁琐，明天再仔细看看优化一下

　　代码

　　1 #include<iostream>

　　2 using namespace std;

　　3

　　4 void swap(int *p1,int *p2)

　　5 {

　　6     //交换p1和p2指向的值

　　7     int tmp=*p1;

　　8     *p1=*p2;

　　9     *p2=tmp;

　　10 }

　　11 void output(int *p,int n)

　　12 {

　　13     while(n>0)

　　14     {

　　15         cout<<*p;

　　16         p++;

　　17         n--;

　　18     }

　　19     cout<<"\n";

　　20 }

　　21

　　22 void fill(int *p1,int *p2,int len,int n)

　　23 {//p1指向已填满的部分，始终指向第一个；

　　24     //p2指向尚余下的部分，待插入那个；

　　25     //len表示已填部分的长度,n表示数组长度

　　26     if(len==n-1)

　　27         {

　　28             output(p1,n);//输出全部数组

　　29         }

　　30     else

　　31     {

　　32         int *p3,*p4;

　　33         int *pp=(int *)malloc(n*sizeof(int));

　　34         for(int i=0;i<n;i++)

　　35         {

　　36             *(pp+i)=*(p1+i);

　　37         }

　　38         p3=pp;

　　39         while(*p3!=*p2)

　　40         {

　　41             p3++;

　　42         }

　　43         p4=p3;

　　44

　　45         for(int i=0;i<n-len;i++)

　　46         {

　　47             swap(p3,p4);

　　48             p4++;

　　49             fill(pp,p3+1,len+1,n);

　　50         }

　　51     }

　　52 }

　　53

　　54 void inti(int *p,int n)

　　55 {//将数组中所有的元素全部初始化，

　　56     int num=1;

　　57     while(num<=n)

　　58     {

　　59         *p=num++;

　　60         p++;

　　61         //cout<<num<<endl;

　　62     }

　　63 }

　　64

　　65 int main()

　　66 {

　　67     int *p,n;

　　68     cout<<"请输入全排列规模：";

　　69     cin>>n;

　　70     p=(int *)malloc(n*sizeof(int));

　　71     inti(p,n);

　　72     fill(p,p,0,n);

　　73     return 0;

　　74 }