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

摘 要：棧是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，遞歸、函數(shù)調(diào)用都離不開棧。對n個元素入棧和出棧的研究是棧的一個主要研究內(nèi)容。利用二叉樹給出了入棧和出棧序列的表示；給出了由前置0棧序列構(gòu)造出二叉樹的算法；證明了對于按次序入棧的n個元素，其出棧序列總數(shù)為C（2n,n)／(n+1)；對三種求解出棧序列算法進行了分析和研究，并提出一種時間復雜度為O( n)判斷某一序列是否為出棧序列的算法，它提高了程序的執(zhí)行效率。

關(guān)鍵詞：出棧序列；Catalan數(shù)；二叉樹

?

中圖分類號：TP311．12????? 文獻標識碼：A????? 文章編號：1673-629X( 2007 )10-0127-03?

?

0 引 言

已知集合N ={1,2,3,…,n}，如果按給定的次序1,2,3,…,n依次人棧，出棧的序列共有多少種?如何給出全部的解?如何判斷某一序列是否為出棧序列?對于這幾個問題，文獻[1～5] 對其進行了分析和研究。在此基礎(chǔ)上，提出一種用二叉樹來表示人棧和出棧序列，求得出棧序列總數(shù)，以及利用棧的性質(zhì)判斷某一序列是否為出棧序列，還給出一種比文獻[2]所提算法執(zhí)行時間更短的程序。

?

1 出棧序列的總數(shù)

??? 由文獻 [1 ～3 ] 可知，出棧序列總共有C(2n,n)／(n+1)種，它是一個Catalan數(shù)。文獻[1]利用n×n的矩形方格， 設(shè)其左下角坐標為(0,0 )，右上角坐標為(n,n)，求從(0,0) 到(n,n)的路徑數(shù)，要求中途所經(jīng)過的點(a,b)，滿足a≤ b，且僅能向右和向上行走；文獻[2]利用1在出棧序列的位置結(jié)合Catalan性質(zhì)而求出；文獻[3]證明了前序序列為1,2,3,…,n的二叉樹，其中序序列即為出棧序列，再由二叉樹的性質(zhì)求出棧序列總數(shù)。