首页计算机计算机基础程序设计基础与数据结构 05 第四章 栈和队列.pptx

05 第四章 栈和队列.pptx

页数:26页文件大小:159.8 KB来源: 程序设计基础与数据结构ppt课件

本课件讲解两种运算受限的线性表:栈与队列。先给出栈的先进后出特性与五项基本操作,分别用顺序栈和链栈实现;再说明栈在函数调用、递归工作栈与迷宫回溯求解中的应用;随后介绍队列的先进先出特性、假溢出问题与循环队列设计,以及链队列的实现,最后以打印任务管理器为例说明队列的应用。

第四章章节导览页,说明栈和队列与线性表的逻辑关系与运算关系,并列出五节内容
栈的定义与结构页,说明插入删除限定在表尾进行并展示栈底栈顶与进出栈方向
栈的五项基本操作清单页,列出初始化、进栈、出栈、取栈顶元素与判空
查看本课件的文字版(共 26 页,供检索与复制)

第1页:第四章 栈和队列

第四章 栈和队列

  • 从逻辑关系的角度来看,栈和队列与线性表相同。
  • 从运算的角度来看,栈和队列的操作是线性表操作的子集。

本章内容:4.1 栈、4.2 栈的应用、4.3 队列、4.4 队列的应用、4.5 小结。

第2页:栈的定义与结构

4.1 栈

栈的定义
栈是指插入和删除都限定在表尾进行的线性表;在栈中允许插入、删除的表尾叫做栈顶,不允许插入、删除的表头叫做栈底。

假设栈 Stack =(a1,a2,…,an),则 a1 为栈底元素,an 为栈顶元素。进栈次序为 a1,a2,…,an;出栈次序为 an,an-1,…,a1。

栈中元素按先进后出的顺序处理,所以栈又称为先进后出(FILO-First In Last Out)的线性表。(图4-1-1 栈的结构示意)

第3页:栈的基本操作

栈的基本操作:

  1. 初始化:生成一个新的空栈。
  2. 进栈:向栈中加入一个新的元素,作为新的栈顶。
  3. 出栈:取得栈顶元素,并将它从栈中删除。
  4. 取栈顶元素:取得栈顶元素的值。
  5. 判空:判别一个栈是否为空,若为空返回 TRUE,否则返回 FALSE。

第4页:顺序栈

4.1.1 顺序栈

  • 栈的顺序存储结构简称顺序栈。
  • 利用一组地址连续的存储单元来存放栈中的数据元素。
  • 在C语言中,通常用一维数组来定义顺序栈。
  • 设置栈顶指针来指示栈顶元素的位置。

第5页:顺序栈的类型定义

顺序栈的存储结构定义:

#define STACK_SIZE 100 typedef struct stack_st { ELEMENT data[STACK_SIZE]; int top; } STACKE;

在C语言中数组下标从0开始,所以空栈的标志是 top = -1。

图4-1-2 栈操作示例:(a) 表示空栈,(b) 栈中插入 A,(c) 依次插入 B、C、D 的情况,(d) 从栈中弹出 D、C 后的情况。

第6页:顺序栈的操作实现

顺序栈五种基本操作的实现:初始化、进栈、出栈、取栈顶元素、判空。

第7页:链栈

4.1.2 链接栈

  • 链栈结构形式与单链表相似。
  • 链栈的栈顶指针就是链表的头指针,结点的插入和删除操作只能在此进行。
  • 链栈的所有操作只针对链栈的头部,故链栈不设头结点。

第8页:链栈的结点定义

链栈的结点结构定义:

typedef struct node_st { ELEMENT data; struct node_st *next; } NODE;

图4-1-3 链栈的结构示意:栈顶为 an,栈底为 a1,结点形式为 data | next。

第9页:链栈的操作实现

链栈五种基本操作的实现:初始化、进栈、出栈、取栈顶元素、判空。

第10页:栈的应用概览

4.2 栈的应用

  • 函数调用与栈
  • 递归与栈
  • 迷宫求解

第11页:函数调用与栈

4.2.1 函数调用与栈

  • 栈在函数调用、递归、语法分析、表达式求值等的实现中都要用到。
  • 在函数调用中,函数调用——返回关系的控制就是通过栈来实现的。
  • 在递归过程中,子程序间的信息传递和控制转移也是通过栈来实现的。

第12页:递归与栈

4.2.2 递归与栈

  • 递归是一种重要的程序设计方法:如果在一个函数、过程或数据结构的定义内部又直接或间接地应用了定义本身,则称它们是递归的。
  • 递归可以分为直接递归和间接递归两种。
  • 直接调用时,在函数内有调用本函数的语句,当执行到这条语句时,程序将转到本函数的第1行重新开始执行。
  • 间接调用时,在 f1 函数内先调用 f2 函数,而在执行 f2 函数中又有调用 f1 的语句。

(图4-5 函数的递归调用:直接调用本函数与间接调用本函数)

第13页:递归工作栈的状态变化

