2011考研考研備考數(shù)據(jù)結(jié)構(gòu)之出棧序列的研究[5]_跨考網(wǎng)

該算法雖然直觀有效，但沒有給出具體的實現(xiàn)。為了比較三種算法的優(yōu)劣，文中基于該算法思想給出了具體的實現(xiàn)，源程序如下：

char sz[60000][12]; //存儲出棧序列

int used; //出棧序列總數(shù)

void stack_out (char s)?

{char buff[15],ch,step[15],*p,*ql,*q2;?

int len,i,j,num1,num2,num;?

strcpy (buff,s);?

len strlen(buff);?

if(len>1)?

{ch=buff [len-1];?

buff [1en-1]=0;?

stack_out(buff);?

num2=used*(1en<<1)*( (1en <<1)-1 )／len／(1en+1); //當(dāng)n=len時的出棧序列數(shù)

numl=num2;?

for(i=used-1;i >=0;i-- ) //在n-l的基礎(chǔ)上求出n的所有出棧序列

{strcpy(step,sz[i]);?

p=strchr(step,buff[1en-2]);?

for(num=0,j=num2-1;j>=0;j--)?

{ql=sz[j];q2=step;

while(*q2!=p )*q1++=*q2++;?

*q1++=ch;?

while(*q2!=0 )*q1++=*q2++;?

*ql=0;num++;?

if(*p++=NULL) break;?

}?

num2--=numl;?

}?

used=numl;?

}?

else?

{sz[0][0]=buff[0];sz[0][1]=0;?

used=1; //當(dāng)n =0時，出棧序列數(shù)為 1?

}?

}