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

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

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

?

中圖分類號(hào)：TP311．12????? 文獻(xiàn)標(biāo)識(shí)碼：A????? 文章編號(hào)：1673-629X( 2007 )10-0127-03?

?

0 引 言

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

?

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

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