栈和队列作业参考答案.ppt

1,第三章栈和队列,作业参考答案,2,作业1.1假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。,#defineM100TypedefstructTwsStackSElemTypestackM;inttop2;intbase2;,3,StatusInistack(TwsStack/push,4,Statuspop(TwsStack/pop,5,作业1.2设有编号1，2，3，4的四辆列车顺序进人一个栈式结构的站台，请写出这四辆列车开出车站的所有可能的顺序。,这四辆列车开出车站的所有可能的顺序共有14种，它们分别是：1，2，3，4；1，2，4，3；1，3，2，4；1，3，4，2；2，1，3，4；1，4，3，2；2，l，4，3；2，3，1，4；2，3，4，1；2，4，3，1；3，2，1，4；3，24，1；3，4，2，1；4，3，2，1,6,作业1.3假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。,TypedefstructQNodeQElemTypedate;structQNode*next;TypedefstructLinkQueuestructQNode*rear;,7,StatusIniQueue(LinkQueue/IniQueue,8,StatusEnQueue(LinkQueue/EnQueue,9,StatusDeQueue(LinkQueue,10,作业1.4回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文,字符串：“madamimadam”,11,Statushuiwen(charstr20)InitStack(S);i=0；m=0;while(stri!=)/过滤空格if(stri=)m=m+1;elsestri-m=stri;i+;stri-m=stri;/字符串结束符”i=0;while(stri!=)Push(S,stri);i+;j=0;while(!StackEmpty(S)Pop(S,e)If(strcmp(strj,e)!=0)returnNO;/不是回文字符j+;returnYes;/huiwen,