《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第05章 栈与队列》由会员分享，可在线阅读，更多相关《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第05章 栈与队列（35页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C+版）,叶核亚,数据结构（C+版）,第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计,数据结构（C+版）叶核亚,第5章 栈与队列,栈和队列是两种特殊的线性表。 5.1 栈 5.2 队列 5.3 递归,数据结构（C+版）叶核亚,5.1 栈,5.1.1 栈的定义 5.1.2 栈的抽象数据类型 5.1.3 顺序栈类 5.1.4 链式栈类 5.1.5 栈的应用,数据结构（C+版）叶核亚,5.1.1 栈的定义,栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的
2、一端进行。 允许操作一端称为栈顶（top），不允许操作的一端称为栈底（bottom）。 栈顶的当前位置是动态的，标识栈顶当前位置的变量称为栈顶指针。 栈中插入数据元素的过程称为入栈（push），删除数据元素的过程称为出栈（pop）。 当栈中没有数据元素时称之为空栈。,图4.1 栈结构,数据结构（C+版）叶核亚,5.1.2 栈的抽象数据类型,栈的数据元素 栈的基本操作 栈的初始化，设置栈状态为空。 判断栈的状态是否为空。 判断栈的状态是否已满。 入栈：将数据元素插入栈中作为新的栈顶数据元素的过程。在入栈之前必须判断栈的状态是否已满，如果栈不满，则接收新数据元素入栈，否则产生上溢错误（overfl
3、ow）。 出栈：取出当前栈顶数据元素，下一个数据元素成为新的栈顶数据元素的过程。在出栈之前，必须判断栈的状态是否为空。如果栈的状态为空，产生下溢错误（underflow）。 获得栈顶数据元素，此时该数据元素未出栈。,数据结构（C+版）叶核亚,5.1.3 顺序栈类,数据结构（C+版）叶核亚,5.1.4 链式栈类,链式栈的结点类 template class OnelinkNode2 /单链表结点类，模板 public: T data; /数据元素域 OnelinkNode2 *next; /指针域，指向后继结点的指针 OnelinkNode2(T,数据结构（C+版）叶核亚,2. 链式栈类的设计与
4、实现,数据结构（C+版）叶核亚,链式栈的基本操作图,数据结构（C+版）叶核亚,5.1.5 栈的应用,1栈是嵌套调用机制的实现基础 2实现深度遍历算法时使用栈 3利用栈以非递归方式实现递归算法,数据结构（C+版）叶核亚,例5.2 判断表达式中括号是否匹配,数据结构（C+版）叶核亚,判断表达式中括号是否匹配的算法描述,数据结构（C+版）叶核亚,例5.3 使用栈计算表达式的值,数据结构（C+版）叶核亚,后缀表达式求值过程,数据结构（C+版）叶核亚,将中缀表达式变为后缀表达式时运算符栈状态的变化情况,数据结构（C+版）叶核亚,后缀表达式求值过程中数据栈状态的变化情况,数据结构（C+版）叶核亚,5.2
5、队列,5.2.1 队列的定义 5.2.2 队列的抽象数据类型 5.2.3 队列的存储结构 5.2.4 顺序循环队列类 5.2.5 链式队列类 5.2.6 队列的应用,数据结构（C+版）叶核亚,5.2.1 队列的定义,队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。 向队列中插入元素的过程称为入队（enqueue），删除元素的过程称为出队（dequeue）。 允许入队的一端为队尾（rear），允许出队的一端为队头（front）。标识队头和队尾当前位置的变量称为队头指针和队尾指针。 当队列中没有数据元素时称作空队列。,数据结构（C+版）叶核亚,5.2.2 队列的抽象数
6、据类型,1队列的数据元素 2队列的基本操作 队列的初始化，设置队列状态为空。 判断队列的状态是否为空。 判断队列的状态是否已满。 入队：将数据元素从队尾处加入队列的过程。在入队之前必须判断队列的状态是否已满，如果队列不满，则接收新数据元素入队，队列满时数据元素不能入队，产生上溢错误（overflow）。 出队：从队头处取出数据元素的过程。在出队之前，必须判断队列的状态是否为空。队列空时，取不到元素，产生下溢错误（underflow）。,数据结构（C+版）叶核亚,5.2.3 队列的存储结构,1队列的顺序存储结构,数据结构（C+版）叶核亚,2顺序循环队列,数据结构（C+版）叶核亚,5.2.4 顺序
7、循环队列类,数据结构（C+版）叶核亚,例5.4 使用顺序循环队列的基本操作,数据结构（C+版）叶核亚,5.2.5 链式队列类,数据结构（C+版）叶核亚,链式队列的基本操作图,数据结构（C+版）叶核亚,5.2.6 队列的应用,1处理等待问题时系统设立队列 队列具有“先进先出”的特性，当需要按一定次序等待时，系统需设立一个队列。 2实现广度遍历算法时使用队列 实现广度遍历算法，如按层次遍历二叉树、以广度优先算法遍历图，都需要使用队列。详细算法将在以后的章节中介绍。,数据结构（C+版）叶核亚,例5.5 解素数环问题,数据结构（C+版）叶核亚,5.3 递归,1问题的定义是递归的 2算法是递归的 如果能
8、够分解成几个相对简单且解法相同或类似的子问题时，只要解决了子问题，那么原问题就迎刃而解，这就是递归求解。例如，5！=54！。 当分解后的子问题可以直接解决时，就停止分解。这些可以直接求解的问题称为递归结束条件。例如，1！=1。 根据递归定义，编写能够直接反映递归定义的递归函数来求解。,数据结构（C+版）叶核亚,例5.6 求n！,数据结构（C+版）叶核亚,例5.7 打印数字塔,数据结构（C+版）叶核亚,3数据结构是递归的,将单向链表结点类的next链与指向链表第1个结点的head递归定义为：,数据结构（C+版）叶核亚,例5.8 实现递归定义的单链表,数据结构（C+版）叶核亚,实习4,1实验目的：使用栈、队列或递归算法求解问题 2题意 （1）走迷宫 一个迷宫可以看成一个二维数组，如图所示。每个迷宫都有一个入口和一个出口，其中白色单元表示通路，黑色单元表示路不通。试寻找一条通过迷宫的路径，从入口进入迷宫，每次移动只能从一个白色单元移到相邻的白色单元，直到移至出口时为止。,数据结构（C+版）叶核亚,（2）骑士游历,在国际象棋的棋盘（8行8列）上放置一“马”，按“马走日字”的规则，马要到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0，y0），编程探索出一条路线，沿这条路线马能遍历棋盘上的所有格子。这就是“骑士游历”问题。,