一个递归函数的运行类似于多个函数的嵌套调用:系统设定一个递归工作栈,每进入一层递归调用时,将相应的信息(函数返回值及返回地址)压入栈顶,而每退出一层递归时,栈顶元素就是要返回的地址。

图中以 power(3) 为例给出六个阶段的工作栈状态:(1) 调用 power(3);(2) 调用 power(2);(3) 调用 power(1);(4) 从 power(1) 返回;(5) 从 power(2) 返回,得 f = 6;(6) 从 power(3) 返回。(图4-6 函数递归调用与返回时工作栈的状态变化示意图)

第14页:迷宫求解

4.2.3 迷宫求解

  • 所谓迷宫求解就是要在迷宫中寻找一条从出口到入口的路径。
  • 采用的是一种试探性的搜索方法:从入口出发,沿着某一方向向前搜索,如果有路可走就继续前进,否则沿原路退回一步,重新选择新的方向,再继续搜索。
  • 如此重复,直到到达出口或者回退到入口(表明迷宫中无路径)。
  • 为了保证在搜索过程中能沿原路回退,需要用一个先进后出的数据结构——栈,来保存搜索过程中走过的路径。

第15页:队列的定义与结构

4.3 队列

队列的定义
队列也是一种运算受限的线性表,它的插入在表的一端,删除在表的另一端;允许插入的一端叫做队尾,允许删除的一端叫做队头。

设队列 Queue = (a1, a2, ..., an),则 a1 就是队头元素,an 是队尾元素。队列是一种先进先出(FIFO-First In First Out)的线性表,元素的插入次序与删除次序均为 a1, a2, ..., an。(图4-3-1 队列结构示意)

第16页:队列的基本操作与存储

队列的基本操作:

  1. 初始化:初始化一个新的空队列。
  2. 判空:判别一个队列是否为空。
  3. 入队列:将一个新元素插入在队尾。
  4. 出队列:删除队头元素,并返回它的值。
  5. 取队头元素:取得队头元素的值。

队列的存储:顺序存储结构、链式存储结构。

第17页:顺序队列的类型定义

4.3.1 队列的顺序存储结构:采用连续的存储单元来存放队列中的元素,简称为顺序队列;在C语言中顺序队列用一个一维数组来存放。

  • 设置两个指针:队头指针与队尾指针。
  • 规定队头指针指向队头元素在一维数组中实际位置的前一个位置,队尾指针指向队尾元素在一维数组中的实际位置。
#define QUEUE_SIZE 100 typedef struct queue_st { ELEMENT data[QUEUE_SIZE]; int head, tail; } QUEUE;

第18页:顺序队列的操作实现

顺序队列五种基本操作的实现:初始化、判空、入队列、出队列、取队头元素。

第19页:循环队列与假溢出

循环队列:

  • 经过 QUEUE_SIZE 次入队列操作后,tail 指针必定指在数组的最高端;此时不论队列还剩多少元素,都认为队列已满,不能再插入新的元素。而实际上经过出队列操作后,数组的低端必定空出很多位置,这种情况是假溢出。
  • 可以把此队列设计成为循环表,称为循环队列。
  • 假设数组的首尾相连,data[0] 接在 data[QUEUE_SIZE-1] 之后;当 tail 等于 QUEUE_SIZE-1 时,如果数组的低端仍有空闲,则下一个元素就插入在 data[0] 中,数据元素的位置通过取模操作求得。
  • 约定循环队列的队头指针指向队头元素在数组中实际位置的前一个位置,队尾指针指向队尾元素在数组中的实际位置。

第20页:循环队列的存储示意

循环队列的存储示意:数组下标 0 至 QUEUE_SIZE-1 首尾相连成环,队头指针 head 指向队头元素的前一位置,队尾指针 tail 指向队尾元素。(图4-3-3、图4-3-4 循环队列示意图)

第21页:循环队列的空满判别

循环队列存储结构上队列的五种基本操作的实现:初始化、判空(含判满)、入队列、出队列、取队头元素。

第22页:链队列

4.3.2 链队列

  • 链队列的组织形式与单链表类似。
  • 链队列的队头指针指向队头元素所在的结点,队尾指针指向队尾元素所在的结点。
  • 插入操作只在队尾进行,删除操作只在队头进行。

第23页:链队列的结构定义

链队列的结构定义:

typedef struct node_st { ELEMENT data; struct node_st *link; } NODE; typedef struct queue_st { NODE *front, *rear; } QUEUE;

(图4-3-5 链队列的结构示意)

第24页:链队列的操作实现

链队列五种基本操作的实现:初始化、判空、入队列、出队列、取队头元素。

第25页:打印任务管理器

4.4 队列的应用:打印任务管理器——打印任务按提交的先后顺序排队,先提交的任务先被处理,这正是队列先进先出特性的典型应用。

第26页:第四章小结

4.5 小结

  • 栈的定义、顺序栈、链接栈、栈的应用
  • 队列的定义、顺序队列、循环队列、链队列、队列的应用
顶部目录