王文龍

(喀什師范學(xué)院 信息工程技術(shù)系 新疆 喀什 844000)

?

輸出出棧序列研究

王文龍

(喀什師范學(xué)院 信息工程技術(shù)系 新疆 喀什 844000)

在棧大小不受限制和受限制兩種情況下，給定入棧序列(1, 2, …,n)，分析出棧序列應(yīng)滿足的性質(zhì)，并據(jù)此給出基于窮舉法和直接后續(xù)法的輸出出棧序列的算法及程序?qū)崿F(xiàn).算法較直觀且易于理解，程序均經(jīng)過(guò)測(cè)試，輸出正確.

棧； 出棧序列； 直接后續(xù)法； 算法； 程序

0 引言

棧是限定僅在表尾端進(jìn)行插入或刪除操作的特殊線性表，具有后進(jìn)先出的特性，這種特性使得棧有著十分廣泛的應(yīng)用.在文獻(xiàn)[1-9]中，對(duì)給定一個(gè)入棧序列，求出棧序列數(shù)量以及如何輸出全部出棧序列等問(wèn)題進(jìn)行了研究，得出了相應(yīng)的研究結(jié)果.然而，以上研究結(jié)果均基于一個(gè)前提：棧的大小是不受限制的，即棧的大小大于等于入棧序列的長(zhǎng)度.而在某些情況下，棧的大小會(huì)受到限制，即棧的大小小于入棧序列的長(zhǎng)度，此時(shí)有關(guān)棧的入棧、出棧問(wèn)題會(huì)發(fā)生變化.因此，本文在棧大小不受限制和受限制兩種情況下，對(duì)輸出全部出棧序列的問(wèn)題進(jìn)行分析研究，并給出了相應(yīng)的算法和程序?qū)崿F(xiàn).

1 出棧序列性質(zhì)

為方便分析，將研究的問(wèn)題描述為給定入棧序列(1,2, …,n)，輸出全部出棧序列.當(dāng)棧大小不受限制時(shí)，依據(jù)棧的特點(diǎn)，較容易得出出棧序列應(yīng)該滿足的性質(zhì).

性質(zhì)1當(dāng)棧大小不受限制時(shí)，序列a1a2…an是(1,2, …,n)的一個(gè)全排列, 則a1a2…an為出棧序列的充要條件是對(duì)于任意的ai, 在它后面的且比它小的數(shù)是降序排列的.

當(dāng)棧的大小受限制時(shí)，即棧的大小k小于入棧序列長(zhǎng)度n時(shí)，出棧序列首先需要滿足性質(zhì)1，然后考慮棧大小受限對(duì)出棧序列的要求.例如有長(zhǎng)度n=6的入棧序列123456，棧的大小k=4，此時(shí)出棧序列的第一位不能超過(guò)元素4，即出棧序列第一位小于等于4，不能大于4，第二位小于等于5，不能大于5.一般情況下，第一位小于等于k，第二位小于等于k+1，依次類推，直到出棧序列第n-k位小于等于n-1.

性質(zhì)2當(dāng)棧的大小受限制時(shí)，即棧的大小k小于入棧序列長(zhǎng)度n時(shí)，序列a1a2…an是(1,2, …,n)的一個(gè)全排列, 則a1a2…an為出棧序列的充要條件是滿足性質(zhì)1并且序列的第j位小于等于k+j-1.

2 棧大小不受限制時(shí)輸出全部出棧序列

要輸出全部出棧序列，可采用窮舉法將入棧序列進(jìn)行全排列，然后根據(jù)出棧序列需要滿足的性質(zhì)，將不滿足的序列排除，剩余的即為出棧序列.此方法需要給出入棧序列的全排列，較為普遍的方法是采用字典序法.

算法1初始序列12…n，當(dāng)前序列a1a2…an.

(1) 從a1a2…an的右端開(kāi)始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)i.若無(wú)法找到這樣的i，則結(jié)束.

(2) 在ai的右邊的數(shù)字中，從右端開(kāi)始，找出第一個(gè)比ai大的數(shù)的序號(hào)j.

