主题：全排列的非递归实现
lt19870917
[专家分：750] 发布于 2007-04-28 16:59:00
发现这个算法不简单啊,通过观察递归栈还是不容易写.
递归算法为:
#include <stdio.h>
#include <stdlib.h>
void f(int a[],int n,int i);
int main(){
int a[5]={1,2,3,4,5};
f(a,5,0);
system("pause");
return 0;
}
void f(int a[],int n,int i){
int k;
static int count=0;
int temp;
if(i==n-1){
for(k=0;k<n;k++){
printf("%d ",a[k]);
}
count++;
printf("\n");
return;
}
for(k=i;k<n;k++){
temp=a[i];
a[i]=a[k];
a[k]=temp;
f(a,n,i+1);
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
if(i==0){
printf("\n\nHas %d",count);
}
}
回复列表 （共6个回复）
沙发
lt19870917 [专家分：750] 发布于 2007-04-28 17:24:00
递归转非递归不是都很容易的,这个就不简单啊
板凳
pink_robin [专家分：30] 发布于 2007-04-29 23:08:00
楼主太厉害了,这个问题我以前想了好久都没解决,佩服呀!!!
3 楼
Czhxdong [专家分：510] 发布于 2007-04-30 16:56:00
还是好递归变形....
4 楼
goal00001111 [专家分：4030] 发布于 2007-04-30 19:02:00
这不就是递归吗?怎么非递归了?真奇怪!
5 楼
bpttc [专家分：8790] 发布于 2007-04-30 19:08:00
//函数原型 void FullArrangement( char* str, void (* visit)( const char* ) );
//函数参数 字符串str中没有重复的字符
//函数功能 visit遍历str中所有字符形成的全排列
#define NULL ( 0 )
#define MAX_STR_NUM ( 20 ) //字符串最大长度
#define SwapChar( X, Y ) { char temp = X; X = Y; Y = temp; }
void FullArrangement( char* str, void (* visit)( const char* ) )
{
char* stack[MAX_STR_NUM];
int top = 0;
char* p = str;
if ( NULL == str )
{
return;
}
while ( '\0' != *p || top > 0 )
{
if ( '\0' != *p )
{
SwapChar( *p, str[top] );
stack[top++] = p; //将要作为首字符的位置入栈
p = str + top; //重新定位p为待排列首位置
}
else
{
if ( '\0' == str[top] )
{
(* visit)( str );
}
p = stack[--top];
SwapChar( *p, str[top] );
++p;
}
}
return;
}
6 楼
bpttc [专家分：8790] 发布于 2007-04-30 20:34:00
翻了翻老底 上面是我以前写过的 有一些错误 重新修改了一下
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Permutation( const char* s )
{
if ( NULL == s )
{
return;
}
int len = strlen( s ) + 1;
char* str = ( char* )malloc( len * sizeof( char ) );
typedef char* StackElem;
StackElem* stack = ( StackElem* )malloc( len * sizeof( StackElem ) );
StackElem* top = stack;
char* head = str;
char* p = str;
char temp;
strcpy( str, s );
while ( '\0' != *p || top != stack )
{
while ( '\0' != *p )
{
temp = *p;
*p = *head;
*head = temp;
*top++ = p;
p = ++head;
}
if ( '\0' == *head )
{
puts( str );
}
p = *--top;
temp = *--head;
*head = *p;
*p++ = temp;
}
free( str );
free( stack );
return;
}
int main()
{
Permutation( "ABCD" );
system( "pause" );
return 0;
}
我来回复
您所在位置：