考察DFS的應用，用棧描述字符串的變化過程。
1 #include <stdio.h>
2 #include <string.h>
3 int len1,len2;
4 char str1[100],str2[100],stk[100],ans[200];
5
6 void output(int n){
7 int i;
8 for(i=0;i<n;i++){
9 printf("%c ",ans[i]);
10 }
11 printf("\n");
12 }
13
14 void go(int in,int out,int p,int top){
15 if(top<0)
16 return;
17 if(in==len1 && out==len2){
18 output(p);
19 return;
20 }
21 if(in<len1){
22 stk[top]=str1[in];
23 ans[p]='i';
24 go(in+1,out,p+1,top+1);
25 }
26 if(top>0 && out<len2 && stk[top-1]==str2[out]){
27 ans[p]='o';
28 go(in,out+1,p+1,top-1);
29 stk[top-1]=str2[out];
30 }
31 }
32
33 int main(){
34 while(scanf("%s%s",str1,str2)>=0){
35 len1=strlen(str1);
36 len2=strlen(str2);
37 printf("[\n");
38 if(len1==len2)
39 go(0,0,0,0);
40 printf("]\n");
41 }
42 return 0;
43 }
#include "stdio.h"
#include "string.h"
char sequence[200] ;
int lens , sp = 99 , rsp = 0 ;
char source[100] , target[100] , result[100] , stack[100];
//sequence[]記錄結果
//lens單詞長度
//sp棧頂
//rsp輸出到result[]的位置
//result[]io操作後的的結果，與target[]比較
void clean()
{
int i ;
for (i = 0 ; i< 200 ; i++)
{
sequence[i] = '\0' ;
}
for(i = 0 ; i < 100 ; i++)
{
source[i] = target[i] = '\0' ;
}
}
void cleanstack()
{
int i = 0 ;
for( i = 0 ;i < 100 ; i++)
{
result[i] = stack[i] = '\0' ;
}
sp = 99 ;
rsp = 0 ;
}
int judge( )//判斷對棧的操作是否合法
{
int counti , counto ;
int i , j ;
counti = counto = 0 ;
for( j = 0 ; j < lens *2 + 1 ; j++)
{
for( i = counti = counto = 0; i < j ; i++)
{
if( 'i' == sequence[i] )
{
counti++ ;
}
else
{
counto++ ;
}
}
if(counto > counti || counto > lens ||counti > lens)
{
return 0 ;
}
}
return 1 ;
}
void push( char ch)
{
stack[sp] = ch ;
sp-- ;
}
void pop()
{
sp++ ;
result[rsp] = stack[sp] ;
rsp++ ;
}
int check()//驗算io操作後的結果是否與target一致
{
int i = 0 ,ssp = 0;
while( i < lens *2)
{
if (sequence[i] == 'i')
{
push(source[ssp]) ;
ssp++ ;
}
else
{
pop() ;
}
i++ ;
}
for(i = 0 ; i < lens ; i++)
{
if ( result[i] != target[i])
{
cleanstack() ;
return 0 ;
}
}
cleanstack() ;
return 1 ;
}
void output(int step )......余下全文>>
根據原文的意思應該是計算機中字母反序輸出的編程
