|
摘 要栈是一种非常重要的数据结构递归函数调用都离不开栈对n个元素入栈和出栈的研究是栈的一个主要研究内容利用二叉树给出了入栈和出栈序列的表示给出了由前置栈序列构造出二叉树的算法证明了对于按次序入栈的n个元素其出栈序列总数为C（nn)／(n+)对三种求解出栈序列算法进行了分析和研究并提出一种时间复杂度为O( n)判断某一序列是否为出栈序列的算法它提高了程序的执行效率 关键词出栈序列Catalan数二叉树 中图分类号TP． 文献标识码A 文章编号X( )
引 言 已知集合N ={…n}如果按给定的次序…n依次人栈出栈的序列共有多少种?如何给出全部的解?如何判断某一序列是否为出栈序列?对于这几个问题文献[～] 对其进行了分析和研究在此基础上提出一种用二叉树来表示人栈和出栈序列求得出栈序列总数以及利用栈的性质判断某一序列是否为出栈序列还给出一种比文献[]所提算法执行时间更短的程序
出栈序列的总数 由文献 [ ～ ] 可知出栈序列总共有C(nn)／(n+)种它是一个Catalan数文献[]利用n×n的矩形方格 设其左下角坐标为( )右上角坐标为(nn)求从() 到(nn)的路径数要求中途所经过的点(ab)满足a≤ b且仅能向右和向上行走文献[]利用在出栈序列的位置结合Catalan性质而求出文献[]证明了前序序列为…n的二叉树其中序序列即为出栈序列再由二叉树的性质求出栈序列总数 [] [] [] [] [] [] [] [] |
