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

3 判斷一個序列是否為出棧序列

隨著n的變大，出棧序列總數(shù)越來越多，由文獻(xiàn)[1]和[5]可知，出棧序列的求解問題是一個NP問題，所以判斷一個序列是否為一個出棧序列更為重要。在文獻(xiàn)[2]的傳統(tǒng)算法中， 根據(jù)棧的定理[2]判斷某一序列是否為出棧序列，該定理是：對于集合N={1,2,3 ,…,n}，如果依次序1,2,3 ,…,n入棧，設(shè)ala2a3…an是1,2,3 ,…,n的一個全排列，則ala2a3…an為出棧序列的充要條件是：對于任意的ai，在它后面的且比它小的數(shù)是降序排列的。由該定理推出結(jié)論： 若p，q，r是入棧序列中的數(shù)，且p<q < r，則出序序列中p，q，r的排列次序不可能是r，p，q。?

由上述推論可設(shè)計出判斷某個序列是否為合法的出棧序列，該算法的源代碼如下：?

flag=l; // 沒標(biāo)志為l，假設(shè)序列a為合法的出棧序列

for(u=0;u<=n-2;u++)?

for(v=u+1;v<=n-1;v++)?

for(w=v+l;w<=n;w++)?

if((a[v]<a[w])&&(a[w]<a[u]))flag=0; //若出棧次序為rpq則為不合法的出棧序列

該算法的時間復(fù)雜度為O(n3)，算法1采用了該方法判斷某一序列是否為出棧序列，其效率太低，為此文中借助于棧實現(xiàn)復(fù)雜度為O(n)的算法，其基本思想描述如下：?

(1) 初始化棧stack，設(shè)置flag為1；?

(2) v=w=0，v指要判斷的序列，w指入棧的序列；?

(3) 如果v > n或flag=0，則轉(zhuǎn)(9)；?

(4) 如果棧stack是空棧，則將第w個入棧序列符號人棧，w++；?

(5) 如果stack棧頂元素值等于序列的第v個元素，或者w ≤ n，則轉(zhuǎn)(7)；?

(6) 第w個入棧元素壓入stack棧中，w ++，轉(zhuǎn)(5)；?

(7) 如果stack棧頂元素值等于序列的第v個元素，則匹配，stack棧頂元素出棧，v++；否則，說明所判斷的序列不是出棧序列，賦flag為零；?

(8) 轉(zhuǎn)(3)；?

(9) 結(jié)束，若此時flag為1，則序列為出棧序列，否則不是。?

將該算法替代算法1中的相應(yīng)部分，稱為改進(jìn)后的算法1。從表1可以看出改進(jìn)后的算法1，在運行時間上比原算法大大縮短，甚至比算法2還要好。