第03章_栈和队列A合编.ppt

递归运算！ void Hanoi ( int n, char x, char y, char z ) { //将n个编号从上到下为1…n的盘子从x柱，借助y柱移到z柱 if ( n = = 1 ) move ( x , 1 , z ) ; //将编号为1的盘子从x柱移到z柱 else { Hanoi ( n-1 , x , z , y ) ;//先将n-1个盘从x柱借助z柱移到y柱 move ( x , n, z) ; //将编号为n的盘子从x柱移到z柱 Hanoi ( n-1 , y , x , z ); //再将n-1个编号从上到下为1…n-1 的盘子从y柱借助x柱移到z柱 } } //Hanoi 程序设计如下： 3.1 栈 * 数据结构课程的内容 第三章：栈和队列 * 第三章 栈和队列 3.1栈 (Stack) 3.2 队列 (Queue) 第三章：栈和队列 * 1. 基本概念 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 基本概念 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 定义: 限定只能在表的一端进行插入和删除运算的线性表。 * 栈的基本概念 与线性表相同，仍为一对一( 1:1)关系。 用顺序栈或链栈存储均可，但以顺序栈更常见 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 即栈顶 基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。 栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base 例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an ) 插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。 an称为栈顶元素 a1称为栈底元素 强调：插入和删除都只能在表的一端（栈顶）进行！ * a1 a2 an 入栈 出栈 栈顶 top 栈底 bottom 栈的示意图 ．．． 例1（严题集3.1）一个栈的输入序列为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种可能性。 例2： 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b * [解答] A）、D）可以， B）、C）不行。 讨论：有无通用的判别原则？ 即对于输入序列1，2，3，不存在输出序列3，1，2 有！若输入序列是 …,Pj…Pk…Pi …(PjPkPi) ，一定不存在这样的输出序列 …,Pi…Pj…Pk … Q1：栈是什么？它与一般线性表有什么不同？ * 栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO) “进”＝插入=压入=PUSH（an+1) “出”＝删除=弹出=POP(an) a1 a2 …… an 顺序栈S ai …… Q2：顺序表和顺序栈的操作有何区别？ * 表头 表尾 低地址 高地址 写入：S[i]= ai 读出： e= S[i] 压入(PUSH): S[top++]=an+1 弹出( POP) : e=S[--top] 低地址 高地址 S[i] a1 a2 ai an …… 顺序表S …… an+1 以