数据结构第三章-1.ppt

第三章 栈和队列,栈（Stack） 队列（Queue） 定义 逻辑结构 存储结构 运算规则 实现方式,汉诺（ Hanoi）塔: 传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。,移动时的规则： 每次只能移动一个盘子； 只能小盘子在大盘子上面； 可以使用任一柱子。,当工作做完之后，就标志着世界末日到来! 。,. 堆栈的定义,3.1.1 堆栈的逻辑结构 堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（bottom）。 特点：先进后出（FILO）或后进先出（LIFO）,例如： 栈 S= (a1 , a2 , a3 , .,an-1 , an ),插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。,an称为栈顶元素,a1称为栈底元素,想一想：要从栈中取出a1，应当如何操作？,强调：插入和删除都只能在表的一端（栈顶）进行！,3.1.2 堆栈的抽象数据类型,ADT Stack Dset： 是一个只能从同一端插入或删除限定性的线性表（e0,e1,en-1）。 Rset： 堆栈的一端（en-1）称为的栈顶（top），而另一端（e0）称为堆栈的栈底（bottom）。 OPSet： ,OPSet： CreatStack()/构造空堆栈 IsEmpty() /为空返回true，否则返回false IsFull () /堆栈满返回true，否则返回false GetTop() /返回栈顶元素 Push(x) /向堆栈中压入元素 Pop(x) /从堆栈中弹出元素,Push()insert()，即在线性表的末端插入一个元素。 Pop() delete(),删除最后一个元素。 栈空时，若再执行pop操作就是一个错误，发生这种情况称之为下溢（underflow）。 栈已满，再执行压入堆栈运算，就是一个错误，称为上溢（overflow）。 GetTop()返回栈顶数据元素，但不删除栈顶上的元素，相当于查找线性表的最后一个数据元素。,如同线性表一样，堆栈也有顺序存贮和链式存贮两种存贮方式。 在不同的存贮方式下，上述运算的执行过程是不相同的，下面就两种不同的存贮方式讨论堆栈运算的实现。,3. 堆栈的顺序存储及操作,3.2.1 堆栈顺序存储 堆栈顺序存储方式: 是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保证堆栈数据元素逻辑上的有序性。 堆栈占用的第一个存储单元的地址，就是堆栈的首地址，也是堆栈中栈底元素（e0）存放的位置。,栈顶指针top,指向实际栈顶后的空位置，初值为-1,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为M top=-1,栈空，此时出栈，则下溢（underflow) top=M-1,栈满，此时入栈，则上溢（overflow),栈空,2.堆栈顺序存储结构定义,typedef struct EType *element; /一维数组 int top; /指向堆栈栈顶元素 int MaxSize; /可存储的最多数据元素 Stack； Stack S，S1，S2；,viod CreatStack (Stack 堆栈栈顶指针设为-1（用户约定），即堆栈为空时，栈顶指针“指向”栈底空间的前面。,3.2.2 堆栈顺序存储结构下的操作,2.判断堆栈是否为空或为满,bool IsEmpty(Stack ,4.返回栈顶元素的值,Status GetTop(Stack ,Status Push(Stack ,5.进栈,6.出栈,Status Pop(Stack ,Q1：堆栈是什么？它与一般线性表有什么不同？,堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进”插入=压入=Push（an+1),“出”删除=弹出=Pop(an),Q2：顺序表和顺序栈的操作有何区别？,写入：Si= ai 读出： e= Si,压入(PUSH): S+top=an+1 弹出( POP) : e=Stop- -,an+1,以线性表 S= (a1 , a2 , . , an-1 , an )为例,前提：一定要预设栈顶指针top,3.3 堆栈的链式存储及操作,3.3.1 堆栈的链式存储 。 特点:是用物理上不一定相邻的存储单元来存储堆栈的元素，附加一个指针域也叫链域, 保证堆栈之间的逻辑上的连续性。,表头链接域top始终指向栈顶结点，即链表的第一个结点。对链式栈，一般不存在栈满问题，除非存储空间全部被耗尽； 链式栈空表现为链式栈的表头结点链接域top的值为空，即链表为空。,3.3.2 链式栈的操作,1.构造链式栈 ChainStack* CreatStack(ChainStack *S) / 构造一个空栈 S=new ChainStack; S-top=NULL; return S; ,2.判断堆栈S是否为空,bool IsEmpty(ChainStack *S) if (!S-top) return true; return false; ,3.返回链式栈栈顶元素的值,将top所指的堆栈元素的值取出，但是top指针不改变 Status GetTop(ChainStack *S, EType ,4.x进栈的示意图如下：,核心语句：,Step 1：q-link= S-top; Step 2：S-top=q；,S-top,q-link,x 结点的生成方式： q=new StackNode; q-data= x ; q-link= ?,Status Push(ChainStack *S, EType ,5.b出栈的示意图如下：,核心语句：,Step 1 :StackNode *p = S-top; Step 2：S-top = p -link; Step 3： delete p;,S-top,5.出栈,Status Pop(ChainStack *S, EType ,void test(int ,断点地址入栈,例1阅读下列递归过程，说明其功能。,输入x10,输入x50,输入x2,输入x3,输入x4,输出sum0,输出sum0+x4,输出sumx4+x3,输出sum x4+x3 +x2,输出sum x4+x3 +x2+x1,注意：最先输入的数据 x1 最后才被累加,程序功能：对键盘输入数据求和，直到输入0结束,test(int ,test(int ,test(int ,运行副本1#,运行副本2#,运行副本3#,int sum; void test(int ,问题1:将test定义改为 void test(int sum),OK?,问题2:将test定义改为 void test(int OK?,例2一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,不存在输出序列3，1，2,讨论：有无通用的判别原则？,有！ 若输入序列是 ,PjPkPi (PjPkPi) ，一定不存在这样的输出序列 ,PiPjPk ,即对于输入序列1，2，3，不存在输出序列3，1，2,问: S4=?,例3：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,答： 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可。,例4：,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A）、D）可以， B）、C）不行。,答：,计算机某年的考研题,3.5 堆栈的应用,3.5.1 检验表达式中括号的匹配 在高级编译语言的翻译成低级语言的过程中，编译程序或解释程序所做的第一件工作就是语法正确性检验，其中检验的主要内容之一就是程序中左右括号是否的匹配。 如C语言中使用“”和“”作为一组语句的左右匹配符，表达式中“（”和“）”作为表达式运算时优先级的限定符等。,“（）（）（）” 。,如果取出的字符是一个左括号，就将它压入堆栈； 如果取出的字符不是括号字符，就再取表达式字符串中的下一个字符； 如果取出的字符是一个右括号，就从堆栈中退出一个左括号，并比较这两个括号： 如果取出的右括号是退出的栈顶左括号所对应的右括号，说明这两个括号匹配成功，继续取下一个字符； 如果取出的右括号不是退出的栈顶左括号所对应的右括号，说明这两个括号匹配失败，结束匹配过程，并报告出错；,表达式“a(b(c+d/e)-f)#”转换成后缀式的演算过程如下所示：,a ( b ( c + d / e ) - f ) #,#,a,(,b,(,c,+,d,/,e,/,/,+,+,-,f,-,#,3.5.2 表达式的求值,中缀表达式：操作数 【操作符】 操作数 前缀表达式：【操作符】 操作数 操作数 后缀表达式：操作数 操作数 【操作符】 运算符出现的顺序，就是表达式运算顺序。 如数学代数式： XY（ABC）D 的表达式的三种表示 中缀表达式： X / Y - (A + B * C) / D 前缀表达式： - / XY / + A * BCD 后缀表达式： XY / ABC * + D / -,XY（ABC）D,- / X Y / + A * B C D,- / X Y / + A * B C D,- / X Y / + A * B C D,- / X Y / + A * B C D,XY（ABC）D,X Y / A B C * + D / -,X Y / A B C * + D / -,X Y / A B C * + D / -,X Y / A B C * + D / -,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,3x5 + (6-8/4)x7后缀式“35684/-7+#”的演算过程如下所示：,3 5 6 8 4 / - 7 + #,3,5,5,5,3,3,= 15,15,6,8,4,/,4,8,= 2,4,8,2,-,2,2,6,6,= 4,4,7,7,7,4,4,= 28,28,+,28,15,=,43,43,result,43,括号匹配算法-顺序栈 括号匹配算法-链式栈,3.5.3 背包问题求解,假设有一个能容纳总体积为T的背包，另有n个体积分别是w1，w2，w3，wn 个物品，现在要在n件物品中选出若干件物品恰好装满背包，求出满足要求的所有解。 实现背包问题的思想是利用尝试回逆法。首先将所有的物品从从0到n-1编号，每个物品的体积值存储在一个对应的数组w中,以后物品就用物品的编号来代,算法的思想：,从0号物品开始顺序地选取物品; 如果当前选取的物品k装不进去（如装入，总体积大于T），则选取下一个物品（k+1），尝试装入。 如果尚未求得解，又已无物品可选，则说明上一个装入的物品不合适，就将堆栈退出一个背包编号，再从这个退出的编号的下一个编号物品尝试。 每求得一组解，就输出堆栈中的所有物品编号（输出不退栈，只是遍历所有堆栈中数据），然后，再退出栈顶数据，再从当前退出的编号的下一个编号物品尝试 直到堆栈为空且达到最大编号。,3.5.4 地图四染色问题求解,用不多于四种颜色为地图染色，使相邻的行政区不重色问题，是计算机科学中著名的定理“四染色”的典型应用 。 典型特征是： 尝试可能最终解决问题的各个步骤，并加以记录 而随后当发现某步骤进入“死胡同”不能解决问题时，就把它取出来删掉。 再取一个新的值尝试，直至尝试到所有数据全部被尝试过或找到所求结果。,一个关系矩阵Rnn来描述各区域之间的边界关系,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黄色 3# 红色 4# 绿色,void MapColor (int r , int n ) 改为: define N 100 void MapColor (int rN , int n ),程序设计 1。顺序堆栈构建、进栈、出栈运算。 2。链式堆栈构建、进栈、出栈运算。 要求：从键盘输入数据元素5个student(定义如下), 给出结果。 typedef struct int num; /学号 char name10; /姓名 student； ty