C语言栈和列课后题.ppt

第三章 栈和队列习题课 3.3 写出下列程序的输出结果(栈的元素类型SElemType为char）。 Void main() { Stack S; Char x, 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 3.3解答 先解释一下你的一个误区： Pop()函数是出栈并且将出栈的元素存放在第二个行参里，所以在这里x的值不再是c了，而是出栈的元素。。 过程： 首先是三个压栈操作，之后栈里的元素为：cak，左边的为栈底，右边是栈顶。 然后一个出栈，此时栈里的元素为：ca，x中存的是k； 之后两次压栈，此时栈里的元素为：catk； 之后一个出栈，此时栈里的元素为：cat，x中存的是k； 最后一次压栈，此时栈里的元素为：cats，x中存的是k； 之后while(!StackEmpty(S)){ Pop(S,y);printf(y); }; 结果是stac， Printf(x); 结果是k， 所以最终的结果为stack 3.4 简述以下算法的功能 (1) Status algo1(Stack S) { int i,n,A[255]; n=0; While(!StackEmpty(S)) {n++;Pop(S,A[n]);} For(i=1;i=n;i++) Push(S,A[i]); } (2) Status algo2(Stack S,int e) { Stack T;int d; InitStack(T); while(!StackEmpty(S)) { Pop(S,d); if (d!=e) Push(T,d); } while (!StackEmpty(T)) { Pop(T,d); Push(S,d); } 3.4 题答案是： (1) 程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在255个以内。 (2)程序段的功能是利用栈T，将一个非空栈S中值等于e变量的元素全部删去。 3.12写出下列程序段的输出结果（队列中的元素类型QElemType为char） Void main() { Queue Q; InitQueue(Q); Char x=’e’, y=’c’; EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQUeue(Q,’a’); While (!QueueEmpty(Q)) { DeQueue(Q,y); Printf(y); } Printf(x); } 输出结果为：char 3.12解答 首先三次入队操作，结果为：crh，左边为对尾，右边是队首， 一次出队一次入队后变为：hcr， 再一次出队一次入队后变为：ahc ，此时x中存的是r， 语句while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };执行后结果为：cha； Printf(x);执行后为：r 故结果为：char。。 3.13、简述以下算法的功能（栈和队列的元素均为int) Void algo3(Queue Q) { Stack S; int d; InitStack(S); while( !QueueEmpty(Q)) { DeQueue(Q,d); Push(S,d); } While(!StackEmpty(S)) { Pop(S,d); EnQueue(Q,d); } } 程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。 1.假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化initstack(tws),入栈push(tws,i,x) 和出栈pop(tws,i),其中i 为0或1，用以分别指示设在数组两