160929101042575_第3章桟和队列分析重点.ppt

设栈S和队列Q的出始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是______.　 A、 6 B、 4 　 C、 3 D、 2 设计一个判别表达式中左、右括号是否配对出现的算法，采用____数据结构最佳。　 A、 线性表的顺序存储结构 B、 队列 　 C、 线性表的链式存储结构 D、 栈 三综合题 1、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) { int i ; arr[64] ; n=0; while (!stackempty(s)) arr[n++]=pos(s); for(i=0;in;i++) push(s,arr[I]); } (2) void demo2(seqstack *s,int m) { seqstack t; int i; initstack(t); while(! Stackempty(s)) if(i=pop(s)!=m) push(t,i); While(! Stackempty(t)) { i=pop(t); push(s,i); } } 2、利用栈的基本操作，写一个返回栈s中结点个 数的算法int stacksize(seqstack s)，并说明s为 何不用作为指针参数？ 3、利用栈的基本操作，写一个将栈中所有结点 均删除算法，并说明S为何要作为指针参数？ 设计一个算法，判断一个算术表达式中的括号是否配对（假设表达式中共有三种括号()和[]和{})。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和next，其中ch域为字符类型。 Status correct(linklist?*head)//判别表达式中三种括号是否匹配{??InitStack(s); Linklist?*p; ??for(p=head ; p!=null ; p=p-link)??{????if(p-ch==(|| p-ch ==[|| p-ch =={) push(s,p-ch);????else if(*p==)||*p==]||*p==})????{??????if(StackEmpty(s)) return ERROR;??????pop(s,c);??????if(p-ch==)c!=() return ERROR;??????if(p-ch==]c!=[) return ERROR;??????if(p-ch==}c!={) return ERROR; //必须与当前栈顶括号匹配????}??}//for??if(!StackEmpty(s)) return ERROR;??return OK;}//correct 435612中到了12顺序不能实现； 135426可以实现。 1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？ 练习 * （2）入队列（示意图） Status EnQueue(Queue Q,ElemType e)　　{ 　　// 在当前队列的尾元素之后，插入元素 e 为新的 队列尾元素　　　s = new QNode; 　　　if (!s) exit(OVERFLOW);　　// 存储分配失败 　　　s-data=e; 　s-next = NULL;　　　Q.rear-next=s;　// 修改尾结点的指针 Q.rear=s; 　　　 // 移动队尾指针 return OK; 　　} （3）出队列（示意1 示意2） Status DeQueue(Queue Q, ElemType e){ // 若队列不空，则删除当前队列 Q 中的头元素， 用 e 返回其值，并返回 OK；否则返回ERROR 　if ( Q.front == Q.rear ) // 链队列中只有一个头结点　return ERROR; 　p = Q.front-next; 　e = p-data;　　　　　　　// 返回被删元素　Q.front-next=p-next;