栈·队列·链表_例题解读.ppt

栈·队列·链表 栈·队列·链表 栈·队列·链表 * 模板来自于 / * 模板来自于 * ——JYT 栈·队列·链表 * * 栈·队列·链表 内容提要 单调队列/栈 链表结构 队列结构 栈结构 数据结构概述 第一章 第二章 第三章 第四章 第五章 * * 栈·队列·链表 01 数据结构概述 Part One * * 栈·队列·链表 数据结构是数据的组织形式，可以用来表征特定的对象数据。 在计算机程序设计中，操作的对象是各式各样的数据，这些数据往往拥有不同的数据结构，例如数组、结构体、联合、指针和链表等。 而算法和数据结构具有千丝万缕的联系，计算机科学家尼克劳斯? 沃思（Niklaus Wirth）提出“数据结构+算法=程序”的著名公式，就是因为不同的数据结构所采用的处理方法不同，计算的复杂程度也不同，因此算法往往是依赖于某种数据结构的，即数据结构是算法实现的基础。 * * 栈·队列·链表 数据结构是计算机中对数据的一种存储和组织方式，同时也泛指相互之间存在一种或多种特定关系的数据的集合。数据结构是计算机艺术的一种体现， 合理的数据结构能够提高算法的执行效率，还可以提高数据的存储效率。 数据结构的分类 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。 * * 栈·队列·链表 线性结构 简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点： 线性结构是非空集。 线性结构有且仅有一个开始结点和一个终端结点。 线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。 栈、队列、数组和串等都是线性结构。 * * 栈·队列·链表 非线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 非线性结构是非空集。 非线性结构的一个结点可能有多个直接前趋结点和直接后继结点。 在实际应用中广义表、树结构和图结构等数据结构都是非线性结构。 * * 栈·队列·链表 常用的数据结构 在计算机科学的发展过程中，数据结构也随着发展。目前，程序设计中常用的数据结构包括如下几个。 数组（Array） 数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。 * * 栈·队列·链表 栈（stack） 栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。 * * 栈·队列·链表 队列（Queue） 队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。 * * 栈·队列·链表 链表（Linked List） 链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。 * * 栈·队列·链表 此外，还有树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）等，在以后的讲课中会具体讲解（反正不是我讲_）。 * * 栈·队列·链表 02 栈结构 Part Two * * 栈·队列·链表 例1：表达式求值（NOIp2013普及组T2） 【问题描述】 给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值，答案对10000取模。 【样例输入】 1+1*3+4 【样例输出】 8 【数据规模】 表达式中加法运算符和乘法运算符的总数≤100000 * * 栈·队列·链表 例2：等价表达式（NOIp2005提高组T4） 【问题描述】 JPY进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。这个题目手算很麻烦，因为JPY对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是JPY，