1， 若入栈的元素为n,则可得到的输出序列数量为 (2n)!/(n+1)(n!)(n!)。
2， 用两个长度相同的栈S1,S2构造一个队列。在S1中进行入队操作，S2中进行出队操作 ，判断队列空的条件是，S1和S2同时为空，判断队列满的条件是S1和S2同时为满。
void EnQueue(ElemType x)
{
if(!Full(S1))
{//S1未满直接进入
S1.Push(x);
}
else
{
if(Empty(S2)==true)
{
while(!Empty(S1))
{
S2.Push(S1.Pop());
}
S1.Push(x);
}
}
}
ElemType DeQueue()
{
if(!Empty(S2))
{
return S2.Pop();
}
else
{
if(!Empty(S1))
{
while(!Empty(S1))
{
S2.Push(S1.Pop());
}
return S2.Pop();
}
}
}
3.求两个正整数的最大公约数的非递归算法。
#define MAX 100
struct Stack
{
int s;
int t;
};
int gcd(int m,int n)
{
int k;
Stack S[MAX];
int top = -1,tmp;
if(m<n)
{
tmp = m;
m = n;
n = tmp;
}
top++;
S[top].s = m;
S[top].t = n;
while(top>=0&&S[top].t!=0)
{
if(S[top].t!=0)
{
tmp = S[top].s;
m = S[top].t;
n = m%tmp;
top++;
S[top].s = m;
S[top].t = n;
}
}
return S[top].s;
}
4．
n+1,m =0
Akm(m,n) = Akm(m-1,1) m!=0,n=0
Akm(m-1,Akm(m,n-1)),m!=0,n!=0
写非递归算法。
#define MAXSIZE 100
typedef struct
{
int tm;
int tn;
}Stack;
int akm(int m,int n)
{
Stack S[MAXSIZE];
int top = 0;
S[top].tm = m;
S[top].tn = n;
do
{
while(S[top].tm!=0)
{
while(S[top].tn!=0)
{
top++;
S[top].tm = S[top-1].tm;
S[top].tn = S[top-1].tn-1;
}
S[top].tm--;
S[top].tn=1;
}
if(top>0)
{
top--;
S[top].tm--;
S[top].tn = S[top].tn+1;
}
}while(top!=0 || S[top].tm!=0);
top--;
return S[top+1].tn+1;
}
5．写出和下列递归过程等价的非递归过程
void test(int &sum)
{
int k;
scanf("%d",&k);
if(k==0) sum = 1;
else
{
test(sum);
sum = k*sum;
}
printf("%d",sum);
}
分析：程序功能是按照输入的整数，按相反顺序进行累计乘法运算
#define MAXSIZE 100
void test(int &sum)
{
int Stack[MAXSIZE];
int top = -1,k;
sum = 1;
scanf("%d",&k);
while(k!=0)
{
Stack[++top] = k;
scanf("%d",&k);
}
printf("%d",sum);
while(top!=-1)
{
sum *=Stack[top--];
printf("%d",sum);
}
}
6．假设表达式由单字母变量和双目四则运算算符构成，写一个算法，将一个书写正确的表达式转换为逆波兰式。
void ConPoland(char express[],char suffix[])
{
char *p = express,ch1 = *p,ch2;
int k = 0;
InitStack(S);
Push(S,'#');
while(!StackEmpty(S))
{
if(!IsOperator(ch1))
suffix[k++] = ch1;
else
{
switch(ch1)
{
case '(':
Push(S,ch1);break;
case ')':
Pop(S,ch2);
while(ch2!='(')
{
suffix[k++] = ch2;
Pop(S,ch2);
}
break;
default:
while(GetTop(S,ch2)&&precede(ch2,ch1))
{
suffix[k++] = ch2;
Pop(S,ch2);
}
if(ch1!='#')
Push(S,ch1);
break;
}
}
if(ch1!="#')
ch1 = *++p;
}
suffix[k] = '\0';
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2006/09/10/500208.html，如需转载请自行联系原作者