(3) 交換ai和aj.

(4) 將ai以后的所有數(shù)倒置，得到一個(gè)新的序列.

(5) 判斷該序列是否滿足出棧序列的性質(zhì)1，若滿足則輸出該序列，轉(zhuǎn)(1).

程序如下：#include "iostream.h"

#include "string.h"

void fx(char a[],int i,int j)

{ int k; char tem;

for(k=i;k<=(i+j)/2;k++)

{ tem=a[k]; a[k]=a[i+j-k]; a[i+j-k]=tem; } }

int pd(char a[],int n)

{ int u,v,w,flag=1;

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

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

for(w=v+1;w<=n;w++)

if((a[v]

return flag; }

void main()

{ int i,j,len,tag=1,count=1;char a[10],tem;

cout<<"please input stack:"<>a; cout<

while(tag)

{ for(i=len;i>0;i--)

if(a[i-1]

if(i-1<0 ) tag=0;

else { for(j=len;j>i;j--)

if(a[i-1]

tem=a[i-1]; a[i-1]=a[j]; a[j]=tem; fx(a,i,len);

if(pd(a,len)) { if(count%5==0) cout<

count++;cout<

不難發(fā)現(xiàn)，此算法效率不高，例如當(dāng)前出棧序列為136542，按算法1，將3和4互換，得到146532，然后將6532倒置，得到下一個(gè)序列142356，再判斷是否是出棧序列，由于4后面比4小的數(shù)有2和3，然而是升序，因此它不是出棧序列.繼續(xù)算法1，依次可以得到142365，142536，142563，142635，142653，143256，只有143256是出棧序列，142356，142365，142536，142563，142635，142653都不是出棧序列，原因均為4后面比4小的數(shù)有2和3，然而都是升序.

為提高效率，可采用直接后續(xù)法，做如下考慮：在將136542中的3和4交換后，得到146532，由于3和2均小于4，因此不直接將6532倒置，而將32當(dāng)作整體再倒置，得到143256.從而從出棧序列136542直接產(chǎn)生后續(xù)的出棧序列143256，而避免產(chǎn)生中間的非出棧序列.

算法2初始序列12…n，當(dāng)前序列a1a2…an.

(1) 從出棧序列a1a2…an的右端開(kāi)始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)i.若無(wú)法找到這樣的i，則結(jié)束.

(2) 在ai的右邊的數(shù)字中，從右端開(kāi)始，找出第一個(gè)比ai大的數(shù)的序號(hào)j.

(3) 交換ai和aj.

(4) 將ai+1到aj-1的數(shù)倒置.

(5) 將ai+1及其后所有數(shù)向左環(huán)移j-i-1位，得到下一個(gè)出棧序列并輸出，轉(zhuǎn)(1).

程序如下：#include "iostream.h"

#include "string.h"

void px(char b[],int sl)

{ int i,j,k; char tem;

for(i=0;i

{k=i;

for(j=i+1;j

if(b[j]

if(k!=i) { tem=b[i]; b[i]=b[k]; b[k]=tem; } } }

void main()

{ int i,j,k,len,tag=1,count=1; char a[10],b[10],tem;

cout<<"please input stack:"<>a; cout<

while(tag)

{ for(i=len;i>0;i--)

if(a[i-1]

if(i-1<0) tag=0;

else { for(j=len;j>i;j--)

if(a[i-1]

tem=a[i-1]; a[i-1]=a[j]; a[j]=tem;

for(k=i;k

b[k]=′

德江县| 涟水县| 成都市| 通州市| 贵南县| 牡丹江市| 定日县| 县级市| 交城县| 西平县| 阿克陶县| 太保市| 益阳市| 得荣县| 阿拉善右旗| 新丰县| 涿鹿县| 苍南县| 淮安市| 兰州市| 普洱| 易门县| 承德县| 阳春市| 汉川市| 莱芜市| 肇州县| 樟树市| 仁布县| 五寨县| 高尔夫| 枝江市| 张家口市| 黑山县| 临潭县| 门头沟区| 焉耆| 美姑县| 彭山县| 镇赉县| 昆明市|