实验二 栈和队列的基本操作实现及其应用

实验二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”相关常量及结构定义：#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefintSElemType;//栈类型定义typedefstructSqStack {SElemType*base;SElemType*top;intstacksize;}SqStack;设计相关函数声明：判断函数：intIsReverse()栈：intInitStack(SqStack&S)intPush(SqStack&S,SElemTypee)intPop(SqStack&S,SElemType&e)intStackEmpty(s)题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。题目三、RailsDescriptionThereisafamousrailwaystationinPopPush

ThelocaltraditionisthateverytrainarrivingfromthedirectionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.ThechieffortrainreorganizationsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.YoucanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheycanmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbelocatedasmanycoachesasnecessaryinthestation.ButonceacoachhasenteredthestationitcannotreturntothetrackinthedirectionAandalsoonceithasleftthestationinthedirectionBitcannotreturnbacktothestation.InputTheinputconsistsofblocksoflines.Eachblockexceptthelastdescribesonetrainandpossiblymorerequirementsforitsreorganization.InthefirstlineoftheblockthereistheintegerNdescribedabove.Ineachofthenextlinesoftheblockthereisapermutationof1,2,...,N.Thelastlineoftheblockcontainsjust0.

Thelastblockconsistsofjustonelinecontaining0.OutputTheoutputcontainsthelinescorrespondingtothelineswithpermutationsintheinput.AlineoftheoutputcontainsYesifitispossibletomarshalthecoachesintheorderrequiredonthecorrespondinglineoftheinput.OtherwiseitcontainsNo.Inaddition,thereisoneemptylineafterthelinescorrespondingtooneblockoftheinput.Thereisnolineintheoutputcorrespondingtothelast``null''blockoftheinput.SampleInput512345541230665432100SampleOutputYesNoYes题目四、SlidingWindowDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseetheknumbersinthewindow.Eachtimetheslidingwindowmovesrightwardsbyoneposition.Followingisanexample:

Thearrayis[1

3

-1

-3

5

3

6

7],andkis3.WindowpositionMinimumvalueMaximumvalue[1

3

-1]

-3

5

3

6

7

-13

1

[3

-1

-3]

5

3

6

7

-33

1

3

[-1

-3

5]

3

6

7

-35

1

3

-1

[-3

5

3]

6

7

-35

1

3

-1

-3

[5

3

6]

7

36

1

3

-1

-3

5

[3

6

7]37Yourtaskistodeterminethemaximumandminimumvaluesintheslidingwindowateachposition.InputTheinputconsistsoftwolines.Thefirstlinecontainstwointegersnandkwhicharethelengthsofthearrayandtheslidingwindow.Therearenintegersinthesecondline.OutputTherearetwolinesintheoutput.Thefirstlinegivestheminimumvaluesinthewindowateachposition,fromlefttoright,respectively.Thesecondlinegivesthemaximumvalues.SampleInput8313-1-35367SampleOutput-1-3-3-333335567题目五（选作考查串知识）DNAEvolution【Description】Evolutionisaseeminglyrandomprocesswhichworksinawaywhichresemblescertainapproachesweusetogetapproximatesolutionstohardcombinatorialproblems.Youarenowtodosomethingcompletelydifferent.GivenaDNAstringSfromthealphabet{A,C,G,T},findtheminimalnumberofcopyoperationsneededtocreateanotherstringT.Youmayreversethestringsyoucopy,andcopybothfromSandthepiecesofyourpartialT.Youmayputthesepiecestogetheratanytime.YoumayonlycopycontiguouspartsofyourpartialT,andallcopiedstringsmustbeusedinyourfinalT.Example:FromS=“ACTG”createT=“GTACTAATAAT”GetGT.........bycopyingandreversing"TG"fromS.GetGTAC...bycopying"AC"fromS.GetGTACTA…..bycopying"TA"fromthepartialT.GetGTACTAATbycopyingandreversing"TA"fromthepartialT.GetGTACTAATAATbycopying"AAT"fromthepartialT.【Input】Thefirstlineofinputgivesasingleinteger,1≤k≤10,thenumberoftestcases.Thenfollow,foreachtestcase,alinewiththestringS,lengthofSislessthen19,andalinewiththestringT,lengthofTislessthen19.【Output】OutputforeachtestcasethenumberofcopyoperationsneededtocreateTfromS,or"impossible"ifitcannotbedone.【SampleInput】4ACGTTGCAACACGTTCGATCGAAAAAAAAAAAAAAAAAAAA【Sampleoutput】1impossible46题目六（选作考查数组知识）MagicSquares描述Followingthesuccessofthemagiccube,Mr.Rubikinventeditsplanarversion,calledmagicsquares.Thisisasheetcomposedof8equal-sizedsquares:12348765Inthistaskweconsidertheversionwhereeachsquarehasadifferentcolor.Colorsaredenotedbythefirst8positiveintegers.Asheetconfigurationisgivenbythesequenceofcolorsobtainedbyreadingthecolorsofthesquaresstartingattheupperleftcornerandgoinginclockwisedirection.Forinstance,theconfigurationofFigure3isgivenbythesequence(1,2,3,4,5,6,7,8).Thisconfigurationistheinitialconfiguration.Threebasictransformations,identifiedbytheletters`A',`B'and`C',canbeappliedtoasheet:'A':exchangethetopandbottomrow,'B':singlerightcircularshiftingoftherectangle,'C':singleclockwiserotationofthemiddlefoursquares.Belowisademonstrationofapplyingthetransformationstotheinitialsquaresgivenabove:A:87651234B:41235876C:17248635Allpossibleconfigurationsareavailableusingthethreebasictransformations.Youaretowriteaprogramthatcomputesaminimalsequenceofbasictransformationsthattransformstheinitialconfigurationabovetoas