[1]李红卫 徐亚平.出栈序列的研究[J].计算机技术与发展,2007,(10):127-129.
LI Hong-wei,XU Ya-ping.Study of Out- Stack Sequence[J].,2007,(10):127-129.
点击复制
出栈序列的研究(
)
《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]
- 卷:
-
- 期数:
-
2007年10期
- 页码:
-
127-129
- 栏目:
-
智能、算法、系统工程
- 出版日期:
-
1900-01-01
文章信息/Info
- Title:
-
Study of Out- Stack Sequence
- 文章编号:
-
1673-629X（2007）10-0127-03
- 作者:
-
李红卫 徐亚平
-
江苏技术师范学院计算机科学与工程学院
- Author(s):
-
LI Hong-wei; XU Ya-ping
-
School of Computer Science and Engineering,Jiangsu Teachers University of Technology
-
- 关键词:
-
出栈序列; Catalan数; 二叉树
- Keywords:
-
out - stack sequence; Catalan number; binary tree
- 分类号:
-
TP311.12
- 文献标志码:
-
A
- 摘要:
-
栈是一种非常重要的数据结构，递归、函数调用都离不开栈。对n个元素人栈和出栈的研究是栈的一个主要研究内容。利用二叉树给出了人栈和出栈序列的表示；给出了由前置O栈序列构造出二叉树的算法；证明了对于按次序人栈的n个元素，其出栈序列总数为C（2n,n）／（n＋1）；对三种求解出栈序列算法进行了分析和研究，并提出一种时间复杂度为O（n）判断某一序列是否为出栈序列的算法，它提高了程序的执行效率
- Abstract:
-
Stack is a very important data structure. Recttrsion and function call cannot get away the stack. Research of the instack and the out - stack of n elements is a main content of stack. Expresses the in- stack and the out - stack sequence with binary tree, gives an algorithm＇to create a binary tree by pre - O stack sequence, proves that the number of out - stack sequence is C （2 n,n ）/（ n ＋ 1 ）when n elements put in the stack in order, analyzes and studies the three algorithms about solutions of out - stack sequence, and presents an algorithm, its time complexity is O（n） , that judges whether some sequence is out - stack sequence. Execution efficiency of the program is improved by the algorithm
备注/Memo
- 备注/Memo:
-
江苏省高校自然科学研究项目（06KJD520052）;江苏技术师范学院数据结构重点课程建设资助项目李红卫（1966-），男，山西阳城人，硕士，副教授，主要研究方向为算法、嵌入式软件系统
更新日期/Last Update:
1900-01-01