{ //返回栈顶元素的值 

  if(IsEmpty()==true) return false; //若栈空则返回 false 

      x=top->data;//栈不空则返回栈顶元素的值 

  return true; 

}

利用栈非递归算法设计

#include<iostream。h>

#include"LinkedStack。h"

int ack(int m,int n)

{

LinkedStack<int> s;

          s。Push(-1);//设置-1为栈中元素的终结点

          do//计算akm(m,n)直至akm(0,n)

       {

          while(m>0)//计算akm(m,n)直至akm(0,1)

       {

       while(n>0)//计算akm(m,n)直至akm(m,0)。

    {

       s。Push(m-1);//将akm(m,n)的前元素m压入栈顶。

               n--;   

    }

       n=1;

       m--;  

       }

          if(m==0) 

       {

n=n+1; 

       s。getTop(m); //取出栈顶元素，赋值给m。

       s。Pop(m);//删除栈顶元素。文献综述

       }

       }while(m!=-1);

            return n;

}

void main()

{

 int m,n;

 cout<<"请输入m的值：m=";

cin>>m;

cout<<"请输入n的值：n=";

cin>>n;

cout<<"警告：不能太大否则系统崩溃！"<<endl;

             cout<<"ack(m,n)的值为："<<ack(m,n)<<endl;

}

为了使问题的研究与讨论更具体，我对问题的规模作了如下假设。设m=1,n=2，

运行结果：

采用非递归的算法时，如果输入的数据使运算过大，则导致无法适时运算出结果，例如m=5,n=6时，

运行结果：

2。2  阿克曼函数

阿克曼函数[12]是数学中的经典问题，是非原始递归函数的例子。已知其函数定义如下：

现要求：

      (1) 根据定义，写出它的递归求解算法；

           (2) 利用栈，写出它的非递归求解算法。

阿克曼函数（Ackerman）是非原始递归函数的例子；它需要两个自然数作为输入值，输出一个自然数。然后，就是递归转非递归的标准流程：

(1) 从一个简单的实例，分析其递归调用树； 来,自.优;尔:论[文|网www.chuibin.com +QQ752018766-

(2) 分析哪些元素需要放在栈中；

(3) 跟踪递归调用过程，分析栈的变化；

(4) 由实例到普通，演绎出算法，这一过程也称作建模。

下面，我们就以akm(2,1)为例，开始分析递归调用树，采用一个栈记忆每次递归调用时的实参值，每个结点两个域。对以上实例，递归树以及栈的变化如下：