精品计算机课件《C语言数据结构》第章栈和队列.pptVIP

若某种高级语言没有指针类型，也能实现链式存储和运算 数据结构涵盖的内容： 第三章 栈和队列 3.1 栈（Stack） 3.2 队列（Queue） 1. 定义 例1（严题集3.1）一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？ 例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 例3： 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b Q1：堆栈是什么？它与一般线性表有什么不同？ Q2：顺序表和顺序栈的操作有何区别？ Q3：什么叫“向上生成”的栈？ “向下生成”又是何意？ Q4：为什么要设计堆栈？它有什么独特用途？ 例6：设正整数a的前驱为PRIOR(a)，后继为NEXT(a)，用递归算法计算a+b。 编制递归算法要注意些什么？ 递归进行是有条件的。一般常把判断语句加在递归语句以前。 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出‘B’ 链栈的入栈操作和出栈操作（教材省略，教师补充） 栈的应用举例 第2章作业2.8 2.10 2.21 2.22 2.34 2.35 通知 1、下周二交第2章作业 习题集2.8 2.10 2.21 2.22 2.34 2.35 2、实验安排 1. 定义 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出B 链栈的入栈操作和出栈操作（教材省略，教师补充） 栈的应用举例 四川科技馆展项－－梵天之塔 堆栈用途？ 今天课程到此结束 通知 1、今晚交第2章作业 习题集2.8 2.10 2.21 2.22 2.34 2.35 2、实验安排 调用函数/子程序非它莫属； 递归运算的有力工具（汉诺塔）； 用于保护现场和恢复现场； 简化了程序设计（表达式求值）。 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 ; 关于整个链队的总体描述 链队中任一结点的结构 因简单而先介绍 1.链队列 讨论： 空链队的特征？ Q (队尾) (队首) front a1 a2 a3 ^ rear p front ^ rear ③ 怎样实现链队的入队和出队操作？ ② 链队会满吗？ front=rear 一般不会，因为删除时有free动作。除非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-