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

2 出棧序列的求解算法

文獻(xiàn)[2]給出兩種算法，第一種是傳統(tǒng)的解法，簡稱算法1，其實(shí)現(xiàn)思想描述如下：?

1) 求1,2,3,…,n的一個全排列ala2a3…an；?

2) 判斷ala2a3…an是否為出棧序列，若是則輸出；?

3) 若所有全排列已求出，則結(jié)束；否則，轉(zhuǎn)(1)。?

該算法時間復(fù)雜度為O(n!)。?

文獻(xiàn)[2]給出的第二種算法，簡稱算法2，實(shí)現(xiàn)思想描述如下：?

(1) 若n=1，則寫下唯一的出棧序列；?

(2) 遞歸調(diào)用該算法求出1作為第k個出棧元素的所有出棧序列。

該算法時間復(fù)雜度是O(C(2n,n)／(1+n) )，但該算法在實(shí)現(xiàn)時，對產(chǎn)生的每一個出棧序列都要與已有的出棧序列進(jìn)行對比，看是否重復(fù)，然后決定是否將新的出棧序列加入到已有的出棧序列中。這種查找工作使程序的實(shí)際運(yùn)行時間增長。?

文獻(xiàn)[4]給出一種更好的算法，簡稱算法3，具體算法描述如下：?

① 若n=1，則寫下唯一的棧排列1；?

② 否則，遞歸調(diào)用該算法生成1,2,3,…,n-1的所有不同的棧排列，然后生成1,2,…,n的所有不同的棧排列，方法是：對于1,2,…,n -1的每一個棧排列，分別將n插入n-1之前，n-1之后，使n與n-1相鄰，以及排在n-1后的每一個數(shù)之后，即可得到1,2,3,…,n-1的棧排列。

該算法利用了棧的性質(zhì)[4]：已知集合N={1,2,3,…,n}，如果按給定的次序1,2,3,…,n依次入棧， 則在出棧序列中，對于任何i ∈N和j∈N( j > i ) ，若排在i之前(i左邊)，要么j與i相鄰， 要么j與i之間所排的任一數(shù)均大于i。