08级第3章栈和队列B【荐】.ppt

通知 1、下周二交第2章作业 习题集2.8 2.10 2.21 2.22 2.34 2.35 2、实验安排 1. 定义 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出B 链栈的入栈操作和出栈操作（教材省略，教师补充） 栈的应用举例 四川科技馆展项－－梵天之塔 堆栈用途？ 今天课程到此结束 Status EvaluateExpression( OperandType result) { InitStack(OPND); InitStack(OPTR);Push(OPTR ,’#’);c=getchar(); while((c!=‘#’)||(GetTop(OPTR)!=‘#’)) { if (!In(c,OP) { Push(OPND,c); c=getchar();} else switch(precede(GetTop(OPTR) , c)) { case ‘’ : Push(OPTR , c); c=getchar(); break; case ‘=’: Pop(OPTR); c=getchar(); break; case ‘’ : Pop(OPTR ,theta); Pop(OPND,b);a=Pop(); Push(OPND, Operate(a, theta,b)) ; break; ; } //switch } //while result=GetTop(OPND); }//EvaluateExpression Operate= a ? b 栈顶与运算符比较并查表3.1 判C是否操作符 问：教材P53表3.1中，?1和?2哪个对应栈顶元素，哪个对应键盘输入值？ 答：根据P53 Precede()函数可知， ?1对应栈顶元素 由表3.1可看出，右括号 ) 和井号 # 作为?2时级别最低； 由c 规则得出： * ，/， + ，-为?1时的优先权低于‘（’，高于‘）’ 由a规则得出：‘（’=‘）’ 表明括号内的运算已完成； ‘ # ’=‘ # ’ 表明表达式求值完毕。 附： 调用函数/子程序非它莫属； 递归运算的有力工具（汉诺塔）； 用于保护现场和恢复现场； 简化了程序设计（表达式求值）。 3.2 队列 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 存储结构 运算规则 实现方式 逻辑结构 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 基本操作：入队或出队，建空队列，判队空或队满等操作。 尾部插入 首部删除 队列定义 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 在队尾插入元素称为入队；在队首删除元素称为出队。 队首 队尾 问：为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 3. 简化程序设计。 答： 队的实现方式是本节重点，关键是掌握入队和出队操作。具体实现依存储结构（链队或顺序队）的不同而不同。 1. 链队列 2. 顺序队 队的抽象数据类型定义： ADT Queue{ 数据对象：D=…… 数据关系：R=…… 基本操作： …… } ADT Queue 建队、入队或出队、判队空或队满等，教材P59-60罗列了9种基本操作。 重点是循环顺序队 链队列类型定义： typedef struct { QueuePtr front ; //队首指针 QueuePtr rear ; //队尾指针 } LinkQueue; 结点类型定义： typedef Struct QNode{ QElemType data; //元素 Struct QNode *next; //指向下一结点的指针 }Qnode , * QueuePtr ;