严蔚敏数据结构 (10)

严蔚敏

数据结构课程的内容

严蔚敏

第三章 栈和队列3.1 栈(Stack) ) 3.2 队列( 队列(Queue) )1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式

严蔚敏

3.1 栈1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式

即栈顶 限定只能在表的一端 一端进行插入和删除运算的 限定只能在表的一端进行插入和删除运算的 线性表. 线性表. 与线性表相同,仍为一对一( 关系. 与线性表相同,仍为一对一 1:1)关系. 关系 用顺序栈或链栈存储均可,但以顺序栈更常见 顺序栈或链栈存储均可, 存储均可 只能在栈顶运算,且访问结点时依照后进先出 栈顶运算 只能在栈顶运算,且访问结点时依照后进先出 LIFO) 先进后出(FILO)的原则. (LIFO)或先进后出(FILO)的原则. 关键是编写入栈 出栈函数, 入栈和 关键是编写入栈和出栈函数,具体实现依顺 函数 序栈或链栈的存储结构有别而不同. 序栈或链栈的存储结构有别而不同.

基本操作有:建栈,判断栈满或栈空,入栈,出栈, 基本操作有:建栈,判断栈满或栈空,入栈,出栈, 读栈顶元素值,等等. 读栈顶元素值,等等.

严蔚敏

栈 是仅在表尾进行插入,删除操作的线性表. 是仅在表尾进行插入,删除操作的线性表. 表尾进行插入 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base 表尾 即 称为栈顶 表头 即 称为栈底 称为栈底 称为 例如: 例如: 栈 S= (a1 , a2 , a3 a1称为栈底元素 强调:插入和删除都只能在表 强调: 的一端(栈顶)进行! 的一端(栈顶)进行!, ……….,an-1 ,

an )an称为栈顶元素 插入元素到栈顶的 操作,称为入栈 入栈. 操作,称为入栈. 从栈顶删除最后一 个元素的操作, 个元素的操作,称 出栈. 为出栈.

想一想:要从栈中取出a1, 想一想:要从栈中取出a 应当如何操作? 应当如何操作?

严蔚敏

Q1:堆栈是什么?它与一般线性表有什么不同? Q1:堆栈是什么?它与一般线性表有什么不同? 堆栈是一种特殊的线性表,它只能在表的一端( 堆栈是一种特殊的线性表,它只能在表的一端(即 一端 栈顶)进行插入和删除运算. 栈顶)进行插入和删除运算. 与一般线性表的区别:仅在于运算规则不同. 运算规则不同 与一般线性表的区别:仅在于运算规则不同.一般线性表 逻辑结构: 逻辑结构:1:1 存储结构:顺序表 存储结构:顺序表,链表 运算规则: 运算规则:随机存取 堆栈 逻辑结构: 逻辑结构: 1:1 存储结构:顺序栈 存储结构:顺序栈,链栈 运算规则:后进先出(LIFO) 运算规则:后进先出

"进"=插入=压入=PUSH(an+1) 进 插入=压入=PUSH( =PUSH "出"=删除=弹出=POP(an) 出 删除=弹出=POP(a

严蔚敏

Q2:顺序表和顺序栈的操作有何区别? Q2:顺序表和顺序栈的操作有何区别? 以线性表 S= (a1 , a2 , …. , an-1

, an )为例 为例顺序表S 顺序表 高地址 an …… S[i] ai …… 低地址 a2 a1 表头 低地址 表尾 高地址 顺序栈S 顺序栈 an+1 an …… ai …… a2 a1

栈顶top 栈顶top 栈顶top 栈顶top

栈底base 栈底base

写入: 写入:S[i]= ai 读出: 读出: e= S[i]

top++ 压入(PUSH): S[top++]= 压入 PUSH): S[top++]=an+1 弹出( e=S[ 弹出 POP) : e=S[- -top]前提:一定要预设栈顶指针top 预设栈顶指针 前提:一定要预设栈顶指针top

严蔚敏

顺序栈S 顺序栈 高地址 an …… ai …… a2 a1

栈顶top 栈顶top

低地址

栈底base 栈底base 栈不存在的条件: 栈不存在的条件: base=NULL; 栈为空 的条件 : base=top; 栈满的条件 : top-base=stacksize;

严蔚敏

Q3:什么叫"向上生成"的栈? 向下生成" Q3:什么叫"向上生成"的栈? "向下生成"又是何 意?若入栈动作使地址向高端增长,称为"向上生成"的栈; 若入栈动作使地址向高端增长,称为"向上生成"的栈; 若入栈动作使地址向低端增长,称为"向下生成"的栈; 若入栈动作使地址向低端增长,称为"向下生成"的栈;

对于向上生成的堆栈: 对于向上生成的堆栈入栈口诀:堆栈指针 先压后加" S[top++ top++]=a 入栈口诀:堆栈指针top "先压后加" : S[top++]=an+1 口诀 先压后加 出栈口诀:堆栈指针 先减后弹" e=S[- top] 出栈口诀:堆栈指针top "先减后弹" : e=S[- -top] 口诀 先减后弹

严蔚敏

Q4:为什么要设计堆栈?它有什么独特用途? Q4:为什么要设计堆栈?它有什么独特用途?

1. 调用函数或子程序非它莫属; 调用函数或子程序非它莫属; 2. 递归运算的有力工具; 递归运算的有力工具 运算的有力工具; 3. 用于保护现场和恢复现场; 用于保护现场和恢复现场; 4. 简化了程序设计的问题. 简化了程序设计的问题.

下面用4个例子来帮助理解堆栈: 下面用 个例子来帮助理解堆栈: 个例子来帮助理解堆栈

严蔚敏

阅读下列递归过程,说明其功能. 例1 阅读下列递归过程,说明其功能.void test(int &sum){ int x; scanf(x);输入x1≠0 输入输入x2 输入 输入x3 输入 输入x4 输入 输入x5= 输入 =0

断点地址 入栈 if(x==0)sum=0;

else{test(sum);sum+=x;} test(sum) printf(sum); }注意: 注意:最先 输入的数据 x1 最后才被 累加输出sum= = 输出 x4+x3 +x2+x1 输出 sum= = x4+x3 +x2 输出 输出 sum= sum= = = x4+x3 0+x4 输出 sum=0 =

程序功能: 程序功能:对键盘输入数 据求和,直到输入0 据求和,直到 …… 此处隐藏：2395字，全部文档内容请下载后查看。喜欢就下载吧 ……