第3章栈与队列B.ppt

告 示 为保证电信6、7、8班和通信1、2班同学的正常上课权限，请同学们依下图就座，敬请配合！ 数据结构课程的内容 实验一 线性表的插入与删除 以福彩和体彩选号器为设计实例，重点掌握循环链表的插入和删除操作。 1. 不仅按实验要求完成了福彩和体彩的摇号模拟，而且还补充了用户填单及获奖等级，逼真、有趣； 上堂课遗留问题讨论 第三章 栈和队列 3.1 栈（Stack） 定 义 教材P59对队列有更详细定义： 链队列示意图 顺序队示意图 问：什么叫“假溢出” ？如何解决？ 答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 例2 ：数组Ｑ[n]用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为: （Ａ） r－f （Ｂ）（n＋f－r）% n （Ｃ）n＋r－f （Ｄ） （n＋r－f）% n 问：为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序）； 操作系统中多道作业的处理（一个CPU执行多个作业）； 3. 简化程序设计。 讨论（代本章小结） 线性表、栈与队的异同点 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。 * 讲 台 电信7班 通信1班 (4列) (4列) 旁听席（最后2行） 电信8班1列 电信6班 电信8班 通信2班 (3列) (3列) (3列) 前门 后门 上机情况: 信6班—16人 信7班—17人 信8班—23人 通1班—23人 通2班—27人 实验内容： 实验小结： 通信一班杨帆同学的设计有独到之处。 教师点评 2. 界面及菜单制作精致，配色协调，尤其是菜单选项相互链接，对用户十分友好； 3. 所有不合法的情况几乎全部考虑到了，并做了恰如其分的对应处理（如输入月份错误不能容忍，但输入数字错误可以重来），思维严谨，周密。 改进建议：目前的摇号程序仍属伪随机方式，用月和日期作为“种子”重复性太强，如果改用C中提供的time（）函数，读取当前时间值，将其作为“种子”，随机性会更强。 ———推荐查阅《C语言编程常见问题解答 》P190 “怎样产生随机数？” 教材P43中case1： DelFirst(hb,qb)；InsFirst(ha,qb)； 是先删除后插入，有无风险？这两条语句能否颠倒？ 2. 教材P53表3.1中，?1和?2哪个对应栈顶元素，哪个对应键盘输入字符？ 答：根据P53Precede()函数可知，?1对应栈顶元素。因此： 答：①无风险，因为删除语句中没有free(p)操作，且链表的合并无需删除结点，只需重链指针。 ② 可以颠倒次序，但会繁琐些，因为InsFirst的入口参数qb还得作为输出参数被送出来。 若 栈顶元素 操作符，则退栈、计算，结果压入OPND栈； 栈顶元素= 操作符且不为‘#’，脱括号（弹出左括号）； 栈顶元素 操作符，压入OPTR栈。 3.2 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 3.2 队列 与同线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队列，判队空或队满等操作。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （头删尾插） 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。 表尾即 an 端，称为 队尾 ； 表头即 a1 端，称为队头。 它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 插