第3章栈和队列作业参考答案

第三章栈和队列作业1、若按教材P44页图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列）。123、132、213、231、321输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。2、试证明：若借助栈由输入序列1、2……n得到的输出序列为p1、p2……pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈j〈k使pjpkpi如果ij，则对于pipj情况，说明pi在pj入栈前先出栈。而对于pipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于ijk，不可能出现pjpkpi的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。3、按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节3--2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D-E↑F4、试编写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列，序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列。例如‘a+b&b+a’是属于该模式的字符序列，而‘a+b&a-b’则不是。StatusModel(){//识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列,序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列InitStack(s);c=getchar();while(c!='&'){Push(s,c);c=getchar();}c=getchar();while(c!='@'&&!StackEmpty(s)){Pop(s,x);if(c==x)c=getchar();elsereturnFALSE;}if(c=='@'&&StackEmpty(s))returnTRUE;elsereturnFALSE;}5、假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘＠’为结束符的字符序列是否是回文。StatusReturnText(){//判断读入的一个以‘@’为结束符的字符序列是否为回文InitStack(s);InitQueue(q);c=getchar();while(c!='@'){Push(s,c);EnQueue(q,c);c=getchar();}while(!EmptyStack(s)){Pop(s,x);DeQueue(q,y);if(x!=y)returnFALSE;}returnTRUE;}6、分析程序(1)、SelemType为char类型，写出下列程序运行结果voidmain(){StackS；charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};printf(x);}输出结果：stack(2)写出下列算法的功能（元素类型为int）voidtest(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}将队列Q中的数据元数进行逆置。7、（选作题）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。（1）voidEnQueue(LinkedListrear,ElemTypex){//rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。s=(LinkedList)malloc(sizeof(LNode));//申请结点空间s-data=x;s-next=rear-next;//将s结点链入队尾rear-next=s;rear=s;//rear指向新队尾}（2）voidDeQueue(LinkedListrear){//rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。if(rear-next==rear){printf(“队空\n”);exit(0);}s=rear-next-next;//s指向队头元素，rear-next-next=s-next;//队头元素出队。printf(“出队元素是”，s-data);if(s==rear)rear=rear-next;//空队列free(s);}