栈和队列答案

《栈和队列答案》由会员分享，可在线阅读，更多相关《栈和队列答案（44页珍藏版）》请在装配图网上搜索。

1、3.1若按教科书31.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道），则请回答：() 如果进站的车厢序列为12，则也许得到的出站车厢序列是什么？(2) 如果进站的车厢序列为1235,则能否得到43562和13542的出站序列,并请阐明为什么不能得到或者如何得到（即写出以 S表达进栈和以 表达出栈的栈操作序列）。解：(1) 12 21 321 1 132 (2）可以得到135426的出站序列,但不能得到412的出站序列。由于456出站阐明1已经在栈中，1不也许先于2出栈。3 简述栈和线性表的差别。解:线性表是具有相似特性的数据元素的一种有限序列。栈是限定仅在表尾进行插入

2、或删除操作的线性表。3.3写出下列程序段的输出成果(栈的元素类型SElmTy为chr）。vd main()Stak;arx,y；nitSac（);x=c; y k;Pu(,x)；Puh（S, a);Ps(,)；Pop(，x）;Ph(, t);Puh(S,x）；Pop(S,x);Push(S, );while(!StakEmpy(S) Po(S，y); ptf()； tf（）;解:stac4简述如下算法的功能（栈的元素类型SEleTyp为int)。(1)taus lgo1(c ） int ,A55;n=0;whie(!tacp(S) n+;Pop(，An）; (i=1;i=n；i+）Psh(S，

3、）;（2)status algo2(Sta S,int e)tk T； int d;nittack（T);wie(!StackEpty(S）Pop（,d);i(d!e) Ph（,d);whle(!StakEmty（T)Pp(T,d);Pu(S,d)；解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e,将其从栈中清除.5 假设以S和分别表达入栈和出栈的操作,则初态和终态均为空栈的入栈和出栈的操作序列可以表达为仅由S和X构成的序列。称可以操作的序列为合法序列(例如，XSX为合法序列，SXS为非法序列）。试给出辨别给定序列为合法序列或非法序列的一般准则,并证明：两个不同的合法（栈操作）序列（

4、对同一输入序列)不也许得到相似的输出元素（注意:在此指的是元素实体,而不是值）序列。解：任何前n个序列中的个数一定不小于X的个数。设两个合法序列为:TSST2SXX 假定前n个操作都相似，从第+1个操作开始，为序列不同的起始操作点。由于前n个操作相似，故此时两个栈（不妨为栈A、B）的存储状况完全相似，假设此时栈顶元素均为a。第n+个操作不同，不妨的第n1个操作为S，T2的第n+1个操作为X。T为入栈操作,假设将b压栈，则1的输出顺序一定是先后a;而T2将a退栈，则其输出顺序一定是先a后。由于T的输出为ba,而T2的输出顺序为ab,阐明两个不同的合法栈操作序列的输出元素的序列一定不同。3.试证明

5、：若借助栈由输入序列2n得到的输出序列为（它是输入序列的一种排列)，则在输出序列中不也许浮现这样的情形:存在着ijk使。解：这个问题和3.1题比较相似。由于输入序列是从小到大排列的,因此若,则可以理解为通过输入序列可以得到输出序列，显然通过序列123是无法得到312的，参见3题。因此不也许存在着ijk使1)out1)c;i（x=0）sum=0;lstest(sum）；sum+=x;coutx;ush(s，x);hil（x0);wle(!StckEmty(s）Pp（s,x);sm+=x;cotumndl；DestorSk();311简述队列和堆栈这两种数据类型的相似点和差别处。解:栈是一种运算受

6、限的线性表,其限制是仅容许在表的一端进行插入和删除运算。队列也是一种运算受限的线性表,其限制是仅容许在表的一端进行插入，而在表的另一端进行删除。. 写出如下程序段的输出成果（队列中的元素类型QElempe为car)。vidmain(）Que Q;niQee(Q);char xe,y c;Enueue(Q， );EQueue(Q, ）;EnQueu(Q,y);DeQueue(，x)；nue(, )；DeQueu(, );EnQueue（Q,a);hile(!eueEmpty(Q）)Deuee(Q,y);cuty;out=p) *top0-=x;ele crrSac overfw！;el(p1+s

7、tacksize1) *+op=x;else crStak vflo!；lemType Po(int )di=i；if(di=0）i(top0top) return +top0;elsrtop0) return *to1-;es rnext;del ;s.size-；intStckegh(Stacks)ren ssze；Status tackEmpty(Stacks)i(ssize=) return TRU;ele return FALSE;atustTop(Sta s,Eleye &e）if(!s.top) retrn EROR;elsees.op-dta;etrn ;StusPush(St

8、ak&s,ElemTe e)Likype;p=new NoeTye;if(！p)ei(OEFLOW）；p-ets.top;s.tp=p;pda=e;ssie+;etr OK;SatusPop(Stac&s,ElemType )LnkTyp p;if(s.tp)e=top-dat;p=so;s.top=p-nxt;eleep;s.size-;retrn O；/ 从栈顶到栈底用it（)函数遍历栈中每个数据元素vid StacTraverse(Stack，Saus（Visi)(ElmTpee)nkTpe p;=s.t；whle() Vist(-data）；3.1 假设如题3.1所属火车调度站的入口处

9、有节硬席或软席车厢(分别以和S表达）等待调度,试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调节到硬席车厢之前。解：in main()Stc s;haruffer80;n i=0，j0;ttack（s);coutBufe；coutBufferenl;whil(Buferi)if(Buferi=S)BuerjBuffei；+;else ush(s,Bufri);i+;whil（Bufferj)Pop(s，uerj）;j+；coutBffered;retun0；3.17 试写一种算法，辨认一次读入的一种以为结束符的字符序列与否为形如序列1&序列2模式的字

10、符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列,而1+33-则不是。解:BOLSymetry(chara)in i=0;tak ;nitStack(s);Elmype x;wile(i!=& & i)Ph(s,ai);i+;if（ai) rurn FASE;i+；whle(ai）Po(s,x);if(!=ai)DestroySak(s）;return FALSE;i；retunTRUE;.18试写一种鉴别体现式中开、闭括号与否配对浮现的算法。解:OOL BracktCorreondncy(car a)n0;Stack s;InitS

11、tack(s);ElemType x;wil(a)sw（ai)ca(：Push(s,i);bek;case :s(s,ai）;reak;case ):GetTo（,)；i(x=（)op（s,);ele retun FALE；break;case ：GetTp(s,x);if(=) Pop(,x)；else rern FALSE；break;eault:bre；+；i（.size!） return FASE;reurnTUE;320 假设以二维数组g(1m, 1n)表达一种图像区域,g,j表达该区域中点（i,j）所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。商定和（

12、i,j0）同色的上、下、左、右的邻接点为同色区域的点。解：#nclue iosrm.h#includeypede strcint;t y;PsTye;edfsructint Colo;nt iitd;Posypeea;EmTyp;#nclude ：VC9tac.h#defie8#deineNlemType gN；oid CreaeGDS(ElemTyp gM);oid ShoGraphr(eType gMN);vod RegioFiln(lemTpeMN,PosTyp CuPs,itewClor);int main()CeatGS（g)；SowGrphArry();Psp StartPs;St

13、artP.=5;ttPos.y=;it FCoo=6;RgoFilling(,SatPos,FilColor）;cutend;ShowGrahrray(）;eturn 0;oid RegionFillin(ElemTpe MN,PosTypeCurP,intFillor）Stacks；IntStack（);EleTy e;int OldCrgCurPos.xCuPos.Color;Push(s，rPos.urPos.y);whi(!tckEmpty(s)P（,);CurPs=e.seat;gCursxCuPos.y.ColorFillCor;gCurPos.xCuro.y.Vsited=1;（

14、urPosxM&！gCurPos.x+CurPos.Viitd &gCuros.+1uros.y.olr=OlColor)Pus(s,gCrPo.x+1urPosy);if（CurPos.x &!gCPs.-1ursy.Visited &guos.-CPs.y.olor=OColor)Puh(,gCros-CrPs.y);i(urPy &！guPos.CurPo.y-1Vied&gCrPos.xCurP.y-1.olor=OdColor)ush(s,gCurPo.xuro.y-);voidCreateGDS（lemTpegMN)n i,；r(i0;iM；i+)or(=；jN;j+）ij.sea

15、tx=；gist.y=j;gj.Viitd=0;gi.olor=0;or(i=2;i5；i+)fr(j=2；j4;j+)gjol=3;fo(i=5;-1；i+)fo（=;j6；j+)gijl=;voihoGrahArr(ElmTy gN)it i，j；for(=0;i+)for(j=0;N；j+)ctgj.Color;ou) etrTRE;lse return ALSE;3.22 如题.21的假设条件，试写一种算法,对以逆波兰式表达的体现式求值。解：har CalVal_Ineoland（charBfer）Sack Ond;Iittack（Opn);int i;char ;EemTyp,2;w

16、hi(fri!=#）f(！sOperar(Buferi)Puh(p,Bufferi)；lso(pnd,e2);Po(pnd，e1);=Cal（e1，Bufer，e2);Push(Op,)；i+;return c;chr Cal(chr c,char o，char c2)ntx,x1,x2；har 10;h0=c;ch=;x1=atoi(h）;hc2;ch1=0;2=toi（h)；swith(p）e +：xx1+x;rek；c -:xx1-x2;rk; *:x=x1x2;rek;cas /:x=x1/x2;beak;defau：break;ta(x，1);retrn c0;.2如题321的假设条

17、件,试写一种算法，判断给定的非空后缀体现式与否为对的的逆波兰体现式，如果是，则将它转化为波兰式。解:#inclde #inlde #inlude srin.hincled:VC99Constant.htypedef car RAY30；tyedf ARAY ElType;pedef stuc odypeEleyp at；NeTyp *next;odType，nkType;typdefrtLikType ; size;Stac;vodittak（Stck s）；atus uh(tc &s，ElmType)；Stus op(Stack &,lemTyee)；SausIspratr（ca ）;Sta

18、tusSakEmpt(Sacks);Sau InvFrPoland（char a）;itain(）cha a0；cout;i(InoFroPland(a）) coutend；ee cut=0& i=9)chi;h1=0;Push（s，ch);els reurn FAS;esech=ai;h1=0；if(!SackEmpty(s)）Pop(s,c2)；(！StackEmty()Pop(s，1);strcat(h,1）;strcat(ch，c2);Psh(s,ch）;elerern FALE;elsereturn ALSE;i+;(!SakEmty(s）)Pop(s,c1);trpy(,1）;lr

19、etrn FLE;if(！tEpty(s) eunFALE;returOK;vd IniStack(Stak &s）s.topNLL;s.se=0；Sttus Psh（Stc &s,Eleyp )LinkTye p；=newNodType;if（！p) ext（OVERFO）;p-eso；s.op=;trpy(pdata,e);.sze+;retrn K;St p(Sack &s,Eemype e)LikTyp p;i(s.to）strcp(e，s.top-data)；p=.tp；tp=p-next;delee p;ssize；retrK;StausStcEp（tack s)if(s.iz=0

20、)return R；ese retrnFALS；Status IOerao（chr c)hp#+-*;ile(*p)i（=）rturRUE;p+;tu ALSE;3.4 试编写如下定义的递归函数的递归算法,并根据算法画出求（5,2)时栈的变化过程。解：it g(it ，int n);n man（)int m,n;cotn；if(n=0) coutg（m,n)enl；le cout）rurn(（m-1,2*n)n);ese rurn;假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。306313218023.2试写出求递归函数F(n）的递归算法,并消除递归：解:inclde #d

21、efnN 20i ain()inti;ta；intn;outn;o(=；n1;i+）i(i1) =1;ele a=*ai/2;couanoblSqt(oule,dbe p,oublee)；int main（)oubeA，p，e;cotApe;cutSqt(A,e）-e & （p*p-A)1）e.nval=e.nal；Pop(s,e）;.mval-;e.nval=e1.nva+1；while(SackLengh(s)!=|e.mval！=0);etre.nva+1;0,am（，) 0 2 1gak(，0）1，ak(2,0) 0ak=akm(-1,1）akm（1,1）,m（,) 1 1=akm(m

22、,n1)=akm(，0），akm（,0） 610akm=akm(m-1，1)=km(0，1)4，akm(0,1) 4 0 m=n+1 退栈0,km(2,） 0 21g=akm(2,0)1，akm(2，0） 6 2 0ak=akm(m-1,1)=am（1，1）2,m(1,1) 4 1 1g=km（,-1)akm(1,0）3，am(1,0) 61 0akmakm(m-1,1）akm(0,1)=2退栈0，km(2,1) 1g=km（2,)1,a(2,0) 62 0ak=ak(m-,)=akm(，1)，am(1,1） 4 1 1g=k(m，-1)=akm(1，)=2; km=akm(m1,g）=akm

23、（0，2)；3，akm(,2) 7 02akmn1= 退栈0,akm(,) 02 g=a(2,0),akm（2,0) 6 2 0am=km（-1，)akm(1,1),ak(1,) 4 =akm(，n-1)=ak（1,)=2； akm=am(-，g)=(,2)=3; 退栈,ak(,1） 0 1g=ak(,0),akm(,0) 6 2 ak=km(m-1,1）=km(，)=3退栈0，akm(2,1) 0 1g=akm（,0)=3; akmakm(1，3)，am（1,) 6 1 3g=akm（1，2）; km（m1,g),akm(，2） 1 2g=km（1,);akm（m1,g),m(1，1） 6

24、1 g=ak(，0)； ak(-1,g）,am(1,0) 0km=akm(0,1)5,k（0，1) 40 1akm(,)=2退栈,akm（2，) 2 =akm(2,0）=3; akm=akm(,3)1,m(,) 61 =akm(,）;ak(1，g),k(1,2） 61 2g=akm(1,1)； ak(m-1,g)3,akm(,1） 6 11gakm(1,）； k（1,g）,akm（,0）6 0kma(0,1）=2退栈,am（2，1） 0 2 1g=akm(2,）=3； am=m(1,3)1，akm(,3) 1 3g=ak(，2); ak（m-1，g)2，ak(1，2) 6 1 g=ak（1,1

25、); km(-1，g)3,akm（,1) 6 1 1g=km(1，0）=2; km(m-1，g）=m（0，2）4,akm(0,2) 7 0 2an+=3退栈0，am(2,1) 0 21gkm(2,0）=;a=k（1,3)1，akm(,3) 13g=akm（1,2)；akm(m-1,g)2,akm(1,2） 6 12g=akm(1,1)； k(m1,g)3，ak(1，1) 6 1 1g=ak（1,0）=2； akm(-,g)=akm(,)=3退栈0,akm(，1) 0 1=ak(2，0)=3； kam（1,3)1,a(,3) 6 1 3gak（,2); m(m1,g)2,km(,2) 6 1 2

26、km(1，1)=3;km(m1，g）=akm(0,3),akm(,3) 7 0 3akn+1= 退栈,km(2,) 0 2g=(2,0)=;akm=akm(,），akm(1,3） 6 1 3=akm(1,2); akm(m1,g）2,akm(1,2) 6 12a(1,1)=3; akm(m-1，)ak（0,)=4 退栈,k（2,) 0 2 1g=k(2,)=; akm=km(1,3)1，akm(1,) 1 3gak(1，2)4; akm(m-1,g)ak(0，4)2，ak(0，4) 7 0 4k=n+1=退栈0,akm(2，1) 02 g=km（，0）=3; kmakm(1,3),ak(,3)

27、 6 1 =ak(,2)=4；ak(-1,g)=akm（0，4）=5退栈，akm（2，1） 0 1g=ak(2,0）3; am=am(1,)=5退栈akm(2,1）=5;3.28 假设以带头结点的循环链表表达队列，并且只设一种指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列何处队列的算法。解:tpee EemType；typede tuct NodeTypeElemTp dat;Ndeype *next;QNod,*tr;tpede tructQtr re;int siz;eu；Stats IiQuu(Quue& q）q.re=LL；q.size=0;reun OK;St

28、ats EnQueu(Que&q,ElemType e)QP ；p=ew QNod;if（!p) etr FALSE;p-data=e;f(!q.rea)q.rerp;-exq.rea；ls-net=q.rer-next;q.ra-ext=p;q.rerp;q.ie+；retur;Staus eQueue（ueu& ，EemTpe& e）QPtrp；if(q.siz=)return FALSE;if（.size=)pq.rer;e=p-data；.rar=NULL;deletep；eseqrearext;ep-data；qrear-nxtp-；dte p;.sz-;rurn OK;329 如果

29、但愿循环队列中的元素都能得到运用,则需设立一种标志域tag，并以tag的值为和1来辨别,尾指针和头指针值相似时的队列状态是“空”还是“满”。试编写与此构造相应的入队列和出队列的算法,并从时间和空间角度讨论设标志和不设标志这两种措施的使用范畴（如当循环队列容量较小而队列中每个元素占的空间较多时,哪一种措施较好）。解：#dneMxQizetypedef nt ElemTye;tpdstrutElempe *bse;in fnt;nt rear;Status tag;uue;StusIntQ（Quu ）q.bas=w lemTypeMaxSize;if(！q.ase)return FALE；q.ro

30、t=;q.ra；q.tag=0;etnK；StatusEnQueue(Qu q,lemType e)if(q.front=q.ear&q.） retunFALSE;elseq.basrr=e;q.r=(qear+1)%MaxQSiz;if（.rear=fnt).t;eturn OK；StatusDeuue(Queu ,lType )if(q.rnt=e&！qag)retr FALSE;esee=qbaseq.frn;q.front=(qront1)%MxQSze;q.t=;retrOK; 设标志节省存储空间，但运营时间较长。不设标志则正好相反。3.30假设将循环队列定义为:以域变量ear和ng

31、分别批示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件,并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素)。解:defin xQizeypeef int Tye;typeef strutElemType *bae；intrear;int lengh;Qee;StatuIiQueue(Queue）q.b=ne ElemypeMaxQSie；if(!.ase)retr F；qrea=；qength=0;retrn K;Status Qeue(Queue&q,ElemType e)f(qrear+1)%MaxQze=(q.ar+MaxQSize-qlenh)Ma

32、xQ)etur FAS;es.bas.ea=;q.=(ear+)%MaxQSize;q.lengt+;et K;Stats DeQue(Queu& q，leTy&e)i(.ea+MaxQSizeqln)%MaxQizqrar）etu FLSE;elsee=q.bse(q.rr+Mxize-q.enth)%MaQie;qlength-;returnOK；3.31 假设称正读和反读都相似的字符序列为“回文”,例如，aba和abca是回文，bde和aba则不是回文。试写一种算法鉴别读入的一种以为结束符的字符序列与否是“回文”。解：Stat Smmetrytrg(char )eue q;f(!ntueue（q)）eurn 0;Sack s；nitSt