数据结构第3章栈和队列.ppt

第三章 栈和队列 1. 栈（Stack） 1. 定义 讨论1：栈是什么？它与一般线性表有什么不同？ 顺序表和顺序栈的操作区别: 讨论：为什么要设计栈？它有什么独特用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。 编制递归算法要注意些什么？ 递归进行是有条件的。一般常把判断语句加在递归语句以前。 例1 一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？ 例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可。 例3： 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b 3.1 栈 顺序栈的入栈操作——例如用栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出‘B’ 链栈的入栈操作和出栈操作 栈的应用举例 第三章 栈和队列 1. 栈（Stack） 定 义 队的实现方式是本节重点： 链队示意图 顺序队示意图 问：什么叫“假溢出” ？如何解决？ 答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 本章小结 * 2. 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 3.1 栈 与线性表相同，仍为一对一( 1:1)关系。 用顺序栈或链栈存储均可，但以顺序栈更常见 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 限定只能在表的一端进行插入和删除运算的线性表。 即栈顶 基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。 栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底bottom 例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an ) 插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。 an称为栈顶元素 a1称为栈底元素 想一想：若要从栈中取出a1，该如何操作？ 强调：插入和删除都只能在表的一端（栈顶）进行！ 答：栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO) “进”＝插入=压入=PUSH（an+1) “出”＝删除=弹出=POP(an) a1 a2 …… an 顺序栈S ai …… 表头 表尾 低地址 高地址 写入：S[i]= ai 读出： e= S[i] 压入(PUSH): S[top++]=an+1 弹出( POP) : e=S[--top] 低地址 高地址 S[i] a1 a2 ai an …… 顺序表S …… an+1 以线性表 S= (a1 , a2 , …. , an-1 , an )为例 栈底bottom 栈顶top 前提：一定要预设栈顶指针top 栈顶top 断点 例： 输入x1≠0 输入x5＝0 输入x2 输入x3 输入x4 输出sum＝0 输出sum＝0+x4 输出sum＝x4+x3 输出sum＝ x4+x3 +x2 输出sum＝x4+x3 +x2+x1 void test(int sum) { int x; scanf(x); if(x==0)sum=0; else{test(sum); sum+=x;} printf(sum); } 答： 例：写出下面C程序段的执行结果。 递归概念及算法实现 运行结果为： 5，120 long int fact(n) int n; { long f; if(n1