数据结构栈和队列的基本操作实现及其应用

《数据结构栈和队列的基本操作实现及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。相关常量及结构定义：#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefintSElemType;//栈类型定义typedefstr

2、uctSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;设计相关函数声明：判断函数：intIsReverse()栈：intInitStack(SqStack&S)intPush(SqStack&S,SElemTypee)intPop(SqStack&S,SElemType&e)intStackEmpty(s)题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。题目三、R

3、ailsDescriptionThereisafamousrailwaystationinPopPushCity.Countrythereisincrediblyhilly.Thestationwasbuiltinlastcentury.Unfortunately,fundswereextremelylimitedthattime.Itwaspossibletoestablishonlyasurfacetrack.Moreover,itturnedoutthatthestationcouldbeonlyadead-endone(seepicture)anddue

4、tolackofavailablespaceitcouldhaveonlyonetrack.ThelocaltraditionisthateverytrainarrivingfromthedirectionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.Thechieffortrainreorganizatio

5、nsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.Youcanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheyc

6、anmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbelocatedasmanycoachesasnecessaryinthestation.ButonceacoachhasenteredthestationitcannotreturntothetrackinthedirectionAandalsoonceithasleftthestationinthedirectionBitcannotreturnbacktothestatio

7、n.InputTheinputconsistsofblocksoflines.Eachblockexceptthelastdescribesonetrainandpossiblymorerequirementsforitsreorganization.InthefirstlineoftheblockthereistheintegerNdescribedabove.Ineachofthenextlinesoftheblockthereisapermutationof1,2,...,N.Thelastlineoftheblockcontainsjust0.Thela

8、stblockconsi