页数:26页文件大小:159.8 KB来源: 程序设计基础与数据结构ppt课件
本课件讲解两种运算受限的线性表:栈与队列。先给出栈的先进后出特性与五项基本操作,分别用顺序栈和链栈实现;再说明栈在函数调用、递归工作栈与迷宫回溯求解中的应用;随后介绍队列的先进先出特性、假溢出问题与循环队列设计,以及链队列的实现,最后以打印任务管理器为例说明队列的应用。
第四章 栈和队列
本章内容:4.1 栈、4.2 栈的应用、4.3 队列、4.4 队列的应用、4.5 小结。
4.1 栈
假设栈 Stack =(a1,a2,…,an),则 a1 为栈底元素,an 为栈顶元素。进栈次序为 a1,a2,…,an;出栈次序为 an,an-1,…,a1。
栈中元素按先进后出的顺序处理,所以栈又称为先进后出(FILO-First In Last Out)的线性表。(图4-1-1 栈的结构示意)
栈的基本操作:
4.1.1 顺序栈
顺序栈的存储结构定义:
#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 后的情况。
顺序栈五种基本操作的实现:初始化、进栈、出栈、取栈顶元素、判空。
4.1.2 链接栈
链栈的结点结构定义:
typedef struct node_st { ELEMENT data; struct node_st *next; } NODE;图4-1-3 链栈的结构示意:栈顶为 an,栈底为 a1,结点形式为 data | next。
链栈五种基本操作的实现:初始化、进栈、出栈、取栈顶元素、判空。
4.2 栈的应用
4.2.1 函数调用与栈
4.2.2 递归与栈
(图4-5 函数的递归调用:直接调用本函数与间接调用本函数)
一个递归函数的运行类似于多个函数的嵌套调用:系统设定一个递归工作栈,每进入一层递归调用时,将相应的信息(函数返回值及返回地址)压入栈顶,而每退出一层递归时,栈顶元素就是要返回的地址。
图中以 power(3) 为例给出六个阶段的工作栈状态:(1) 调用 power(3);(2) 调用 power(2);(3) 调用 power(1);(4) 从 power(1) 返回;(5) 从 power(2) 返回,得 f = 6;(6) 从 power(3) 返回。(图4-6 函数递归调用与返回时工作栈的状态变化示意图)
4.2.3 迷宫求解
4.3 队列
设队列 Queue = (a1, a2, ..., an),则 a1 就是队头元素,an 是队尾元素。队列是一种先进先出(FIFO-First In First Out)的线性表,元素的插入次序与删除次序均为 a1, a2, ..., an。(图4-3-1 队列结构示意)
队列的基本操作:
队列的存储:顺序存储结构、链式存储结构。
4.3.1 队列的顺序存储结构:采用连续的存储单元来存放队列中的元素,简称为顺序队列;在C语言中顺序队列用一个一维数组来存放。
#define QUEUE_SIZE 100 typedef struct queue_st { ELEMENT data[QUEUE_SIZE]; int head, tail; } QUEUE;顺序队列五种基本操作的实现:初始化、判空、入队列、出队列、取队头元素。
循环队列:
循环队列的存储示意:数组下标 0 至 QUEUE_SIZE-1 首尾相连成环,队头指针 head 指向队头元素的前一位置,队尾指针 tail 指向队尾元素。(图4-3-3、图4-3-4 循环队列示意图)
循环队列存储结构上队列的五种基本操作的实现:初始化、判空(含判满)、入队列、出队列、取队头元素。
4.3.2 链队列
链队列的结构定义:
typedef struct node_st { ELEMENT data; struct node_st *link; } NODE; typedef struct queue_st { NODE *front, *rear; } QUEUE;(图4-3-5 链队列的结构示意)
链队列五种基本操作的实现:初始化、判空、入队列、出队列、取队头元素。
4.4 队列的应用:打印任务管理器——打印任务按提交的先后顺序排队,先提交的任务先被处理,这正是队列先进先出特性的典型应用。
4.5 小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}