第3章栈和队列第3章栈和队列B(620KB).pptVIP

数据结构课程的内容 * 上堂课遗留问题讨论 * 教材P43中case1： DelFirst(hb,qb)；InsFirst(ha,qb)； 是先删除后插入，有无风险？这两条语句能否颠倒？ 2. 教材P53表3.1中，?1和?2哪个对应栈顶元素，哪个对应键盘输入字符？ 答：根据P53Precede()函数可知，?1对应栈顶元素。因此： 答：①无风险，因为删除语句中没有free(p)操作，且链表的合并无需删除结点，只需重链指针。 ② 可以颠倒次序，但会繁琐些，因为InsFirst的入口参数qb还得作为输出参数被送出来。 若 栈顶元素 操作符，则退栈、计算，结果压入OPND栈； 栈顶元素= 操作符且不为‘#’，脱括号（弹出左括号）； 栈顶元素 操作符，压入OPTR栈。 第三章 栈和队列 3.1 栈（Stack） * 3.2 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 定 义 * 3.2 队列 与同线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队列，判队空或队满等操作。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （头删尾插） 教材P59对队列有更详细定义： * 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。 表尾即 an 端，称为 队尾 ； 表头即 a1 端，称为队头。 它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 插入元素称为入队；删除元素称为出队。 队头 队尾 队列的抽象数据类型定义见教材Ｐ59－60 队列的存储结构为链队或顺序队 （常用循环顺序队） 链队列示意图 * 讨论： 空队列的特征？ Q (队尾) (队首) front a1 a2 a3 ^ rear p front ^ rear ③ 怎样实现入队和出队操作？ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next; 完整动作设计参见教材P61-62 ② 队列会满吗？ front=rear 一般不会，因为删除时有free动作。除非内存不足！ 顺序队示意图 * Q (队尾) (队首) front a1 a2 a3 data a4 0 . . . . . . . 99 rear ② 队列会满吗？ 很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。 ① 空队列的特征？ 约定：front=rear 队尾后地址 入队(尾部插入)：v[rear]=e; rear++; 出队(头部删除)：x=v[front]; front++; 讨论： 假溢出 有缺陷 ③ 怎样实现入队和出队操作？ 3.2 队列 问：什么叫“假溢出” ？如何解决？ 答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 * 3.2 队列 解决假溢出的途径———采用循环队列 * a3 a2 a1 0 1 2 3 N-1 rear front 循环队列（臆造） 顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案有三： ① 加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear ② 使用一个计数器记录队列中元素个数（即队列长度）； ③ 人为浪费一个单元，令队满特征为front=(rear+1)%N； * 队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度：L=（N＋rear－front）% N J2 J3 J1 J4 J5 front rear 选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。