《数据结构第3章其它线性结构》由会员分享，可在线阅读，更多相关《数据结构第3章其它线性结构（146页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 第3章 其它线性结构,第3章 其它线性结构,栈,队列,串,数组,广义表,3.1 栈,栈（Stack）是只允许在表的同一端进行插入和删除操作的特殊的线性表。,（进栈、压入）,（退栈、弹出）,当栈中没有任何元素时称为空栈。,3.1 栈,由于栈的插入和删除操作总是在栈顶进行，所以，后进去的元素一定先出来。因而，栈又被称为后进先出（Last In First Out）的线性表，简称LIFO表。,1,3,2,1,2,3,2,1,3,3,2,1,2,3,1,若输入序列是1,2,3， 则可能的输出序列有 哪些？,思考：,3.1 栈,栈的抽象数据类型定义,栈的存储结构及操作实现,栈的应用举例,
2、3.1.1栈的抽象数据类型定义,3.1.2 栈的存储结构及操作实现,栈是一种操作受限的特殊的线性表。因此，线性表的存储结构同样适用于栈，故栈也可以采用顺序存储结构和链式存储结构。,顺序栈,链栈,栈的顺序存储表示顺序栈,栈的顺序存储表示顺序栈用一维数组来模拟连续的存储空间。将0下标端设为栈底，栈的第i个元素存放在i-1下标位置。设置一个栈顶指针（或称指示器）top来指示栈顶位置。初始时，栈为空，置top = 0；入栈时，top加1；出栈时，top减1；当栈满时，top等于数组空间大小。因此，top总是指在栈顶元素的后一个下标位置。,顺序栈类定义,顺序栈的基本操作的实现,1. 栈初始化,顺序栈的基
3、本操作的实现,2.销毁栈,顺序栈的基本操作的实现,3.清空栈,顺序栈的基本操作的实现,4.判栈空,顺序栈的基本操作的实现,5.求长度,顺序栈的基本操作的实现,6. 取栈顶元素的值,顺序栈的基本操作的实现,7. 入栈,e,顺序栈的基本操作的实现,8. 出栈,对于顺序栈，应注意： 入栈时，应首先判断栈是否已满。若栈满，则需要先扩展空间。 出栈和取栈顶元素时，必须保证栈不空。若栈空，则不能进行相应操作，否则会导致异常错误。在上述顺序栈的基本操作中，它们的时间复杂度均为O(1)。,顺序栈,栈的链式存储表示链栈,可用不带头结点的单链表来表示链栈。当栈非空时，top指向栈顶元素结点；而当栈为空时，top为
4、空指针。,链栈类定义,链栈的基本操作的实现,1. 栈初始化,链栈的基本操作的实现,2.销毁栈,链栈的基本操作的实现,3.清空栈,链栈的基本操作的实现,4.判栈空,链栈的基本操作的实现,5.求长度,链栈的基本操作的实现,6.取栈顶元素的值,链栈的基本操作的实现,7.入栈,链栈的基本操作的实现,8.出栈,在链栈中，由于元素的存储空间是在需要时通过new运算符动态分配的，因此，正常情况下，不会出现栈满的情形，除非内存中没有空闲的存储空间可供分配。在链栈的操作中，栈的销毁、清空、求长度操作的时间复杂度为O(n)，因为需要对链表的每一个元素结点进行处理。其余操作的时间复杂度为O(1)。,链栈,3.1.3
5、 栈的应用举例,回文判断,迷宫问题,表达式求值,递归和汉诺塔问题,3.1.3 栈的应用举例回文判断,【例3.1】 回文判断 所谓回文，是指一个字符串的字符序列（不包括空格）顺读和逆读是一样的。 例如：“dad“、“mum“、“noon“、“was it a cat i saw“都是回文，而“good“，“so so“则不是。,本例读入一个字符串，过滤字符串中的空格，然后检查其是否回文。 可以用栈来处理。对去掉了空格的串通过两遍扫描来检查其是否回文。第一遍扫描，将每个字符压入栈，形成一个逆序的串。第二遍扫描，将原串中的每一个字符与从栈中弹出的字符作比较，若字符不同，则结束处理，该串不是回文。若直
6、到栈空每一对比较的字符都相同，则该串是回文。,程序请见教程 P.55,3.1.3 栈的应用举例迷宫问题,【例3.2】 迷宫问题 找出一条从迷宫的入口到出口的通路（如果存在通路）。,用一个二维数组模拟迷宫地图，如图(A)所示，0表示可以通行，1表示墙壁，无法通过。为了方便处理边界，可以在迷宫的四周加设围墙，如图(B)所示。,图(A) 迷宫地图,图(B) 加设围墙后的迷宫地图,迷宫问题,在迷宫中行进时必须遵循三个原则： 1. 每一步只走一格； 2. 遇到死胡同时退回一步，看是否有其他的路可以走； 3. 走过的路不会再走第二次。,用回溯法来求解迷宫问题: 首先从入口出发，按东南西北的次序依次向下一步
7、探索，若未走过且能通过，则前进一步进入下一位置；否则试探下一个方向。若所有的方向均没有通路，则将该点标为死胡同并沿原路退回到前一步，再换下一个方向继续试探。直到找到一条通路，或无路可走返回到入口。,为此，程序在搜索迷宫出口的过程中不但要记录走过的路径，还必须判断下一步应该往哪个方向走，可以选择的方向有4个，分别为东（右）、南（下）、西（左）、北（上）。,迷宫问题,在求解过程中，为了能够退回到前一步以便继续向下一个方向探索前进，需要用一个栈来保存当前所走线路沿途的每一个位置的坐标以及从该位置前进的方向，而栈顶的位置便是当前的位置。当到达出口时，栈中从底到顶即为一条由入口到出口的通路。路径上的每一
8、步到达的位置用序号（从1开始）编排，称为足迹。若存在从入口到出口的路径，则程序以足迹的形式输出一条路径。,程序请见教程 P.57,3.1.3 栈的应用举例表达式求值,【例3.3】 表达式求值 求一个表达式的值是程序设计语言编译程序中的一个基本问题，实现表达式的求值是栈的一个典型应用。,在这里，仅讨论最基本的算术四则运算：（加）、（减）、（乘）、（除），以及为了强调优先计算的括号。,表达式可定义为（“:=”为定义符）： 表达式 := 运算数 := 无符号整数 | 表达式 | (表达式) 运算符 := + | | * | / | ( | ) | =,表达式求值,在此，把一个运算数或一个运算符均称为
9、一个元素。,算术四则运算的规则为： （1）先乘除、后加减； （2）同级运算时先左后右； （3）先括号内，后括号外。,算法设置了两个栈：,(1)运算数栈（OPRD）：存放处理表达式过程中的运算数。,(2)运算符栈（OPTR）：存放处理表达式过程中的运算符。,表达式求值,假设表达式语法正确，并以“=”结束。算术表达式求值的算法如下： 1. 初始化运算数栈和运算符栈；将运算符“=”压入运算符栈； 2. 读入一个元素； 3. 当元素不为“=”或运算符栈顶不为“=”时，循环执行：若元素是一个运算数，则将其压入运算数栈，读入下一个元素；若元素是运算符(op2)，则将运算符栈的栈顶运算符(op1)与运算符o
10、p2比较优先级（运算符间的优先关系见P.62 表3.1）：若op1op2，则从运算符栈弹出运算符给op，并先后从运算数栈中弹出两个运算数给y和x，计算xy（如果是除运算且除数为0，则报错并结束算法）的值并将结果压入运算数栈。直到op1和op2均为“=”。 4. 运算数栈的栈顶元素就是求得的表达式的值。,程序请见教程 P.62,表达式求值,算法的计算过程举例:,5 + ( 6 - 4 / 2 ) * 3 =,运算数栈,运算符栈,_,5,=,_,+,_,(,_,6,_,-,_,4,_,/,_,_,/,2,4,2,=2,2,-,2,6,=4,4,_,*,_,3,_,*,3,4,=12,12,+,7,
11、12,5,=17,17,3.1.3 栈的应用举例递归和汉诺塔,在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自身（即递归）。,函数的调用和返回是利用栈来完成的。系统为运行的程序设置一个工作栈，当执行调用语句时，系统先把有关当前函数的必要信息（包括返回地址、实参、局部变量等信息）组成一个活动记录，保存到栈中，然后才去执行被调函数。当被调函数执行完后，再从栈中弹出一个活动记录，根据其中的返回地址，将控制转移回调用函数，并恢复当前信息。当有多个函数嵌套调用时，按照“后调用先返回”的原则来处理。,递归和汉诺塔,以下是函数调用和返回时工
12、作栈的变化示意图：,一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调函数是同一个函数。,递归和汉诺塔,【例3.4】汉诺塔问题,传说婆罗门圣殿（Temple of Brahman）里有一个塔台，台上立有3根钻石柱子A，B和C，在A柱上插了64个金圆盘，每一个圆盘都比其下面的略小一些。教士们需要将A柱上的圆盘移到C柱上。,移动的规则是： 1. 一次只能移动一个圆盘； 2. 圆盘可以移到A、B和C中的任一个柱子上； 3. 任何时候大盘都不能放到小盘的上面。,汉诺塔问题,这样，问题就变成了将n 1个圆盘从B柱移到C柱了。这个问题与n个圆盘的问题具有相同的特性，只是问题规模减小了1，因
13、此可以用同样的方法求解。,用计算机来完成这个任务可以很方便地用递归来求解。设A柱上最初有n个圆盘，求解的方法是： 如果n = 1，则将这个圆盘直接从A柱移到C柱。否则，执行以下3步： 1. 先将A柱的上面n - 1个圆盘移到B柱； 2. 将A柱上最大的圆盘移到C柱； 3. 将B柱上的n - 1个圆盘移到C柱。,汉诺塔问题,下面以4个圆盘为例，移动过程为：,汉诺塔问题,递归算法如下：,汉诺塔问题,以hanoi(3, a, b, c)为例，递归函数hanoi执行过程中递归工作栈的变化情况为：,汉诺塔问题,递归和汉诺塔,递归函数结构清晰，易于理解，系统会自动实现和管理递归工作栈，给编程带来很大的方便
14、。,从以上讨论可知，递归函数的执行是通过栈来实现的。实际上，借助栈也可以将一个递归算法（函数）改写为一个非递归算法（函数）。,3.2 队列,队列（Queue）是一种只允许在表的一端插入元素，在另一端删除元素的特殊的线性表。,当队列中没有任何元素时称为空队列。,3,2,1,2,3,1,对于队列，先进入的元素将先被删除出队列，因此队列又被称为先进先出（First In First Out）的线性表，简称FIFO表。,3.2 队列,队列的抽象数据类型定义,队列的存储结构及操作实现,队列的应用举例,3.2.1队列的抽象数据类型定义,3.2.2 队列的存储结构及操作实现,和栈类似，队列也是一种操作受限的
15、特殊的线性表，同样可以采用顺序存储结构和链式存储结构来表示队列。,循环队列,链队列,队列的顺序存储表示循环队列,队列的顺序存储表示循环队列队列的顺序存储表示同样是利用一维数组来实现。为了方便队列的插入和删除操作，需要设置两个变量front，rear分别用来指示队列的队头和队尾元素的位置，称为队头指针和队尾指针（或称队头指示器和队尾指示器）。,约定：初始化队列时，置front = rear = 0。,每当一个元素从队尾入队时，先将元素放在rear所指的位置，然后rear加；而每当一个元素从队头出队时，将front加。因此，当队列非空时，rear总是指向队尾元素的后一个位置，而front总是指向队
16、头元素位置。,队列的顺序存储表示循环队列,队列的入队、出队示意图：,从图中可以发现： (1)在状态(a)和(d)时，队列均为空，它们的共同特点是front=rear，因此可以以此作为判断队列空的条件。 (2)在状态(e)下，rear已经到了数组的外面，说明队尾元素已经放到数组的最后一个元素位置了，如果再有元素入队就会出现数组越界。但数组前端还有空余位置可以存放入队的元素。这种现象称为“假溢出”。,队列的顺序存储表示循环队列,解决假溢出的一种有效方法是将队列的数组看成头尾相接的环状空间，当队尾元素放到数组的最后一个位置时，如需入队就把新元素接着存放在数组的0下标位置，这样的队列称为循环队列。如下图所示：,队列的顺序存储表示循环队列,假设用于存储队列的一维数组大小为size，在这样的循环队列中，需要注意：,(1)前面已经提到，入队时rear需后移，而出队时front需后移。但它们都应在0到size-1范围内移动，若移到size位置时应回到0位置。分别可以用如下语句来实现：rear = (rear + 1) % size;front = (front + 1) % size;,
