《栈·队列·链表_例题概要》由会员分享，可在线阅读，更多相关《栈·队列·链表_例题概要（25页珍藏版）》请在金锄头文库上搜索。
1、JYT,栈队列链表,2019/10/28,1,栈队列链表,内容提要,单调队列/栈,链表结构,队列结构,栈结构,数据结构概述,第一章,第二章,第三章,第四章,第五章,2019/10/28,2,栈队列链表,01,数据结构概述,Part One,2019/10/28,3,栈队列链表,数据结构概述,数据结构是数据的组织形式，可以用来表征特定的对象数据。 在计算机程序设计中，操作的对象是各式各样的数据，这些数据往往拥有不同的数据结构，例如数组、结构体、联合、指针和链表等。 而算法和数据结构具有千丝万缕的联系，计算机科学家尼克劳斯 沃思（Niklaus Wirth）提出“数据结构+算法=程序”的著名公式，
2、就是因为不同的数据结构所采用的处理方法不同，计算的复杂程度也不同，因此算法往往是依赖于某种数据结构的，即数据结构是算法实现的基础。,2019/10/28,4,栈队列链表,数据结构概述,数据结构是计算机中对数据的一种存储和组织方式，同时也泛指相互之间存在一种或多种特定关系的数据的集合。数据结构是计算机艺术的一种体现， 合理的数据结构能够提高算法的执行效率，还可以提高数据的存储效率。 数据结构的分类 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。,2019/10/28,5,栈队列链表,数据结构概述,线性结构 简单地说，线性结构就是表中各个结点具有线
3、性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点： 线性结构是非空集。 线性结构有且仅有一个开始结点和一个终端结点。 线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。 栈、队列、数组和串等都是线性结构。,2019/10/28,6,栈队列链表,数据结构概述,非线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 非线性结构是非空集。 非线性结构的一个结点可能有多个直接前趋结点和直接后继结点。 在实际应用中广义表、树结构和图结构等数据结构都是非线性结构。,2019/10/28,7,栈队列链表,数据结构
4、概述,常用的数据结构 在计算机科学的发展过程中，数据结构也随着发展。目前，程序设计中常用的数据结构包括如下几个。 数组（Array） 数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。,2019/10/28,8,栈队列链表,数据结构概述,栈（stack） 栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来
5、存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。,2019/10/28,9,栈队列链表,数据结构概述,队列（Queue） 队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。,2019/10/28,10,栈队列链表,数据结构概述,链表（Linked List） 链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存
6、储结构在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。,2019/10/28,11,栈队列链表,数据结构概述,此外，还有树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）等，在以后的讲课中会具体讲解（反正不是我讲_）。,2019/10/28,12,栈队列链表,02,栈结构,Part Two,2019/10/28,13,栈队列链表,栈结构,例1：表达式求值（NOIp2013普及组T2） 【问题描述】 给定一个只包含加法和乘法
7、的算术表达式,请你编程计算表达式的值，答案对10000取模。 【样例输入】 1+1*3+4 【样例输出】 8 【数据规模】 表达式中加法运算符和乘法运算符的总数100000,2019/10/28,14,栈队列链表,栈结构,例2：等价表达式（NOIp2005提高组T4） 【问题描述】 JPY进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。这个题目手算很麻烦，因为JPY对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题
8、。假设你是JPY，能完成这个任务吗？,2019/10/28,15,栈队列链表,栈结构,例2：等价表达式（NOIp2005提高组T4） 这个选择题中的每个表达式都满足下面的性质： 表达式只可能包含一个变量“a”。 表达式中出现的数都是正整数，而且都小于10000。 表达式中可以包括四种运算“+”（加）、“-”（减）、“*”（乘）、“”（乘幂），以及小括号“(”、“)”。小括号的优先级最高，其次是“”，然后是“*”，最后是“+”和“-”。“+”和“-”的优先级是相同的。相同优先级的运算从左到右进行。 幂指数只可能是1到10之间的正整数（包括1和10）。 表达式内部，头部或者尾部都可能有一些多余的空
9、格。,2019/10/28,16,栈队列链表,栈结构,例2：等价表达式（NOIp2005提高组T4） 【样例输入】 (a+1)2 3 (a-1)2+4*a a+1+a a2+2*a*1+12+10-10+a-a 【样例输出】 AC,2019/10/28,17,栈队列链表,03,队列结构,Part Three,2019/10/28,18,栈队列链表,04,链表结构,Part Four,2019/10/28,19,栈队列链表,链表结构,例3：梦幻布丁（HNOI2009） 【问题描述】 N个布丁摆成一行，进行M次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。例如颜色
10、分别为1,2,2,1的四个布丁一共有3段颜色。 【数据范围】 N,M 100000,2019/10/28,20,栈队列链表,链表结构,例3：梦幻布丁（HNOI2009） 【样例输入】 4 3 1 2 2 1 2 1 2 1 2 【样例输出】 3 1,2019/10/28,21,栈队列链表,05,单调队列/栈,Part Five,2019/10/28,22,栈队列链表,单调队列/栈,例4：棋盘制作（ZJOI2007） 【问题描述】 给一个N*M的01矩阵，求最大01相间子矩阵面积。 【样例输入】 3 3 1 0 1 0 1 0 1 0 0 【样例输出】 6,2019/10/28,23,栈队列链表,【数据范围】 N,M2000,06,小小结,Part Six,2019/10/28,24,栈队列链表,2019/10/28,25,栈队列链表,Good Luck & Have Fun,
